You are here
Homemaximally consistent
Primary tabs
maximally consistent
A set $\Delta$ of wellformed 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. $\Delta$ is deductively closed ($\Delta$ is a theory): $\Delta\vdash A$ iff $A\in\Delta$.
2. $\Delta$ is complete: $\Delta\vdash A$ or $\Delta\vdash\neg A$ for any wff $A$.
3. for any wff $A$, either $A\in\Delta$ or $\neg A\in\Delta$.
4. If $A\notin\Delta$, then $\Delta\cup\{A\}$ is not consistent.
5. $\Delta$ is a logic: $\Delta$ contains all theorems and is closed under modus ponens.
6. $\perp\notin\Delta$.
7. $A\to B\in\Delta$ iff $A\in\Delta$ implies $B\in\Delta$.
8. $A\land B\in\Delta$ iff $A\in\Delta$ and $B\in\Delta$.
9. $A\lor B\in\Delta$ iff $A\in\Delta$ or $B\in\Delta$.
Proof.
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. 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. 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. 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. 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. This is true for any consistent set.
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. 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. 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. any complete consistent theory is maximally consistent.
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.

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).
Mathematics Subject Classification
03B05 no label found03B10 no label found03B99 no label found03B45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections