Common sense in Yamashita Lab.
Gödel’s incompleteness theorems
Yukihiko Yamashita
Tokyo Institute of TechnologyContents• What is ‘set’• Gödel’s first incompleteness theorem• Gödel’s second incompleteness theorem

11 SetQueistion: What is set?

2

Queistion: X = {S | S is a set} is a set?

3

1.1 Russell’s paradox
Let W = {S | S < S }.
Queistion: W ∈ W?
Assume that W ∈ W, then W < W.
Assume that W < W, then W ∈ W.
Axioms of set is necessary41.2 ZermeloFraenkel set theory with axiom of choice• Axiom of extensionality: ∀z(z ∈ x ↔ z ∈ y) ↔ x = y• Axiom of pairing: ∃z∀u(u ∈ z ↔ u = x or u = y)
• Axiom of union: ∃y∀z(z ∈ y ↔ ∃u(u ∈ x and z ∈ u))• Axiom of power set ∃y∀z(z ∈ y ↔ z ⊂ x)
• Axiom of empty set: ∃x∀y(y < x)
• Axiom of infinity: ∃x[φ ∈ x and ∀y(y ∈ x → y ∩ {y} ∈ x)]• Axiom schema of replacement:∀x∀y∀z(ϕ(x, y) and ϕ(x, z) → y = z)→ ∃u∀y[y ∈ u ↔ ∃x(x ∈ u and ϕ(x, y))]• Axiom of regularity: x , φ → ∃y(y ∈ x and y ∩ x , φ)
• (Axiom of choice):∀x ∈ u(x , φ) and ∀x, y ∈ u(x , y → x ∩ y = φ)→ ∃v∀x ∈ u∃!t(t ∈ x and t ∈ v)
We can discuss almost all mathematical issues.
Queistion: Is ZFC is consistent?
51.3 Peano axioms
Because ZFC is too diﬃcult, we show axioms of natural numbers called Peanoaxioms.
• Any natural number x has its successor x0.
• There exist a natural number 0 that is not a successor.
• If x0 = y0, we have x = y.
• For any logical expression ϕ(x), we have the following relation
ϕ(0), ∀x(ϕ(x) → ϕ(x0)) ↔ ∀xϕ(x)(Mathematical induction).

61.4 Recursive functions
In order to define calculation on integers, the primitive recursive function isdefined.
• Function which provide a constant c:
f (x1, . . . , xk ) = c.
• Function which select a input variable xi (1 ≤ i ≤ k):f (x1, . . . , xk ) = xi.
• Function which provides the successor:
f (x) = x0.
• Compound function: Assume that f (x1, . . . , xk ), g1(x11, . . . , x1n1 ),. . . , and,gk (xk1, . . . , xknk ) are primitive recursive functions,f (g1(x11, . . . , x1n1 ), . . . , gk (xk1, . . . , xknk )).
• Function defined recursively: Assume that g(x2, . . . , xk ), h(x, y1, . . . , yk )7are primitive recursive functions.
f (0, x2, . . . , xk ) = g(x2, . . . , xk )f (x0, x2, . . . , xk ) = h( f (x, x2, . . . , xk ), x, x2, . . . , xk )Example: For g(x) = x, h(x) = x0
plus(0, y) = g(y)(= y)plus(x0, y) = h(plus(x, y))(= plus(x, y)0)
Question: What is plus(x, y).
Let’s prove plus(x, y) = plus(y, x) by using Peano axioms.
Hint: Prove plus(0, y0) = plus(0, y)0, plus(x, y0) = plus(x, y)0, and plus(x, y0) =plus(y0, x).
Recursive function f (x1, . . . , xk ): t = f (x1, . . . , xk ): is defined as the minimum t such that g(x1, . . . , xk , t) = 0 with a primitive recursive function
g(x1, . . . , xk , t),Calculation is defined as a function realized by a recursive function.
8

2 Incompleteness theorems
2.1 First and second Incompleteness theorems
Assume that T is a recursive and formal theory including natural numbers.
(i) If T is consistent, there exists a sentence G in T such that we cannot
prove either G or ¬G.
(ii) If T is consistent, the consistence of T cannot proven.

• ¬G: the negation of G.
• G is called Gödel’s sentence.
• G can be realized.

92.2 Gödel’s sentence• We can map a natural number to every sentence. Thus there is one to one
mapping between a sentence and a natural number.
• For example, if we express a sentence by character codes, it is a hugebinary number.
• For a sentence A, the corresponding natural number is described by dAe
and called the Gödel’s number of A.
• Let Bew(dAe) be a logical expression such that A can be proven.
• Since we can give a natural number to a proof, “There is a proof” is equivalent to “There is a natural number with a condition”.
• Since a primitive recursive function can check whether a number is a
proof or not, we can know whether a proof exists or not by a recursivefunction.
• Proofs can be handled in the natural number theory.
• Let Sub(n, m) be the Gödel’s number of a logical expression such that anatural number n is substituted into a free variable of a logical expressionof Gödel’s number m, which has only one free variable. This is a func10

tion from two integers to a integer and realized by a primitive recursivefunction.
• A logical expression R(n) is defined by ¬Bew(Sub(n, n)).
• The Gödel’s sentence G is defined by R(dR(n)e).
• In dR(n)e, a Gödel’s number as a free variable is assigned to n.
• We have the following equivalency:G ↔ ¬Bew(Sub(dR(n)e, dR(n)e))(1)• This Sub(dR(n)e, dR(n)e)) is given by the Gödel’s number of the logicalexpression when we substitute the Gödel’s number of R(n) into n in R(n).
Therefore it is the Gödel’s number of R(dR(n)e) or G. (Note that dR(n)e isa natural number.)• Then, we have the following equivalency:G ↔ ¬Bew(dGe)(2)

This means if G is true, we cannot prove G, and if G is not true, we canprove.
112.3 Consistence
Definition Theory T is consistent:
There is no case such that both A and ¬A are proven for a logical expressions A.

• If a theory T is not consistent, we can prove A∧¬A for a logical expressionA.
• For any logical expression B, from a logic theory we have¬B → A ∨ ¬A(= true).
• By considering its contraposition, we haveA ∧ ¬A → B.
• Since A ∧ ¬A can be proven, any logical expression B is proven.
• Therefore, not consistent theory can not use at all.
• Con(T ) denotes that a theory T is consistent.
12(3)3 Outline of proof of Gödel’s first incompleteness theorem• If G can be proven, G becomes true and G cannot be proven. This contradicts to that G can be proven.
• If ¬G can be proven, we can prove Bew(dGe). Then, Bew(dGe) is true andG can be proven. Because G and ¬G can be proven, This contradicts theconsistence of the theory.
4 Outline of proof of Gödel’s second incompleteness theorem
Let’s describe formally what we proved for the first theorem:
Con(T ) → ¬Bew(dGe)
Con(T ) → ¬Bew(d¬Ge)
If we can prove Con(T ) formally, we can prove ¬Bew(dGe) and can prove G.
This contradicts to the first theorem.

13

5 Conclusion• Diagonal method is used.
• The concept ‘calculation’ that is very important in computer was born todiscuss theories and proofs strictly.
• In order to show there is no proof, we have to define procedure or algorithm.
• For the purpose,the recursive function and the Turing machine are defined,and computers are invented.
• Anyway I feel uneasy since we cannot prove the consistence of present
theories of mathematics.

14

Proof of plus(x, y) = plus(y, x).
1. We will prove plus(x, 0) = plus(0, x) for any x by mathematical induction
with respect to x. When x = 0, we haveplus(0, 0) = plus(0, 0).
Assume that plus(x, 0) = plus(0, x), we haveplus(x0, 0) = (plus(x, 0))0 = (plus(0, x))0 = x0 = plus(0, x0).
2. We will prove plus(x, y0) = plus(x, y)0 for any x and y by mathematicalinduction with respect to x. When x = 0, we have for any yplus(0, y0) = y0 = plus(0, y)0
Assume that plus(x, y0) = plus(x, y)0 for any y, we haveplus(x0, y0) = plus(x, y0)0 = (plus(x, y)0)0 = plus(x0, y)015

3. Now will will prove plus(x, y) = plus(y, x) for any x and y by mathematicalinduction with respect to y. 1. yields
plus(x, 0) = plus(0, x).
Assume that plus(x, y) = plus(y, x) for any x, we have from 2.
plus(x, y0) = (plus(x, y))0 = (plus(y, x))0 = plus(y0, x).

16