maximally consistent

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

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

1. $\mathrm{\Delta }$ is deductively closed ($\mathrm{\Delta }$ is a theory): $\mathrm{\Delta }⊢A$ iff $A\in \mathrm{\Delta }$.

2. $\mathrm{\Delta }$ is complete: $\mathrm{\Delta }⊢A$ or $\mathrm{\Delta }⊢\mathrm{\neg }A$ for any wff $A$.

3. for any wff $A$, either $A\in \mathrm{\Delta }$ or $\mathrm{\neg }A\in \mathrm{\Delta }$.

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

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

6. $⟂\notin \mathrm{\Delta }$.

7. $A\to B\in \mathrm{\Delta }$ iff $A\in \mathrm{\Delta }$ implies $B\in \mathrm{\Delta }$.

8. $A\wedge B\in \mathrm{\Delta }$ iff $A\in \mathrm{\Delta }$ and $B\in \mathrm{\Delta }$.

9. $A\vee B\in \mathrm{\Delta }$ iff $A\in \mathrm{\Delta }$ or $B\in \mathrm{\Delta }$.

Proof.

1. If $A\in \mathrm{\Delta }$, then clearly $\mathrm{\Delta }⊢A$. Conversely, suppose $\mathrm{\Delta }⊢A$. Let $ℰ$ be a deduction of $A$ from $\mathrm{\Delta }$, and $\mathrm{\Gamma }:=\mathrm{\Delta }\cup \{A\}$. Suppose $\mathrm{\Gamma }⊢B$. Let ${ℰ}_1$ be a deduction of $B$ from $\mathrm{\Gamma }$, then $ℰ,{ℰ}_1$ is a deduction of $B$ from $\mathrm{\Delta }$, so $\mathrm{\Delta }⊢B$. Since $\mathrm{\Delta }⊬⟂$, $\mathrm{\Gamma }⊬⟂$, so $\mathrm{\Gamma }$ is consistent. Since $\mathrm{\Delta }$ is maximal, $\mathrm{\Gamma }=\mathrm{\Delta }$, or $A\in \mathrm{\Delta }$.

2. Suppose $\mathrm{\Delta }⊬A$, then $A\notin \mathrm{\Delta }$ by 1. Then $\mathrm{\Delta }\cup \{A\}$ is not consistent (since $\mathrm{\Delta }$ is maximal), which means $\mathrm{\Delta },A⊢⟂$, or $\mathrm{\Delta }⊢A\to ⟂$, or $\mathrm{\Delta }⊢\mathrm{\neg }A$.

3. If $A\notin \mathrm{\Delta }$, then $\mathrm{\Delta }⊬A$ by 1, so $\mathrm{\Delta }⊢\mathrm{\neg }A$ by 2, and therefore $\mathrm{\neg }A\in \mathrm{\Delta }$ by 1 again.

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

5. If $A$ is a theorem, then $\mathrm{\Delta }⊢A$, so that $A\in \mathrm{\Delta }$ by 1. If $A\in \mathrm{\Delta }$ and $A\to B\in \mathrm{\Delta }$, then $A,A\to B,B$ is a deduction of $B$ from $\mathrm{\Delta }$, so $B\in \mathrm{\Delta }$ by 1.

6. This is true for any consistent set.

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

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

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

∎

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

1. any complete consistent theory is maximally consistent.

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

Proof.

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

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

Remarks.

• In the converse of 2, we require that $\mathrm{\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⊢A$ or $V⊢\mathrm{\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
Canonical name	MaximallyConsistent
Date of creation	2013-03-22 19:35:13
Last modified on	2013-03-22 19:35:13
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	10
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03B05
Classification	msc 03B10
Classification	msc 03B99
Classification	msc 03B45
Related topic	FirstOrderTheories
Defines	complete