# When and why does the Lindenbaum extension construction fail for second order theories?

From any consistent set of first order sentences $\Gamma$, one may generate by an inductive process a unique set of sentences $\Delta(\Gamma)$ such that $\forall A, \Gamma \models A \implies A \in \Delta(\Gamma)$. That is, one may construct a complete set of all sentences that are true as a consequence of $\Gamma$.

The construction, called the Lindenbaum Extension of $\Gamma$, is obtained by a very direct process of adding whatever sentences are true as a consequence of $\Gamma$ to produce a set $\Gamma_1$, adding all consequences of $\Gamma_1$, to produce $\Gamma_2$, and so on up to some $\Gamma_{SomeLarge Ordinal}$, which we conclude to be $\Delta(\Gamma)$ by virtue of the construction.

Now clearly such a trick does not apply to all consistent sets of second order sentences: Peano arithmetic, for example, has infinitely many different models obtained by appending Godel sentences or their negations to the standard axioms and observing the consequences.

Clearly, therefore, $\Delta$ is not necessarily unique if it exists for second order theories- but I am having a hard time seeing whether, in the example of peano arithmetic, it exists at all, given that the construction is, as it were, deterministic in its choices. Perhaps, then, the existence of a Lindenbaum extension requires the axiom of choice? Or something weaker? Can they ever not exist?

Also, my intuition tells me that the 'deterministic' nature of the construction fails because recursive enumerability of truth conditions fails in general for second order theories. Is this correct? If so, what is a good (sketch?) proof that shows (on a direct level, with no fancy Godel coding!) that this is the sticking point? Is the axiom of choice enough to 'short-cut' enumerability?

Edit: Also, does one need to develop $\Gamma$ to a larger ordinal for second order theories?

-
"Now clearly such a trick does not apply to all consistent sets of second order sentences: Peano arithmetic, for example, has infinitely many different models obtained by appending Godel sentences or their negations to the standard axioms and observing the consequences." But second order PA, with standard semantics, has only one model, up to isomorphism ... –  Peter Smith Jan 13 '13 at 15:06

There is no need for an inductive construction. Given a theory $\Gamma$, we can define $\Delta(\Gamma)$ to be the set $$\bigcap_{M \in \operatorname{Mod}(\Gamma)} \{ \phi : M \vDash \phi\}$$ where $\operatorname{Mod}(\Gamma)$ is the set of all models of $\Gamma$. In other words, $\phi \in \Delta(\Gamma)$ if and only $\phi$ is true in every model of $\Gamma$.
This works for both first order semantics and second order semantics. In both cases each theory has a well-defined set of models, each of which has a particular set of sentences that it satisfies, so the intersection is well defined. The main difference is that full second-order semantics allow fewer models, so $\Delta(\Gamma)$ will in general be larger in these semantics than it would in first order semantics.
Separately, the inductive construction described in the question converges after one step; if $\Gamma \vDash \Gamma_1$ and $\Gamma_1 \vDash \phi$ then $\Gamma \vDash \phi$. So we can take "some large ordinal" to be 1. This is also true for provability; if $\Gamma \vdash \Gamma_1$ and $\Gamma_1 \vdash \phi$ then $\Gamma \vdash \phi$.
Is the issue that $\Delta(\text{PA})$ is not a complete theory, where PA is first-order Peano arithmetic? It certainly is not complete, due to the incompleteness phenomenon. On the other hand, the second-order Peano axioms $\text{PA}_2$ have only one model in full second-order semantics, so $\Delta(\text{PA}_2)$ is a complete theory.