2014 Jul 31

I can’t remember when I first started playing with Gödel codings of graph-theoretic structures, which arose in logical and computational settings, but I remember being egged on in that direction by Martin Gardner’s 1976 column on Catalan numbers, planted plane trees, polygon dissections, etc.  Codings being injections from a combinatorial species to integers, either non-negatives or positives I was especially interested in codings that were also surjective, thereby revealing something about the target domain of arithmetic.

The most interesting bijection I found was one between positive integers and finite partial functions from to   All of this comes straight out of the primes factorizations.  That type of bijection may remind some people of Dana Scott’s   Corresponding to the positive integers there arose two species of graphical structures, which I dubbed “riffs” and “rotes”.  See these links for more info:

The On-Line Encyclopedia of Integer Sequences (OEIS)

• Riffs & Rotes
• A061396
• A111788

Jon Awbrey