What property of the reals prevents us from constructing a bijection between the reals and the natural numbers?

Question

I have seen the diagonal proof that implies such a construction is impossible, but I do not understand what property the reals possess that prevents this construction from happening.

I am asking because I'm trying to understand what it really means for there to be multiple sizes of infinity.

EDIT: The answers I'm getting are not quite the kind I am looking for. I'm looking for a more abstract answer. If we have two collections of things, one being the size of the natural numbers (call it A) and one being the size of the real numbers (call it B), what property does B possess that A does not that (intuitively) prevents a bijection from being constructed between the two.

Answer 1

It would be the supremum axiom: The fact that for every bounded above set there exists a least upper bound, i.e. supremum. This implies the existence of irrational numbers within the reals.

For example, $\sqrt{2}$ would be the supremum of the bounded above set $[0,\sqrt{2})$.

For you to have an intuition of what is going on, you can think of the natural/rational number line as a number line full of holes whereas the real number line is absolutely continuous. The holes in the natural number line are obvious (for example between $1$ and $2$ we have $1.1, 1.5,\ldots$) and those in the rational number line are the ones left by the irrational numbers.

Answer 2

When you construct an infinite decimal in the diagonlization argument, the least upper bound axiom of $\mathbb{R}$ guarantees that the infinite decimal you've constructed is actually a real number; if you tried to perform the diagonlization argument with $\mathbb{Q}$, that would be your stumbling block.

Answer 3

The underlying truth is the following:

Given any set $X$ there is no surjective map $f: \>X\to{\cal P}(X)$.

This means that ${\cal P}(X)$ has "essentially more elements" than $X$, say $2^n$ compared to the $n$ elements of $X$, if $X$ is finite.

Proof. Consider an arbitrary map $f: \>X\to{\cal P}(X)$. This map assigns to each $x\in X$ a subset $A_x\subset X$. Now look at the special set $$Q:=\{x\in X\,|\, x\notin A_x\}\quad \in{\cal P}(X)\ .$$ I claim that $Q\notin f(X)$; hence $f$ is not surjective. Assume to the contrary that $Q=f(x_*)$ for some $x_*\in X$. We now argue about the membership of $x_*$ in $Q$. By definition of $Q$ and of $x_*$ one has $$x_*\in Q\quad\Leftrightarrow\quad x_*\notin f(x_*)\quad\Leftrightarrow \quad x_*\notin Q\ ,$$ which is absurd.$\quad\square$