Section 2.5: Problem 1 Solution »

# Section 2.5: Soundness and Completeness Theorems

## Soundness

Every logical axiom is valid.
A1: Exercise 2.4.3(b). A3: Exercise 2.2.3. A4: Exercise 2.2.4. A5: By definition.
A6: Similar to Exercise 2.2.5, but using induction in general.
A2: We prove and use $\overline{s}(u_{t}^{x})=\overline{s(x|\overline{s}(t))}(u)$ and (Substitution Lemma) $\vDash_{\mathfrak{A}}\phi_{t}^{x}[s]\mbox{ iff }\vDash_{\mathfrak{A}}\phi[s(x|\overline{s}(t))]$ (where $t$ is substitutable for $x$ in $\phi$ ) for terms and formulas, respectively.
A set of wffs $\Gamma$ is called satisfiable iff there is $\mathfrak{A}$ and $s:V\rightarrow|\mathfrak{A}|$ such that $\mathfrak{A}$ satisfies (every member of) $\Gamma$ with $s$ .
(Soundness Theorem) If $\Gamma\vdash\phi$ , then $\Gamma\vDash\phi$ .
• 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.
(Completeness Theorem; Gödel, 1930) If $\Gamma\vDash\phi$ , then $\Gamma\vdash\phi$ .
• 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\in\Delta\}$ , $P^{\mathfrak{A}}=\{|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}||\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$ .
(Compactness Theorem) If , then for some finite $\Gamma_{0}\subseteq\Gamma$ , $\Gamma_{0}\vDash\phi$ .
• $\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 $\in P^{\mathfrak{A}}$ iff $|a-b|=1$ , there is an elementarily equivalent disconnected structure.

## Decidability

(Enumerability Theorem) For a reasonable language (the set of parameters can be effectively enumerated and the relations $\{|P\mbox{ is an }n\mbox{-place predicate symbol}\}$ and $\{|f\mbox{ is an }n\mbox{-place function symbol}\}$ are decidable), the set of valid wffs can be effectively enumerated.
• 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.