2.2 Axiomatic Systems

Definition 1.5 (Axiomatic System) An axiomatic system is a finite sequence of propositions or propositional schemes \(a_1, a_2, \dots, a_N\), which are called axioms.

Definition 1.6 (Definition of a Proof) A proof of a proposition \(p\) within an axiomatic system \(a_1,a_2,\dots, a_N\) is a finite sequence of propositions \(q_1, q_2, \dots, q_M\) where \(q_M \iff p\) such that for any \(1\leq j \leq M\) one of the following is true:

  • \(q_j\) is a proposition from the list of axioms
  • \(q_j\) is a a tautology (a proposition that is always true independent of the propositions of which it is made).4 e.g. the proposition \(p \lor \neg p\) is always true, independent of what \(p\) actually is.
  • \(q_j\) can be deduced from two previous steps \(m\) and \(n\); \(\exists\, 1 \leq m , n \leq j : q_M \land q_N \implies q_j\).

In sum, every step of a proof must be an axiom, a tautology, or a deduction from two previous steps.

Remark. If \(p\) can be proven from an axiomatic system \(a_1, \dots, a_N\), we often write \[a_1, \dots, a_N \vdash p. \] This definition allows us to easily recognize a proof.

Remark. Tautologies can be pulled from the axioms without impairing the power of the axiomatic system. An extreme case of this property is found for the axiomatic system of propositional logic: the empty sequence.

Definition 1.7 (Consistency) An axiomatic system is said to be consistent if there exists a proposition \(q\) which cannot be proven from the axioms.

Why do we define such a system to be consistent? Consider an axiomatic system containing both the propositions \(s\) and \(\neg s\). Then you could pull in a tautology \(s \land \neg s \implies q\), which would actually work out by ex falso quodlibet since \(s \land \neg s\) is always false.

Proof (Propositional Logic is Consistent). As follows:

  • It suffices to show that there exists a proposition that cannot be proven within propositional logic.
  • Since propositional logic has no axioms, every step of the proof can only invoke tautologies.
  • But then you cannot prove, for example, \(q \land \neg q\) since \(q\) is a proposition that is not necessarily a tautology.

Theorem 1.2 (Gödel) Any axiomatic system that is powerful enough to encode the elementary arithmetic of natural numbers is either inconsistent or contains a proposition that can neither be proven nor disproven. To prove this, Gödel assigned a number to every mathematical statement and used a Barber Paradox-type argument to identify a proposition neither provable nor disprovable.