Saturday, March 03, 2018

Cantorian Diagonal Argument

Cantor’s diagonal argument that there are more real numbers than natural numbers gets its name from its picture proof (as below), and it generalizes to show that powersets are always bigger than their original sets.

Cantor originally used collections instead of sets, but they gave him a paradox. Now, a collection of things is just those things being referred to collectively, so it is hard to see how that could have been the problem. But Cantor introduced the notion of a set, or consistent collection, and most modern mathematicians use axiomatic sets, for added confidence, and define numbers from them.
      Nevertheless, there really are numbers of things, so I take the logical essentials of Cantors paradox, and find a lacuna. My version of the diagonal argument shows that given some things, cardinally more selections from them are possible. As is the case with Cantor’s diagonal argument, it is best to begin with small collections, and build up from there, so that the general case can be more easily understood, by comparison with those simpler cases.

There are clearly three things:
      clearly there are
Given those three words, we can select a couple, e.g. ‘clearly’ and ‘there.’ There are three ways of making a pair – three different pairs that could be made – from those three words: {‘clearly,’ ‘there’}, {‘there,’ ‘are’} and {‘clearly,’ ‘are’}.
      Each of those ways of making a pair derives from, and is therefore defined by, the presence of two particular things in the original collection. Given those two things, there is that way of making a pair, whether or not anyone would or could make it. Because the original things were distinct, those pairs are distinct, and so each can count as one thing, as when we think of those three ways of making a pair. Possible selections are, in that sense, things.
      In a similar sense, collections are things, e.g. those are three collections of words. But given some things, thinking of just some of them as yet another thing can easily seem like the weak link in a chain of reasoning that leads to a contradiction. (After all, the collection of one thing is just that thing.) It is clearer that, given some things, a way of making a pair from them is indeed another thing. (A way of selecting just one thing is a way of selecting.)

Making a pair is just one way of making a selection. There are, in total, 2 to the power of 3, or 2^3= 8 possible selections from a collection of 3 things (cf. its powerset). It is an elementary result in combinatorics that there are 2^3 ways of assigning 2 labels, say ‘In’ and ‘Out,’ to 3 things, e.g.
      for the pair that is ‘clearly’ and ‘there,’
      ‘clearly’ has the label ‘In,’ as does ‘there,’
      while ‘are’ has ‘Out’ because it is not in that sub-collection.
In general, for any collection of things, T, there is a selection-collection, S(T), of all the combinatorially possible selections from T, each corresponding to some combination of as many ‘In’s and ‘Out’s as there are things in T.
      There is the selection-collection of 2^8 = 256 possible selections from the aforementioned 8, for example; and there are, similarly, a further 2^256 possible selections from that collection, and so on.
      Each of those possibilities is distinguished and defined by the presence of pre-existing things in the original collection, and so they are all implicitly there already, with our original 3 things.
      There is therefore an infinitely big collection of combinatorial possibilities, say N (from which further selections might possibly be taken, giving us S(N); and so on).

Two collections of things have the same cardinal number of things when there are one-to-one mappings from each collection onto all of the other. Cardinality therefore captures some of the intuitive sense of there being as many things in one collection as there are in another. Whether cardinal numbers are rightly called ‘numbers’ or not does not matter here; for the purposes of this proof, the main thing about cardinality is that it is an equivalence relation: it is reflexive, symmetric and transitive. Cardinality therefore partitions collections into equivalence classes. In particular, S(N) is not in the same class as N, for the following reason.

For simplicity, the things in N will be given the names
‘1’ (e.g. naming {‘clearly,’ ‘there,’ ‘are’}),
‘2’ (e.g. naming {‘clearly,’ ‘there’}),
‘3’ and so forth. To get the things in S(N) we associate the things in N with either ‘In’ or else ‘Out,’ and so each thing in S(N) can be named by an infinite sequence of ‘I’s and ‘O’s.
      If S(N) had the same cardinality as N, then we could associate each combinatorially possible sequence of ‘I’s and ‘O’s with one of the names of the things in N, and thereby list all the combinatorially possible sequences of ‘I’s and ‘O’s.
      E.g. the element of S(N) whose name is the sequence I, I, O, O, … might be associated with the element of N named by ‘1,’ and so on:

 N         S(N)

 1           I           I         O         O         …

 2          O         O         I          O         …

 3           I          O        O         O         …

 4           I          O         I           I         ...

…         …         …        …         …         ...

If we can name an element of S(N) that is not in that list (for any such list), then that will show that N and S(N) are not the same size; and we can specify one that is different from each of those by specifying that:
its 1st label differs from the 1st label of the element associated with 1,
its 2nd label differs from the 2nd label of the element associated with 2,
and so on (e.g. O, I, I, O, ...). And that diagonal argument generalizes to show that every selection-collection, S(T), is cardinally bigger than its original collection, T, as follows.

We begin by supposing, counterfactually, that S(T) has the same cardinality as T, i.e. that there are one-to-one mappings from T onto all of S(T). Let M be one such mapping.
      We use M to specify a collection 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 (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. Consequently there is no such M; S(T) does not have the same cardinality as T. And since S(T) has at least one element for each thing in T – e.g. the selection of that thing – hence S(T) is bigger than T.

So, given any 3 things, there is an infinitely big collection, N, and an even bigger collection, S(N), and the even bigger S(S(N)) = S^2(N), and similarly S^3(N) and so on.
      All the things in all those collections are collectively the union, U, of those collections; so, there is also U. U is bigger than each of those S^n(N), for natural numbers n, because it contains all the things in each S(S^n(N)). Furthermore S(U) is even bigger, and so on. So there is also the union, say V, of all the S^n(U) for natural numbers n. S(V) is even bigger, and so on; and so forth, past W, say.
      There will be a union, UU, of U, V, W, …, and thence a union, UV, of all the S^n(UU), and similarly UW, and so on, through VU, VV, VW, ..., and so forth. There will be a union, UUU, of UU, VV, WW, …, and a union of U, UU, UUU, …, and so on, and so forth.

Paradox arises because we naturally assume that each of the possible selections that such endlessly reiterated selection-collections and infinite unions would or could ever show there to be is already a possibility, that it is already there, as a possible selection. It follows that they were all there already, that they are collectively some collection, C, of all those possible selections.
      But, there cannot be any such collection, because its elements, simply by existing, would define those of S(C); and by the diagonal argument, S(C) would contain even more things of that very kind. And we cannot – by the meaning of ‘not’ – have both that C does contain all such possible selections and that C does not contain them all.


No comments: