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

[Vaughan Pratt]

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