Rote Arithmetic

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

[Archive Copy]

Subj:  Rote Arithmetic
Date:  Thu, 19 Sep 2002 22:14:42 -0400
From:  Jon Awbrey <[email protected]> [now at [email protected]]
  To:  SeqFan <[email protected]>

Residual Questions ...

Here is how I last defined rotes:

JA: | @ is a rote.
    |
    | If f is a finite function from rotes to rotes,
    | say, f : index_j ~> exponent_j for j = 1 to k,
    | where the "indices" and "exponents" are rotes,
    | then the following tree is a rote:
    |
    |  i_1  e_1  i_k  e_k
    |   o----o    o----o
    |    \  ...  /
    |     \  |  /
    |      \ | /
    |       \|/
    |        @
    |
    | where the rotes for the "indices" (source elements) i_j
    | and the "exponents" (target elemnts) e_j are attached
    | at the places indicated.

Strictly speaking, I probably should have stipulated that
each f is a "finite partial function" from rotes to rotes,
but since the set of rotes is infinite the partiality of f
might be taken as implicit in the fact of its being finite.

Let $N$ ("Script N") be the set of rotes.

Let (X -> Y) be the set of functions from X to Y.

Let [X -> Y] be the set of finite partial functions from X to Y.

Then we have the isomorphism $N$ ~=~ [$N$ -> $N$],
that is, every rote k : $N$ is uniquely analyzed
as a finite partial function k : $N$ -> $N$, and
every such function gets a unique gödel number
in $N$.  Notice the polymorphism of types.

1 = {} = the empty function

2 = (p_1)^1 = {<1, 1>}

3 = (p_2)^1 = {<2, 1>}

4 = (p_1)^2 = {<1, 2>}

5 = (p_3)^1 = {<3, 1>}

6 = (p_1)^1 (p_2)^1 = {<1, 1>, <2, 1>}

As rooted trees, these look like this:

                                        o--o
                                        |
                    o--o         o--o   o--o          o-o
                    |            |      |            /
          o--o      o--o      o--o      o--o    o-o o-o
          |         |         |         |        \ /
@         @         @         @         @         @

1         2         3         4         5         6

Anyway, I think this is right, but I've learned not
to trust stuff like this until several other people
have a chance to go over it.

Jon Awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o