Jon Awbrey jawbrey at att.net
Thu Jul 31 10:04:13 EDT 2014

Re: Tim Chow
At: http://www.cs.nyu.edu/pipermail/fom/2014-July/018053.html

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 S to integers, either non-negatives N or 
positives M, 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 between positive integers M and finite partial functions 
from M to M.  All of this comes straight out of the primes factorizations.  That type of bijection 
may remind some people of Dana Scott's D_∞.  Corresponding to the positive integers there arose two 
species of graphical structures, which I dubbed "riffs" and "rotes".  See these links for more info:



oeiswiki: http://www.oeis.org/wiki/User:Jon_Awbrey

More information about the FOM mailing list