Monday, May 23, 2016

On the Famous Proof that the Natural Numbers are Indefinitely Extensible


There are clearly numbers of things in the world, e.g. you and I are two individuals. And to think of us in that way is essentially to think of us as the elements of a pair-set, {you, I}. So let us say that a natural set is any whole number of things. Note that {you, I} is also a subset, there being other people. And note that numbers and sets are themselves things in the sense that there are numbers and sets of them.

Do mathematicians discover facts about such natural numbers as 2? If so, then Georg Cantor’s famous paradox of the 1890s was essentially a mathematical proof that the natural numbers (i.e. 0, 1, 2, …) are ever-growing in number, because what Cantor did was to obtain a contradiction from the assumption that there is a set of them all. I will go through the mathematical steps of the proof below; but to begin with, Cantor’s proof was paradoxical because each whole number is essentially the logical possibility of that many things, and if something is ever going to be possible, then it was never logically impossible.

Cantor’s proof has therefore been taken to be a refutation of the assumption that mathematicians discover facts about such natural numbers: Most twentieth-century mathematicians defined the natural numbers, e.g. 0 is usually defined to be the empty set within an axiomatic set theory (usually ZFC), 1 to be {0} and so on. Axiomatic set theory is used because Cantor’s proof used a natural kind of set that has been blamed for the paradox (and called “na├»ve”). But such sets exist as clearly as natural numbers do and so, like the natural numbers, they should not be defined, but scientifically described.

That is because there is at least one way in which the natural numbers could, possibly, be ever-growing in number, because logical possibilities can become more fine-grained over time. Suppose that time is not so much like space that future events are already there (at future times), and consider any existing man. He was always possible, but it is only with hindsight that we can describe the logical possibility of his existing with such direct reference to him. Before he existed there was only the possibility of someone just like him, to whom we could not directly refer.

The logical possibility of n things, for each natural number n, could, then, have originally been part of the logical possibility of numbers of things, only becoming the logical possibility of things in that number when that number was created, perhaps as part of the analysis of the concept of a thing by some creative power that exists primarily in a world of spiritual stuff (and which may therefore appear triune to us), thereby creating an abstract realm of sortal natural kinds and their associated numbers prior to the physical objects and incarnate creatures of this world. Note that what matters here is only that that is a logical possibility (not even Richard Dawkins claims that God is impossible, only that He almost certainly does not exist).

Let us, then, assume that there is a natural set of all the natural numbers, N = {0, 1, 2, …}. Clearly the subset {0, 1, 2} is already part of N, as is every other subset; all the subsets of N are there implicitly, and so there is the set of all of them, P(N), the power set of N. Cantor showed that P(N) is cardinally bigger than N (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) by way of a diagonal argument; and both of those steps generalise: Given any set, there are implicitly all of its subsets, so that there is also its power set, to which the following diagonal argument applies.

Let S be any set, and let P(S) be its power set. If S and P(S) had the same cardinality, there would be one-to-one mappings from S onto all of P(S), so let us assume that they do and 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. 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. Consequently D is contradictory, and so there is no such m, and so S and P(S) do not have the same cardinality. And since P(S) contains a singleton for each element of S, hence P(S) is cardinally bigger than S.

So as well as N, there is also P(N), and P(P(N)) and so forth, an infinite sequence of power sets. Consequently there is also the set of all the elements of all of those sets, U, their union. U is cardinally bigger than each of those power sets because it contains all the elements of the power set of each of them. And of course, P(U) is cardinally bigger than U. And so on (there is another infinite sequence of power sets, then another union, and eventually an infinite sequence of unions that we can also take the union of, and so on).

There must be a set, T, of all that could possibly be found in that way (via power set and union), because all of it is already there to be found. But if T is a set, then P(T) contains cardinally more of precisely those sorts of elements; and that contradiction means that we went wrong somewhere. And from our assumption of N we made only logical moves, so it must have been that assumption that was false: The natural numbers are certainly ever-growing in number (in time that is not much like space).

Tuesday, May 10, 2016

What is Proof?

Over a hundred years ago, Cantor proved that the natural numbers are temporal: Assume, with Plato and against Aristotle, that they are not temporal, so that they all coexist, insofar as numbers do exist (the main thing is that we can count them, e.g. {1, 2, 3} are three numbers). Since they all exist atemporally, so do all their subsets (e.g. {1, 2, 3}), and so there is a set (an atemporal collection) of all the subsets of that set. By a simple diagonal argument (which you can google) that set of subsets is of larger cardinality than the original set. (Two sets have the same cardinality when the elements of one of them can be put into some one-to-one correspondence with the elements of the other.) And the set of all of the subsets of that set of subsets is of even larger cardinality, because the diagonal argument applies quite generally to any set and the set of all its subsets. (This gives us three equivalence classes of infinite sets, associated with three infinite cardinalities.) So, we can get cardinally bigger and bigger sets in that way. And when there is an endless sequence of such sets, the union of all of them will also be an atemporal collection, because each of those sets was implicit in the previous set, and it will have a cardinality larger than any of those sets, because each is followed in that sequence by sets of larger cardinality. And from that union we can again consider the set of all its subsets, and so on. Now, all these atemporal collections are implicit with the set of natural numbers, so they all exist (insofar as such things do exist) atemporally; but, Cantor proved that they cannot all exist atemporally: Suppose they do. Then there is a set of them all. But implicit in them is the collection of all of their subsets, which would be cardinally more of them, whereas we have assumed that we had the set of them all. So, we have assumed that the natural numbers are not temporal, and obtained a contradiction; that is a classical mathematical proof of the temporality of the natural numbers. However, most people assume that numbers are timeless, and so Cantor took himself to have proved that the totality of the numbers was indeed contradictory (akin to human reasoning being inferior to religious insight), while most of his peers replaced the natural numbers with axiomatic structures that had not been shown to be contradictory. Axiomatic set theory has been the foundation of mathematics for nearly a hundred years, but why do mathematicians throw numbers away (why take number-words to be referring to axiomatic sets) just because of an inconvenient proof? We expect others to accept the conclusions of our proofs, when we have proofs...