Is there a bijection between the reals and naturals?

Question

I found this pop math article saying that there was a paper published last year that proved that the cardinalities of the reals and naturals are equal. Is this true or is it a misinterpretation of the result? If it is true, I'm dying to know what the bijection between the two sets is.

Answer 1

This could have been written clearer. I think the culprit is the section:

The problem was first identified over a century ago. At the time, mathematicians knew that “the real numbers are bigger than the natural numbers, but not how much bigger. Is it the next biggest size, or is there a size in between?” said Maryanthe Malliaris of the University of Chicago, co-author of the new work along with Saharon Shelah of the Hebrew University of Jerusalem and Rutgers University.

In their new work, Malliaris and Shelah resolve a related 70-year-old question about whether one infinity (call it p) is smaller than another infinity (call it t). They proved the two are in fact equal, much to the surprise of mathematicians.

If read quickly, this suggests that $\mathfrak{p}$ and $\mathfrak{t}$ refer to the cardinality of the set of reals and the set of naturals, respectively. This is not the case, though.

---

So what sort of thing are $\mathfrak{p}$ and $\mathfrak{t}$, then?

$\mathfrak{p}$ and $\mathfrak{t}$ are what are known as cardinal characteristics of the continuum (CCCs) - cardinals which are (i) known to be uncountable, and (ii) measure how big a set of reals has to be to have some "universality" property.

For example, one simple CCC is the dominating number, $\mathfrak{d}$: this is the smallest cardinality of a set $F$ of functions $\mathbb{N}\rightarrow\mathbb{N}$ such that for each $g:\mathbb{N}\rightarrow\mathbb{N}$ there is some $f\in F$ such that $f(n)>g(n)$ for all but finitely many $n$ (we say $f$ dominates $g$). Clearly $\mathfrak{d}$ is at most continuum (since that's how many functions $\mathbb{N}\rightarrow\mathbb{N}$ there are in the first place), and it's also uncountable: if $f_i:\mathbb{N}\rightarrow\mathbb{N}$ for $i\in\mathbb{N}$, the function $$h(i)=\sum_{j\le i}f_j(i)=f_1(i)+f_2(i)+...+f_i(i)$$ is not dominated by any of the $f_i$s.

Another simple CCC is the bounding number, $\mathfrak{b}$. This is "dual" to $\mathfrak{d}$ (in a sense that can be made precise): $\mathfrak{b}$ is the smallest size of any family $G$ of functions $\mathbb{N}\rightarrow\mathbb{N}$ such that no single $f$ dominates all functions in $G$. Again, $\mathfrak{b}$ is clearly at most continuum, and is uncountable since any countably many functions can be dominated by a single function (think about the construction of the $h$ above).

Now cardinal arithmetic is notoriously badly behaved - even basic facts about it tend to be undecidable in ZFC. For example, ZFC doesn't even prove that $\kappa<\lambda \implies 2^\kappa<2^\lambda$. So it's really exciting to see ZFC-provable facts about infinite cardinalities; conversely, it's important to understand when certain questions can't be resolved in ZFC alone. In this context, what we care about is comparing CCCs. We can think about it this way: the two trivial CCCs are $\omega_1$ ("the smallest size of an uncountable set of reals") and $2^{\aleph_0}$ ("the smallest size of a set containing all the reals"); and in between we have the interesting CCCs. Of course, if $\omega_1=2^{\aleph_0}$ then the whole picture collapses; this is the continuum hypothesis, and it's consistent with ZFC. At the far other end, it's known that we can separate certain CCCs - e.g. that it is consistent with ZFC that $\mathfrak{b}<\mathfrak{d}$. (An interesting topic is separating multiple CCCs simultaneously - see this MO question.)

This leaves open:

What equalities between CCCs can we prove in ZFC? What inequalities can we disprove?

As an example of the latter, ZFC proves that $\mathfrak{b}\le\mathfrak{d}$ - we can't have $\mathfrak{b}>\mathfrak{d}$ (this is a good exercise). More broadly, the collection of disprovable inequalities between many CCCs (not including $\mathfrak{p}$ and $\mathfrak{t}$, though) is summed up in Cichon's diagram. Malliaris and Shelah proved a result of the former kind - showing that two CCCs were in fact equal. My understanding is that this type of result is much, much rarer even in general, and of course in this particular case it was extremely surprising (see Shelah's quote in the linked article).

Of course, I haven't tried to define $\mathfrak{p}$ and $\mathfrak{t}$; the definitions are there, but they're a bit technical, and more to the point it's hard to see why someone would care. A good analysis of them is not something I can fit into an MSE answer; but hopefully what I've written explains a bit about where this sort of thing can come from!

Answer 2

You're misinterpreting what the article says. Malliaris and Shelah did prove that two cardinals are equal -- or rather, that two definitions of particular cardinals happen to define the same cardinal -- but the cardinals they proved equal are not $|\mathbb N|$ and $|\mathbb R|$.

This brief article from the links at the bottom does offer the relevant definitions:

The cardinal $\mathfrak p$ is the minimum cardinality of a collection $\mathcal F$ of infinite subsets of $\mathbb N$, all of whose finite intersections are infinite, such that there is no single infinite $A\subseteq \mathbb N$, such that every element of $\mathcal F$ contains $A$ except for a finite error. The cardinal $\mathfrak t$ is defined similarly, except one only quantifies over families $\mathcal F$ which are totally ordered by containment modulo a finite error.