Show that any consistent extension $L^*$ of L has a consistent extension ${{L^*}^*}$ which is complete.

Question

If $L^*$ is a consistent extension of L and $\phi$ is a formula which is not a theorem of $L^*$ , then the extension of $L^*$ obtained by including $(¬\phi)$ as an extra axiom is consistent.

Show that any consistent extension $L^*$ of L has a consistent extension ${{L^*}^*}$ which is complete.

This is an 8 mark question that is frequently on past papers. I know it has something to do with a proposition I have; "Suppose $L^*$ is a consistent extension of L and $\phi$ is not a theorem of $L^*$. Let ${{L^*}^*}$ be the extension of $L^*$ obtained by including $(¬\phi)$ as an extra axiom.Then ${{L^*}^*}$ is consistent." But then is the question not asking me to show it is COMPLETE not consistent?

Answer 1

We have the Proposition 1 :

Let L* be a consistent extension of L and let $\varphi$ be a wf formula of L which is not a theorem of L*. Then L** is also consistent, where L** is the extension of L obtained from L* by including $\lnot \varphi$ as an additional axiom.

We want to prove the Proposition 2 :

Let L* be a consistent extension of L. Then there is a consistent complete extension of L*.

Proof. Let $\alpha_0, \alpha_1, \alpha_2$ .... be an enumeration of all the wfs of L. We shall build a sequence $J_0, J_l, J_2$ .. of extensions of L* as follows.

Let

$J_0 =$ L*

If $\vdash_{J_0} \alpha_0$, let $J_1 = J_0$.

If not $\vdash_{J_0} \alpha_0$, then add $\lnot \alpha_0$ as a new axiom to obtain $J_1$ from $J_0$.

In general, for $n \ge 1$, to construct $J_n$, from $J_{n-1}$ : if $\vdash_{J_{n-1} } \alpha_{n-1}$, then $J_n = J_{n-1}$, and if not $\vdash_{J_{n-1} } \alpha_{n-1}$, then let $J_n$ be the extension of $J_{n-1}$ obtained by adding $\lnot \alpha_{n-1}$ as a new axiom.

L* is consistent, i.e. $J_0$ is consistent, by assumption. For $n \ge 1$, if $J_{n-1}$ is consistent, then $J_n$ is consistent, by Proposition 1 above. Hence by induction, each $J_n$, is consistent ($n \ge 0$).

Now define $J$ to be that extension of L* which has as its axioms all the wfs which are axioms of at least one of the $J_n$.

Now we show that $J$ is consistent. Suppose the contrary. Then there is wfs $\alpha$ such that $\vdash_J \alpha$ and $\vdash_J \lnot \alpha$. Now the proofs in $J$ of $\alpha$ and $\lnot \alpha$ are finite sequences of wfs, so each proof can contain instances of only finitely many of the axioms of $J$.

Therefore there must exist $n$ which is large enough so that all these axioms which are used are axioms of $J_n$. It follows that $\vdash_{J_n} \alpha$ and $\vdash_{J_n} \lnot \alpha$. This contradicts the consistency of $J_n$ and so $J$ must be consistent.

It remains to show that $J$ is complete. Let $\varphi$ be a wf of L. $\varphi$ must appear in the list $\alpha_0, \alpha_1, \alpha_2$ .... say $\varphi$ is $\alpha_k$. If $\vdash_{J_k} \alpha_k$, then certainly $\vdash_J \alpha_k$, since $J$ is an extension of $J_k$. If not $\vdash_{J_k} \alpha_k$, then according to the construction of $J_{k+1}$, $\lnot \alpha_k$ is an axiom of $J_{k+1}$, and so $\vdash_{J_{k+1} } \lnot \alpha_k$. This implies that $\vdash_J \lnot \alpha_k$.

So in any case we have $\vdash_J \alpha_k$ or $\vdash_J \lnot \alpha_k$, i.e.

$\vdash_J \varphi$ or $\vdash_J \lnot \varphi$and so $J$ is complete.

See Alan Hamilton, Logic for mathematicians (2nd ed - 1988), page 41.

Note. The construction above was first used for first-order logic by Adolf Lindenbaum, a Polish mathematician and logician, who was killed by the Nazis in the summer of 1941 [see Geoffrey Hunter, Metalogic: An Introduction to the Metatheory of Standard First Order Logic (1971), page 110.]