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}\u22a2\u0338\u27c2$. In other words, $\u27c2$ 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}\u22a2A\}$ is not the set of all wff’s

3.
there is a formula^{} $A$ such that $\mathrm{\Delta}\u22a2\u0338A$.

4.
there are no formulas $A$ such that $\mathrm{\Delta}\u22a2A$ and $\mathrm{\Delta}\u22a2\mathrm{\neg}A$.
Proof.
We shall prove $1.\Rightarrow 2.\Rightarrow 3.\Rightarrow 4.\Rightarrow 1.$

$1.\Rightarrow 2$.
Since $\u27c2\notin \{A\mid \mathrm{\Delta}\u22a2A\}$.

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

$3.\Rightarrow 4$.
If $\mathrm{\Delta}\u22a2A$ and $\mathrm{\Delta}\u22a2\mathrm{\neg}A$, then $A,A\to \u27c2,\u27c2,\u27c2\to B,B$ is a deduction^{} of $B$ from $A$ and $\mathrm{\neg}A$, but this means that $\mathrm{\Delta}\u22a2B$ for any wff $B$.

$4.\Rightarrow 1$.
Since $\mathrm{\Delta}\u22a2\mathrm{\neg}\u27c2$, $\mathrm{\Delta}\u22a2\u0338\u27c2$ as a result.
∎
Below are some properties of consistency:

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

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

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 truthvaluation $v$ such that $v(A)=1$ for all $A\in \mathrm{\Delta}$, then $\mathrm{\Delta}$ is consistent.

7.
If $\u22a2\u0338A$, 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.

2.
$\mathrm{\Delta},\mathrm{\neg}A\u22a2\u27c2$ iff $\mathrm{\Delta}\u22a2\mathrm{\neg}\mathrm{\neg}A$ by the deduction theorem^{} iff $\mathrm{\Delta}\u22a2A$ by the substitution theorem.

3.
If $\mathrm{\Gamma}$ is not consistent, $\mathrm{\Gamma}\u22a2\u27c2$. If $\mathrm{\Gamma}\subseteq \mathrm{\Delta}$, then $\mathrm{\Delta}\u22a2\u27c2$ as well, so $\mathrm{\Delta}$ is not consistent.

4.
Since $\mathrm{\Delta}$ is consistent, $\u27c2\notin $ Ded$(\mathrm{\Delta})$. Now, if Ded$(\mathrm{\Delta})\u22a2\u27c2$, but by the remark below, $\u27c2\in \text{Ded}(\mathrm{\Delta})$, a contradiction^{}.

5.
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\u22a2\u27c2$ and $\mathrm{\Delta},\mathrm{\neg}A\u22a2\u27c2$, or $\mathrm{\Delta}\u22a2\mathrm{\neg}A$ and $\mathrm{\Delta}\u22a2\mathrm{\neg}\mathrm{\neg}A$, or $\mathrm{\Delta}\u22a2\mathrm{\neg}A$ and $\mathrm{\Delta}\u22a2A$ by the substitution theorem on $A\leftrightarrow \mathrm{\neg}\mathrm{\neg}A$, but this means $\mathrm{\Delta}$ is not consistent, a contradiction.

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

7.
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 $\u27c2$ and each ${q}_{j}$ replaced by $\top $ (which is $\mathrm{\neg}\u27c2$). Then ${A}^{\prime}\in \mathrm{\Delta}$. Furthermore, $v({A}^{\prime})=v(A)=0$. Now, for any valuation $u$, since $u(\u27c2)=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 \u27c2$, which implies that $\mathrm{\Delta}\u22a2\u27c2$.
∎
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})\u22a2A$.
Proof.
If $A\in \text{Ded}(\mathrm{\Delta})$, then $\mathrm{\Delta}\u22a2A$, so certainly Ded$(\mathrm{\Delta})\u22a2A$, as Ded$(\mathrm{\Delta})$ is a superset^{} of $\mathrm{\Delta}$.
Before proving the converse, note first that if $\mathrm{\Delta}\u22a2B$ and $\mathrm{\Delta}\u22a2B\to A$, $\mathrm{\Delta}\u22a2A$ 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})\u22a2A$. 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. ∎
Title  properties of consistency 

Canonical name  PropertiesOfConsistency 
Date of creation  20130322 19:35:07 
Last modified on  20130322 19:35:07 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  18 
Author  CWoo (3771) 
Entry type  Feature 
Classification  msc 03B45 
Classification  msc 03B10 
Classification  msc 03B05 
Classification  msc 03B99 
Related topic  FirstOrderTheories 
Defines  deductive closure 
\@unrecurse 