# maximally consistent

A set $\Delta$ of well-formed formulas (wff) is maximally consistent if $\Delta$ is consistent and any consistent superset of it is itself: $\Delta\subseteq\Gamma$ with $\Gamma$ consistent implies $\Gamma=\Delta$.

Below are some basic properties of a maximally consistent set $\Delta$:

1. 1.

$\Delta$ is deductively closed ($\Delta$ is a theory): $\Delta\vdash A$ iff $A\in\Delta$.

2. 2.

$\Delta$ is complete: $\Delta\vdash A$ or $\Delta\vdash\neg A$ for any wff $A$.

3. 3.

for any wff $A$, either $A\in\Delta$ or $\neg A\in\Delta$.

4. 4.

If $A\notin\Delta$, then $\Delta\cup\{A\}$ is not consistent.

5. 5.

$\Delta$ is a logic: $\Delta$ contains all theorems and is closed under modus ponens.

6. 6.

$\perp\notin\Delta$.

7. 7.

$A\to B\in\Delta$ iff $A\in\Delta$ implies $B\in\Delta$.

8. 8.

$A\land B\in\Delta$ iff $A\in\Delta$ and $B\in\Delta$.

9. 9.

$A\lor B\in\Delta$ iff $A\in\Delta$ or $B\in\Delta$.

###### Proof.
1. 1.

If $A\in\Delta$, then clearly $\Delta\vdash A$. Conversely, suppose $\Delta\vdash A$. Let $\mathcal{E}$ be a deduction of $A$ from $\Delta$, and $\Gamma:=\Delta\cup\{A\}$. Suppose $\Gamma\vdash B$. Let $\mathcal{E}_{1}$ be a deduction of $B$ from $\Gamma$, then $\mathcal{E},\mathcal{E}_{1}$ is a deduction of $B$ from $\Delta$, so $\Delta\vdash B$. Since $\Delta\not\vdash\perp$, $\Gamma\not\vdash\perp$, so $\Gamma$ is consistent. Since $\Delta$ is maximal, $\Gamma=\Delta$, or $A\in\Delta$.

2. 2.

Suppose $\Delta\not\vdash A$, then $A\notin\Delta$ by 1. Then $\Delta\cup\{A\}$ is not consistent (since $\Delta$ is maximal), which means $\Delta,A\vdash\perp$, or $\Delta\vdash A\to\perp$, or $\Delta\vdash\neg A$.

3. 3.

If $A\notin\Delta$, then $\Delta\not\vdash A$ by 1, so $\Delta\vdash\neg A$ by 2, and therefore $\neg A\in\Delta$ by 1 again.

4. 4.

If $A\notin\Delta$, then $\neg A\in\Delta$ by 3., so that $\neg A,A,\perp$ is a deduction of $\perp$ from $\Delta\cup\{A\}$, showing that $\Delta\cup\{A\}$ is not consistent.

5. 5.

If $A$ is a theorem, then $\Delta\vdash A$, so that $A\in\Delta$ by 1. If $A\in\Delta$ and $A\to B\in\Delta$, then $A,A\to B,B$ is a deduction of $B$ from $\Delta$, so $B\in\Delta$ by 1.

6. 6.

This is true for any consistent set.

7. 7.

Suppose $A\to B\in\Delta$. If $A\in\Delta$, then $B\in\Delta$ since $\Delta$ is closed under modus ponens. Conversely, suppose $A\in\Delta$ implies $B\in\Delta$. This means that $\Delta,A\vdash B$. Then $\Delta\vdash A\to B$ by the deduction theorem, and therefore $A\to B\in\Delta$ by 1.

8. 8.

Suppose $A\land B\in\Delta$, then by modus ponens on theorems $A\land B\to A$ and $A\land B\to B$, we get $A,B\in\Delta$, since $\Delta$ is a logic by 5. Conversely, suppose $A,B\in\Delta$, then by modus ponens twice on theorem $A\to(B\to A\land B)$, we get $A\land B\in\Delta$ by 5.

9. 9.

Suppose $A\lor B\in\Delta$. Then $\neg(\neg A\land\neg B)\in\Delta$ by the definition of $\lor$, so $\neg A\land\neg B\notin\Delta$ by 3., which means $\neg A\notin\Delta$ or $\neg B\notin\Delta$ by the contrapositive of 8, or $A\in\Delta$ or $B\in\Delta$ by 3. Conversely, suppose $A\in\Delta$ or $B\in\Delta$. Then by modus ponens on theorems $A\to A\lor B$ or $B\to A\lor B$ respectively, we get $A\lor B\in\Delta$ by 5.

The converses of 2 and 3 above are true too, and they provide alternative definitions of maximal consistency.

1. 1.

any complete consistent theory is maximally consistent.

2. 2.

any consistent set satisfying the condition in 3 above is maximally consistent.

###### Proof.

Suppose $\Delta$ is complete consistent. Let $\Gamma$ be a consistent superset of $\Delta$. $\Gamma$ is also complete. If $A\in\Gamma-\Delta$, then $\Gamma\vdash A$, so $\Gamma\not\vdash\neg A$ since $\Gamma$ is consistent. But then $\Delta\not\vdash\neg A$ since $\Gamma$ is a superset of $\Delta$, which means $\Delta\vdash A$ since $\Delta$ is complete. But then $A\in\Delta$ since $\Delta$ is deductively closed, which is a contradiction. Hence $\Delta$ is maximal.

Next, suppose $\Delta$ is consistent satisfying the condition: either $A\in\Delta$ or $\neg A\in\Delta$ for any wff $A$. Suppose $\Gamma$ is a consistent superset of $\Delta$. If $A\in\Gamma-\Delta$, then $\neg A\in\Delta$ by assumption, which means $\neg A\in\Gamma$ since $\Gamma$ is a superset of $\Delta$. But then both $A$ and $\neg A$ are deducible from $\Gamma$, contradicting the assumption that $\Gamma$ is consistent. Therefore, $\Gamma$ is not a proper superset of $\Delta$, or $\Gamma=\Delta$. ∎

Remarks.

• In the converse of 2, we require that $\Delta$ be a theory, for there are complete consistent sets that are not deductively closed. One such an example is the set $V$ of all propositional variables: it can be shown that for every wff $A$, exactly one of $V\vdash A$ or $V\vdash\neg A$ holds.

• So far, none of the above actually tell us that a maximally consistent set exists. However, by Zorn’s lemma, it is not hard to see that such a set does exist. For more detail, see here (http://planetmath.org/LindenbaumsLemma).

• There is also a semantic characterization of a maximally consistent set: a set is maximally consistent iff there is a unique valuation $v$ such that $v(A)=1$ for every wff $A$ in the set (see here (http://planetmath.org/CompactnessTheoremForClassicalPropositionalLogic)).

Title maximally consistent MaximallyConsistent 2013-03-22 19:35:13 2013-03-22 19:35:13 CWoo (3771) CWoo (3771) 10 CWoo (3771) Definition msc 03B05 msc 03B10 msc 03B99 msc 03B45 FirstOrderTheories complete