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

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.

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.

• 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. – Mauro ALLEGRANZA Jun 5 '18 at 8:00
• Thank you! Does that mean the definition provided by the book is wrong and my proof is ok? – 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'$.