[FOM] Plea for literature on recursion theory in V_\omega

[Paul Tarau]

The following papers discuss the Ackermann encoding from Hereditarily
Finite Sets to Natural Numbers, as well as a few other things, ranging
from "hereditarily finite functions" to encodings for graphs,
hypergraphs, BDDs, Church numerals, Von Neumann ordinals, etc. and
their connection to pairing/unpairing functions:

http://logic.csci.unt.edu/tarau/research/2008/tarau_hfs.pdf
http://logic.csci.unt.edu/tarau/research/2008/tarau_shape_shifting.pdf

They contain links to the actual Haskell code running all the
examples. Given the focus on an "executable set theory" most things
stay within HFS, except that Haskell's lazy evaluation is sometime
used to generate infinite streams of of various objects that have
bijective encodings to Natural Numbers.

Paul Tarau

P.S. There are also some nice pictures of Hereditarily Finite Sets and
their friends in the papers :-)

On Wed, Apr 30, 2008 at 3:07 AM, Vaughan Pratt <pratt at cs.stanford.edu> wrote:
> Natural numbers and hereditarily finite sets are equally well encoded as
>  finite length bit strings starting with 1 (i.e. zero-suppressed).  Each
>  such string represents in the former case the sum of 2^i over all bit
>  positions i containing 1, and in the latter case the set containing the
>  i-th hereditarily finite set when the i-th bit position contains 1,
>  starting with the empty set as the zeroth hereditarily finite set and
>  taking the rightmost bit to be in position zero as usual.  The i-th
>  hereditarily finite set in the latter encoding is the one encoded by the
>  binary numeral for i in the former encoding.  Since i < 2^i, this
>  encoding is well-defined.
>
>  The hereditarily finite sets from 0 through 8 = 1000 are (in order) {},
>  {{}}, {{{}}}, {{},{{}}}, {{{{}}}}, {{},{{{}}}}, {{{}},{{{}}}},
>  {{},{{}},{{{}}}}, and {{{{{}}}}}.  (So the sets containing the empty set
>  are exactly the odd-numbered ones, those containing {{}} are congruent
>  to 2 or 3 mod 4, and so on.)  These differ from the finite von Neumann
>  ordinals, which are also hereditarily finite, in that every hereditarily
>  finite set appears.
>
>  When necessary the usual convention of writing 0 for the empty string
>  can be followed in both encodings; in the former the empty string
>  denotes zero and in the latter the empty set.
>
>  There being no particular advantage of other alphabets over {0,1}, from
>  an effectiveness standpoint it makes no difference whether you claim to
>  be using Goedel numbers or Goedel sets since in both cases they can
>  reasonably be assumed to be bit strings in the implementation, and may
>  as well be the same bit strings at that.
>
>  Sorry I don't have any references for this encoding, but it's easily
>  derived from e.g. Wikipedia's treatment of hereditarily finite sets at
>  http://en.wikipedia.org/wiki/Hereditarily_finite_set (to pick a very
>  accessible example).
>
>  What notations exist for the hereditarily countable sets?  I don't see
>  an obvious extension of the above.
>
>  Vaughan Pratt
>
>
>
>
>  Csaba Henk wrote:
>  > Dear FOM members,
>  >
>  > I am to write my PhD thesis. I plan to base my "design" on recursion
>  > theory built up in V_\omega (ie., the universe of hereditarily finite
>  > sets [as a first-order structure with the language of set theory]).
>  >
>  > All textbooks I know of use an arithmetic context for explaining
>  > recursion theory. I'd like to ask: do you know of some book which uses
>  > V_\omega for this purpose? Or any book which discusses the well-known
>  > semantic equivalence (yes, this is a vague term, but you should know
>  > what I mean...) of <\omega, + , *> and <V_\omega, \epsilon> ?
>  >
>  > (I know this is a well explored area, but I don't know how much of this
>  > remained "folklore"... My focus is on finding nicely worded definitions
>  > and theorems which I can use as references for my original work.)
>  >
>  > Thanks for your suggestions!
>  >
>  > Regards,
>  > Csaba
>  > _______________________________________________
>  > FOM mailing list
>  > FOM at cs.nyu.edu
>  > http://www.cs.nyu.edu/mailman/listinfo/fom
>  _______________________________________________
>  FOM mailing list
>  FOM at cs.nyu.edu
>  http://www.cs.nyu.edu/mailman/listinfo/fom
>