# Is there a bijection between the reals and naturals?

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.

• It's certainly a misinterpretation. $|\mathbb{R}| > |\mathbb{N}|$ is a proven fact. – MathematicsStudent1122 Sep 13 '17 at 2:07
• The naturals are countable by definition, the reals are uncountable by many arguments. Since they don't have the same cardinality, they can't have a bijection. – Kaynex Sep 13 '17 at 2:08
• Published on April 1? – Bram28 Sep 13 '17 at 2:08
• As the article itself says, "Cantor was able to show that the real numbers can’t be put into a one-to-one correspondence with the natural numbers." This article is talking about something else entirely. See the sidebar about halfway down the page starting with "Briefly, p is the minimum size of a collection of infinite sets of the natural numbers..." – Bungo Sep 13 '17 at 2:13
• @Kaynex: that’s over-complicating things a bit — the reals being uncountable means by definition that they have no bijection with the naturals, so that fact itself is the answer here, it doesn’t need to be put together with any other ingredients. – Peter LeFanu Lumsdaine Sep 14 '17 at 7:00

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.

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!

• Also worth linking, mathoverflow.net/questions/168125/short-proof-of-frak-p-t – Asaf Karagila Sep 13 '17 at 7:13
• This answer is very educational and gives a much broader understanding of the topic than the accepted answer. +1 for not trying to define the two exotic cardinals, but giving the background information on why the assumption in OP is mistaken instead. – glaux Sep 13 '17 at 10:36
• Was thinking should it not be aleph _1 instead of 2^{aleph_0} just a tiny addition to an good answer – Willemien Sep 20 '17 at 11:25
• @Willemien No - $\aleph_1$ and $2^{\aleph_0}$ are potentially quite different. What I wrote is correct. – Noah Schweber Sep 20 '17 at 13:19