The Frivolous Theorem of ArithmeticPosted: November 25, 2009
Steven Pigeon recently introduced to us the Frivolous Theorem of Arithmetic in his Harder, Better, Faster blog. As a complement, I shall present a rigorous, rather useless but quite educative proof of this theorem which will serve as a base for more inquiries in the internal structure of natural numbers.
The theorem reads as follows:
Almost all natural numbers are very, very, very large.
First and foremost, this yields the question of what is considered very, very, very large. In fact, the notion of a number being large or very large is inexistant in mathematics and irelevant to the internal structure of numbers. Hence, for the purpose of this proof, we shall choose a überlargeness threshold that we shall call M, a natural number. In fact, you can be an eccentric fellow and say 1 is already large enough for you and so be it. On the other end, maybe the excruciatingly, humongously large number:
is a number you envison as almost big (the Google calculator accepts to calculate 10! but dutifuly refuses to calculate 10!!; how unfortunate !). Regardless, the proof still holds. Let A and B be two sets such that:
Where A is the set of natural numbers smaller than or equal to the threshold and B the set of numbers we consider to be very, very, very large. To prove the theorem, we have to compare the cardinalities (the number of elements) of both sets. First, we note that the cardinality of of A is:
And the cardinality of the set of natural numbers is:
Which reads aleph-null, the first transfinite cardinal number who denotes the cardinality of countably infinite sets, i.e. sets with elements which can be counted individually, even if there is an infinite number of them. Since there exists a one-on-one relation (bijectivity) between N and B, which is of the form:
And according to the properties of cardinalities:
Meaning there is an infinity of numbers larger than M, a number chosen to be überlarge and we can thus conclude that almost all natural numbers are very, very, very large. This proof led us to an important insight on the internal structure of natural numbers: since each natural number has a succesor which also has a succesor (1 has succesor 2, which has succesor 3, ad nauseam), no natural number can be used to express the cardinality of this set. We can’t simply say there is an “infinite” number of natural numbers, as this is too imprecise. In fact, there is an injective relation between the reals and the naturals but there can be no bijective relation between the two sets, meaning that the cardinality of the naturals is “smaller” than the cardinality of the reals. Intuitively, the cardinality of reals is also infinite, meaning we have two or more types of “infinity”. This will be the subject of a follow-up post.