NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/sci/logic/1925

Text File | 1992-11-05 | 4.9 KB | 103 lines

Newsgroups: sci.logic
Path: sparky!uunet!pmafire!mica.inel.gov!guinness!garnet.idbsu.edu!holmes
From: [e-mail] (Randall Holmes)
Subject: Re: Impredicativity - was: Russell's Paradox
Message-ID: <[e-mail]>
Sender: [e-mail] (Usenet News mail)
Nntp-Posting-Host: garnet
Organization: Boise State University
References: <[e-mail]> <[e-mail]>
Date: Thu, 5 Nov 1992 16:57:54 GMT
Lines: 90

In article <[e-mail]> [e-mail] (Vaughan R. Pratt) writes:
>In article <[e-mail]> [e-mail] (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.

I meant exactly what I said.  Foundation is an axiom of ZF.  The
system without Foundation is called ZF-.

  You can't rank sets without FA.

This is true (you can't rank sets in ZFC-).  But you _can_ rank sets
in ZFC- + AFA; you just do it differently.  See below.

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

Here is the informal procedure for ranking sets in AFA.  Rank 0 has
one member, the empty set.  (You need something to start the process).
Once rank a is constructed, rank a+1 consists of all sets A such that
the relation E|TC(A) (membership restricted to the transitive closure
of A) is isomorphic to a graph whose nodes are all of rank a.  The
isomorphism type of E|TC(A) determines A exactly under AFA.  Take
unions of ranks at limit ordinals.  Call rank a H(a).  It is easy to
prove that H(a) and V(a) (the well founded sets of rank a in the usual
sense) have the same cardinality and that H(a) includes V(a) (this is
only for infinite ordinals a; the finite ranks do look different).
This shows that ZFC- + AFA is _not_ significantly different from ZFC;
its universe has the same hierarchical structure, and not very many
sets are added at each level of the hierarchy.

There are ways to destroy the hierarchical structure of the universe
in fragments of ZFC, but you must jettison both Choice and Foundation,
and perhaps add some atoms, in order to do so.  AFA has the same
hierarchy bulding potential as FA, because of its "strong
extensionality" consequences.


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


--
The opinions expressed        |     --Sincerely,
above are not the "official"    |     M. Randall Holmes
opinions of any person        |     Math. Dept., Boise State Univ.
or institution.            |     [e-mail]