logicset-theory
Is there another way to proof that there can't be a bijection between reals and natural not using Cantor diagonal?
I was wondering about diagonal arguments in general and paradoxes that don't use diagonal arguments. Then I was puzzled because I couldn't think another way to show that the cardinality of the reals isn't the same as the cardinality of naturals.
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!
Yes. Cantor set has cardinality of the reals (continuum).
As Cantor Set $\subset \mathbb R$ it's cardinality is at most $|\mathbb R|$ and as it is uncountable it's reasonable that we can't have found a contradiction to "Continuum Hypothesis" and found a cardinality between $|\mathbb Q|$ and $|\mathbb R|$ so it reasonable that Cantor set has the cardinality of the reals.
But to seal the deal we need a bijection between Cantor set and $\mathbb R$.
Following a comment by Arturo Magidin:
If $x \in [0,1]$ then $x = \sum\limits_{i=0}^{\infty} b_i 3^{-i}$ for some sequence of $b_i$ where each $b_i=0,1,2$. If we disallow infinite tailing $0$s then this sequence is unique. This is just writing $x$ is decimal in base $3$. But where all terminating decimals are replaced with tailing $2$s.
Likewise if $y \in [0,1]$ then $y = \sum\limits_{i=0}^{\infty} c_i 2^{-1}$ for some sequence of $c_i = 0,1$. And if we disallow infinite tailing $0$s 0 this sequence is unique. This is just the base $2$ decimal.
If $x = \sum b_i 3^{-i}$ is in the Cantor set then none of the $b_i = 1$. That is because we removed the middle third of all segments and $b_k = 1$ means $\sum\limits_{i=0}^{k-1} b_i 3^{-i} < x < \sum\limits_{i=0}^{k-1} b_i 3^{-i} + 2*3^{-k}$ would mean $x$ is in some middle third.
So let $f(\sum b_i 3^{-i}) = \sum c_i 2^{-i}$ where if $b_i = 0$ then $c_i = 0$ and if $b_i = 2$ then $c_i = 1$. $f$ is a bijection between the Cantor set and $[0,1]$.
but on the other hand, a set of measure 0 that has a bijection with R looks very strange as well.
Ah.... not really. It seems counterintuitive because ... to have measure $0$ no two points can be connected in the set so $\color{red}{\text{for any point there must be a measurable distance before the "next" one}}$ and there can only be countably many such points. But that clause in $\color{red}{\text{red}}$ is completely erroneous and is based on a naive concept of numbers must "follow each other". Uncountable numbers don't.
And the Cantor set exists merely to be a simple counter example.
Best Answer
One way is through the use of measure theory. The measure of the unit interval $[0,1]$ is $1$, while the measure of any countable subset of the reals is $0$. This is enough to demonstrate that $[0,1]$ is uncountable, for if it were countable then its outer measure would have to be $0$.
The outer measure of a general subset $A \subset \mathbb R$ is defined as
$$m^*(A) = \inf \Big\{ \sum_i \ell(I_i) : A \subset \bigcup_i I_i\Big\}$$
where $(I_i)_i$ is any countable collection of intervals, $I_i = [a_i, b_i]$ for some reals $a_i < b_i$ for each $i$, and $\ell(I)$ is the length of the interval, defined as $\ell(a,b) = b - a$. What this definition means is: cover the set $A$ by (at most countably many) intervals, however you may like, and sum the lengths of those intervals. The (limiting) smallest possible total length is what the outer measure of $A$ is.
See here for a proof that a countable set has outer measure zero, and see here for a proof that the unit interval $[0,1]$ has outer measure $1$.