Delving into Infinities [Linear Orderings Part 1]

Recently, me being in my senior year of high school, I have being writing many mission statements. In questions similar to "Why math" or "Favorite instances in mathematics" I have written about Linear Orderings to the point that the admissions officers might assume that I just mugged up the name of one area of math to sound fancy. In actuality my mathematical journey has been long and varied; however the reason the particular math circle session stands out to me is because it was the first time I genuinely enjoyed being stuck in a problem. Currently, that's one of my favourite parts of mathematics. Yes- being stuck is frustrating however it feels more like the experience of running a marathon (or a swimathon in my case) where the struggle is immense but the feeling of satisfaction after the race makes you forget the pain and convinces you that the distance was fun. Moreover, getting stuck causes me to wiggle stretch and really push my brain to its limits, which I find just not possible if not challenged adequetely.

 Lets get into the math itself. The most famous example used to teach infinities is the Hilbert's Hotel. The premise is really simple: there is a hotel with an infinite number of rooms numbered 1, 2, 3, 4, 5....

Q. Suppose all the rooms are occupied. However, one more person desires to stay at the hotel. Normally you would turn him away but how can you use infinity to your advantage?

Well, similar to how in grade school the largest number infinity was always usurped by infinity plus one, we shift all the guests one room to the right. 1 goes to 2, 2 goes to 3, etc. After this process, the room one is free to put the new guest into. (Note we can use the same process for any finite number k of guests that show up by shifting everyone from a to room a+k)

 Q. Now, instead of finite number of guests show up?

In this case, you can't use the same strategy as before- you'll end up having a guy walk up to infinity (which is not possible). Thus, we have to approach using a different strategy. The strategy we come up with is the following, shift every person to the room with double their current room number. The person in room 1 goes to room 2, the person in room 2 goes to room 4, 3 goes to 6, etc. This leaves us with all the odd numbered rooms to occupy the infinite new guests in. More specifically looking at the situation, we can see that the even numbers are an bijection of the natural numbers. That is to say we can simply map all the natural numbers without gaps onto the even numbers by doubling and vice verca. However, one infinity may also appear larger than the other. Take the natural numbers' set and remove the even numbers' set; we are still left with all the odd numbers. This would indicate that the natural numbers are a larger set than the even numbers contradicting the mapping argument. However, both are true as in subtracting the two gives a non null set yet both sets are of the same size. This is some of the intricacies of infinite sets. 

Q.  Is it possible to map integers to natural number. In the infinite line of people what if it doesn't start neatly from 0 then 1, 2, 3, ... \(\infty\) however expands infinitely in both the direction with no way to start?

When trying to approach the positives and negatives separately you yield no results. Starting from the natural numbers then the negatives makes sense however -1 would be infinitth number (not allowed). Thus, we make use of the same anchor: 0. 0 then 1 then -1 then 2 then -2, etc. In essence all positive numbers n map to 2n-1 and negative numbers -n map to 2n.

Q. We talked about mapping the integers numbers to the natural numbers. What about other sets, can we map rational numbers to the natural numbers. In other words, if an infinite number of busses (bus 0, bus 1, bus 2, bus, 3, bus 4, ...) show up with each an infinite number of people (bus 1 seat 1, bus 1 seat 2,...) 

Firstly, we note that the setup with an infinite number of infinite buses is equal to the rational number case. This is due to the fact that the bus numbers and the seat numbers are similar to the p and q of the r = p/q form of rational numbers. So how do we map rationals to natural numbers? Well, at first it may seem impossible not only are all the real numbers included in the rationals even if you label\[a \rightarrow 1 \]\[b \rightarrow 2\], there will be an unlisted number between them \[c = \frac{a+b}{2}\]. However, to map the sets, we force properties of natural numbers. So how do we list all the passengers across all the infinite buses? Can we?

The answer is yes, and the trick is gorgeous. Instead of going bus by bus — which would trap us forever on bus $0$ — we go diagonally. Arrange all the pairs $(n, m)$ in a grid: rows are bus numbers, columns are seat numbers. Then trace a diagonal path through the grid:

\[
(0,0) \to (0,1) \to (1,0) \to (2,0) \to (1,1) \to (0,2) \to (0,3) \to \cdots
\]

Every pair $(n, m)$ gets hit eventually. There is no hiding in this grid — trace far enough along the diagonal path and you'll reach any seat on any bus. This means we can assign every rational number a natural number: its position in this diagonal walk. And that is a bijection. The rationals are countable.

So here we are: the natural numbers, the integers, and the rationals are all the same size of infinity. The technical word for this size is $\aleph_0$ (aleph-null). Any set that can be put in bijection with $\mathbb{N}$ is called countably infinite. And one could be forgiven for thinking that all infinities must be countable. After all, we've been incredibly creative — diagonals, doublings, zigzags — and it's always worked. Surely every infinite set can be listed?

And then Cantor walked in and ruined everything. Beautifully.

 

The Real Numbers: An Infinity Too Large to List

Can we list all real numbers between $0$ and $1$? Suppose — just suppose — that we could. Then we'd have some list:
\[
r_0 = 0.d_{00}\, d_{01}\, d_{02}\, d_{03} \cdots
\]
\[
r_1 = 0.d_{10}\, d_{11}\, d_{12}\, d_{13} \cdots
\]
\[
r_2 = 0.d_{20}\, d_{21}\, d_{22}\, d_{23} \cdots
\]
\[
\vdots
\]
where $d_{ij}$ denotes the $j$-th decimal digit of $r_i$. Cantor's move is now almost theatrical in its simplicity. Construct a new number $x = 0.x_0 x_1 x_2 \cdots$ by going down the diagonal and changing each digit: let $x_i$ be any digit different from $d_{ii}$ (say, $x_i = 5$ if $d_{ii} \neq 5$, else $x_i = 3$). Now:

 

• $x$ differs from $r_0$ in the first decimal place.  
• $x$ differs from $r_1$ in the second decimal place.
• $x$ differs from $r_n$ in the $(n+1)$-th decimal place.

So $x$ is not on the list. But $x$ is a real number between $0$ and $1$. Contradiction. No matter how cleverly you list the reals, there will always be a real number that escapes the list. The real numbers are uncountable.

There are strictly more real numbers than natural numbers. This is the first time we've encountered two infinities of genuinely different sizes.

This is where most courses stop. But for us, this is merely the warm-up. In the next post we move from asking how many elements a set has to asking something far more architectural: in what order do they sit?