0
$\begingroup$

I am trying to prove that it follows from the Compactness Theorem that every consistent first-order theory has a maximally consistent extension (I hope that this will allow me to turn the usual Henkin proof of the Completeness Theorem into a proof that does not rely on the Axiom of Choice; recall that the Compactness Theorem is strictly weaker than the Axiom of Choice). However, I am not really sure about the details of my proof; for some reason, it feels a bit fishy. The proof goes like this:

Let $L$ be a language, let $T$ be a (syntactically) consistent $L$-theory and denote by $F(L)$ the set of all $L$-formulas. We will prove that it follows from the Compactness Theorem that $L$ can be extended to a maximally (syntactically) consistent theory. Let $\mathscr{L}$ be the language that has one constant symbol $c_\phi$ for each $\phi\in F(L)$, one unary predicate symbol $\mathcal{T}$ and one $n$-ary predicate symbol $\operatorname{Con}^n$ for each $n\in\mathbb{N}$. Next, let $\Sigma$ be the $\mathscr{L}$-theory consisting of the sentences $\mathcal{T}(c_\phi)$ for all $\phi\in T$, $\mathcal{T}(c_\phi)\lor\mathcal{T}(c_{\neg\phi})$ for all $\phi\in F(L)$, $$\forall x_1\ldots x_n(\mathcal{T}(x_1)\land\dots\land\mathcal{T}(x_n)\rightarrow\operatorname{Con}^n(x_1,\ldots,x_n))$$ for all $n\in\mathbb{N}$ and $\operatorname{Con}^n(c_{\phi_1},\ldots,c_{\phi_n})$ for all $\phi_1,\ldots,\phi_n\in F(L)$ such that $\{\phi_1,\ldots,\phi_n\}$ is syntactically consistent and all $n\in\mathbb{N}$. We will use the Compactness Theorem to prove that $\Sigma$ has a model. Let $\Sigma_0\subseteq\Sigma$ be finite, let $\{\phi_1,\ldots,\phi_n\}$ be the set of all $L$-formulas $\phi$ such that $c_\phi$ occurs somewhere in $\Sigma_0$ and let $$X=\{\phi_1,\ldots,\phi_n\}\cup\{\neg\phi_1,\ldots,\neg\phi_n\}.$$ We prove by induction on $n$ that $X$ can be turned into a model of $\Sigma_0$. It suffices to find a consistent extension $T'\subseteq X$ of $T\cap X$ such that either $\phi_i\in T'$ or $\neg\phi_i\in T'$ for all $i$. If $n=1$, this is trivial. Suppose that the claim holds for $k$ and let $n=k+1$. Let $$T''\subseteq\{\phi_1,\ldots,\phi_k\}\cup\{\neg\phi_1,\ldots,\neg\phi_k\}$$ be the extension given by our induction hypothesis. Then, either $T''\cup\{\phi_n\}$ or $T''\cup\{\neg\phi_n\}$ is consistent; set $T'=T''\cup\{\phi_n\}$ if $T''\cup\{\phi_n\}$ is consistent and $T'=T''\cup\{\neg\phi_n\}$ otherwise. Hence, by the Compactness Theorem, $\Sigma$ has some model $\mathcal{M}$. It is clear that the theory $$T^*=\{\phi\in F(L):c_\phi^\mathcal{M}\in\mathcal{T}^\mathcal{M}\}$$ is a maximally consistent extension of $T$. QED

Does this proof work? For some reason, the step where I add the sentence $\operatorname{Con}^n(\phi_1,\ldots,\phi_n)$ for all $n$-tuples $(\phi_1,\ldots,\phi_n)$ such that $\{\phi_1,\ldots,\phi_n\}$ is consistent feels particularly fishy to me but I can't really explain why. Given a finite set of $L$-formulas, do we always know (can we always find out) whether it is consistent or not?

I am very grateful for any comments/help!

$\endgroup$
4
  • $\begingroup$ It seems just like routine non-constructive reasoning to add $\mathrm Con^n(\ldots)$ for all the consistent sets without necessarily having a way to decide what they are. But I think what you actually need is $\lnot \mathrm Con^n$ for the inconsistent sets, or I don't see how it's clear that $T^*$ is consistent. $\endgroup$ Apr 11 at 15:12
  • $\begingroup$ This can be streamlined a bit to use propositional compactness (taking the first order sentences to be propositional variables). Which is similar to constructing the Lindenbaum algebra and using the ultrafilter lemma directly. $\endgroup$ Apr 11 at 15:28
  • $\begingroup$ (The issue I might raise with using first order compactness is how are you weakening choice in the proof of first order compactness to the ultrafilter lemma? I can’t see a way of doing it that doesn’t feel like we’re doing the same work twice.) $\endgroup$ Apr 11 at 15:46
  • $\begingroup$ @spaceisdarkgreen Thanks for the comments! I agree that I should have added $\neg\operatorname{Con}(\ldots)$ for inconsistent sets instead. I'm not really sure why I was confused about that part so I guess you are right. I will look into what you said about propositional compactness/Lindenbaum algebras. For your final comment: There is a proof that the ultrafilter lemma implies the compactness in "The Axiom of Choice" by Jech. However, I agree that Jech's proof of this almost looks like a proof of the completeness theorem. $\endgroup$
    – Jon
    Apr 11 at 17:04

0

You must log in to answer this question.

Browse other questions tagged .