# 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. Sep 13, 2017 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. Sep 13, 2017 at 2:08
• Published on April 1? Sep 13, 2017 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..."
– user169852
Sep 13, 2017 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. Sep 14, 2017 at 7:00

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 Sep 13, 2017 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. Sep 13, 2017 at 10:36
• Wow. Do you know of any resources to $\kappa<\lambda \implies 2^\kappa<2^\lambda$ not being provable in ZFC that would be understandable to someone who only had one graduate class in set theory? (We covered ordinals/cardinals, but only the concept of models of set theory, not actually looking at them)
– Alan
Apr 5 at 15:41
• @Alan Not really, sadly. The excellent book Set theory for the working mathematician treats Martin's Axiom (which in conjunction with $\neg\mathsf{CH}$ implies $2^{\aleph_0}=2^{\aleph_1}$ despite $\aleph_0<\aleph_1$) towards the end, and starts from little prerequisites, but is rather dense. Additionally there are some nice survey articles on $\mathsf{PFA}$ (which outright implies $2^{\aleph_0}=2^{\aleph_1}=\aleph_2$), but I don't know how accessible there are. Apr 5 at 15:44
• The issue is that in order to say much about what $\mathsf{ZFC}$ can't prove, we really need to talk about how to build models of $\mathsf{ZFC}$ (admittedly this can be avoided in Godel-type situations, but this isn't one of those); specifically, we need forcing. Now there are many well-written expositions of forcing out there, including Chow's, but it's quite difficult to master no matter how you cut it. Apr 5 at 15:47

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.