Re: Timothy Chow • Shifting Paradigms?

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 $S$ to integers, either non-negatives $\mathbb{N}$ or positives $\mathbb{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 one between positive integers $\mathbb{M}$ and finite partial functions from $\mathbb{M}$ to $\mathbb{M}.$  All of this comes straight out of the primes factorizations.  That type of bijection may remind some people of Dana Scott’s $D_\infty.$  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)

Jon Awbrey

An interesting tangent to the main subject, but one that I had some ready thoughts on.

This site uses Akismet to reduce spam. Learn how your comment data is processed.