# FOM: well-founded extensional relations

holmes@catseye.idbsu.edu holmes at catseye.idbsu.edu
Wed Jun 14 10:22:42 EDT 2000

Dear Allen  (cc FOM list, re an error in my comments on representing
set theory in the theory of well-founded extensional relations):

You wrote:

>    Was "union" in the last sentence just a typo for "replacement" (and was
>I just being stupid to be confused by it?)?

You are right.  Take any set of sets, represented as a graph, and drop
the second tier of nodes of the graph, connecting each to the old top
node, and one obtains the union.  So union is not a problem -- it
really does come for free.  Replacement is the axiom for which you
need regularity of the cardinality of the underlying universe of
objects.

It all comes of writing things down off the top of one's head.

Just for the record:

represent sets by equivalence classes of well-founded extensional
relations with top on a universe of objects which have domain smaller
than the universe of objects

extensionality
foundation
union
separation

By assuming that there is a well-ordering of the universe of objects
one gets

choice

Axioms one gets with the assumption that the universe of objects is infinite
(the arguments I have in mind for these use choice, which is why it appears
above):

pairing
infinity

Axiom one gets with the assumption that the cardinality of the
universe is regular (not the sum of a smaller number of smaller
cardinals) (choice used):

replacement

Axiom one gets with the assumption that the cardinality of the universe
is strong limit:

power set

If the underlying theory is just second-order logic, it takes a little
care to express the claims about the cardinality of the universe, but
they all can in fact be expressed.

If one didn't restrict oneself to relations smaller than the universe,
then the picture would be different.  Power Set would be false and
Replacement would follow as soon as choice and infinity were assumed.

Actually, one gets more than ZFC.  One gets an interpretation of
Morse-Kelley; proper classes can be represented by "large"
well-founded extensional relations (graphs the size of the universe
whose "elements" are smaller than the universe), and quantification
over proper classes can be used in the intepreted set theory in
instances of separation, replacement, and class comprehension.

I don't think any of this is terribly original.  I know about it because
it is the standard technique for attempting to interpret ZFC in NF and
related theories.

And God posted an angel with a flaming sword at | Sincerely, M. Randall Holmes
the gates of Cantor's paradise, that the       | Boise State U. (disavows all)
slow-witted and the deliberately obtuse might | holmes at math.boisestate.edu
not glimpse the wonders therein. | http://math.boisestate.edu/~holmes