Everything is $\aleph_1$
Apology and Updates
Okay… Before we get into the post itself – I want to address the elephant in the room.
I have not written a post in about four months (which is miles away from the goal I had in mind when I started the blog), and for that I am sorry! I thought I could document my qual-prep process in the blog, but the blog ended up being a way for my brain to obsess over a single topic for sufficiently longer than it needed, which put the entire time-sensitive endeavor in jeopardy. So I took a break (albeit, much longer than initially anticipated) – but I’ve got some good news!
I have, as of me typing this now, passed both of my analysis and algebra qualifying examinations at the University of Missouri! I am taking a chill semester right now to figure out what it is that I want to do in research. For my first semester, I am currently enrolled in Topology, Complex Analysis and Algebraic Geometry, and those classes are splendid – I look forward to writing more about them soon.
This is going to be a two part post. In this first part, I will outline a problem statement and talk about its resolution and consequences, which are interesting by their own rights. In the second part, I will talk about how my pursuit to write a blog post about one of my alternative solutions led me down a rabbit hole of string rewriting systems and generalized fractal generation.
Problem statement
It was a simple problem in my Topology homework. It went as follows:
For each item below, prove that the cardinality of the pairs of sets are the same
(a) $\mathbb{R}$ and $(-1,1)$
(b) $[0,1]\times[0,1]$ and $[0,1]$
Now really, this question has nothing to do with topology itself. This was a part of my first homework assignment filled with such standard questions as a way to jog our memory on some undergraduate analysis. But there is really pretty math to be seen and enjoyed here. As always you are more than welcome to attempt to solve the problem before coming back to read more.
Resolution
To the uninitiated, this is surprising especially because in both cases, one is a strict subset of the other!
With infinite sets – in order to show that two sets are of equal cardinality, we can not actually bother counting the elements. Instead we employ certain techniques that will get us the equality in a formal sense.
Say we have two sets $A$ and $B$, and we want to show that they have the same cardinality. The first technique is to find a bijection (injection + surjection) between $A$ and $B$. Injectivity (or one-to-one) shows us that every element of $A$ is uniquely identified with some element of $B$ (thus $|A| \leq |B|$), and surjectivity (or onto) tells us that every element of $B$ is mapped to by some element of $A$ (So $|A| = |B|$). In fact, a stronger result is true: Two sets $A$ and $B$ have the same cardinality if and only if there exists a bijection between them.
Another technique that is just as powerful is to find an injection from $A$ to $B$, and a different one from $B$ to $A$. This is equivalent to proving that both sets have the same number of points because an injection uniquely associates a single element in the codomain to an element in the domain. Thus if there is an injection from $A$ to $B$, then $|A| \leq |B|$, and with the other injection we will have $|B| \leq |A|$, giving us $|B| = |A|$.
Part (a)
Part (a) is usually resolved using a standard trick by considering the function
$$f(x) = \tan\left(\frac{\pi}{2}x\right)$$
and notice that $\lim_{x\to \pm 1} f(x) = \pm \infty$, and $f(x)$ is an injective monotonically increasing function in $(-1,1)$; and is thus a bijection.
While this example works and establishes the bijection, it is certainly not my favorite proof of this fact. My favorite proof of this fact is very visual, and I first encountered it in my first ever proof writing class during my undergraduate studies when my professor mentioned it to me as an off-handed side note after class. This bijection too has a closed form, namely
$$\varphi(x) = \frac{x}{\sqrt{1+x^2}}$$
which you can verify to be an injection and a surjection using some pretty mundane and arguably ugly algebra; but there is a more visual way to realize this bijection.
We start with the bottom half of a circle in $\mathbb{R}^2$ centered at $(0,1)$ of radius $1$. Now for any $r \in \mathbb{R}$, consider the line connecting $(r,0)$ and $(0,1)$. This line intersects the circle at say a point $p = (p_1, p_2)$. Define $\varphi(x) = p_1$1. Visually, this looks as follows
Now isn’t that so visually beautiful!? The injectivity is realized by the fact that the line connecting $(r,0)$ and $(0,1)$ is the unique line normal to the circle at the point of intersection, and the surjectivity is realized easily from the above illustration. This sort of a “projection” is called a steriographic projection (or at least a version of it) and I will (maybe?) write about it some day. So that is part (a) done.
Part (b)
For part (b), there is also a standard solution, and then there is a more funky solution that I prefer (which will eventually lead us into the rabbit hole of fractal generation, in part 2 of this post). The standard solution is as follows. Instead of providing a bijection (which is in some sense kind of ugly since it breaks up into a whole lot of cases), we will provide and injection from $[0,1] \to [0,1]\times [0,1]$ and then a different injection from $[0,1]\times [0,1] \to [0,1]$.
Of course, $[0,1]$ naturally injects into $[0,1]\times [0,1]$ via the inclusion map $f_1(x) = x$, and so $|[0,1]| \leq |[0,1]\times[0,1]|$. It is the other injection that is interesting. Given a point $(x,y) \in [0,1]\times[0,1]$ write $$x = 0.a_1a_2a_3\dots \quad \text{ and } y = 0.b_1b_2b_3\dots$$
with $a_i,b_i \in \{0,1,\dots,9\}$. Now of course, we have to be careful and disallow infinite tails of $9$’s because we might then consider $0.4999999\dots$ and $0.5000000\dots$ as different elements, when they are the same. So, if we see an element with an infinite tail of $9$’s we will replace it with its counterpart having an infinite tail of $0$’s. With this convention in hand, we consider $$\varphi(x,y) = 0.a_1b_1a_2b_2\dots$$
Visually, this looks like
Where of course, the numbers in the example have an infinite tail (of zeroes if you so insist). We are interweaving the decimal digits of $x$ and $y$ and the resulting real number has to be a unique value since if we have two decimal expansions equal
$$0.a_1b_1a_2b_2\dots = 0.c_1d_1c_2d_2\dots$$
then it must be that $a_i = c_i$ and $b_i = d_i$ (notice that our assumption of removing the infinite tails of $9$ becomes relevant here!), and this tells us that the points on the square we started with had to have been the same! Thus $\varphi$ is injective, and so $|[0,1]\times[0,1]| \leq |[0,1]|$ and our desired equality holds!2
This is how the map looks when applied to each point of the unit square.
This allows us to realize that this map is more or less local with respect to the $x$ coordinate. This is because given a point with $x$-coordinate $0.a_1a_2\dots$ the most it can change to is $0.a_19a_1\dots$ and it moves to the right, or $0.a_10a_2\dots$ and it moves to the left. In either case, this point in the square is mapped to a point that is within $0.01$ units of its $x$-coordinate. So while on the onset, this might look like a map that could be super chaotic– all it is, is a simple rotation (depending on the $y-$value) and projection down to the $x$-axis.
Before we wrap up this part, I just want to highlight a consequence of what we have achieved. But in order to motivate this consequence, we need to do a little bit of extra work involving three realizations.
In part $(a)$ we showed that there is a bijection between $\mathbb{R}$ and $(-1,1)$ – but this can be extended to $[-1,1]$. This is because for any given $n \in \mathbb{N}$, if we let $\epsilon_n = 1/n$ and consider the circle to have center $\left(0, 1+\epsilon_n\right)$ and of radius $1+\epsilon_n$ and do the same sort of $\varphi$ map we would prove that there is a bijection between $\Lambda_n = \left(-1- \epsilon_n, 1+ \epsilon_n\right)$ and $\mathbb{R}$. Since $n$ was arbitrary to begin with, we can let it go off to infinity, and notice that this will give us a bijection between $\mathbb{R}$ and $\lim_{n \to \infty} \Lambda_n$. Notice also that
$$\lim_{n \to \infty} \Lambda_n = \bigcap_{n=1}^{\infty} \Lambda_n = [-1,1]$$
[$\Lambda_j$ is contained inside $\Lambda_{j-1}$ for any $j$, and so $\Lambda_{n} = \Lambda_n \cap \Lambda_{n-1} \cap \dots \cap \Lambda_1$. So if we let $n$ get larger and larger, $\Lambda_n$ gets smaller and smaller, and in the limit, we only contain elements that are in the intersection of all the $\Lambda_n$]
Thus there is a bijection $\varphi$ from $\mathbb{R}$ to $[-1,1]$. Now if we consider the map $$\phi(x) = \frac{1}{2}[\varphi(x) + 1]$$
$\phi$ is a bijection from $\mathbb{R}$ to $[0,1]$.Define $\Phi: \mathbb{R} \times \mathbb{R} \to [0,1]\times[0,1]$ given by $\Phi(x,y) = (\phi(x), \phi(y))$, this is a bijection between $\mathbb{R} \times \mathbb{R}$ and $\mathbb{R}$. You can think about this as, given any $x$ in the $x$-axis and $y$ in the $y$-axis, $\phi(x)$ tells which vertical strip on the unit square you belong, and $\phi(y)$ tells you which horizontal strip on the unit square you belong; and thus $\Phi(x)$ corresponds uniquely to the point of intersection of these two strips. It is easy to assert from this point that $\Phi$ is a bijection.
Visually this looks like:
- Recall that two sets have the same cardinality if and only if there is a bijection between them. So from part $(b)$ we know that there is some bijection $\psi$ between $[0,1]\times[0,1]$ and $[0,1]$.
We are finally ready to state the consequence.
$$\text{The map } \phi^{-1}\circ \psi\circ \Phi: \mathbb{R}\times \mathbb{R} \to \mathbb{R} \text{ is a bijection!}$$
Since it is a composition of bijections. Thus $\mathbb{R} \times \mathbb{R}$ and $\mathbb{R}$ have the same number of points!3.
I have, at this point, rambled on more than I had initially intended to; and I think this is a pretty good stopping point for part 1. In part 2 we will explore a technique to generate fractals using these things called L-systems and hopefully try to understand the overarching concept of a Semi-Thue system.
verify that the closed form of $\varphi$ presented in the post is indeed what $p_1$ is. ↩