# properties of consistency

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

1. 1.

$\Delta$ is consistent

2. 2.

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

3. 3.

there is a formula $A$ such that $\Delta\not\vdash A$.

4. 4.

there are no formulas $A$ such that $\Delta\vdash A$ and $\Delta\vdash\neg A$.

###### Proof.

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

1. $1.\Rightarrow 2$.

Since $\perp\notin\{A\mid\Delta\vdash A\}$.

2. $2.\Rightarrow 3$.

Any formula not in $\{A\mid\Delta\vdash A\}$ will do.

3. $3.\Rightarrow 4$.

If $\Delta\vdash A$ and $\Delta\vdash\neg A$, then $A,A\to\perp,\perp,\perp\to B,B$ is a deduction of $B$ from $A$ and $\neg A$, but this means that $\Delta\vdash B$ for any wff $B$.

4. $4.\Rightarrow 1$.

Since $\Delta\vdash\neg\perp$, $\Delta\not\vdash\perp$ as a result.

Below are some properties of consistency:

1. 1.

$\Delta\cup\{A\}$ is consistent iff $\Delta\not\vdash\neg A$.

2. 2.

$\Delta\cup\{\neg A\}$ is not consistent iff $\Delta\vdash A$.

3. 3.

Any subset of a consistent set is consistent.

4. 4.

If $\Delta$ is consistent, so is Ded$(\Delta)$.

5. 5.

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

6. 6.

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

7. 7.

If $\not\vdash A$, and $\Delta$ contains the schema based on $A$, then $\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\neg\neg A$, so we will just prove one of them.

1. 2.

$\Delta,\neg A\vdash\perp$ iff $\Delta\vdash\neg\neg A$ by the deduction theorem iff $\Delta\vdash A$ by the substitution theorem.

2. 3.

If $\Gamma$ is not consistent, $\Gamma\vdash\perp$. If $\Gamma\subseteq\Delta$, then $\Delta\vdash\perp$ as well, so $\Delta$ is not consistent.

3. 4.

Since $\Delta$ is consistent, $\perp\notin$ Ded$(\Delta)$. Now, if Ded$(\Delta)\vdash\perp$, but by the remark below, $\perp\in\mbox{Ded}(\Delta)$, a contradiction.

4. 5.

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

5. 6.

If $v(A)=1$ for all $A\in\Delta$, $v(B)=1$ for all $B$ such that $\Delta\vdash B$. Since $v(\perp)=0$, $\Delta$ is consistent.

6. 7.

Suppose $v(A)$ for some valuation $v$. Let $p_{1},\ldots,p_{m}$ be the propositional variables in $A$ such that $v(p_{i})=0$ and $q_{1},\ldots,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 $\perp$ and each $q_{j}$ replaced by $\top$ (which is $\neg\perp$). Then $A^{\prime}\in\Delta$. Furthermore, $v(A^{\prime})=v(A)=0$. Now, for any valuation $u$, since $u(\perp)=0$ and $u(\top)=1$, we get $u(A^{\prime})=v(A^{\prime})=0$. In other words, $u(\neg A^{\prime})=1$ for all valuations $u$, so $\neg A^{\prime}$ is valid, and hence a theorem of $L$ by the completeness theorem. But this means that $A^{\prime}\leftrightarrow\perp$, which implies that $\Delta\vdash\perp$.

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

###### Proof.

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

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

Now, suppose Ded$(\Delta)\vdash A$. We induct on the length of the deduction sequence of $A$. If $n=1$, then $A\in\mbox{Ded}(\Delta)$ and we are done. Now, suppose the length of is $n+1$. If $A$ is either a theorem or in Ded$(\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},\ldots,A_{i}$ is a deduction of $A_{i}$ from Ded$(\Delta)$, and it has length $i\leq n$, by the induction step, $A_{i}\in\mbox{Ded}(\Delta)$. Similarly, $A_{j}\in\mbox{Ded}(\Delta)$. But this means that $A\in\mbox{Ded}(\Delta)$ by the last paragraph. ∎

Title properties of consistency PropertiesOfConsistency 2013-03-22 19:35:07 2013-03-22 19:35:07 CWoo (3771) CWoo (3771) 18 CWoo (3771) Feature msc 03B45 msc 03B10 msc 03B05 msc 03B99 FirstOrderTheories deductive closure