The Frivolous Theorem of Arithmetic

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:

M = 10!!!!!!!!!!!!!!

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:

A = \{ x \in \mathbb{N} : x \leq M \}

B = \mathbb{N} - A = \{ x \in \mathbb{N} : x > M \}

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:

|A| = M

And the cardinality of the set of natural numbers is:

|\mathbb{N}| = \aleph_0

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:

F(x) =\left\{\begin{array}{rl} M - x & \text{if } 0 < x \leq M + 1 \\ x & \text{if } x > M + 1\end{array}\right.

And according to the properties of cardinalities:

|B| = \aleph_0

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.


2 Comments on “The Frivolous Theorem of Arithmetic”

  1. Computation theory comes to your help in this case. An infinite set can be put into bijection with \mathbb{N} if, and only if, there exist a program to enumerate the elements of your infinite set. That is, the set can have an infinite number of elements, but countably so.

  2. Also, I’m not so sure that fundamental mathematics as we know them doesn’t tell us things about the space of überlarge numbers. For example, almost no überlarge number is prime as the density of primes is approximatively \frac{n}{\ln n} around n (see here). I’m sure there is a lot to be discovered yet, far beyond the mere extension of what we know about “normal” numbers (that is, smallish).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s