FOM: Canonical codings

[Stephen Fenner]

Joe,

On Mon, 3 Sep 2001 JoeShipman at aol.com wrote:

> Godelnumber:{eventually-zero infinite sequences of non-negative integers}-->
> {positive integers}
> Godelnumber((x1,x2,x3,...,x_n,0,0,0,0,.....))=(p1^x1)*(p2^x2)*...*(p_n^x_n)
> where p1,p2,... is the sequence of primes 2,3,5,...
>
> ...
>
> OPair:{ordered pairs of non-negative integers}-->non-negative integers
> OPair((x,y))=x + (x+y)(x+y+1)/2
> This counts pairs
> (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0),(0,4),...
>

Because (0,0) = 0, you can get Godelnumber from OPair in a reasonably
cononical way:

(x1,x2,x3,...,xn,0,0,0,0,...) = (x1,(x2,(x3,(...,(xn,0)))))

Actually, this gives you a bijection

(eventually-zero infinite sequences of nonnegative integers) <-->
(nonnegative integers)

provided we make one minor adjustment: define

OPair(x,y) = y + (x+y)(x+y+1)/2

This works for any pairing function where

     OPair(x,y) > 0 ==> OPair(x,y) > y

for all nonnegative integers x,y.

To code all finite sequences of nonnegative integers, identify

0 = []   (the empty sequence)

and

[x1,...,xn] = 1 + (n-1,(x1,(x2,...,(x{n-1},xn))))

This seems canonical to me, but maybe I've been programming in Lisp too
long.


BTW - Does anyone know if (eventually-zero infinite sequence of
nonnegative integers) has a name?  I've been calling these things
"omega tuples" in my classes.

Steve