Maximal consistent sets are complete

**Giraffro** · March 25th 2010, 07:54 PM

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

Please help?

**emakarov** · March 26th 2010, 05:50 AM

Wait, I also have an issue with definitions.

First, I am used to the definition that $\Gamma$ is complete if

or

: 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, " $\Gamma$ is maximal consistent" means that every proper superset of $\Gamma$ is inconsistent, though $\Gamma$ itself is consistent.

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

(1)

or

(2) $\forall\Gamma'\subseteq\text{Sent}(\mathcal{L})$ , $\Gamma\subset\Gamma'$ implies that $\Gamma'$ is inconsistent

are equivalent, and any of them implies

(3)

or

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 $\Gamma$ is consistent and prove (1) => (2) => (1) and (1) => (3). (Below $\bot$ denotes a contradictory formula and I assume that $\phi\to\bot$ is equivalent to $\neg\phi$ .)

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

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

(1) => (3): This is obvious: for every $\phi$ , either $\phi\in\Gamma$ or $\neg\phi\in\Gamma$ by (3). Therefore, $\Gamma\vdash\phi$ or $\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.

**emakarov** · March 26th 2010, 06:02 AM

If

is a maximal consistent set of sentences (

or

, but not both) is complete (

or

).

By the way, the formula

or

in the assumption above does not mean that $\Gamma$ is maximal and so it does not imply

or

. There are axiomatizable complete theories (e.g., dense linear orders). This means that there is a small set of axioms $\Delta$ that generates the whole theory $\Gamma$ , i.e., $\Gamma=\{\phi\mid\Delta\vdash\phi\}$ . Now, there are such $\Delta$ and $\Gamma$ that $\Gamma$ is complete (in my sense, i.e., $\Gamma\vdash\phi$ or $\Gamma\vdash\neg\phi$ for every $\phi$ ), and so $\Delta$ is complete. However, $\Delta$ does not have to be maximal.

**MoeBlee** · March 26th 2010, 01:19 PM

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).

**Giraffro** · March 26th 2010, 03:23 PM

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 $\mathcal{L}$ be a first order language, $\Gamma \subseteq \text{Sent}(\mathcal{L})$ be consistent. Then the following statements are equivalent:

$\Gamma$ is complete, as in your definition.
$\exists \mathcal{A}$ an $\mathcal{L}$ -structure such that $\Gamma \vDash \text{Th}(\mathcal{A})$ .
$\forall \mathcal{A}, \mathcal{B}$ models of $\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.

**MoeBlee** · March 26th 2010, 04:17 PM

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'.

**Giraffro** · March 26th 2010, 04:20 PM

Yeh it's fine now. Thanks!

Thread: Maximal consistent sets are complete

LinkBack

Thread Tools

Display

Maximal consistent sets are complete

Similar Math Help Forum Discussions

Complete sets demonstrations

Consistent Estimator

consistent property

which of the following are complete sets, and why?

Consistent Estimator

Search Tags