🚀 go-pugleaf

In article <Bx81Ho.9HL@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>Randall Holmes - a question.  You say that it is a *theorem* of ZF that
>
>   "for any set x, for some ordinal a, x E V(a)" .
>
>[where V(a) is defined by  V(0) = {}
>                           V(a+1) = P{V{a}}
>                           V(L) = U{a < L}[V(a)] (L a limit ordinal). ]
>
>Is this really true ? Surely not. The collection of V's is a model for ZF, yes.
>But the above isn't a theorem, is it? 
>I expect it *is* a theorem of ZF+AxFndtn.

I'm sure that's what Randall meant.  You can't rank sets without FA.
If you weaken FA to AFA you have counterexamples to the above like
Omega = {Omega}, to which the above definition cannot assign any
ordinal in a way that satisfies these equations.  (Consider the least
ordinal a for which Omega E V{a}.  Clearly a is not 0.  Since Omega has
only one element a cannot be a limit ordinal.  So a is a successor
ordinal, call it b+1.  But then Omega is a subset of V{b}, whence
Omega's only element, Omega, is an element of V{b} and hence of rank
less than a, contradiction.)

Conversely, once you have FA you can prove the above theorem by
assigning a rank to each set by the following informally described
procedure.  To rank set x, assign ranks to its elements.  This
recursive procedure is well-defined because there are no infinite
descending membership chains.  Now take the rank of x to be the least
ordinal strictly greater than the rank of any element of x.  This rank
will be 0 when x is empty, a successor ordinal when x contains an
element of rank maximal among its siblings, and otherwise a limit
ordinal.

This informal procedure can be made rigorous as follows.  The form of
FA that I find most useful for these purposes is the Axiom Schema of
Restriction, namely one axiom for every ZF formula phi(x) with one free
variable x.  The axiom says that either phi holds of no set, or there
exists a set y for which phi holds of y but of none of its members.

So now take phi(x) to be "for every ordinal a, x is not in V(a)".  If
phi holds of no set we are done.  Otherwise by restriction there is a
set y for which phi(y) holds but for all members z of y, phi(z) is
false.  If y is empty this contradicts the first equation defining V.
If y is nonempty then all its members have ranks.  If there is a
maximum rank b of those members then y is a subset of V(b), hence an
element of V(b+1) by the second equation.  If there is no maximum rank
then let b be the union of these ranks, necessarily a limit ordinal.
Then y is an element of V(b) by the third equation, and we are done.
(And hence of course phi holds of no sets.)
-- 
Vaughan Pratt				There's no truth in logic, son.