FOM: Cantor's Theorem & predicativity

[A.P. Hazen]

    There's an old result of Fitch's that CAN be taken as indicating that
(some form of) Cantor's Theorem is essentially impredicative.  Details a
few paragraphs on.
   There seem to be about as many notions of predicativity as there are
notions of constructivity, making Robert Tragesser's questions even harder
to get to grips with (though no less interesting).
    (a)  Take the basic idea as being about set existence: we assume some
domain of THINGS (see (b) and (e) below). A predicativist thinks that a set
of these things exists if you can specify its members by a condition in
which you perhaps quantify over the things, but not over sets of them.  If
the best you can do is to specify the members of the supposed set by a
condition quantifying over SETS of things, then the predicativist doubts
whether it exists.  To make the idea concrete, pretend the THINGS are the
natural numbers: a predicativist believes in arithmetic sets, but may have
doubts about analytic ones.
     (b)  What can the THINGS be?  Well, one possibility is for them to be
... sets!  There is no reason why one can't make the predicativist's
distinctions about classes of sets defined in different ways.  Analogue: we
distinguish between arithmetic and analytic CLASSES of sets as well as
between arithmetic and analytic SETS of numbers.
     (c) Back to sets of THINGS.  Suppose you are a predicativist who
believes in predicatively defined sets, and suppose someone specifies the
membership of a putative set of things with a condition quantifying over
(not sets in general, but) the predicatively defined sets mentioned in (a).
Perhaps you could say that the putative set is SECONDARILY PREDICATIVE, and
exists (though it doesn't belong to the elite domain of "primary"
predicative sets introduced in (a)).  This viewpoint gets its natural
formalization in RAMIFIED SECOND-ORDER LOGIC.  Probably the best reference
on Ramified 2nd-Order Logic is sections 58-59 of Alonzo Church's 1956
"Introduction to Mathematical Logic."
     (d) If you combine the ramification (c) with the acceptance of classes
of higher types (b) you get Ramified Higher-Order Logic: Russell's system
in his 1908 "Mathematical Logic as based on the theory of types" (repr. in
several places, including Van Heijenoort's "From Frege to Gödel") and
"Principia Mathematica," but without the Axiom of Reducibility.  Best
introduction to (a modernized and streamlined version of) the system:
Church's "Comparison of Russell...Tarski," in "JSL" 1976; repr. with
correction in R.L. Martin, ed.,"Recent Essays on Truth and the Liar
Paradox."   ***BUT*** the way you combine higher orders and predicativity
isn't obvious, and Russell seems to have formulated a new, and perhaps
mathematically stronger, version in the 1925 second edition to "Principia
Mathematica." For details see the article by Hazen & Davoren in the
"Australasian Journal of Philosophy" for December 2000 (v. 78, n. 4).
     (e)  But what are the THINGS you start out with? There are at least
two possibilities of interest to the Foundations of Mathematics. (i) Let
the THINGS be the natural numbers, and assume the principle of mathematical
induction in addition to the predicative set-theoretic machinery.  Weyl, in
"Das Kontinuum," did this, using only the basic predicative set-theory of
(a). This approach leads to what is now known as "predicative analysis":
Lorenzen's work in the 1950s, and of course Feferman's work.
Alternatively, (ii) assume there are infinitely many things, but don't
assume anything else about them, and in particular don't assume induction.
A certain amount of arithmetic can be derived on this basis, but the
mathematics is MUCH weaker than "predicative analysis": cf. Burgess & Hazen
in "Notre Dame Journal of Formal Logic" v. 39 (1998), pp. 1-17 for details.
(Most of the results in this paper, and all the hard ones, are Burgess's.)
Whether using Russell's 1925 set theory would allow the derivation of more
mathematics I don't know.  I'd like to.
----
    Back to Cantor's Theorem.  In the 1930's, Frederick Fitch studied a
fairly strong predicative set theory: natural numbers as THINGS with
induction taken as axiomatic, and full Ramified Higher-Order Logic (as in
the first edition of "Principia," though I think his results would still
hold if you substituted the 1925 set theory).  A paper in JSL v. 3 (1938)
proved the consistency of this system, and a follow-on in the next volume
showed-- this is the POINT of my post-- that it could be consistently
extended with axioms to the effect that EVERY infinite set is denumerable.
Thus, for example, there is a one-one mapping between the natural numbers
and the universe of ("primary") predicative sets of natural numbers, and
another one-one mapping between the natural numbers and the universe of
what I called "secondarily predicative" sets of numbers, and so on.
Cantor's theorem, of course, survives in a way: the logic of the diagonal
argument is o.k.  The one-one mapping between, say, numbers and primary
sets of numbers has to be far enough out in the ramification-hierarchy that
it can't be appealed to in defining a primary set.  But Cantor's theorem as
a claim about the SIZE of sets goes.  Cantor's Theorem appears to be
essentially impredicative, not because of anything funny about the logic of
the diagonal argument, but because the very concept of CARDINALITY can't
really be formulated  if one's theory of relations and sets is ramified.
Allen Hazen
Philosophy Department
University of Melbourne