# Maximal consistent sets are complete

• Mar 25th 2010, 07:54 PM
Giraffro
Maximal consistent sets are complete
I'm stuck on a problem on the theory of structures and essentially boiled it down to this: If $\displaystyle \Gamma$ is a maximal consistent set of sentences ($\displaystyle \forall \phi \in \text{Sent}(\mathcal{L}), \Gamma \vdash \phi$ or $\displaystyle \Gamma \vdash \neg \phi$, but not both) is complete ($\displaystyle \forall \phi \in \text{Sent}(\mathcal{L}), \phi \in \Gamma$ or $\displaystyle \neg \phi \in \Gamma$). I've seen another definition for maximal consistency which says that there are no proper consistent extensions of $\displaystyle \Gamma$ and that this is equivalent to being complete, but I fail to see an equivalence between these two definitions. (Thinking)

• Mar 26th 2010, 05:50 AM
emakarov
Wait, I also have an issue with definitions.

First, I am used to the definition that $\displaystyle \Gamma$ is complete if http://www.mathhelpforum.com/math-he...8f4d1643-1.gif or http://www.mathhelpforum.com/math-he...f6fe588e-1.gif: see PlanetMath and MathWorld. (I was surprised that Wikipedia defines completeness as maximal consistency.) That's why saying that Peano Arithmetic is incomplete immediately implies that there is an independent sentence, i.e., a sentence that is neither proved nor disproved.

Second, the phrase "maximal consistent" is not idiomatic. For any strict order <, saying "x is maximal" means that there is no y such that x < y. (As an aside, note that this is different from saying that x is the greatest, which means that y <= x for all y.) Here the order is set inclusion, so a set is maximal (in a family of sets) if it does not have a proper superset. Correspondingly, "$\displaystyle \Gamma$ is maximal consistent" means that every proper superset of $\displaystyle \Gamma$ is inconsistent, though $\displaystyle \Gamma$ itself is consistent.

Now, of course, when $\displaystyle \Gamma$ is consistent, these things:

(1) http://www.mathhelpforum.com/math-he...561f3f43-1.gif or http://www.mathhelpforum.com/math-he...39b298c0-1.gif
(2) $\displaystyle \forall\Gamma'\subseteq\text{Sent}(\mathcal{L})$, $\displaystyle \Gamma\subset\Gamma'$ implies that $\displaystyle \Gamma'$ is inconsistent

are equivalent, and any of them implies

(3) http://www.mathhelpforum.com/math-he...8f4d1643-1.gif or http://www.mathhelpforum.com/math-he...f6fe588e-1.gif

So one may say that this is arguing about definitions, though I think that distinguishing properties that hold by definition and those that need to be proved is helpful here.

Let's assume that $\displaystyle \Gamma$ is consistent and prove (1) => (2) => (1) and (1) => (3). (Below $\displaystyle \bot$ denotes a contradictory formula and I assume that $\displaystyle \phi\to\bot$ is equivalent to $\displaystyle \neg\phi$.)

(1) => (2): Suppose $\displaystyle \Gamma\subset\Gamma'$. Take $\displaystyle \phi\in\Gamma`\setminus\Gamma$. Since $\displaystyle \phi\notin\Gamma$, $\displaystyle \neg\phi\in\Gamma$ by (1). Therefore, both $\displaystyle \phi$ and $\displaystyle \neg\phi$ are in $\displaystyle \Gamma'$, and so $\displaystyle \Gamma'$ is inconsistent.

(2) => (1): Assume the contrary, i.e., $\displaystyle \phi\notin\Gamma$ and $\displaystyle \neg\phi\notin\Gamma$ for some formula $\displaystyle \phi$. Then both $\displaystyle \Gamma\cup\{\phi\}$ and $\displaystyle \Gamma\cup\{\neg\phi\}$ are inconsistent by (2), i.e., $\displaystyle \Gamma\cup\{\phi\}\vdash\bot$ and $\displaystyle \Gamma\cup\{\neg\phi\}\vdash\bot$. By Deduction Theorem (or by Implication Introduction rule), $\displaystyle \Gamma\vdash\phi\to\bot$ and $\displaystyle \Gamma\vdash\neg\phi\to\bot$, i.e., $\displaystyle \Gamma\vdash\neg\phi$ and $\displaystyle \Gamma\vdash\neg\neg\phi$. This means that $\displaystyle \Gamma$ is inconsistent, a contradiction.

(1) => (3): This is obvious: for every $\displaystyle \phi$, either $\displaystyle \phi\in\Gamma$ or $\displaystyle \neg\phi\in\Gamma$ by (3). Therefore, $\displaystyle \Gamma\vdash\phi$ or $\displaystyle \Gamma\vdash\neg\phi$.

I am not sure what advice to give about how best to appropriate these proofs. Usually, I don't remember every detail, but I have an intuition about a maximal consistent set as something that knows everything, so one cannot add new knowledge to it.
• Mar 26th 2010, 06:02 AM
emakarov
By the way, the formula http://www.mathhelpforum.com/math-he...8f4d1643-1.gif or http://www.mathhelpforum.com/math-he...f6fe588e-1.gif in the assumption above does not mean that $\displaystyle \Gamma$ is maximal and so it does not imply http://www.mathhelpforum.com/math-he...561f3f43-1.gif or http://www.mathhelpforum.com/math-he...39b298c0-1.gif . There are axiomatizable complete theories (e.g., dense linear orders). This means that there is a small set of axioms $\displaystyle \Delta$ that generates the whole theory $\displaystyle \Gamma$, i.e., $\displaystyle \Gamma=\{\phi\mid\Delta\vdash\phi\}$. Now, there are such $\displaystyle \Delta$ and $\displaystyle \Gamma$ that $\displaystyle \Gamma$ is complete (in my sense, i.e., $\displaystyle \Gamma\vdash\phi$ or $\displaystyle \Gamma\vdash\neg\phi$ for every $\displaystyle \phi$), and so $\displaystyle \Delta$ is complete. However, $\displaystyle \Delta$ does not have to be maximal.
• Mar 26th 2010, 01:19 PM
MoeBlee
Giraffro, to answer your question briefly: It is NOT the case that maximally consistent is equivalent to complete (since an inconsistent set of formulas is complete). But there are other equivalences. Which equivalence in particular are you having a hard time proving?

Definitions:

A set of formulas G is consistent iff there is not a formula P such that G |- P and G |- ~P.

A set of formulas G is complete iff for every sentence S we have either G |- S or G |- ~S.

A set of formulas G is maximally consistent iff (G is consistent & for all sentences S not in G we have Gu{S} is inconsistent).
• Mar 26th 2010, 03:23 PM
Giraffro
Quote:

Originally Posted by MoeBlee
Giraffro, to answer your question briefly: It is NOT the case that maximally consistent is equivalent to complete (since an inconsistent set of formulas is complete). But there are other equivalences. Which equivalence in particular are you having a hard time proving?

Definitions:

A set of formulas G is consistent iff there is not a formula P such that G |- P and G |- ~P.

A set of formulas G is complete iff for every sentence S we have either G |- S or G |- ~S.

A set of formulas G is maximally consistent iff (G is consistent & for all sentences S not in G we have Gu{S} is inconsistent).

I've managed to show the equivalence eventually, but here was what I was stuck on. Let $\displaystyle \mathcal{L}$ be a first order language, $\displaystyle \Gamma \subseteq \text{Sent}(\mathcal{L})$ be consistent. Then the following statements are equivalent:

1. $\displaystyle \Gamma$ is complete, as in your definition.
2. $\displaystyle \exists \mathcal{A}$ an $\displaystyle \mathcal{L}$-structure such that $\displaystyle \Gamma \vDash \text{Th}(\mathcal{A})$.
3. $\displaystyle \forall \mathcal{A}, \mathcal{B}$ models of $\displaystyle \Gamma, \text{Th}(\mathcal{A}) = \text{Th}(\mathcal{B})$.

In my lecture course, a set of sentences is defined to be 'maximal consistent' if it is consistent and complete in your definitions, which is where the confusion started. Thanks for clearing that up. I'll bear that in mind in the future. (Yes)
• Mar 26th 2010, 04:17 PM
MoeBlee
So you showed the equaivalences of 1-3 okay? Let me know if you need any help with them (they seemed right to me as I looked at them rather qucikly).

And yes, it is easy to see that my definition of 'maximally consistent' is equivalent with 'consistent and complete'.
• Mar 26th 2010, 04:20 PM
Giraffro
Yeh it's fine now. Thanks!