A Step by Step Guide to Gödel’s Incompleteness Proof:
6: Relations of Natural Numbers 1 to 23

This is a relation that asserts that y is divisible by x with no remainder .

e.g. the relation 72/6 applies, but 73/6 does not apply.

 

In Gödel’s paper…

This is a relation that asserts that x is a prime number. i.e: x is one of 2, 3, 5, 7, 11, 13, 17, 19, 23, …

e.g. the relation Prim(7) applies, but Prim(8) does not apply.

 

In Gödel’s paper…

This is a function whose value is the n^th largest prime number that is a factor of x .

e.g. 4 Pr [ 2³ · 3 · 5³ · 7⁴ · 11 · 13³ ] = 7

(7 is the 4^th largest prime factor of 2³ · 3 · 5³ · 7⁴ · 11 · 13³)

 

In Gödel’s paper…

This is the factorial function as mentioned previously in this guide. Its value is given by multiplying together n and all the natural numbers that are smaller than n (except zero).

 

e.g. 4! = 4 · 3 · 2 · 1

 

In Gödel’s paper…

This is a function whose value is the n^th largest prime number.

 

e.g. Pr(5) = 11 (the 5^th largest prime is 11; the four smaller primes are 2, 3, 5 and 7)

 

In Gödel’s paper…

This is a function which is defined in terms of the function n Pr x above, and gives the value of the smallest factor of the exponent of the n^th largest prime in the number x.

 

e.g. 5 Gl [ 2³ · 3³ · 5¹ · 7¹¹ · 11¹⁹ · 13³ ] = 19 (the 5^th largest prime in x is 11, and its exponent is 19)

 

If x is the Gödel number of the formula X, i.e: x = φ[ X ], then n Gl x corresponds to:

the symbol at the n^th position in the symbol string X

 

 

e.g. if X = ff 0(y₁), then x = φ[ X ] = 2³ · 3³ · 5¹ · 7¹¹ · 11¹⁹ · 13³

then 5 Gl [ 2³ · 3³ · 5¹ · 7¹¹ · 11¹⁹ · 13³ ] = 19 to correspond to:

the operation of obtaining the 5^th symbol of the symbol string ff 0(y₁), which is y₁

where 19 = ψ[ y₁ ].

 

In Gödel’s paper…

This is a function whose value is the number of unique prime factors in x.

e.g. l(2³ · 3³ · 5³ · 7¹) = 4 (there are only four unique prime factors: 2, 3, 5, 7).

 

If x is the Gödel number of the formula X, i.e: x = φ[ X ], then l(x) corresponds to:

the operation of counting the number of individual symbols/variables in the formula X

 

e.g. if X = fff 0, then x = φ[ X ] = 2³ · 3³ · 5¹ · 7¹, then

l(2³ · 3³ · 5¹ · 7¹) = 4 corresponds to:

the operation of counting the number of symbols in fff 0, which is 4.

 

In Gödel’s paper…

This is a function which raises 2 to the power of x, e.g. R(19) = 2¹⁹

So R(x) = φ[ X ]

where x = ψ[ X ] (as given by ψ - the Psi function - the function that assigns a unique number to a symbol X of the formal system), and where X is a single symbol or a variable of the formal system P .

 

 

e.g. if X = (, then x = ψ[ ( ] = 11, and

R(x) = 2¹¹ corresponds to:

the operation of obtaining the Gödel number of the symbol (, which is φ[ ( ] = R(ψ[ ( ]) = 2¹¹

 

In Gödel’s paper…

This function can be thought of as ‘shifting’ up the prime factors of the second number y. It is probably easiest to understand this function by an example.

[ 2³ ] * [ 2³ · 3³ · 5³ · 7¹ ] = 2³ · 3³ · 5³ · 7³ · 11¹

 

And x  *  y = φ[ XY ], where x = φ[ X ] and y = φ[ Y ]

i.e: φ[ X ]  *  φ[ Y ] = φ[ XY ]

 

that is, if x= φ[ X ] and x= φ[ Y ], then the function x  *  y corresponds to:

the operation of concatenating X and Y

where X and Y are symbol strings of the formal system P .

 

e.g. if X = f and Y = fff 0, then x = φ[ X ] = 2³, and y = φ[ Y ] = 2³ · 3³ · 5³ · 7¹

then 2³ * 2³ · 3³ · 5³ · 7¹ = 2³ · 3³ · 5³ · 7³ · 11¹ corresponds to:

the operation of concatenating the symbol strings f and fff 0 to give ffff 0.

 

In Gödel’s paper…

For this function,

0 N x = φ[ X ]

1 N x = φ[ f X ]

2 N x = φ[ ff X ]

…

…

n N x = φ[ fff…ff X ], where there are n occurrences of f

that is, if x = φ[ X ], then the value of n N x corresponds to:

the operation of prefixing n repeated occurrences of the symbol f in front of the symbol string X

 

 

e.g. if X is f 0, and φ[ f 0 ] = 2³ · 3¹

then 3 N (2³ · 3¹) = 2³ · 3³ · 5³ · 7³ · 11¹ corresponds to:

the operation of prefixing f 0 by three instances of f, which gives ffff 0.

 

In Gödel’s paper…

For this function,

Z(n) = n N R(1), and R(1) = 2¹, so

 

Z(n) = n N 2¹= φ[ fff…ff 0 ]

where there are n occurrences of f, since by the Gödel numbering function, 2¹ corresponds to the formal symbol for zero, which is 0. So the value of Z(n) corresponds to:

the operation of prefixing n repeated occurrences of the symbol f in front of the symbol 0

 

e.g. Z(5) = φ[ fffff 0 ] = 2³ · 3³ · 5³ · 7³ · 11³ · 13¹ corresponds to:

the operation of obtaining the Gödel number of fffff 0

 

In Gödel’s paper…

This function can be thought of as multiplying the number x by an ‘initial’ 2¹¹, and ‘shifting’ each of the exponents of the prime factors of the number x up to the next largest prime, and then multiplying the result by a ‘final’ next largest prime with an exponent of 13. The exponent of the ‘initial’ 2 is 11, since 11 is the matching number for the opening bracket (11 = ψ[ ( ]), and the exponent of the ‘final’ prime is 13, since 13 is the matching number for the closing bracket (13 = ψ[ ) ]). It is probably easiest to understand this function by an example:

E(2³ · 3³ · 5³ · 7³ · 11¹) = 2¹¹ · 3³ · 5³ · 7³ · 11³ · 13¹ · 17¹³

In this example 17 is the additional ‘final’ next largest prime (with the exponent of 13).

 

Note that E(x) = φ[ ( X ) ]

where x = φ[ X ], and where X is a symbol string of the formal system P.

 

See Function 8, which gives that

φ[ ( X ) ] = φ[ ( ] * φ[ X ] * φ[ ) ]

that is, if x = φ[ X ] then the value of E(x) corresponds to:

the operation of putting brackets on either side of the symbol string X

 

e.g. if X = ffff 0, and φ[ ffff 0 ] = 2³ · 3³ · 5³ · 7³ · 11¹, then

E(x) = φ[ ( X ) ] = φ[ (ffff 0) ] = 2¹¹ · 3³ · 5³ · 7³ · 11³ · 13 · 17¹³ corresponds to:

the operation of enclosing the symbol string ffff 0 by brackets to give (ffff 0).

 

In Gödel’s paper…

This function can be thought of as multiplying the number x by an ‘initial’ 2⁵ · 3¹¹, and ‘shifting’ each of the exponents of the prime factors of the number x up to the next largest prime, and then multiplying the result by a ‘final’ next largest prime with an exponent of 13. The exponent of the ‘initial’ 2 is 5, since 5 is the matching number for the negation symbol (5 = ψ[ ¬ ]), and the exponent of the ‘initial’ 3 is 11, since 11 is the matching number for the opening bracket (11 = ψ[ ( ]); the exponent of the ‘final’ prime is 13, since 13 is the matching number for the closing bracket (13 = ψ[ ) ]). It is probably easiest to understand this function by an example:

Neg(2³ · 3³ · 5³ · 7³ · 11¹) = 2⁵ · 3¹¹ · 5³ · 7³ · 11³ · 13³ · 17¹ · 19¹³

In this example 19 is the additional ‘final’ next largest prime (with the exponent of 13).

 

And Neg(x) = φ[ ¬(X) ]

where X is a string of symbols of the formal system P, and ¬, ( and ) are symbols of the formal system P.

 

Function 8 above gives that

φ[ ¬ ] * φ[ ( ] * φ[ X ] * φ[ ) ] = φ[ ¬(X) ]

 

that is, if x = φ[ X ] then the value of Neg(x) corresponds to:

the operation of putting the symbol ¬ in front of the symbol string X

i.e: creating the negation of the formula X

 

e.g. if X = ffff 0, and φ[ ffff 0 ] = 2³ · 3³ · 5³ · 7³ · 11¹

then Neg(x) = φ[ ¬(ffff 0) ] = 2⁵ · 3¹¹ · 5³ · 7³ · 11³ · 13³ · 17¹ · 19¹³ corresponds to:

the operation of enclosing the symbol string ffff 0 by brackets and prefixing that by the negation symbol to give ¬(ffff 0).

 

In Gödel’s paper…

For this function,

x Dis y = φ[ (X) ∨ (Y) ]

where X and Y are symbol strings of the formal system P, and ∨ is a symbol of the formal system P.

 

Function 8 above gives that

φ[ ( ] * φ[ X ] * φ[ ) ] * φ[ ∨ ] * φ[ ( ] * φ[ Y ] * φ[ ) ] = φ[ (X) ∨ (Y) ]

 

that is, if x = φ[ X ] and y = φ[ Y ], then the value of x Dis y corresponds to:

the operation of concatenating the symbol string (X), the symbol ∨, and the symbol string (Y).

i.e: creating a formula by joining two formulas by the ‘or’ symbol ∨

 

e.g. if X = f 0, and φ[ f 0 ] = 2³ · 3¹, and Y = ff 0, and φ[ ff 0 ] = 2³ · 3³ · 5¹, then

x Dis y = φ[ (f 0) ∨ (ff 0) ] = 2¹¹ · 3³ · 5¹ · 7¹³ · 11⁷ · 13¹¹ · 17³ · 19³ · 23¹ · 29¹³ corresponds to:

the operation of enclosing the symbol strings f 0 and ff 0 by brackets and interposing the symbol ∨ between them to give (f 0) ∨ (ff 0).

 

In Gödel’s paper…

For this function,

x Gen y = φ[ X ∀ (Y) ]

where X and Y are symbol strings of the formal system P, and ∀ is a symbol of the formal system P.

 

Function 8 above gives that

φ[ X ] * φ[ ∀ ] * φ[ ( ] * φ[ Y ] * φ[ ) ] = φ[ X ∀ (Y) ]

 

that is, if x = φ[ X ] and y = φ[ Y ], then the value of x Gen y corresponds to:

the operation of concatenating the symbol string X, the symbol ∀, and the symbol string (Y).

i.e: creating the generalization of a formula by prefixing it with a variable and the ‘For all’ symbol (though note that in this function X is not restricted to being a variable - it can be any symbol string of the system P; the definition of what constitutes a variable is given by Relation 12) .

 

e.g. if X is a type 1 variable, and x = φ[ z₁ ], and Y is some formula, where y = φ[ Y ], then

x Gen y = 2²³ · 3⁹ · …    = 2^{ψ[ z₁ ]} · 3^{ψ[ ∀ ]} · … corresponds to:

the operation of bracketing the formula Y and prefixing it by z₁∀

 

In Gödel’s paper…

This is a relation, which asserts that x = pⁿ, where p is a prime number greater than 13.

e.g. the relation 1 Var 17 applies; 2 Var 23² applies; 2 Var 19 does not apply (since the exponent of 19 is not 2).

 

The relation n Var x is an assertion regarding natural numbers n and x, and corresponds to the assertion:

the symbol string X is a type n variable of the formal system P

where x = ψ[ X ].

 

Note that n Var x defines a correspondence to a variable of the formal system by the use of the ψ function rather than using the φ function directly. The n defines the type of the corresponding variable X.

 

e.g. if X is the variable x₃ of the formal system, and ψ[ x₃ ] = 17

then 3 Var 17³ corresponds to:

the assertion that the symbol string x₃ is a type 3 variable.

 

In Gödel’s paper…

This is a relation whose definition follows directly from the previous relation (n Var x), i.e: it asserts that x = pⁿ, where p is a prime number greater than 13, and n > 0.

 

The relation Var(x) is an assertion regarding a natural number x, and corresponds to the assertion:

the symbol string X is a variable of the formal system P

where x = ψ[ X ].

 

Similar to the definition for n Var x. Var(x) also defines a correspondence to a variable of the formal system by the use of the ψ function.

 

e.g. if X is the variable y₂ of the formal system, and ψ[ y₂ ] = 19², then Var 19² corresponds to:

the assertion that the symbol string y₂ is a variable of the formal system P.

 

In Gödel’s paper…

Typ₁′(x) is not used anywhere else, its only role is in the definition of the relation Typ_n(x).

Typ_n(x) asserts that either x = 2³ · 3³ · … · p^q, or x = 2^pn, where p, q and n must satisfy certain conditions.

 

Typ₁′(x) asserts that either:

x = 2³ · 3³ · … · p¹, where p is some prime number; this corresponds to:

X is a symbol string of the form 0, f 0, ff 0, fff 0, …,

where x = φ[ X ].

or

x = 2³ · 3³ · … · p^q, where p is some prime number and q is some prime number greater than 13; this corresponds to:

X is a symbol string of the form x₁, f x₁, ff x₁, fff x₁, …, or y₁, f y₁, ff y₁, fff y₁, …, etc,

where x = φ[ X ].

 

For Typ_n(x), for the case when n = 1, the case is simply

Typ₁(x) = Typ₁′(x)

 

when n > 1, Typ_n(x) asserts that:

x = 2^pn, or x = (2^p)ⁿ, where p is some prime number greater than 13; this corresponds to:

X is a string of type n (which is the same as a variable of type n)

where x = φ[ X ].

See Type n string definition for the definition of a type n string/variable.

 

So, Typ_n(x) is an assertion regarding a natural number x, and corresponds to the assertion:

the symbol string X is a type n string of the formal system P

where x = φ[ X ].

 

In Gödel’s paper…

Elf(x) is a relation that corresponds to the assertion:

the symbol string X is an elementary formula of the formal system P.

where x = φ[ X ]. See elementary formula.

 

Op(x, y, z) is a relation that corresponds to the assertion:

the symbol string X of the formal system P is of the form

¬(Y), or

(Y) ∨ (Z), or

x∀(X),

where x = φ[ X ], y = φ[ Y ] and z = φ[ Z ] and Y and Z are symbol strings of the formal system P.

See the formulas following the section elementary formula.

 

FR(x) is a relation which asserts that:

 

 

Form(x) is a relation which asserts that:

the symbol string X is a formula of the formal system P

where x = φ[ X ], and x is the exponent of the largest prime p in a number n, where:

 

x = 2^{φ[ Y₁ ]} · 3^{φ[ Y₂ ]} · 5^{φ[ Y₃ ]} · … p^{φ[ Y_m ]}

 

See Formula definition for definition of a formula of the system P.

 

In Gödel’s paper…