Could anyone check my proof please?

In particular I am not sure if my interpretation that 'if $Σ$ is complete, then it is also consistent' is correct, because this seems possible only if the definition is '$Σ$ is complete iff it is consistent and ...etc', but it is conditional in the definition instead.

I am interpreting it as such because in an exercise the textbook said 'Suppose that $Σ$ is maximal consistent. Then $Σ$ is consistent', which seems to indicate that the complete-consistent relation is indeed an iff, and I thought it is perhaps an error.

Let $Σ$ be a set of formulas in a language L. Prove that if $Σ$ is complete, then it is maximal consistent.

enter image description here

Assume that $Σ$ is complete, then by definition it is also consistent. This fulfills the first condition of being max. consistent.

For the 2nd condition, I will prove its equivalent (which isn't obvious to me why but I will take it for granted). So suppose $\phi \not\inΣ$, I need to prove that $Σ \cup\{\phi\}$ is inconsistent.

But by the def. of completeness, either $\phi\inΣ$ or $\lnot\phi\inΣ$ - we have $\phi \not\inΣ$, so $\lnot\phi\inΣ$. Thus $Σ \cup\{\phi\} \vdash\lnot\phi$.

On the other hand we $\phi\inΣ \cup\{\phi\}$, so $Σ \cup\{\phi\} \vdash \phi$ -but this means $Σ \cup\{\phi\}$ is inconsistent.

  • 1
    $\begingroup$ Yes: consider it as a definition : "we shall say that $\Sigma$ is complete iff it is consistent and ..." But in the proof we need only the "if" part, because it is assumed that $\Sigma$ is complete. $\endgroup$ – Mauro ALLEGRANZA Jun 5 '18 at 8:00
  • $\begingroup$ Thank you! Does that mean the definition provided by the book is wrong and my proof is ok? $\endgroup$ – Daniel Mak Jun 5 '18 at 8:09

First, a methodological remark: in a definition, often the general "if" (e.g., in the definition of $Y$, "$X$ is $Y$ if something happen") should be intended as "iff". On the contrary, in the statement of a theorem, "if" is always intended as "if", and "iff" is always intended as "iff". So, a set of formula $\Sigma$ is complete iff $\Sigma$ is consistent and for each formula $\varphi$ in $L$, either $\varphi \in \Sigma$ or $\lnot \varphi \in \Sigma$. But the theorem that you have to prove is only that completeness implies maximal consistency, not also the converse.

Your proof is correct. To complete the picture, you just have to prove that the two definitions of maximal consistency are equivalent, i.e. that given a set of formula $\Sigma$ in $L$ the two following conditions are equivalent:

  1. for any consistent set of formulas $\Sigma'$ in $L$ with $\Sigma \subseteq \Sigma'$, we have $\Sigma = \Sigma'$;
  2. for any formula $\varphi$ in $L$ with $\varphi \notin \Sigma$, we have that $\Sigma \cup \{\varphi\}$ is inconsistent.

Let us prove that 1. $\Rightarrow$ 2. Let $\varphi \notin \Sigma$ a formula in $L$. Then, $\Sigma \subsetneq \Sigma \cup \{\varphi\}$. Since $\Sigma \neq \Sigma \cup \{\varphi\}$, $\Sigma \cup \{\varphi\}$ is inconsistent by 1.

Let us prove that 2. $\Rightarrow$ 1. Let $\Sigma'$ be a set of formulas in $L$ such that $\Sigma \subseteq \Sigma'$. We have to prove that if $\Sigma'$ is consistent then $\Sigma = \Sigma'$. By contraposition, suppose $\Sigma \neq \Sigma'$. Then, there is a formula $\varphi \in \Sigma' \smallsetminus \Sigma$. By 2., $ \Sigma \cup \{\varphi\}$ is inconsistent, hence $\Sigma'$ is inconsistent because $\Sigma \cup \{\varphi\} \subseteq \Sigma'$.

  • $\begingroup$ Thank you! If only my textbook has talked about this confusing convention before... $\endgroup$ – Daniel Mak Jun 6 '18 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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