properties of consistency

Fix a (classical) propositional logic $L$. Recall that a set $\mathrm{\Delta }$ of wff’s is said to be $L$-consistent, or consistent for short, if $\mathrm{\Delta }⊬⟂$. In other words, $⟂$ can not be derived from axioms of $L$ and elements of $\mathrm{\Delta }$ via finite applications of modus ponens. There are other equivalent formulations of consistency:

1. $\mathrm{\Delta }$ is consistent

2. Ded$(\mathrm{\Delta }):=\{A\mid \mathrm{\Delta }⊢A\}$ is not the set of all wff’s

3. there is a formula $A$ such that $\mathrm{\Delta }⊬A$.

4. there are no formulas $A$ such that $\mathrm{\Delta }⊢A$ and $\mathrm{\Delta }⊢\mathrm{\neg }A$.

Proof.

We shall prove $1.\Rightarrow 2.\Rightarrow 3.\Rightarrow 4.\Rightarrow 1.$

1. Since $⟂\notin \{A\mid \mathrm{\Delta }⊢A\}$.

2. Any formula not in $\{A\mid \mathrm{\Delta }⊢A\}$ will do.

3. If $\mathrm{\Delta }⊢A$ and $\mathrm{\Delta }⊢\mathrm{\neg }A$, then $A,A\to ⟂,⟂,⟂\to B,B$ is a deduction of $B$ from $A$ and $\mathrm{\neg }A$, but this means that $\mathrm{\Delta }⊢B$ for any wff $B$.

4. Since $\mathrm{\Delta }⊢\mathrm{\neg }⟂$, $\mathrm{\Delta }⊬⟂$ as a result.

∎

Below are some properties of consistency:

1. $\mathrm{\Delta }\cup \{A\}$ is consistent iff $\mathrm{\Delta }⊬\mathrm{\neg }A$.

2. $\mathrm{\Delta }\cup \{\mathrm{\neg }A\}$ is not consistent iff $\mathrm{\Delta }⊢A$.

3. Any subset of a consistent set is consistent.

4. If $\mathrm{\Delta }$ is consistent, so is Ded$(\mathrm{\Delta })$.

5. If $\mathrm{\Delta }$ is consistent, then at least one of $\mathrm{\Delta }\cup \{A\}$ or $\mathrm{\Delta }\cup \{\mathrm{\neg }A\}$ is consistent for any wff $A$.

6. If there is a truth-valuation $v$ such that $v(A)=1$ for all $A\in \mathrm{\Delta }$, then $\mathrm{\Delta }$ is consistent.

7. If $⊬A$, and $\mathrm{\Delta }$ contains the schema based on $A$, then $\mathrm{\Delta }$ is not consistent.

Remark. The converse of 6 is also true; it is essentially the compactness theorem for propositional logic (see here (http://planetmath.org/CompactnessTheoremForClassicalPropositionalLogic)).

Proof.

The first two are contrapositive of one another via the theorem $A\leftrightarrow \mathrm{\neg }\mathrm{\neg }A$, so we will just prove one of them.

1. $\mathrm{\Delta },\mathrm{\neg }A⊢⟂$ iff $\mathrm{\Delta }⊢\mathrm{\neg }\mathrm{\neg }A$ by the deduction theorem iff $\mathrm{\Delta }⊢A$ by the substitution theorem.

2. If $\mathrm{\Gamma }$ is not consistent, $\mathrm{\Gamma }⊢⟂$. If $\mathrm{\Gamma }\subseteq \mathrm{\Delta }$, then $\mathrm{\Delta }⊢⟂$ as well, so $\mathrm{\Delta }$ is not consistent.

3. Since $\mathrm{\Delta }$ is consistent, $⟂\notin$ Ded$(\mathrm{\Delta })$. Now, if Ded$(\mathrm{\Delta })⊢⟂$, but by the remark below, $⟂\in \text{Ded}(\mathrm{\Delta })$, a contradiction.

4. Suppose $\mathrm{\Delta }$ is consistent and $A$ any wff. If neither $\mathrm{\Delta }\cup \{A\}$ and $\mathrm{\Delta }\cup \{\mathrm{\neg }A\}$ are consistent, then $\mathrm{\Delta },A⊢⟂$ and $\mathrm{\Delta },\mathrm{\neg }A⊢⟂$, or $\mathrm{\Delta }⊢\mathrm{\neg }A$ and $\mathrm{\Delta }⊢\mathrm{\neg }\mathrm{\neg }A$, or $\mathrm{\Delta }⊢\mathrm{\neg }A$ and $\mathrm{\Delta }⊢A$ by the substitution theorem on $A\leftrightarrow \mathrm{\neg }\mathrm{\neg }A$, but this means $\mathrm{\Delta }$ is not consistent, a contradiction.

5. If $v(A)=1$ for all $A\in \mathrm{\Delta }$, $v(B)=1$ for all $B$ such that $\mathrm{\Delta }⊢B$. Since $v(⟂)=0$, $\mathrm{\Delta }$ is consistent.

6. Suppose $v(A)$ for some valuation $v$. Let $p_1,\mathrm{\dots },p_m$ be the propositional variables in $A$ such that $v(p_i)=0$ and $q_1,\mathrm{\dots },q_n$ be the variables in $A$ such that $v(q_j)=1$. Let $A^{\prime }$ be the instance of the schema $A$ where each $p_i$ is replaced by $⟂$ and each $q_j$ replaced by $\top$ (which is $\mathrm{\neg }⟂$). Then $A^{\prime }\in \mathrm{\Delta }$. Furthermore, $v(A^{\prime })=v(A)=0$. Now, for any valuation $u$, since $u(⟂)=0$ and $u(\top )=1$, we get $u(A^{\prime })=v(A^{\prime })=0$. In other words, $u(\mathrm{\neg }{A}^{\prime })=1$ for all valuations $u$, so $\mathrm{\neg }{A}^{\prime }$ is valid, and hence a theorem of $L$ by the completeness theorem. But this means that $A^{\prime }\leftrightarrow ⟂$, which implies that $\mathrm{\Delta }⊢⟂$.

∎

Remark. The set Ded$(\mathrm{\Delta })$ is called the deductive closure of $\mathrm{\Delta }$. It is so called because it is deductively closed: $A\in \text{Ded}(\mathrm{\Delta })$ iff Ded$(\mathrm{\Delta })⊢A$.

Proof.

If $A\in \text{Ded}(\mathrm{\Delta })$, then $\mathrm{\Delta }⊢A$, so certainly Ded$(\mathrm{\Delta })⊢A$, as Ded$(\mathrm{\Delta })$ is a superset of $\mathrm{\Delta }$.

Before proving the converse, note first that if $\mathrm{\Delta }⊢B$ and $\mathrm{\Delta }⊢B\to A$, $\mathrm{\Delta }⊢A$ by modus ponens. This implies that Ded$(\mathrm{\Delta })$ is closed under modus ponens: if $B$ and $B\to A$ are both in Ded$(\mathrm{\Delta })$, so is $A$.

Now, suppose Ded$(\mathrm{\Delta })⊢A$. We induct on the length of the deduction sequence of $A$. If $n=1$, then $A\in \text{Ded}(\mathrm{\Delta })$ and we are done. Now, suppose the length of is $n+1$. If $A$ is either a theorem or in Ded$(\mathrm{\Delta })$, we are done. Now, suppose $A$ is the result of applying modus ponens to two earlier members, say $A_i$ and $A_j$. Since $A_1,\mathrm{\dots },A_i$ is a deduction of $A_i$ from Ded$(\mathrm{\Delta })$, and it has length $i\le n$, by the induction step, $A_i\in \text{Ded}(\mathrm{\Delta })$. Similarly, $A_j\in \text{Ded}(\mathrm{\Delta })$. But this means that $A\in \text{Ded}(\mathrm{\Delta })$ by the last paragraph.∎