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. ∎

Title	properties of consistency
Canonical name	PropertiesOfConsistency
Date of creation	2013-03-22 19:35:07
Last modified on	2013-03-22 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