We proceed now to the rigorous development of the proof sketched above, and begin by giving an exact description of the formal system P, for which we seek to demonstrate the existence of undecidable propositions. P is essentially the system obtained by superimposing on the Peano axioms the logic of PM16
etc
- ~(Sx1 = 0)
Zero is the successor of no number. Expanded into the basic signs, the axiom is: ~(a2 ∀ (~(a2(x1)) ∨ a2(0)))
This is the smallest axiom in the entire system (although there are smaller theorems, such as 0=0).
- Sx1 = Sy1 ⊃ x1 = y1
If x+1 = y+1 then x=y. Expanding the ⊃ operator we get: ~(Sx1 = Sy1) ∨ (x1 = y1) And expanding the = operators we get: ~(a2 ∀ (~(a2(Sx1)) ∨ a2(Sy1))) ∨ (a2 ∀ (~(a2(x1)) ∨ a2(y1)))
- x2(0).x1 ∀ (x2(x1) ⊃ x2(fx1)) ⊃ x1 ∀ (x2(x1))
The principle of mathematical induction: If something is true for x=0, and if you can show that whenever it is true for y it is also true for y+1, then it is true for all whole numbers x.
[178]II. Every formula derived from the following schemata by substitution of any formulae for p, q and r.
-
p ∨ p ⊃ p
-
p ⊃ p ∨ q
-
p ∨ q ⊃ q ∨ p
-
(p ⊃ q) ⊃ (r ∨ p ⊃ r ∨ q)
III. Every formula derived from the two schemata
-
v ∀ (a) ∨ Subst a(v|c)
-
v ∀ (b ⊃ a) ∨ b ⊃ v ∀ (a)
by making the following substitutions for a, v, b, c (and carrying out in I the operation denoted by “Subst”): for a any given formula, for v any variable, for b any formula in which v does not appear free, for c a sign of the same type as v, provided that c contains no variable which is bound in a at a place where v is free.23
IV. Every formula derived from the schema
- (∃u)(v ∀ (u(v) ≡ a))
on substituting for v or u any variables of types n or n + 1 respectively, and for a a formula which does not contain u free. This axiom represents the axiom of reducibility (the axiom of comprehension of set theory).
V. Every formula derived from the following by type-lift (and this formula itself):
- x1 ∀ (x2(x1) ≡ y2(x1)) ∨ x2 = y2.
This axiom states that a class is completely determined by its elements.
etc
In the proof of Proposition VI the only properties of the system P [which is Peano and PM ie axiom of reducibility employed were the following:
-
The class of axioms [which include AR] and the rules of inference (i.e. the relation “immediate consequence of”) are recursively definable (as soon as the basic signs are replaced in any fashion by natural numbers).
-
Every recursive relation is definable in the system P (in the sense of Proposition V).
Hence in every formal system that satisfies assumptions 1 and 2 [ which includes AR] and is ω-consistent, undecidable propositions exist of the form (x) F(x), where F is a recursively defined property of natural numbers, and so too in every extension of such