Section 2.5: Soundness and Completeness Theorems

Soundness

• If $\Gamma$ is satisfiable, then $\Gamma$ is consistent. This is, in fact, equivalent to the theorem.
• If $\vdash\phi\leftrightarrow\psi$ or, equivalently, $\phi\vdash\psi$ and $\psi\vdash\phi$ , then $\phi$ and $\psi$ are logically equivalent.
  • Alphabetic variants are logically equivalent.

• If $\Gamma$ is consistent, then $\Gamma$ is satisfiable. This is, in fact, equivalent to the theorem.
  Let $\Gamma$ be consistent. First, we expand the language by adding infinitely many constant symbols $c_{\alpha}$ , and expand $\Gamma$ by adding wffs $\neg\forall x\phi\rightarrow\neg\phi_{c_{\alpha(\phi,x)}}^{x}$ for each $\phi$ (in the expanded language) and $x$ using constant symbols $c_{\alpha(\phi,x)}$ such that $\alpha(\phi,x)\neq\alpha(\psi,y)$ and $c_{\alpha(\phi,x)}$ does not occur in $\phi$ . The resulting set $\Gamma'$ is consistent. Further, we extend $\Gamma'$ to a consistent $\Delta$ such that for each $\phi$ , either $\phi\in\Delta$ or $\neg\phi\in\Delta$ (in the uncountable case we use Zorn’s Lemma, but however we do this, $\Delta$ turns out to be deductively closed: $\Delta\vdash\phi$ iff $\phi\in\Delta$ ).
  Second, we define a) a new binary relation $E$ (instead of $=$ ); b) a structure $\mathfrak{A}$ where $|\mathfrak{A}|$ is the set of all terms (of the expanded language), $E^{\mathfrak{A}}=\{<u,t>|u=t\in\Delta\}$ , $P^{\mathfrak{A}}=\{<t_{1},\ldots,t_{n}>|Pt_{1}\ldots t_{n}\in\Delta\}$ , $c^{\mathfrak{A}}=c$ ; $f^{\mathfrak{A}}(t_{1},\ldots,t_{n})=ft_{1}\ldots t_{n}$ , and c) a function $s:V\rightarrow|\mathfrak{A}|$ by $s(x)=x$ ($\overline{s}(t)=t$ ). Then, $\phi\in\Delta$ iff $\vDash_{\mathfrak{A}}\phi^{*}[s]$ where $\phi^{*}$ is $\phi$ with $=$ replaced by $E$ .
  Third, we note that $E^{\mathfrak{A}}$ is a congruence relation for $\mathfrak{A}$ (an equivalence relation such that $P^{\mathfrak{A}}$ and $f^{\mathfrak{A}}$ are compatible with $E^{\mathfrak{A}}$ ), therefore, the quotient structure $\mathfrak{A}/E$ is such that a) $h(t)=[t]$ is a homomorphism of $\mathfrak{A}$ onto $\mathfrak{A}/E$ where $[t]=\{u\in|\mathfrak{A}||<u,t>\in E^{\mathfrak{A}}\}$ , b) $E^{\mathfrak{A}/E}$ is the equality relation on $|\mathfrak{A}/E|$ , and c) $\phi\in\Delta$ iff $\vDash_{\mathfrak{A}/E}\phi[h\circ s]$ . The restriction of $\mathfrak{A}/E$ to the original language satisfies every member of $\Gamma$ with $h\circ s$ .

• $\Gamma$ is satisfiable iff every finite $\Gamma_{0}\subseteq\Gamma$ is satisfiable. $\Sigma$ has a model iff every finite $\Sigma_{0}\subseteq\Sigma$ has a model.
• Disjoint $EC_{\Delta}$ classes can be separated by an $EC$ class: if for two sets of sentences, $\mbox{Mod}\Sigma_{1}\cup\Sigma_{2}=\emptyset$ , then there is a sentence $\tau$ such that $\mbox{Mod}\Sigma_{1}\subseteq\mbox{Mod}\tau$ and $\mbox{Mod}\Sigma_{2}\subseteq\mbox{Mod}\neg\tau$ .
• For $\mathfrak{A}=(\mathbb{Z};P^{\mathfrak{A}})$ where $<a,b>\in P^{\mathfrak{A}}$ iff $|a-b|=1$ , there is an elementarily equivalent disconnected structure.

Decidability

• A finite language is one having only finitely many parameters. A finite language is reasonable.
• A reasonable language must be countable.
• If $\Gamma$ is decidable and the language is reasonable, then $\mbox{Th}\Gamma$ and $\{\phi|\Gamma\vDash\phi\}$ are effectively enumerable.
• If $\Gamma$ is decidable, the language is reasonable, and for every sentence $\sigma$ , $\Gamma\vDash\sigma$ or $\Gamma\vDash\neg\sigma$ , then $\{\sigma|\Gamma\vDash\sigma\}$ is decidable.