Let $\mathcal{L}$ be any language of predicate logic, $\Sigma_0$ a consistent theory in $\mathcal{L}$. Let P be the set of all consistent theories $\Sigma \supseteq \Sigma_0$ in $\mathcal{L}$. With the relation $\subseteq$ P becomes partial ordered.

I'm trying to show that
1) every chain in P (i.e., every through $\subseteq$ total ordered subset K$\subseteq$ P) is limited. (I.e. for every chain $K \subseteq P$ there is $\Sigma^{\ast} \in P$ such that for all $\Sigma \in K$ $\Sigma \subseteq \Sigma^{\ast}$ holds. The suggestion ist to check, if the constructed set $\Sigma^{\ast}$ really is in P and to not forget that not every chain is orderisomorphic (I hope that's the correct English word for it) to $(\mathbb{N}, <)$;

2) if $\Sigma \in P_{\mathcal{L}}$ is maximal (i.e. there's no $\Sigma' \supseteq \Sigma$ in P), then $\Sigma$ is complete;

3) conclude with the Lemma of Zorn that for every consistent theory there is a complete consistent theory, which is superset of it.

My problem lies within point 1). Neither do I see intuitively how this holds nor do I have an idea of how to proof it. 3) Will be easy once 1) and 2) are shown, I think.

So I'm looking forward to your ideas for 1) and 2).


For part one, you want to take $\Sigma^*$ to be the union of the chain $K$. You need to show it is a consistent theory extending $\Sigma_0.$ That it extends $\Sigma_0$ is obvious. If it were inconsistent, the inconsistency would come from some finite number of sentences $\varphi_1,\ldots \varphi_n\in \Sigma^*$. For each $\varphi_i,$ choose a $\Sigma_i\in K $ such that $\varphi_i\in \Sigma_i.$ Then take $\Sigma$ to be the maximum of $\Sigma_1,\ldots, \Sigma_n.$ Then $\Sigma\in K,$ and is inconsistent, contradicting the fact that $K$ only contains consistent sets of statements.

I’m not sure what to make of the suggestion that $K$ is not necessarily order isomorphic to $\mathbb N.$ I guess maybe people in the past have written the above proof making a tacit assumption that it is and they want to warn you against that.

For 2, show that if $\Sigma$ is not complete, then there is a sentence $\varphi\notin \Sigma$ such that $\Sigma\cup\{\varphi\}$ is consistent.

  • $\begingroup$ Thank you! I'd completely forgotten about the trick to take the union! For 2), we assume that $\Sigma$ is not complete. So there is $\phi$ in $\mathcal{L}$ such that it doesn't hold that either $\Sigma \vdash \Phi$ or $\Sigma \vdash \neg \phi$. We consider $\Sigma':=\Sigma \cup \phi$. We do this with all $\psi$ which cause $\Sigma$ to not be complete until we have the theory $\tilde{\Sigma}$. Then $\tilde{\Sigma}\supset \Sigma$ and $\tilde{\Sigma} \in P$ in contradiction to the maximality of $\Sigma$. But I don't see how to explain the $\tilde{\Sigma}$ is consistent? $\endgroup$ – Studentu Nov 25 '18 at 4:22
  • $\begingroup$ 3) With the Lemma of Zorn we get that there is at least one maximal element in P. Due to 2), this element is also complete. But I don't get how to explain that 3) follows from this. Intuitively, it is clear to me, but if we take the maximal element $\Sigma^{\ast}$ for example, it doesn't have to hold that $\Sigma_0 \in \Sigma^{\ast}$, because it could be another maximal element which $\Sigma_0$ is a subset of. $\endgroup$ – Studentu Nov 25 '18 at 4:23
  • 1
    $\begingroup$ For 2 you only need to show that if $\Sigma \nvdash \phi$ and $\Sigma \nvdash \lnot\phi,$ then either $\Sigma\cup\{\phi\}$ or $\Sigma\cup\{\lnot\phi\}$ are consistent (actually, both are). This shows that if $\Sigma\in P$ is incomplete, then it is not maximal in $P,$ which is what you need. For 3, yes it does have to hold that $\Sigma_0\subseteq \Sigma^*$ since all $\Sigma \in P$ have $\Sigma_0\subseteq\Sigma.$ $\endgroup$ – spaceisdarkgreen Nov 25 '18 at 6:11
  • 1
    $\begingroup$ The general theorem you can show it that $\Sigma\cup \{\phi\}$ is consistent if and only if $\Sigma \nvdash \lnot\phi .$ For the direction you need, assume $\Sigma\cup \{\phi\}$ is inconsistent then show $\Sigma \vdash \lnot \phi.$ You only need to use very general facts about the system. For instance by the deduction theorem, if $\Sigma\cup \{\phi\}\vdash \psi,$ and $\Sigma\cup \{\phi\}\vdash \lnot\psi,$ then $ \Sigma \vdash \phi\to \psi$ and $\Sigma \vdash \phi\to \lnot \psi.$ Can you show from there that $\Sigma \vdash \lnot\phi$? $\endgroup$ – spaceisdarkgreen Nov 25 '18 at 19:34
  • 1
    $\begingroup$ @Studentu Some of that is on the right track, but you need $\Sigma \vdash \lnot\phi,$ not just $\Sigma\cup\{\phi\}\vdash \lnot \phi.$ If you have the $\bot,$ symbol, you might just do $ \Sigma\cup\{\phi\}\vdash\bot,$ and then use the deduction theorem to get $\Sigma \vdash \phi\to \bot.$ How close this is to $\Sigma\vdash \lnot \phi$ depends on the system you're using (in some systems it's the same thing by definition). $\endgroup$ – spaceisdarkgreen Nov 25 '18 at 21:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.