FOM: well-founded extensional relations

Stephen G Simpson simpson at
Wed Jun 14 15:06:13 EDT 2000

holmes at writes:

 > interpreting Zermelo-style set theory using well-founded
 > extensional relations in a general context; I would be interested
 > to hear if anyone knows about the history of this idea.

This idea is fundamental in the study of (subsystems of) second order
arithmetic, descriptive set theory, etc.  In such a context,
hereditarily countable sets are encoded as well founded binary
relations on the natural numbers.  A refined version of this appears
in Section VII.3 of my book ``Subsystems of Second Order Arithmetic''
(Springer, 1999).  The title of the section is ``A Set-Theoretic
Interpretation of ATR0''.

I have not tried to trace the history of this idea, but I know that
the Mostowski school in Poland, as early as the 1950's perhaps, was
using it to interpret subsystems of set theory into second order
arithmetic.  One of the results is that Z_2 and ZFC - powerset are
mutually interpretable.  Cf also the Mostowski collapsing lemma.  An
even earlier reference is the footnote in G"odel's 1939 monograph on
the continuum hypothesis, where G"odel points out that under V=L there
is a projective well ordering of the reals.  This is proved by
encoding constructibly countable initial segments of the constructible

-- Steve

More information about the FOM mailing list