Mm… today I read about Cantor’s diagonalisation argument, arguing that there exists infinities which are bigger than others. At first, this sounds obvious, but when considering that for an infinity (let’s call it X), X+1=X, this suddenly seems a lot less obvious.
It would seem of utmost importance to give a general idea of the definition of equal sizes of 2 sets. For finite sets, this is already obvious by, in short, counting. The size of {1,2,3} is 3, which is less than the size of {-1,-2,-3,-4}, but for infinities, this is again less obvious (bah… infinities just have to be this hateful).
However, we note that it is possible to compare sizes of finite sets in a different way. Let’s just say that we wish to compare the sizes of the two abovementioned sets. We attempt to achieve a bijection between members of the 2 sets, say 1->-1, 2->-2, 3->-3, and lo and behold, we are stuck, for there is no other element in {1,2,3} left to biject to -4. So how do we know that it is impossible to choose a different mapping from the first set to the next that produces a bijection? In this case, it is simple, and trivial by Pigeonhole Principle (finite sets ftw!). However, as we shall see the in the case infinite sets, this is no longer as straightforward nor convenient (again, infinities are irritating; bzz…).
Firstly, let me brief explain why X+1=X. Suppose X is the cardinality (size) of the set of natural numbers, because other infinite sets are probably just analogous, but infinitely (pun!) more irritating to write an explanation for. So, a bijection is given as follows: let the new element representing the +1 be 0 (yes, 0 isn’t a natural number to me, now stop that argument already). A bijection (from set of natural numbers to the set also with 0) would be 1->0, 2->1, 3->2, …, n->n-1,… where n is, well…, any natural number.
Taking this one step further, now let us “prove” that X+X=X*2=X. Again, suppose that X is the cardinality of the set of natural numbers. Let the new X elements be a1, a2, a3,…. Now, a bijection (from the set of size X to the set of size 2X) is given by 1->1, 2->a1, 3->2, 4->a2, and so on, with n->(n+1)/2 if n is odd, and n->a(n/2) if n is even, for all natural numbers. (Ok, I admit set notation looks cooler, but I’m typing.)
As an attempted Mathematician, let me enthusiastically take this just one step further (the hour’s getting late!). The next thing in the series is to prove that X^2=X. This is cooler.
All right. Time out. I just thought of something to whine about infinities in general. The main problem with infinities is that unlike finities (is there such a word? O.o), inductive approaches do not work. For example:
1=1+0+0+0+0… = 0+1+0+0+0…=…=0+0+0+0+…=0 (?).
Clearly, there is a step in the middle where the induction just fails. Hence, infinities tend to refute everyday logic of things like… … … … … … … … … an irritating thing.
Back to proving X^2=X: now let us consider the set of positive rational numbers, given in (sometimes improper) fractions. A rational number is one expressible in terms of a/b, where a and b are integers. Hence, a positive rational number can be expressed as a/b, where a and b are rational numbers. Yay! Now we shall arrange the rational numbers in a square with a top left hand corner and the other corners at infinity. Being a nitpickish person, I shall arrange it as such:
1/1 1/2 1/3 1/4 …
2/1 ---- 2/3 ---- …
2/1 ---- 2/3 ---- …
3/1 3/2 ---- 3/4 …
4/1 ---- 4/3 ---- …
. . . .
. . . .
. . . .
Now, imagine a grasshopper from Bremen , Germany
1 2 9 10 …
4 3 8 11 …
5 6 7 12 …
16 15 14 13 …
. . . .
. . . .
. . . .
Now we formulate our bijection in the order of the leaps our dear grasshopper makes:
1->1/1, 2->1/2, 3->2/1*, 4->3/1, 5->3/2, and so on. Now, every rational number has a corresponding natural and vice versa. Therefore, by our definition, X=X^2. Wonderful.
*since 2/2 has been nitpickily replaced by a dash for being the same as 1/1
Readers are like, totally encouraged to attempt to prove that X=XX (see tetration), and owing to the awesomeness of Conway , a->n->3, a->n->4 (see Conway
Honestly, the original purpose of this post was to raise a contradiction I convinced myself of, but that has since been resolved. Nevertheless, it would probably be interesting to figure out where the mistake lies. Let the hunt for the fatal flaw begin.
Cantor’s diagonalisation argument (omg finally on to the point of the post) can roughly be stated as follows:
The power set of a set S refers to the set of all subsets of S (or so I believe). So, illustrating with a finite example, the power set of {1,2} contains the null set {}, {1}, {2}, and finally {1,2}, the set itself.
The argument concludes that the power set of any infinite set is larger than the set itself.
For the sake of convenience and easy reading, we shall assume that the infinite set involved is the set of natural numbers.
Firstly, a bijection between the power set and a real number (haven’t really thought much about this yet, might be wrong) between 0(inclusive) and 1(exclusive) can be established as follows:
Let such an arbitrary real number be denoted as 0.abcdefghijklmnopqrstuvwxyzα…, written in binary. Now let a subset of the natural numbers S map, in the bijection to the following real number: 0.abc… where a=0 if 1 is not an element of S and 1 otherwise, b=0 if 2 is not an element of S and 1 otherwise, and so on. Therefore, both the set of real numbers from 0 to 1 (yes, I might regret saying this) and the power set of the set of natural numbers are of the same cardinality.
Now let us prove that the cardinalities of the power set of the set of natural integers exceeds that of the set of natural numbers. We approach this via a proof by contradiction.
Suppose otherwise; i.e. there exists a bijection between the set of natural numbers and the power set of the set of natural numbers. Then there exists a bijection between the set of real numbers between 0 and 1 and the set of natural numbers. Let the bijection (from natural numbers to the power set) be as follows:
1->0.…
2->0.…
3->0.…
and so on, where (naturally) represents either 0 or 1.
However, we observe that there is a real number between 0 and 1 that is definitely not equal to one of the real numbers already bijected to. A possible real number can be expressed as: 0.b1b2b3b4b5b6b7…, where b1 is NOT() (binary operators!), b2 is NOT(), b3 is NOT() and so on. Hence, the bijection is not a bijection, i.e. there exists a contradiction, meaning our original assumption of a bijection between the set of natural numbers and its power set is impossible.
Intuitively, a corollary is that 2^X>X, since the cardinality of the power set is larger than the cardinality of a set itself.
However, if we consider the powers of 2, we notice that there are an infinite number of perfect powers of 2, and for convenience, we shall call the infinity Y. Now, 2^Y and Y are not equal, meaning that this set is smaller than 2^Y, by the above argument. However, if we map n->2^n, we notice that the number of powers of 2 and the number of integers are in fact equal since the bijection holds. Therefore, 2^Y indeed equals the number of natural numbers. However, if we consider the first k powers of 2, there are 2^k natural numbers smaller than or equal to the largest power of 2 mentioned. By extension, the number of natural numbers is roughly equal to 2^Y (arguably with a factor of 2). But that gives 2^Y>=X/2=X=Y. Clearly, something is wrong somewhere. Can you find the fatal error?
My solution is given in (hopefully) the same colour as the background below. Highlight to review.
Whoever said that the power set of an arbitrary infinity X had cardinality 2^X? The combinatorial argument for this does not appear to hold for infinities as it is inductively based. See what I mean about infinities being irritating and counterintuitive?
