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

Vaughan Pratt pratt at cs.stanford.edu
Wed Apr 30 04:07:23 EDT 2008

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.)
>