🚀 go-pugleaf

In article  <Bx2ALr.3Az@cantua.canterbury.ac.nz> Bill Taylor writes:
]...
]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.

So long as you have some reason to suppose that the thing being
defined exists, and that only one thing satisfies the definition, I
have no problem with such definitions.  I was in no way criticizing
mathematical practice, which is generally quite safe in this regard.

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

Thank you for this concises statement of one of the positions I
disagree with :-).  As I said before, the impredicativness of the
definition does not concern me, it is the recursiveness.  Let me try
to be more precise about my position:

When I speak of sets in this context, I am specifically speaking of
those objects which are the extension of a property, prior to any other
knowledge about the objects.  Formally, for a property p, there is a
set y = {x : p(x)} such that p(x) <=> x E y.  This notation should be
viewed merely as a language for talking about sets, not as part of a
theory of sets.  In particular, I have not yet claimed that _all_
properties have extensions that are sets.

Now speaking from this intuitive basis, it is legitimate to ask whether
ZF (or NFU or any other set theory) accurately depicts these objects.
More specifically, we can ask whether any model of ZF corresponds to the
objects we are talking about.  In any such discussion, we can make
formal statements about the models of ZF, but not about the intuitive
notion, so arguments will necessarily be informal.  (Please note that
when I argue that the models of ZF do not correspond to my intuitive
notion of what a set is, I do not mean (1) that ZF has no models, (2)
that the sets modeled by ZF are not real sets, or (3) that ZF is
useless.)

I argue that the models of ZF do _not_ in fact correspond to my
intuitive notion of what a set is.  For example the notion of classes
that are not sets seems to have no correspondence in idea of properties.
If a class is the extension of a property, then it is a set.  And if it
is not the extension of a property, then what does it mean for it to
exist?  It would surely be possible to present a theory of properties
containing a notion of "superproperties" corresponding to classes.  But
such a theory would not correspond to my intuitions of what a property
is.

Then consider the property P represented by the open sentence "__ is a
property".  I claim that P is a perfectly good property that ought to
have a perfectly good extension.  Furthermore, P(P) is an intelligible
notion that ought to correspond to the intelligible notion that {x :
P(x)} E {x : P(x)}.  There are many examples of this sort, all leading
me to conclude that any set theory that does not allow arbitrary
self-referencing sets does not correctly describe the notion of the
extension of a property.

Finally, Russell's paradox is expressible in terms of properties without
regard to sets.  Since sets exist only in virtue of being the extensions
of properties, I claim that the paradoxical set is only the extensional
version of a problem that exists quite independently of the extensions.
So any "solution" to the paradox that claims to see the problem in the
notion of set or set abstraction or extension is wrong, because the
identical problem exists independently of sets or set abstraction or
extension.

This, in my view, automatically rules out the explanation that the
paradox is due to the fact that some properties do not have extensions
that are sets.  In the property version of the paradox, this amounts to
the claim that some properties are not properties.  But if you accept
this solution (re-worded in such a way as to make it reasonable), then I
can show that the notion of non-self-membership is one of these
non-properties, so you still have not proven that there are some
properties that do not have sets as extensions.  Clearly there are
_non-properties_ that do not have sets as extensions, but that is quite
a different claim.

Let use call these properties-that-are-not-properties pseudo-properties
for the moment.  What are these pseudo-properties and where do they come
from?  Let us examine the pseudo-property R represented by "__ is not
true of itself".  We find that R behaves very much like a property
because we can say for most objects x that either R(x) or ~R(x) is true.
But when we ask whether R(R), we find that R(R) <=> ~R(R), which is a
contradiction.  But I assume that there can't be any contradictions in
the real (mathematical) world, so I have to suppose that the
contradiction lies elsewhere, specifically in the language used to name
the property.  In other words there is no real contradictory property,
there is only a failed attempt to name a property.

So how did the attempt to name the property fail?  The answer is: by an
ill-founded recursion.  As I showed before, recursive definitions are
definitions-by-equation, and those equations may not have unique
solutions.  When they don't have unique solutions you get a
contradiction or a violation of the law of the excluded middle.
So I claim that the attempt to define a unique property failed.  Either
you described two different properties R1 and R2 such that R1(R1) and
~R2(R2), or you described no properties at all.  The important point is
that the contradiction exists in _the language_, not in the world of
mathematical objects.

It is easy to show that the problem is recursion rather than
impredicativness by showing a version of the paradox without
quantifiers.  The Liar's Paradox, which is a zeroth order version of
Russel's is such a version:

  L = ~L

Now this simple definition produces a paradox with no machinery more
complex than recursion and negation.  It might be tempting to blame the
paradox on negation, but notice that

  M = M

contains no negation but is still problematic in that it causes a
violation of the law of the excluded middle.  I am _not_ claiming that
recursive definitions are illegitimate in any sense.  I am only
pointing out that before you can use a recursive definition you need
to know that the equation has a unique solution.  The set construction
of Russel's paradox does not name a unique set.

So solutions to the paradoxes should be viewed as changing the language
to avoid ill-founded recursion, not as changing our view of what sets
exist.  ZF, NFU, and Russel's type theory all avoid the paradox by
removing recursion and replacing it with iteration.  As a result, they
get systems that are missing the sets that can't be defined with their
version of iteration.  In some sense it is even too strong to say that
their solutions are "wrong", since they _are_ solutions.  Rather, I
should say that (1) the usual explanations of how these systems avoid
the paradox are wrong, and (2) the systems are missing a lot of sets
that don't have to be missing.
-- 
					David Gudeman
gudeman@cs.arizona.edu