Wednesday, May 29, 2013

The Set-theoretical Paradoxes

I have another piece on semantic paradox in The Reasoner in June; but, what about the set-theoretical paradoxes? The seminal paradox of Bertrand Russell (1902: ‘Letter to Frege’, in 1967: Jean van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, 124–5), for example, concerns the class of classes that do not belong to themselves. (In this context, classes are extensions of predicates: all and only the things that satisfy the predicate belong to the class.) Some classes – e.g. the class of humans – do not belong to themselves – the class of humans is a class, not a human – and the class of all such classes is paradoxical: it belongs to itself if, and only if, it does not. Russell conceived this paradox when thinking about the set-theoretical paradoxes, because a class is a kind of set; but, Russell’s paradox can also be expressed directly in terms of predicates:
Let w be the predicate: to be a predicate that cannot be predicated of itself. Can w be predicated of itself? From each answer its opposite follows. (Ibid, 125)
Note that “is a human” is a predicate expression, not a human, so it does not describe itself; the question is, what about “does not describe itself”? It describes itself if, and only if, it does not, which is paradoxical (it is widely known as Grelling’s paradox). But, we might as well say that “does not describe itself” describes itself insofar as it does not, from which it follows that it describes itself as much as it does not. So the question arises, could the class of classes that do not belong to themselves belong to itself as much as not? Classes can be like that, e.g. the class of all men would be like that if some hominids had been about as human as not. If we call one such hominid ‘Strider’, then it was about as true as not that Strider was human. Were there no such hominids, then some human would have had non-human parents.

That – the fuzzy set – resolution of Russell’s paradox coheres rather well with my preferred resolutions of the semantic paradoxes – e.g. The Liar Paradox, from The Reasoner 7(4) – but, the set-theoretical paradoxes originally arose from the mathematics of Georg Cantor, and they concerned, not classes of classes, but numbers of numbers. And of course, numbers are far from fuzzy. You and I, for example, are two people, and there is surely no doubt that we know what is meant by ‘two’ (for all the uncertainty over Strider's personhood). So, let us begin with 0, 1, 2, 3 and so forth, the products of the process of adding 1 to the previous number, starting with 0. Rather trivially, the collection of all those numbers is all of them, referred to collectively; and while some collections – e.g. stamp collections – are variable, if a collection is non-variable then we can say that it is a set (as in “a set of stamps”). On this conception, a set is some particular number of logical objects. To include the numbers 0 and 1, and so make this conception more like the standard conception (and also simplify proofs), let us also include logical objects that can play the role of singletons – sets with a single element – and Ø, the empty set. So, given that we have a set {0, 1, 2 …}, it contains some definite number of numbers, say א (aleph) of them.
......Cantor showed that every set has more subsets than it has elements, in the cardinal sense of ‘more’. (Two sets have the same cardinal number of elements when the elements of each set can all be paired up with those of the other (cf. Hume's principle).)
Let S be any set, and let P (for ‘powerset’) be the set of all its subsets (including Ø and S). If S and P had the same cardinality, then there would be one-to-one mappings from S onto all of P, so let M be one such mapping. Let a subset of S, say D, be specified as follows: For each member of S, if the subset that M maps it to contains it, then D does not contain it, and otherwise D does. The problem is that since D differs from every subset that M maps the members of S to, D differs from every subset of S, whereas D is by definition a subset of S. So, D is contradictory, and so there is no such M. So S and P do not have the same cardinality, and since P contains a singleton for each element of S, P is bigger than S.
So, {0, 1, 2 …} has beth-one subsets, where beth-one is bigger than aleph, and the set of all those sets has beth-two subsets, and so on. If that endless sequence of bigger and bigger sets is a non-variable sequence, then there is a union – a set of the elements – of all those sets, which is even bigger, with בω (beth-omega) sets. (Omega is the ordinal number of the sequence 1, 2, 3 and so forth.) And that union has בω + 1 subsets, and so on: for any such set there is the set of its subsets, and for any endless sequence of such sets there is, if it is a non-variable sequence, its union. In total, there is a sequence of sets – and a corresponding sequence of numbers, the sizes of those sets – which must be variable; were it not, we would have moved on from that ordered set of sets to its union, and thence to the subsets of that union (and so on). But of course, it is paradoxical that our total sequence of numbers is variable – is of necessity growing forever – because few of us think that numbers that do not already exist could suddenly appear. Suppose, for example, that the number 101 had not always existed; would that not mean that there was once a time when there were no such possibilities as, for example, the possibility of 101 Dalmatians? And note that this paradox cannot be resolved as Russell’s paradox was resolved above, because the idea of something being as variable as not is nonsensical.

Nevertheless, the intuition that numbers are atemporal is not unquestionable, because new possibilities can be constructed out of more general possibilities. You were always possible, for example, and yet the possibility of you in particular was only distinct from the more general possibility of people just like you once you existed (to be directly referred to). And it is not too odd to think of arithmetic as constructed from such logical concepts as those of possibility and class. E.g. the obvious meaning of “2 + 2 = 4” is that if we had two things of some kind, then if we got another two of that kind we would have four. So, it is conceivable that, while 101 Dalmatians were always possible, there was once a time when that possibility only existed as part of a more general possibility (of bigger numbers). Such constructivism can be defended atheistically – e.g. see George Lakoff and Rafael E. Núñez (2000: Where Mathematics Comes From: How the Embodied Mind Brings Mathematics into Being, New York: Basic Books) – and theistically, e.g. see Paul Copan and William Lane Craig (2004: Creation out of Nothing: A Biblical, Philosophical, and Scientific Exploration, Grand Rapids, MI: Baker Academic).
......Whether we are atheists who believe that the human brain evolved in a finite world, or theists who entertain divine ineffability and infinitude, we would have such reasons to doubt that we could ever be justifiably sure about the nature of infinity, though. And another reason why we should keep an open mind about this is that, while it is clearly counter-intuitive to think of the finite cardinal numbers as temporal, it is, if you think about it, no less counter-intuitive to think of them as atemporal. E.g. the arithmetic of such numbers as א and ω is very different to that of the finite cardinal numbers, whence the theoretical behaviour of that many objects is counter-intuitive. Hilbert’s famous Hotel can be built upon Galileo’s paradox, for example. And the difference between cardinal and ordinal arithmetic gives rise to the counter-intuitive behaviour of my quasi-supertask (2003:Infinite Sequences, Finitist Consequence’, British Journal for the Philosophy of Science 54, 591–9). And the infinite set of the finite cardinal numbers covers the whole range of the finite (in units), and yet every one of those numbers is infinitely far from infinite, whence Lévy’s paradox. For more examples, see José Benardete (1964: Infinity: An Essay in Metaphysics, Oxford: Clarendon Press), and Peter Fletcher (2007: ‘Infinity’, in Dale Jacquette, Philosophy of Logic, Amsterdam: Elsevier, 523–585).
......Intuitively, numbers are timeless; but while it is certainly possible that there is a set of all the finite cardinal numbers, it is also possible that there is not. Both possibilities are counter-intuitive, so both can be supported in ways that would seem compelling were it not for that ‘both’. So, one might think that modern mathematics would have been based on results that follow, not just from one, but from both possibilities. However, such is not the case. Now, the ubiquity of the standard real number line might be explained by its being easy to use, simple and familiar, but there is a similar bias towards assuming that there is a non-variable collection {0, 1, 2 …} in such fundamental research areas as theoretical physics and pure mathematics, which is puzzling. For clues, see Ivor Grattan-Guinness (2000: The Search for Mathematical Roots, 1870–1940: Logics, Set Theories and the Foundations of Mathematics from Cantor through Russell to Gödel, Princeton University Press), and Peter Markie (2013:Rationalism vs. Empiricism’, in Edward N. Zalta, The Stanford Encyclopedia of Philosophy).

It might be objected that there is no real puzzle because {0, 1, 2 …} is not an informal set in pure mathematics, but is an axiomatic set defined by means of a formal logic. However, that would be to ignore, not to explain, the mystery. We know perfectly well what the cardinal numbers 0, 1, 2, 3 and so forth are; if we had some axioms that did not describe them, we would not throw those numbers away and start using those axioms instead, however nice their formal properties were. To do so would hardly be scientific.
......Perhaps I should add that we do not get a third kind of set-theoretical paradox from the axiomatic conception. Paradoxes arise when we have contradictory beliefs, and formal structures have no intrinsic meaning; formal axiomatic sets only give us mathematical models of set-theoretical paradoxes. So, while it is true that paradoxes can be avoided if we use formal sets, we did not really resolve the set-theoretical paradoxes by moving from naïve set theory to axiomatic set theory.