Proof's Nearest Kin

Paradoxes are akin to proofs: We have a paradox when we have a very good argument for something that is beyond belief, a proof when we have a logical argument for something not too odd. Many a paradox is therefore a proof by reductio ad absurdum of the negation of its weakest premise. Georg Cantor’s famous paradox of the 1890s was exceptional, being a logical argument for a contradiction, but it thereby proved that human reasoning is not perfectly logical. In response the twentieth century saw a proliferation of formal logics, but as we develop such calculi with mathematical precision we might easily forget that some illogicality is unavoidable in our reasoning. To remind us, then, the following is the essence of Cantor’s paradox.

Consider any 3 things, e.g. a chair, a plate and a fork. There are clearly 3 different ways of making a pair from those 3 things (e.g. the chair and the fork are, collectively, a pair), each of which derives from, and is defined by, the presence of 2 particular things in our original collection of 3 things: Given those 2 things, we have that way of making a pair. Now, making a pair is just one way of making a selection. There are 8 different ways of making selections from our original collection because there are 2³ ways of assigning the labels “In” and “Out” to 3 things (e.g. the chair has “In,” the plate has “Out,” and the fork has “In”). Given our original collection, there are also those 8 combinatorial possibilities, those 8 ways of making selections, ways that are entirely grounded in our original things and which are therefore distinguished from each other whether there is a selector who can make those selections or not. Let us call them possible selections, from our original collection, and say that they are collectively the selection collection for our original collection. In general, for any natural number n, if there is a collection of n things, then there is also a selection collection of 2ⁿ possible selections from it.

We can safely assume that there are 2 things (e.g. you and I are 2 people), so there is also the selection collection of 4 possible selections from those 2 things, and the selection-collection of 16 possible selections from those 4, and so on. All those possible selections are there already, intrinsically distinguished from each other, and so there are infinitely many things, which are certainly things in the weak sense that there are numbers of them, in the fairly weak sense of cardinal number. Two collections of things have the same cardinal number of things when there are 1-to-1 mappings from each collection onto the other. Cardinality is fairly weak, e.g. there are clearly fewer prime numbers than natural numbers in some stronger sense, but it is an equivalence relation – it is reflexive, symmetric and transitive – and so it partitions collections into equivalence classes. For any collection of things, T, there are possible selections from T – each corresponding to some combination of as many “In” and “Out” labels as there are things in T – even if T is infinite, and so there is a selection collection, S(T), of all the possible selections from T. And for the following reason (which is essentially Cantor’s diagonal argument) every selection collection is cardinally bigger than its original collection.

Suppose that S(T) has the same cardinality as T. There would then be 1-to-1 mappings from T onto all of S(T). So let M be one such mapping. We might then use M to specify D as follows: For each thing in T, if the possible selection that M maps that thing to includes that thing (in other words, if that thing has the label “In” in that possible selection) then D does not include it (i.e. it has the label “Out” in D), but otherwise D does; and there is nothing else in D. Since the only things in D are things in T, D should be in S(T); but according to its specification, D would differ from every possible selection that M maps the things in T to, and so D would differ from everything in S(T). D is therefore contradictory, and so there is no such M. Consequently S(T) does not have the same cardinality as T. And since S(T) contains at least one thing for each thing in T – e.g. the possible selection whose only “In” label is assigned to that thing – and cardinality is an equivalence relation, hence S(T) is bigger than T.

Given you and I, then, there is some infinitely big collection, say N, and so by the diagonal argument above with T = N there is also a bigger collection, S(N), and by the diagonal argument with T = S(N) there is the even bigger S(S(N)) = S²(N), and there is similarly S³(N), and so on. All the things in all those collections are collectively the union of those collections, U, which is bigger than each of those Sⁿ(N), for natural numbers n, because it contains all the things in each S(Sⁿ(N)). Furthermore S(U) is even bigger, and so on; so there is also the union, say V, of all the Sⁿ(U) for natural numbers n. And again, S(V) is even bigger, and so on and so forth. Now, each of the possible selections that such endlessly reiterated selection collections and infinite unions would or could ever show to be there is already there, as a combinatorial possibility that is implicitly distinguished from all the others of that kind, and so they are collectively some collection, C, of all the possible selections of that kind. But by the diagonal argument, their selection collection, S(C), would contain even more things of that kind. That contradiction shows that we went wrong somewhere, but why should even highly evolved primates know where?