This entry will be a tad shorter than what we had so far, and will have mostly additional things that should be discussed regarding infinity. Starting off with a debt I owe you from the last entry, so without further ado, let's kick this off!

Aleph - from zero to hero:

Last time we learned what is א‎₀ - the countable infinity - really is: it's the smallest cardinality of infinity, and represents infinities that can still be put in an ordered list. However, we did see that there are uncountable infinities, and we also know that the next step from א‎₀ is simply called א (aleph). But, what does it exactly mean? What determines the aleph-cardinality of a set? We know that the smallest aleph cardinality is the countable infinity, which makes it easier to determine if a certain sat is א0 or not, but what about uncountable infinite sets? How do we know if the cardinality of ℝ is א, or א‎₂, א‎₃, or something else maybe? What distinguishes the infinite number of uncountable infinities from each other?

Well, in order to delve into that, we first need to know what a power-set is. Its definition is a tad confusing:

Let A be a set. The power set of A is the set of all subsets contained in A, and is notated P(A). That is, if we use the set-builder notation that we saw in entry number 2: P(A) = {S | S⊆A}. Note that a power set is always a set of sets.

For example, if A = {1,2,3}, then P(A) = { Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }. Note that I bolded out Ø (the empty set) and {1,2,3} (the set A itself). That is because, it is important to note that the power set of any set will always have the empty set and the original set itself as elements. If you look back at the 2nd entry you will see that I mentioned the empty set is contained in every set (i.e it is a subset of every set), and every set is also a subset of itself. All the rest of the elements are non-empty, strict subsets of the original set A. Now, how are power sets important to our topic? Because of their cardinality. Let's say that |A| = n. Then |P(A)| = 2ⁿ, that is, 2 to the nth power. Why is that? Well, there's a simple answer for that using combinatorics. But we haven't discussed that yet, so we'll leave it at that for the moment. We can already see though, that for the set A = {1,2,3} that we defined earlier, |A| = 3 and |P(A)| = 2³ = 8. Still don't believe me? Try thinking of different sized sets and write down their power sets. You'll see for yourselves.

So, the question we now need to ask ourselves, what is |P(ℕ)|? Is it 2^א‎₀? Yes, that is exactly what it is.

But wait...

In the previous entry, we discussed the continuum hypothesis, which suggests that there doesn't exist a set whose cardinality is strictly between א‎₀ and א. Does that mean that 2^א‎₀ = א? Well, that is kinda where the continuum hypothesis was born: Georg Cantor theorized that there's nothing that's strictly between א‎₀ and א, and we know that |P(ℕ)| = 2^א‎₀, but infinity being weird as we know it is, it wouldn't be trivial to just assume that 2^א‎₀ > א‎₀. Luckily, we can prove that P(ℕ) is uncountable, with a very similar strategy to the one we used when showing that ℝ is uncountable:

First, assume by contradiction that P(ℕ) is countable. Therefore, the elements of P(ℕ) can be put in an ordered list. Now, what we will do, is translate each element of P(ℕ), which is a certain set of naturals - into an infinite sequence of ones and zeroes, in the following manner:

Let S∈P(ℕ) and let n∈ℕ. If n∈S, then the nth digit in the sequence representing S will be 1. Otherwise, it will be 0. Confusing, I know, so here's a few examples:

• S = {0,1,2,3}, the sequence will be: 1111000000...
• S = {1,3,7}, the sequence will be: 010100010000...
• S = {0,2,4,6...} (all evens), the sequence will be: 10101010...
• S = Ø, the sequence will be: 00000000...
• S = ℕ, the sequence will be: 11111111...

So, let's say we have such an infinite list of infinite sequences that allegedly represent all the sets in P(ℕ). Same as we did with ℝ, we will construct a "rogue" sequence that cannot appear on the list. Looking at the first digit of the first sequence on the list, if it's 1 then the first digit in our rogue sequence will be 0, and vice versa. Then the 2nd digit in our rogue sequence will be similarly determined by the 2nd digit of the 2nd sequence on the list, and so on and so forth. That would give us the exact same result as we got when proving that ℝ is uncountable, resulting in the conclusion that P(ℕ) is also uncountable, and therefore 2^א‎₀ > א‎₀. Q.E.D.

Now, given that the continuum hypothesis suggests that there's nothing strictly between א‎₀ and א, that would mean that (allegedly, assuming the continuum hypothesis is correct) 2^א‎₀ = א. Generalizing this proposition, we can say: let S be an infinite set, such that |S| = א‎_n for some n∈ℕ. Then |P(S)| = 2^א‎_n = א‎_n+1. That is commonly known as the "Generalized Continuum Hypothesis". Yes, mathematicians are horrendously unoriginal when it comes to naming stuff.

In fact, it is possible to show a bijection between P(ℕ) and ℝ, but it's a pretty long proof that uses several other theorems and concepts which we haven't discussed (such as binary representations of numbers and the Cantor-Schreder-Bernstein theorem), so we'll skip it for now. In any case, that is how you determine the aleph cardinality of an uncountable set: if you have an uncountable set, say S, and you can find a bijection between S and P(ℕ), then |S| = 2^א‎₀. Otherwise, if you can find a bijection between S and P(P(ℕ)) (which is a set of sets of sets), then |S| = 2^2א‎₀ (which would be equal to א‎₂ according to the continuum hypothesis). Otherwise, go to P(P(P(ℕ))), and so on.

If Chuck Norris has one infinity and you have 2 infinities, Chuck Norris has more infinities than you:

Well, not really; you actually have the same amount. Depending on the cardinality of course. OK, maybe that wasn't a perfect analogy... but I like Chuck Norris jokes! Anyway, allow me to explain what I'm getting at here; assume you have 2 countably infinite sets, and Chuck Norris has 1 countably infinite set. Now, let's say you perform a union between your two sets and create one big set. Who has the bigger set, you or Chuck? You both have sets of the same size! Reason being, that a union of 2 countably infinite sets is still countably infinite, i.e א‎₀. Let us prove that.

There is one important thing to note before starting this proof, though; we all know, since entry number 3, that if there exists a bijective function between 2 sets, then these sets are equivalent. However, that conditioning works both ways: for any two equivalent sets, there exists a bijection between them. That bijection might not be an explicit function with a specific formula (well, the sets don't have to be sets of numbers to begin with), but there is always a way to have a surjective, one-to-one matching between the elements of two equivalent sets. That is a very powerful theorem: if we start off with the knowledge that 2 sets are equivalent, we can just go off with there being a certain bijection between them even if we have no idea what that bijection actually is.

Anyway, let's get to it. Assume we have 2 countably infinite sets, A and B. Let's also assume that A∩B = Ø, i.e the two sets have no elements in common (when 2 sets have no elements in common, they are said to be "disjoint").

Seeing as |A| = |B| = |ℕ| = א‎0, there exists a bijective function f: ℕ→A and a bijective function g: ℕ→B.

Now, define: C = A∪B, and a function h:ℕ→C, by:

• If x is even, then h(x) = f(x/2).
• If x is odd, then h(x) = g((x-1)/2).

We will prove that h is bijective, thus showing that C is a countably infinite set. Firstly, it's easy to see that h is total, as it is well defined for every x∈ℕ. Now to prove that it is injective:

• Let x,y∈ℕ such that h(x) = h(y). We will prove that x=y.
• Option 1: x and y are even.
  • By definition of h that means that h(x) = f(x/2), h(y) = f(y/2).
  • That is, f(x/2) = f(y/2).
  • Seeing as f is a bijection, it has to be injective, which means that necessarily x/2=y/2.
  • Multiplying both sides by 2 yields x=y.
• Option 2: x and y are odd.
  • By definition of h that means that h(x) = g((x-1)/2), h(y) = g((y-1)/2).
  • that is, g((x-1)/2)=g((y-1)/2).
  • Seeing as g is a bijection, it has to be injective, which means that necessarily (x-1)/2=(y-1)/2.
  • Multiplying both sides by 2 and adding 1 yields x=y.
• Option 3: x is even and y is odd, without loss of generality. We will show why this is impossible.
  • Assume by contradiction that it is possible for x to be even and y to be odd while h(x) = h(y).
  • By definition of h that means that h(x) = f(x/2), h(y) = g((y-1)/2).
  • That is, f(x/2) = g((y-1)/2).
  • We know that A and B are disjoint. We also know that, f(x) is an element in A while g(y) is an element in B, for all x,y∈ℕ.
  • Since f(x/2) = g((y-1)/2), we actually get that there is an element that belongs in both A and in B. That is a contradiction! Therefore, our assumption must be false, which means that it is impossible for x to be even and y to be odd while h(x) = h(y).

All possible cases have been covered, therefore we have proven that h is injective. Q.E.D. Now to prove it's surjective:

• Let y∈C. We will show that there exists a x∈ℕ such that h(x)=y.
• Option 1: y∈A.
  • Seeing as f is a bijection, it has to be surjective, which means that there exists some x∈ℕ such that f(x)=y.
  • Choosing z=2x, we get h(z) = h(2x) = f(2x/2) = f(x) = y, as required.
• Option 2: y∈B.
  • Seeing as g is a bijection, it has to be surjective, which means that there exists some x∈ℕ such that g(x)=y.
  • Choosing z=2x+1, we get h(z) = h(2x+1) = g((2x+1-1)/2) = g(x) = y, as required.

All possible cases have been covered, therefore we have proven that h is surjective. Q.E.D. Now we see that h is indeed bijective, which means that |C| = |ℕ| = א‎0 - which teaches us that the union of 2 countably infinite sets is also countably infinite.

Now, interesting thought: what happens if we have 3 countably infinite sets? Say, A, B and D? We already know that the union of A and B, which we called C, is countably infinite. So the union of A, B and D, will actually be the union of C and D (which we can call E), which is, well, exactly the same as the union of A and B which we now proved to be countably infinite. So the union of 3 countably infinite sets is still countably infinite. The major plot twist, however, comes when we reach 4 countably infinite sets!

Just kidding, it's still just the same. And same for 5, 6, 7, or however many sets you want to throw into that union. In fact, the union of a countably infinite number of countably infinite sets, is still countably infinite.

So, if Chuck Norris has one countably infinite set, and you have a countably infinite number of countably infinite sets... Chuck Norris still has just as much infinity as you. He's just that much of a badass.

Some more sorcery and witchcraft:

The bijection between the naturals and the integers that we saw last time is pretty tame compared to what we're going to see right now. I mean, really, you're about to witness some real Elder-Wand-level stuff. Let's start by seeing what an interval is, which is pretty intuitive. First, we have 2 basic types of intervals: open and closed, notated (a,b) and [a,b] respectively (a<b necessarily). What these things mean, is:

• The open interval (a,b) is the set of all reals that are strictly between a and b, ergo {x∈ℝ | a < x < b}.
• The closed interval [a,b] is the set of the numbers a, b, and all reals that are between a and b, ergo {x∈ℝ | a ≤ x ≤ b}.

Other than that, there's semi-closed intervals (or semi-open, both names are equivalent) - [a,b) and (a,b]. The number that's next to the square bracket is included in the interval, the other one isn't. Easy.

Now, here comes the part with the Luciferian black magic: every interval - open, closed or semi-closed - is equivalent to the entire set of reals. No matter how small. Even |(0.001,0.002)| = |ℝ|. Let's go ahead and prove the equivalence of ℝ to (0,1) for example. It's a pretty long proof though, so here goes:

Define f:(0,1)→ℝ by:

• If 0 < x < 0.5, then f(x) = (x - 0.5)/x.
• If 0.5 ≤ x < 1, then f(x) = (x - 0.5)/(1 - x).

Easy to see that f is total, given that it's defined for all x∈(0,1). Let's show it's injective:

• Let x,y∈(0,1) such that f(x) = f(y). We will show that x=y.
• Option 1: 0 < x,y < 0.5.
  • By definition of f, that means that f(x) = (x - 0.5)/x, f(y) = (y - 0.5)/y.
  • That is, (x - 0.5)/x = (y - 0.5)/y.
  • Multiplying both sides by xy and simplifying yields xy - 0.5y = xy - 0.5x.
  • Subtracting xy from both sides and multiplying by -2 yields x=y, as required.
• Option 2: 0.5 ≤ x,y < 1.
  • By definition of f, that means that, f(x) = (x - 0.5)/(1 - x), f(y) = (y - 0.5)/(1 - y).
  • That is, (x - 0.5)/(1 - x) = (y - 0.5)/(1 - y).
  • Multiplying both sides by (1 - x)(1 - y) and simplifying yields: x - 0.5 - xy + 0.5y = y - 0.5 - xy + 0.5x.
  • Adding (0.5 + xy) to both sides yields x + 0.5y = y + 0.5x.
  • That is, 0.5x = 0.5y. Multiplying both sides by 2 yields x=y, as required.
• Option 3: 0 < x < 0.5, 0.5 ≤ y < 1, without loss of generality. We will show why this is impossible.
  • Assume by contradiction that it is possible.
  • Therefore, by definition of f, we get: f(x) = (x - 0.5)/x, f(y) = (y - 0.5)/(1 - y).
  • That is, (x - 0.5)/x = (y - 0.5)/(1 - y). That is only possible when x=y=0.5.
  • However we know that x < 0.5. We have reached a contradiction, therefore it is impossible for the equality f(x) = f(y) to hold while 0 < x < 0.5, 0.5 ≤ y < 1.

We have covered all possible options, so we deduce that f is injective. Now to prove it's surjective:

• Let y∈ℝ. We will show that there exists some x∈(0,1) such that f(x) = y.
• Option 1: y < 0.
  • Consider x = -1/(2y - 2). Note that this is a positive expression.
  • Since y < 0, then necessarily 2y - 2 < -2, so 1/(2y - 2) > -0.5, meaning 0 < -1/(2y - 2) < 0.5.
  • Therefore f(x) = f(-1/(2y - 2)) = (-1/(2y - 2) - 0.5)/(-1/(2y - 2)) = 1 + (2y - 2)/2 = 1 + y - 1 = y.
• Option 2: y ≥ 0.
  • Consider x = (y + 0.5)/(y + 1). Note that y + 0.5 < y + 1, so (y + 0.5)/(y + 1) < 1.
  • Simplifying x, we get x = 1 - 1/(2y + 2).
  • Since y ≥ 0, then 2y + 2 ≥ 2, so 1/(2y + 2) ≤ 0.5, meaning 1 - 1/(2y + 2) ≥ 0.5.
  • Therefore f(x) = f(1 - 1/(2y + 2)) = (1 - 1/(2y + 2) - 0.5)/(1 - (1 - 1/(2y + 2))) = (0.5 - 1/(2y + 2))/(1/(2y + 2)) = ...
  • ... = ((2y + 2 - 2)/(4y + 4))/(1/(2y + 2)) = (y/(2y + 2))/ (1/(2y + 2)) = (y/(2y + 2))/(2y + 2) = y.

All options have been covered, therefore f is surjective. Finally, we deduce that f is bijective, and therefore |(1,0)| = |ℝ|. Q.E.D.

Now, that was a long proof with a pretty complicated function. But I think that the thought of every small interval being equivalent to the entire x-axis of real numbers, is pretty baffling. As I said, infinity is absolutely mind-blowing.

If you didn't read the proof, though, here's another way of looking at it. Consider the function f(x) = tan(π(x - 0.5)). Yes, we haven't discussed trigonometric functions such as tan yet, but here's the graph of this function (when defined as f:ℝ→ℝ):

Look at the interval (0,1), or any other interval (n,n+1) on the picture above: we can see that the red graph in that interval is unbounded from above nor from below - it shoots up to infinity and down to negative infinity, which is to say that it is surjective. We also see that no 2 points on that interval have the same y value, therefore it is also injective. In other words, the x values in the interval (x,y) are injectively and surjectively mapped onto ℝ. The image, by the way, is taken from Desmos - an online graphing calculator, which pretty much saved my butt in calculus.

In summary:

So, that closes our saga on infinity, which started pretty much at the very first entry. I hope I managed to pass some of my love for this subject, and maybe even math as a whole, onto you. It's truly fascinating in my opinion and there's always more to learn - but I think I'll leave it at that for now. In future entries I will discuss some other topics in math; calculus, combinatorics, and maybe other things too. So thanks for sticking with me so far, and hope to see you in future entries too! As always, your feedback will be appreciated and questions will gladly be answered.