- T*(x,x),
- if T(x,y) then T*(x,y),
- and if T*(x,y) and T*(y,z) then T*(x,z).

In this note I will show how to implement T*(x,y) in the language of arithmetic.

Any nonempty finite sequence of natural numbers a_{n} ...
a_{2} a_{1} a_{0} can be encoded as a single number t,
namely by selecting a number p that is larger than all of them and
regarding a_{n}...a_{2}a_{1}a_{0}
to be the p-ary representation of t. The sequence 3 5 7 0 1 for
instance could be encoded by the number 35701, if one selects p to be 10.
The number t is calculated by the formula t = _{i=0}^{n} a_{i} p^{i}.
The sequence 3 5 13 0 1 can not be encoded in base 10 however.
For this sequence one needs to choose p larger than 13. In general the
choice of p depends on the sequence, so the sequence is encoded not
just by t, but really by the pair (t,p).

This encoding is not unique however. The pair (35701,10) for instance
is the encoding of the sequence 3 5 7 0 1, but it is also the encoding
of the sequence 0 3 5 7 0 1. Because uniqueness is important here, I
choose (35701,10) to be the encoding of the sequence 3 5 7 0 1 only,
i.e. I only encode sequences a_{n} ...
a_{2} a_{1} a_{0} with a_{n} > 0.
Now a pair (0,p) does not encode a sequence, but any pair (t,p) with t
> 0 does.

Write Last(t,p,y) if y is the last number in the sequence encoded by t
and p, i.e. if y = a_{0}. The formula Last(t,p,y) can be
expressed arithmetically as

y < p r (t = rp+y).

Write First(t,p,x) if x is the first number in the sequence encoded by t and p, i.e. if x = a
0 < x < p n s
(t = xp^{n}+s s < p^{n}).

u < p v < p
i
r
s
(t = rp^{i+2}+up^{i+1}+vp^{i}+s
s < p^{i}
r+u > 0).

Now the reflexive and transitive closure T*(x,y) of a formula T(x,y) with free variables x and y can almost be defined by

t p (First(t,p,x) Last(t,p,y) (Neighbours(t,p,u,v) T(u,v)).

This formula says that there is a sequence at p (First(t,p,x+1) Last(t,p,y+1) (Neighbours(t,p,u+1,v+1) T(u,v)).

The construction above generalizes easily from relations between numbers to relations between vectors of numbers. I will illustrate this for vectors of length 3, but the number 3 plays no special role here. The case of length 3 is what I need in my proof of Goedel's incompleteness theorem.

Let T(x_{1},x_{2},x_{3},y_{1},y_{2},y_{3})
be an arithmetical formula with six free variables x_{1},
x_{2}, x_{3}, y_{1}, y_{2} and y_{3}.
Its *reflexive and transitive closure*
T*(x_{1},x_{2},x_{3},y_{1},y_{2},y_{3})
is the smallest predicate satisfying

- T*(x
_{1},x_{2},x_{3},x_{1},x_{2},x_{3}), - if T(x
_{1},x_{2},x_{3},y_{1},y_{2},y_{3}) then T*(x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}), - and if
T*(x
_{1},x_{2},x_{3},y_{1},y_{2},y_{3}) and T*(y_{1},y_{2},y_{3},z_{1},z_{2},z_{3}) then T*(x_{1},x_{2},x_{3},z_{1},z_{2},z_{3}).

Next I will show how to implement T*(x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}) in the language of arithmetic.

Three equally long nonempty finite sequences of natural numbers
a_{n} ... a_{2} a_{1} a_{0} and
b_{n} ... b_{2} b_{1} b_{0} and
c_{n} ... c_{2} c_{1} c_{0}
can be encoded by three numbers t_{1}, t_{2} and
t_{3}, namely by selecting a number p that is larger than all
numbers in the three sequences and
regarding a_{n}...a_{2}a_{1}a_{0}
to be the p-ary representation of t_{1}, and
b_{n}...b_{2}b_{1}b_{0}
to be the p-ary representation of t_{2}, and
c_{n}...c_{2}c_{1}c_{0}
to be the p-ary representation of t_{3}.
The triple of sequences is thus encoded by the quadruple
(t_{1},t_{2},t_{3},p).

In order to make the encoding unique, I only encode sequences in which
a_{n} > 0 and b_{n} > 0 and c_{n} > 0.

Write Last(t_{1},t_{2},t_{3},p,y_{1},y_{2},y_{3}) if
y_{1}, y_{2} and y_{3} are the last numbers in
the sequences, i.e. if (y_{1},y_{2},y_{3}) =
(a_{0},b_{0},c_{0}). The formula
Last(t_{1},t_{2},t_{3},p,y_{1},y_{2},y_{3}) can be expressed
arithmetically as

y_{1} < p
r_{1} (t_{1}=r_{1}p+y_{1})
y_{2} < p
r_{2} (t_{2} = r_{2}p+y_{2})
y_{3} < p
r_{3} (t_{3} = r_{3}p+y_{3}).

0 < x_{1} < p
0 < x_{2} < p
0 < x_{3} < p
n (
s_{1}
(t_{1} = x_{1}p^{n}+s_{1}
s_{1} < p^{n})
s_{2}
(t_{2} = x_{2}p^{n}+s_{2}
s_{2} < p^{n})
s_{3}
(t_{3} = x_{3}p^{n}+s_{3}
s_{3} < p^{n})
).

u_{1} < p u_{2} < p u_{3} < p
v_{1} < p v_{2} < p v_{3} < p

i (
r_{1}
s_{1}
(t_{1}=r_{1}p^{i+2}+u_{1}p^{i+1}+v_{1}p^{i}+s_{1}
s_{1} < p^{i}
r_{1}+u_{1} > 0)

r_{2}
s_{2}
(t_{2} = r_{2}p^{i+2}+u_{2}p^{i+1}+v_{2}p^{i}+s_{2}
s_{2} < p^{i}
r_{2}+u_{2} > 0)

r_{3}
s_{3}
(t_{3} = r_{3}p^{i+2}+u_{3}p^{i+1}+v_{3}p^{i}+s_{3}
s_{3} < p^{i}
r_{3}+u_{3} > 0)
).

t_{1}
t_{2}
t_{3}
p
(First(t_{1},t_{2},t_{3},p,x_{1}+1,x_{2}+1,x_{3}+1) Last(t_{1},t_{2},t_{3},p,y_{1}+1,y_{2}+1,y_{3}+1)
(Neighbours(t_{1},t_{2},t_{3},p,u_{1}+1,u_{2}+1,u_{3}+1,v_{1}+1,v_{2}+1,v_{3}+1)
T(u_{1},u_{2},u_{3},v_{1},v_{2},v_{3})).

If arithmetic would be defined so as to contain exponentiation, the above implementation would be complete (considering that a < b can be rewritten as k: a+1+k = b).

However, arithmetic only features 0,1,+,x and =. The reason that
exponentiation is not included in the definition of arithmetic, is that
it doesn't add to the expressiveness of the language: the formula
x = y^{n} is expressible in exponentiation-free arithmetic:
Let E(i,u,y,j,v,y') be the formula

i = j+1 u = vy y' = y

then x = y
"p is prime"
n (q = p^{n})

d ( d 1 k (q = kd) k (d = kp) )

which says that for any divisor d of q with d 1, p must be a divisor of d. This implies that p is a prime divisor of q and q has no other prime divisors than p.The only requirement on the number p in the implementation of reflexive and transitive closure above, is that it is sufficiently large. No generality is lost if one requires p to be prime. Now the formula First(t,p,x) can be reformulated as

0 < x < p
q
("p is prime"
n (q = p^{n})
s
(t = xq+s s < q)).

u < p v < p
q
("p is prime"
i (q = p^{i})
r
s
(t = rqpp+uqp+vq+s
s < q
r+u > 0)).

Rob van Glabbeek | rvg@cs.stanford.edu |