What are the basic ideas behind the standard proof of the Lindenbaum's Lemma?

Question

I have a question about Lindenbaum's Lemma for Propostitional Logic:

Any consistent set $\Gamma$ of formulas is a subset of a maximal consistent set $\Gamma^{\prime}$ of formulas.

The outline of the proof (by Hunter's book) is the following:

1. By enumeration theorem, a machine can map the whole set of propositional formulas onto the set of natural numbers; let $\phi_n$ the $n^{th}$ formula in this sense.

2. Let recursively define the function $\Gamma_n$ as

   • $\Gamma_0=\Gamma$,
   • $\Gamma_{n+1}=\Gamma_n\cup \{\phi_{n+1}\}$ if $\Gamma_n\not{\vdash}\neg\phi_{n+1}$ and $\Gamma_{n+1}=\Gamma_n$ otherwise.

3. Let $\Gamma'$ be the union of $\Gamma_0, \Gamma_1, ..., \Gamma_n, ...$

4. etc.

Ok! I understood it. But here is my trouble:

1. It would be better if we could directly define $\Gamma^{\prime}$ like any set s.t. for any formula $\phi$:

   • if neither $\phi$ nor in $\neg\phi$ can be deduced by $\Gamma$ then $\phi$ is in $\Gamma^{\prime}$;
   • if $\phi$ can be deduced by $\Gamma$ then $\phi$ is in $\Gamma^{\prime}$
   • if $\neg\phi$ can be deduced by $\Gamma$ then $\neg\phi$ is in $\Gamma^{\prime}$

   In fact with this definition the claim of the lemma is automatically verified! But, I know, something is wrong. However, in order to "accept" this proof, I need to find motivations to why one cannot shorten/simplify it.

2. Are steps 1-3 necessary because we cannot ensure otherwise the existence of the set $\Gamma^{'}$?
3. If yes, are we using replacement axiom scheme in step 2 and union axiom in step 3?
4. If yes, what is the particular instance of the replacement axiom scheme that we are using? Namely, which is the actual, exact first-order formula we are considering?

Remark. I know that this is a metatheorem, and therefore its metaproof does not strictly depend by any formal theory (like ZFC is), however it is the current best justification for steps 1-3 that I found. But I'm absolutely not conviced by this, I really need your help to understand.

Thank you!

Answer 1

Your set $\Gamma'$ does not work. Consider a formula $\phi$ such that neither $\phi$ nor $\neg \phi$ can be deduced from $\Gamma$. Then, by your definition, $\phi$ will be in $\Gamma'$. But letting $\psi=\neg\phi$, it is also true that neither $\psi$ nor $\neg\psi$ can be deduced from $\Gamma$. So $\psi$ will also be in $\Gamma'$. So both $\phi\in\Gamma'$ and $\neg\phi\in\Gamma'$, and $\Gamma'$ is not consistent.

More generally, even if you modify your definition to avoid this specific issue, there is no guarantee that your set $\Gamma'$ will be consistent. Each individual new formula you added is consistent with $\Gamma$, but they may not be consistent with each other. That is why the recursive procedure of steps 1-3 is important, to guarantee that the set $\Gamma'$ is actually consistent. It has nothing to do with being able to formally construct the set.

In detail, here is how you prove the set $\Gamma'$ given by steps 1-3 is consistent. If it were inconsistent, some finite subset $F\subseteq\Gamma'$ would be inconsistent. Then for some $n$, $F\subseteq \Gamma_n$. But we can prove by induction on $n$ that $\Gamma_n$ is consistent for all $n$ (since if $S\not\vdash \neg\phi$ then $S\cup\{\phi\}$ is consistent). This is a contradiction, and thus $\Gamma'$ is consistent.