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

Internet Message Format | 1992-11-06 | 5.7 KB

Path: sparky!uunet!destroyer!ncar!noao!arizona!gudeman
From: [e-mail] (David Gudeman)
Newsgroups: sci.logic
Subject: Re: Impredicativity - was: Russell's Paradox
Message-ID: <[e-mail]>
Date: 5 Nov 92 21:05:17 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 122

In article  <[e-mail]> Bill Taylor writes:
]He also suggests my views may be due to "an accident of culture", by which
]he probably means a form of Zermelist indoctrination.  ;-)

I'd like to suggest that the primary intuitive notions that people
have of sets is as a physical collection of some sort.  Such a notion
would rule out self-membership.  In fact, the iterative hierarchy
seems to accurately reflect this notion, and if I were content to view
sets as "collections of objects", then I would have no problem with
ZF.  However, if you take a more general notion of what a set is,
namely that it is the extension of a property, then I don't see how
you can avoid the notion of sets that contain themselves.

Even so, I acknowledge that there are problems with this view.  For
example, the simple notion of extensionality

  x = y <=> (Forall z E x . Exist w E y . z = w)

is no longer sufficient to tell whether two sets are equal.  This can
be seen by examining the following pairs of sets and trying to decide
whether the two sets are equal or not:

  S1 = {{},S1}, S2 = {{},S2}

  S1 = {{},S1}, S2 = {{},S1}

  S1 = {{},S2}, S2 = {{},S1}

(this is no doubt familiar to many people familiar with the issues of
abstract data structures).  The problem is, of course, that
equivalence is being defined recursively and the definition is not
well-founded when sets can be members of themselves.  (It _is_
well-founded if the sets are all well-founded).

]As I say, my immediate thoughts were (i) that these paradoxes were basically
]all the same, (though now some are pompously distinguished as being semantic
]or syntactic);

I heartily agree.

] and (ii) that the resolution was obvious, namely that the
]paradoxes were a simple cheat caused by defining something in terms of itself,
]a vicious circle, in fact...

I _would_ heartily with this, except that you seem to be talking about
a circularity of some sort in the semantic domain, and I don't believe
that it occurs there.

]No-one has really responded to my idea though; that the "impredicativity of
]self-reference" and the "impredicativity of self-candidacy" were clearly
]distinguishable.   Pity.  *I* thought it was a good idea. (sob)

I know how you feel :-).  Anyway, the reason I don't agree with your
conclusions is because there are plenty of examples of
"impredicativity of self-reference" that don't lead to paradox.

]Many thanks too, to David Gudeman, for his long and interesting article,
]clarifying his views somewhat on impredicativity vs recursiveness, and
]sets vs properties. David ascribes great importance to the distinction
]between properties and sets, as far as sorting out the Russell paradox goes.

Actually, I don't.  I claim that the property version of the paradox
and the set version of the paradox ought to have the same solution,
and that most solutions given to the set paradox don't apply to the
property solution (your solution does though).  But there is no need
to refer to properties to see that the set paradox results from an
ill-founded recursion.

The main reason I brought in propeties was because I was tired of
having my statements contradicted by reference to ZF.  I wanted to
have some way to get accross the point that when I say "set", I do not
mean "one of the things described in ZF".  So ZF is in no way an
arbitriter of whether I am right in what I say about sets.

]Indeed, they may well be different things; many have thought so, but most
]have had a hard time making much headway with the idea. Many mathematicians
]probably believe that there are many sets which correspond to no property,
]("random-ish" ones);

If S is such a set, then it corresponds to the property of being a
member of S, doesn't it?

]and perhaps that there are different properties
]corresponding to the same set (intensional definitions of sets). But neither
]idea seems to have become settled into orthodox math.

Since I was assuming an intensional view of properties (how else could
sets be the extensions of properties?) this is certainly true.

]And I don't really think Russell is altered by framing it in property form:

I agree completely.

]The trouble with David Gudeman's idea, that some "apparent" properties are
]not really properties, is that he gives no clear way of determining when
]they are and when they're not.

Foul!  Foul!  I never claimed to be a constructivist.  I don't have to
give an effective procedure for determining whether a given open
sentence describes a property or not.  I can just say that if the open
sentence is either true or false (but not both) for all
instantiations, then it actually describes a property.  Otherwise it
fails to describe a property.  Of course if I wanted to make a
consistent theory out of my ideas I would have to restrict open
sentences in such a way that only those that describe properties can
be used as objects.  Any such restriction would necessarily eliminate
some real sets from being talked about, but I think I could do a lot
better than ZF.

]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 ?   :-(

Nope :-).  x has a perfectly acceptable range.  The problem is caused
by the form of P.
--
                    David Gudeman
[e-mail]