## You are here

Homeproperties of consistency

## Primary tabs

# 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. $\Delta$ is consistent

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

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

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.\Rightarrow 2$.
Since $\perp\notin\{A\mid\Delta\vdash A\}$.

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

- $3.\Rightarrow 4$.
- $4.\Rightarrow 1$.
Since $\Delta\vdash\neg\perp$, $\Delta\not\vdash\perp$ as a result.

∎

Below are some properties of consistency:

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

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

3. Any subset of a consistent set is consistent.

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

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. If there is a truth-valuation $v$ such that $v(A)=1$ for all $A\in\Delta$, then $\Delta$ is consistent.

7.

Remark. The converse of 6 is also true; it is essentially the compactness theorem for propositional logic (see here).

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

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

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

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.

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.

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.

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

## Mathematics Subject Classification

03B45*no label found*03B10

*no label found*03B05

*no label found*03B99

*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