# Equivalence of Definitions of Consistent Proof System

## Theorem

The following definitions of the concept of **Consistent Proof System for Propositional Logic** are equivalent:

Let $\LL_0$ be the language of propositional logic.

Let $\mathscr P$ be a proof system for $\LL_0$.

### Definition 1

Then $\mathscr P$ is **consistent** if and only if:

- There exists a logical formula $\phi$ such that $\not \vdash_{\mathscr P} \phi$

That is, some logical formula $\phi$ is **not** a theorem of $\mathscr P$.

### Definition 2

Suppose that in $\mathscr P$, the Rule of Explosion (Variant 3) holds.

Then $\mathscr P$ is **consistent** if and only if:

- For every logical formula $\phi$, not
*both*of $\phi$ and $\neg \phi$ are theorems of $\mathscr P$

## Proof

### Definition 1 implies Definition 2

Suppose that $\neg \vdash_{\mathscr P} \phi$.

Suppose additionally that there is some logical formula $\psi$ such that:

- $\vdash_{\mathscr P} \psi, \neg \psi$

By the Rule of Explosion:

- $\psi, \neg \psi \vdash_{\mathscr P} \phi$

By Provable Consequence of Theorems is Theorem, we conclude:

- $\vdash_{\mathscr P} \phi$

in contradiction to our assumption.

$\Box$

### Definition 2 implies Definition 1

Suppose either $\phi$ or $\neg \phi$ is not a theorem of $\mathscr P$.

The implication follows trivially.

$\blacksquare$

## Sources

- 1959: A.H. Basson and D.J. O'Connor:
*Introduction to Symbolic Logic*(3rd ed.) ... (previous) ... (next): $\S 4.4$: Conditions for an Axiom System: Theorem $3$, Theorem $4$