[Math] Prove that if $T$ is maximal consistent theory then $T$ is satisfiable

logicpropositional-calculus

I want to prove that

If $T$ be a maximal consistent subset of the set of all formulas then
$T$ is satisfiable.

By using the following facts I have proved for a maximal consistent $T$;
$$T\vdash A \ \Leftrightarrow A \in T$$
$$T\vdash \neg A \ \Leftrightarrow A \notin T$$
$$T\vdash A\wedge B \ \Leftrightarrow \{A,B\} \in T$$
$$T\vdash A\vee B \ \Leftrightarrow A \in T \text{ or } B \in T$$

I want to show that there exists some truth assignment function which makes all the formulas in $T$ true.

I get that I have to use induction on the complexity of formulas somehow. But i don't really know where to start off.

Let say I have a maximal consistent $T = \{A_0,A_1,\ldots\}$ then the all above properties hold. Now what? Should I assume that the formulas in $T$ are atomics for minimal complexity as a base case for the induction? How to construct the truth assignment function?

I think I'm having trouble grasping the "big idea" of this.

I may assume the soundness theorem if it helps by the way.

Best Answer

See : Dirk van Dalen, Logic and Structure (5th ed - 2013), 2.5 Completeness, page 43 :

Lemma 2.5.11 If $\Gamma$ is [maximally] consistent, then there exists a valuation $v$ such that $v(\psi) = 1$, for all $\psi \in \Gamma$.

In order to show that $\Gamma$ is satisfiable, we define a valuation $v$ on propositional variables such that $v(p_i ) = 1$ if $p_i \in \Gamma$ and $v(p_i ) = 0$ otherwise and then extend it to all formulae.

To show that $\varphi = 1$ iff $\varphi \in \Gamma$, we need induction on complexity of $\varphi$.

  1. For atomic $\varphi$, the claim holds by definition [this is the base case for induction].

  2. If $\varphi$ is $ψ ∧ σ$, then $v(\varphi)=1$ iff $v(ψ) = v(σ) = 1$ iff, by induction hypothesis : $ψ,σ \in \Gamma$, and thus $\varphi \in \Gamma$ (because $\Gamma$ is maximally consistent, and thus it is is closed under derivability). Conversely : $ψ ∧ σ \in \Gamma$ iff $ψ,σ \in \Gamma$ and, again by induction hypothesis : $v(ψ) = v(σ) = 1$ and so $v(\varphi)=1$.

  3. The same for $ψ \lor σ$.

  4. If $\varphi$ is $ψ → σ$, then $v(ψ → σ) = 0$ iff $v(ψ) = 1$ and $v(σ) = 0$ iff, by induction hypothesis : $ψ \in Γ$ and $σ \notin Γ$ iff $ψ → σ \notin Γ$, by the properties of maximal consistency.

Related Question