Impredicativity - was: Russell's Paradox. - Thread - go-pugleaf

Impredicativity - was: Russell's Paradox.

#32

Author: Bill Taylor
Date: Sun, 01 Nov 1992 23:58

154 lines
9922 bytes

I fear that David Gudeman and Chris Menzel's sniping is about to descend from
complaints of miscommunication, lack of knowledge and spelling mistakes (!), to
that of mere personal abuse, any moment now.  That would be a great pity, as
I have found this Russell Paradox discussion quite interesting and informative.
These overheated flame wars are most often seen in the politics and religion
newsgroups, where they belong; though we sometimes see them in logic too, alas.
I suppose because foundations is the nearest thing to religion in mathematics.

It's always a great danger for a third party to insert himself into the
firing line of a duel, but I will do so, as the discussion has strayed
towards a matter that has long bothered me.
----

The matter is, IMPREDICATIVITY, and it's role in Russell's Paradox.

Chris Menzel has suggested that impredicativity is unobjectionable in
mathematics generally, and not an essential part of Russell's Paradox, and
I basically agree. Gudeman has asserted that impredicativity *is* closely
associated with Russell's Paradox, and that at least it needs careful
handling in regular mathematics, to the extent that an impredicative
definition usually needs a proof of existence and uniqueness to qualify it
fully as a definition (though these are often so obvious that they are ignored).
And again I agree.  I believe that a source of conflict here is that the term
impredicativity is used in two different ways, that are seldom distinguished.
                           ~~~~~~~~~~~~~~~~~~

Impredicativity, in the sense of defining a thing by using a definition whose
body refers to the thing being defined, is an integral part of ordinary
mathematics, where it can hardly be avoided. I agree with Menzel (and most
mathematicians) that such use is quite harmless.

For instance, defining x as "the solution of x = exp(-x)", or as "the largest
solution of x^5 - 8x^4 + 1 = 0",  are impredicative in this sense.  I do not
refer to the use of the letter "x" of course, (which I have treated sloppily
as a constant and a bound variable alternately), but the number itself, which
has been defined only by implicitly referring to a set of numbers of which
it may be a member.      This form of impredicativity is merely using a
definition to *pick out* some particular thing which we know *already exists*,
as Menzel observes; and seems thoroughly harmless.

Similarly for that favourite example of impredicativity so suspicious to
constructivists: the least upper bound of a set of reals.   The usual
definition would be by a Dedekind cut; that of the set of rationals that are
no greater than some real in the given set. This is thought to be dangerously
impredicative by some, in that to check for a rational to be in the set, one
must test it against all possible reals, and this may include the very real
that one is trying to define. I have never seen the force of this objection,
which seems to me no more sensible than for the equation-root examples above.
I consider that Menzel's "picking out" remarks fully apply to this, and
easily dispose of any objections.

Another example, (given in Cohen's book on Continuum Hypothesis independence),
is that of S = "the set of natural numbers n, such that N may be partitioned
into n parts none of which contains arbitrarily long arithmetic sequences".
Apparently this form of impredicativity is also considered dangerous by some.
It arises in that to determine whether an "n" is in S, some of the partitions
which need to be checked may include S itself.  Again, I cannot see the slightest
objection to this form of impredicativity; the "picking out" remarks still apply.


The above examples are all of what I would call "harmless impredicativity";
that of referring to a defined term in the body of it's own definition. (Of
course one must bear in mind that it will in general need a theorem to back
up the definition, at least in principle, as Gudeman points out).

HOWEVER, I believe that there is a truly dangerous form of impredicativity,
which goes somewhat beyond this, and is at the heart of the Russell Paradox.

Poincare and Russell both made an attempt to pin the blame on the
"Vicious Circle" idea. This has usually been dismissed, wrongly I believe;
either on the grounds that it is too informal, (but what isn't, to begin with),
or that it can only be clarified into an instance of impredicativity, which,
as we mostly agree, is usually harmless, and to deny which "would put one
fairly and squarely with intuitionists and other fanatics". JUST KIDDING, no-one
ever goes this far of course, but that often seems to be the tenor of
dismissals of the vicious circle idea.  Now I think that this is most unfair;
and that one may well espouse the vicious circle idea as being the root cause
of Russell's Paradox *without* objecting to impredicativity at large; AND that
this idea can pretty well be made exact, as follows.

The trouble with the Russell set, (or the universal set), is this. Attempting
to define it by naive comprehension as R = { x | phi(x) } , is objectionable;
not (though) because phi may implicitly *refer to* R itself, which is mere
"harmless impredicativity", but because the  **range of candidate members**
includes R itself.  This is the key to "vicious circle" impredicativity, it
seems to me.

To define a *set* (by comprehension), means to consider its possible members,
so the set itself cannot possibly be considered as a prospective member, because
it has not (yet) been defined. Doubtless this will sound just like "harmless
impredicativity" to many, but I think it is a distinguishable special case,
and the one that contains all the venom of the paradox. To attempt to define a
set by looking at a prospective member as possibly being the set itself, seems
to be *asking* for trouble. A true vicious circle; far worse than "harmless".
It seems to be a hopeless confounding of the very meaning of "membership".

I don't know the history of it too well, but I suspect this is what really
lay behind the Poincare and early Russell explanation attempts. It may well
lie behind Gudeman's objections, (though as he seemingly doesn't object to
selfmembership or a universal set, it may not satisfy him).

I think the Poincare/Russell views of vicious-circle containing an "essential"
impredicativity have been needlessly dismissed, and confused with "harmless"
impredicativity.   Of course this view *automatically* entails that no set
can be a member of itself. This may be considered disturbing in view of
Menzel's remark that Aczel's selfmembering set theory is equiconsistent with
ZF. But I hardly think this is a bother. I have read some and listened some to
Aczel's theory, and it is great fun, and nice math, but it has always struck
me as being an essentially graph-theoretic excercise, and having little to
do with what sets "really are", in a Cantorian sense. I may be treading on
some toes, but IMHO these selfmembered "sets" have little to do with our
concerns here.

The question of what should be done to eliminate this dangerous essential
(vicious-circle) impredicativity, but leave the harmless form, has long
excercised foundationalists. The ZF solution, of "limitation of size" seems
to be the preferred, natural and simplest solution. Some, including Gudeman,
object on the grounds that it is too restrictive; but something of the
sort seems almost unavoidable, as Menzel implies. Some method of "preventing"
sets from being candidates for their own membership is needed, and Menzel
is fairly convincing in his summary that the iterative hierarchy meets this
need precisely. I agree with him that the appearance of proper classes as
collections with unbounded rank in the hierarchy is in no way mysterious,
and is the natural resolution of the situation. Some conception of the
iterative hierarchy seems unavoidable as the intended model of ZF, which in
turn seems unimpeachable as formalizing the basic Cantorian ideas.

All the same, I have a lingering sympathy with Gudeman's objection that
this has not yet perhaps been *completely* demonstrated, and that there may
still be some way of approaching set theory less restrictively than size
limitation or the iterative hierarchy. I should say I think it exceptionally
*unlikely* that any such approach will be found, (as do most mathematicans),
but it seems to me the possibility cannot yet be totally dismissed.   I *do*
think though, that any resolution must firmly stick to the idea that self
membership is out of the question from the very start, as it is at the heart
of the Russell Paradox, and its vicious circle.
---

In summary then, my view is that in attempting to define any set by

    S = { x | phi(x) } ,

(i) one may easily allow S to be mentioned by phi, (harmless impredicativity);

(ii) one must NOT allow S to be an instance of "x", (essential impredicativity).

One might well give these the fancy names: "impredicativity of self-reference",
and "impredicativity of self-candidacy", respectively.

------------------------------------------------------------------------------
            Bill Taylor              wft@math.canterbury.ac.nz
------------------------------------------------------------------------------
                    Kleeneness is next to Godelness.
------------------------------------------------------------------------------

Re: Impredicativity - was: Russell's Paradox.

#33

Author: Andrew Dabrowski
Date: Mon, 02 Nov 1992 03:56

21 lines
1401 bytes

wft@math.canterbury.ac.nz writes:

Some conception of the
iterative hierarchy seems unavoidable as the intended model of ZF, which in
turn seems unimpeachable as formalizing the basic Cantorian ideas.

All the same, I have a lingering sympathy with Gudeman's objection that
this has not yet perhaps been *completely* demonstrated, and that there may
still be some way of approaching set theory less restrictively than size
limitation or the iterative hierarchy. I should say I think it exceptionally
*unlikely* that any such approach will be found, (as do most mathematicans),
but it seems to me the possibility cannot yet be totally dismissed.



I write:

What about Aczel's AFA?  I don't think there's any profound difficulty
pointed up by Russell's paradox, no more so than in trying to solve
x=x+1.  Aczel has shown that there's a very nice, natural set theory

Re: Impredicativity - was: Russell's Paradox.

#34

Author: Vaughan R. Pratt
Date: Mon, 02 Nov 1992 04:08

70 lines
4250 bytes

In article <Bx2ALr.3Az@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>...This may be considered disturbing in view of
>Menzel's remark that Aczel's selfmembering set theory is equiconsistent with
>ZF. But I hardly think this is a bother. I have read some and listened some to
>Aczel's theory, and it is great fun, and nice math, but it has always struck
>me as being an essentially graph-theoretic excercise, and having little to
>do with what sets "really are", in a Cantorian sense. I may be treading on
>some toes, but IMHO these selfmembered "sets" have little to do with our
>concerns here.

Ooh, ouch, you got toe number 3.  :-)

There is a foundational advantage to eschewing Aczel's cyclic-graph
view of membership (AFA or AntiFoundation Axiom) in favor of the
standard (but rarely if ever appealed to in ordinary maths) Foundation
Axiom that membership is not only an acyclic but well-founded
relation.  The advantage is that the nonexistence of a set of all sets
has a trivial proof: such an object would entail a cycle in the
membership relation, forbidden by FA.

That Russell felt obliged to give a more broadly applicable argument
suggests that FA was not held to be an evident property of sets by
mathematicians in 1905.  That it is self-evident to you now seems more
an accident of culture---your training---than of something inherent in
the notion of set.

While I'm on this topic, let me express a preference for stating the
Cantor-Russell "paradox" in its positive form: every set X has a
nonmember set, i.e. a set Y that is not a member of X.  The more usual
negative "paradoxical" form, that there is no set of all sets, follows
immediately.  Here are two proofs of the positive form, respectively
with and without FA.

1. With FA the obvious witness Y is X itself.  For if X were a set
belonging to X we would have a cycle in the membership relation.

2. Without FA, Russell subpoenas the more elusive set Y of all members
of X not members of themselves.  To see more visually than with the
usual symbol-pushing that this Y is not a member of X, picture the
restriction to X of the membership relation as a square 0-1-valued
matrix E: for any two elements x,y in X, E[x,y] = 1 just when x is a
member of y.  Every member Z of X appears exactly once as a column of
this matrix, with a 1 in just those rows W for which W is a member of
Z.  The set Y is the complement of the diagonal straightened to
vertical.  For every column Z of E, the column Y differs from Z in row
Z.  Hence Y is not a member of X, making it the desired witness.

Now what is the relationship between arguments 1 and 2?  Well, if we
announce FA *after* carrying out this construction (like producing your
discount coupon after being served) we notice that the diagonal of E is
all 0's, whence its complement is all 1's.  This means that argument 2
under FA produces X.  Hence argument 1 does not produce a different set
from argument 2, just the set that it must produce in the presence of
FA.  That is, argument 1 is what 2 simplifies to in the presence of
FA.

While this point of view may not immediately convert the reader from FA
to Aczel's AFA, it does encourage the sort of perspective from which
AFA can start to be seen as a very reasonable point of view.

For my own part I cannot imagine how I ever used to believe that FA was
an inherent property of sets.  I was simply bullied into it.

>                    Kleeneness is next to Godelness.

Dynamite .sig!
-- 
                                       |
Vaughan Pratt                          |                          ttarP nahguaV
Why do mirrors reverse words&not lettersrettel ton&sdrow esrever srorrim od yhW

Re: Impredicativity - was: Russell's Paradox.

#41

Author: Bill White
Date: Mon, 02 Nov 1992 20:26

33 lines
2557 bytes

In article <Bx2ALr.3Az@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>For instance, defining x as "the solution of x = exp(-x)", or as "the largest
>solution of x^5 - 8x^4 + 1 = 0",  are impredicative in this sense.  I do not
>refer to the use of the letter "x" of course, (which I have treated sloppily
>as a constant and a bound variable alternately), but the number itself, which
>has been defined only by implicitly referring to a set of numbers of which
>it may be a member.      This form of impredicativity is merely using a
>definition to *pick out* some particular thing which we know *already exists*,
>as Menzel observes; and seems thoroughly harmless.
>
>Similarly for that favourite example of impredicativity so suspicious to
>constructivists: the least upper bound of a set of reals.   The usual
>definition would be by a Dedekind cut; that of the set of rationals that are
>no greater than some real in the given set. This is thought to be dangerously
>impredicative by some, in that to check for a rational to be in the set, one
>must test it against all possible reals, and this may include the very real
>that one is trying to define. I have never seen the force of this objection,
>which seems to me no more sensible than for the equation-root examples above.
>I consider that Menzel's "picking out" remarks fully apply to this, and
>easily dispose of any objections.
Can't we just construct the reals using Cauchy sequences of rationals rather
than Dedekind cuts?  If we do this, we can actually construct the series
solution to x = exp(-x) or the largest solution of any polynomial we wish.
Perhaps the really interesting example of impredicativity here is when we
form (necessarily uncountable) quotient sets.

I read someplace (perhaps Johnstone's book on Topos Theory) that all of 
(intuitionistic) set theory can be developed in the (purely equational) 
theory of toposes, and that this requires no leap of existentialist faith 
as large as the existence of equivalence classes.

					Peace,
					Bill White

Re: Impredicativity - was: Russell's Paradox.

#43

Author: Chris Menzel
Date: Mon, 02 Nov 1992 20:54

25 lines
1879 bytes

In article <1992Nov2.040843.4524@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>That Russell felt obliged to give a more broadly applicable argument
>suggests that FA was not held to be an evident property of sets by
>mathematicians in 1905.

Most certainly true.  Well-foundedness wasn't really an issue until
the cumulative hierarchy started to take hold.  Mirimanoff explored
the axiom a bit around 1918, and sensed an important distinction
between well-founded and non-well-founded ("extraodinary," in his
terms) sets.  But it wasn't really until Zermelo's great 1931 paper
(still untranslated, for some reason) "Uber Grenzzahlen und
Mengenbereiche" in which he described the hierarchy in great detail
that foundation became an unquestioned part of set theory.

>That it is self-evident to you now seems more
>an accident of culture---your training---than of something inherent in
>the notion of set....

I think that's too strong if, like me, you were introduced to set
theory via the iterative hierarchy.  If that's your picture of sets,
then the axiom *is* self-evident, and well-foundedness *is* an
inherent property of sets.  The question is rather whether the
iterative hierarchy encompasses *all* the sets, or whether we've just
been looking at a rather limited portion of the universe, as is the
case if we take the universe to be nonwellfounded ala Aczel.

Re: Impredicativity - was: Russell's Paradox.

#46

Author: Vaughan R. Pratt
Date: Tue, 03 Nov 1992 04:15

22 lines
1763 bytes

In article <1992Nov2.205433.21208@tamsun.tamu.edu> cmenzel@tamsun.tamu.edu (Chris Menzel) writes:
>In article <1992Nov2.040843.4524@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>>That it [Foundation Axiom] is self-evident to you now seems more
>>an accident of culture---your training---than of something inherent in
>>the notion of set....
>
>I think that's too strong if, like me, you were introduced to set
>theory via the iterative hierarchy.  If that's your picture of sets,
>then the axiom *is* self-evident, and well-foundedness *is* an
>inherent property of sets.  The question is rather whether the
>iterative hierarchy encompasses *all* the sets, or whether we've just
>been looking at a rather limited portion of the universe, as is the
>case if we take the universe to be nonwellfounded ala Aczel.

The iterative hierarchy is consistent with Z but not with ZF.
Replacement (F) says in effect that any construction you can iterate
yields a set.  Hence if the universe is an iterative hierarchy it is a
set.

Anyone brought up on the iterative hierarchy was told a lie.
-- 
Vaughan Pratt			Ain't no truth in logic, son.

Re: Impredicativity - was: Russell's Paradox.

#51

Author: Joshua D. Guttman
Date: Tue, 03 Nov 1992 16:13

14 lines
1356 bytes

In article <1992Nov3.041515.27732@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:

   The iterative hierarchy is consistent with Z but not with ZF.
   Replacement (F) says in effect that any construction you can iterate
   yields a set.  Hence if the universe is an iterative hierarchy it is a
   set.

   Anyone brought up on the iterative hierarchy was told a lie.

I would have read replacement as saying that any construction you can iterate
*through a set* will yield a set.  Since the ordinals do not form a set,
iterating through them to produce the universe need not yield a set.  

	Josh

Re: Impredicativity - was: Russell's Paradox.

#52

Author: Joshua D. Guttman
Date: Tue, 03 Nov 1992 16:16

14 lines
1356 bytes

In article <1992Nov3.041515.27732@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:

   The iterative hierarchy is consistent with Z but not with ZF.
   Replacement (F) says in effect that any construction you can iterate
   yields a set.  Hence if the universe is an iterative hierarchy it is a
   set.

   Anyone brought up on the iterative hierarchy was told a lie.

I would have read replacement as saying that any construction you can iterate
*through a set* will yield a set.  Since the ordinals do not form a set,
iterating through them to produce the universe need not yield a set.  

	Josh

Re: Impredicativity - was: Russell's Paradox.

#54

Author: Randall Holmes
Date: Tue, 03 Nov 1992 16:17

56 lines
3222 bytes

In article <1992Nov2.205433.21208@tamsun.tamu.edu> cmenzel@tamsun.tamu.edu (Chris Menzel) writes:
>In article <1992Nov2.040843.4524@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>>That Russell felt obliged to give a more broadly applicable argument
>>suggests that FA was not held to be an evident property of sets by
>>mathematicians in 1905.
>
>Most certainly true.  Well-foundedness wasn't really an issue until
>the cumulative hierarchy started to take hold.  Mirimanoff explored
>the axiom a bit around 1918, and sensed an important distinction
>between well-founded and non-well-founded ("extraodinary," in his
>terms) sets.  But it wasn't really until Zermelo's great 1931 paper
>(still untranslated, for some reason) "Uber Grenzzahlen und
>Mengenbereiche" in which he described the hierarchy in great detail
>that foundation became an unquestioned part of set theory.
>
>>That it is self-evident to you now seems more
>>an accident of culture---your training---than of something inherent in
>>the notion of set....
>
>I think that's too strong if, like me, you were introduced to set
>theory via the iterative hierarchy.  If that's your picture of sets,
>then the axiom *is* self-evident, and well-foundedness *is* an
>inherent property of sets.  The question is rather whether the
>iterative hierarchy encompasses *all* the sets, or whether we've just
>been looking at a rather limited portion of the universe, as is the
>case if we take the universe to be nonwellfounded ala Aczel.
>

Actually, Aczel's universe is not very much larger than the usual
universe.  It is hierarchical in much the same way as the universe of
ZFC, with the stages H(a) of the hierarchy generated as follows:

	H(0) = {{}}

	H(a + 1) = sets with the property that membership on their
transitive closure is isomorphic to a graph with nodes taken from
H(a).

	H(L) = U{a < L}[H(a)] (L limit).

	Under AFA, the isomorphism type of the graph of membership on
the transitive closure of a set determines the set uniquely, so the
cardinality of H(a + 1) can be shown to be the same as the cardinality
of the power set of H(a) for infinite a (this is not true for finite
a), which implies that the cardinalities of the H(a)'s are the same as
those of the V(a)'s in the well-founded universe, for infinite
ordinals a.

	AFA does not actually make the universe noticeably larger.


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

🚀 go-pugleaf

Thread View: sci.logic

Impredicativity - was: Russell's Paradox.

Re: Impredicativity - was: Russell's Paradox.

Re: Impredicativity - was: Russell's Paradox.

Re: Impredicativity - was: Russell's Paradox.

Re: Impredicativity - was: Russell's Paradox.

Re: Impredicativity - was: Russell's Paradox.

Re: Impredicativity - was: Russell's Paradox.

Re: Impredicativity - was: Russell's Paradox.

Re: Impredicativity - was: Russell's Paradox.

Thread Navigation