From: holmes@garnet.idbsu.edu (Randall Holmes)
Subject: Re: Impredicativity - was: Russell's Paradox
Organization: Boise State University
Date: Thu, 5 Nov 1992 16:42:51 GMT

In article <1992Nov4.073717.22625@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>In article <Bx693z.H37@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>>Indeed, ZF intrinsically suggests it
>>*without* the bother of a foundation axiom, by limiting the set formation
>>possibilities so that self-membership is at least not immediately achieved
>
>What is the reasoning here?  That a theory T "intrinsically suggests"
>not-P for any P not in T?  If neither P nor not-P are in T, which of
>not-P or not-not-P (= P) does T "intrinsically suggest?"
>
>>The slick form of AF, that every nonempty set has a member disjoint from it,
>
>Where is this form given?  And why doesn't it rule out Omega = {Omega}?
>(Just asking, I'm not expert on this stuff.)

Thomas Jech, _Set Theory_, first page.  It does rule out Omega =
{Omega}; it is a form of the axiom of foundation (AF, not AFA).

>
>>But I'm open on well-foundedness: for all I know, there may well be sets like
>>A = { 1 , { 2 , { 3 , { 4 , {.....}}}}} . Such a set seems very well defined on
>>the face of it, so it *could* exist, for all I know. No self-membership there.
>>
>>REQUEST: If someone can produce a way of getting a self-membered set from the
>>set A above, using the other ZF constructions, I would *love* to see it !!!!
>
>If you are comfortable with A, you should not mind
>B = { 1 , { 1 , { 1 , { 1 , {.....}}}}} .
>
>But by AFA, B = {1, B}, making B a member of itself.

This uses a very strong extensionality property which follows from
AFA; there is no reason why there cannot be a sequence of distinct
sets xi such that xi = {1,x[i+1]} in ZFC without Foundation.  Of
course, this makes the symbol above ambiguous (the original expression
with 1,2,3,4... also fails to specify a unique set in ZFC- -- there
could be many such sets).

>
>As soon as you weaken FA to AFA, the possibility of self-membership
>arises.

You do not "weaken" FA to AFA; ZFC- + FA and ZFC- + AFA are both
stronger than ZFC-, but neither is stronger than the other.

>
>>That is another reason I went to the trouble of posting my first article; it
>>seems to me to make a very clear criterion for locating the essential
>>impredicativity of Russell, which shows up most clearly in the *set* form:
>>                 { x | P(x) }  ,
>>the essential impredicativity comes from the bad range of x, not the form of P.
>>
>>Doesn't *anyone* else think so ?   :-(
>
>I do.  But I forgot to say in my earlier message that the main point of
>my positive reformulation of Russell's paradox was to remove this
>impredicativity from the argument.  Witness Y was constructed as the
>set of all *elements of X* not members of themselves.  This established
>a positive result without any impredicativity.  Russell's theorem is
>not so much a corollary of this theorem as an interpretation of it, in
>that "there is no set of all sets" formalizes as "every set is
>nonuniversal", or "every set has a nonmember".
>
>>That's partly why I don't think that Aczel's
>>set theory is really basic, delightful though it is. It can't look like
>>fundamental set theory if a convincing show of consistency has to route
>>through ZF's consistency.

It doesn't; its consistency can be proven in ZFC- (or ZF-) (just like
that of full ZFC).  Foundation or the lack thereof has nothing to do
with consistency strength.

>
>ZF+FA is even stronger than ZF+AFA.  So by that reasoning ZF+FA can't
>look like like a fundamental set theory either.  Yet you seem to prefer
>ZF+FA to ZF+AFA.

No, it isn't.  They have exactly the same strength (and both describe
hierarchically structured universes).

>
>>I hope you are taking your own rubbishing
>>(concerning Z vs ZF) like a man !  It's a tough life on the net !
>
>Being mistaken at the top of your voice does have its drawbacks.
>Yesterday definitely wasn't my day, I got something really wrong on
>sci.math involving measure theory, much more wrong than Z vs. ZF, which
>I maintain is a highly debatable matter, the near-universal acceptance
>of the cumulative hierarchy as a model of ZF notwithstanding.
>-- 
>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.			|     holmes@opal.idbsu.edu
Newsgroups: sci.logic,alt.uu.future