[Math] Natural and Real sets of numbers, which one is bigger than another

integersnatural numbersreal numbers

From the years ago, it has always been this question in my mind which a teacher of high school talked about in a class but I never found it's correct answer.

We have set of natural numbers ${1,2,3,4,5,…}$ and set of real numbers.

We have two concepts to prove that these sets of numbers are equal or smaller than each other.

Concept 1

If we choose any number from the natural numbers, we can choose a number from real set of number, so they are equal.

Concept 2

Natural numbers are subset of the real numbers, so natural numbers set is smaller than set of real numbers.

Which concept is correct?

Best Answer

The renown Cantor's Diagonal Argument shows that although we can easily map the set of natural numbers to the set of real numbers in many ingenious ways, we can never find a surjection $f:\mathbb N\rightarrow\mathbb R$. A surjection here means $f(\mathbb N)=\mathbb R$. Instead, as Cantor proved, we can do no better than $f(\mathbb N)\subset\mathbb R$.

This means that any counting function $f:\mathbb N\rightarrow\mathbb R$ assigning enumerations to the real numbers such that the real numbers can be written as a list $\mathbb R=\{f(1),f(2),...\}$ is impossible. The set $\{f(1),f(2),...\}$ can contain some of the real numbers, but not all.

In this sense, which is called cardinality (see link in comments), the set of real numbers is bigger.


There are various proofs of Cantor's Diagonal Argument. One is to prove the more general statement that given a set $A$, the so-called Power Set $\mathcal P(A)$ containing all subsets of $A$ always has bigger cardinality than $A$.

So assume we have found an enumeration $f:\mathbb N\rightarrow\mathcal P(\mathbb N)$. Then $f(n)$ is some subset of $\mathbb N$ as for instance $\{2,4,6,8,...\}$. If $f$ were surjective it should be possible for any element $B\in\mathcal P(\mathbb N)$ to find some $b\in \mathbb N$ with $f(b)=B$.

Consider $B\in\mathcal P(\mathbb N)$ defined as $$ B=\{n\in\mathbb N\mid n\notin f(n)\} $$ Assume we have found $b$ such that $f(b)=B$. Suppose $b\in B=f(b)$, but then the above definition implies that $b$ should not be an element of $B$. So we must have $b\notin B=f(b)$, but then the above definition tells us that $b$ should be in $B$. Contradiction! For any function $f$ the set $B$ above is well defined, but as just shown no element of $\mathbb N$ can map to it. We must have $f(\mathbb N)\subset\mathcal P(\mathbb N)\setminus B$, so in particular $f(\mathbb N)\neq\mathcal P(\mathbb N)$ for any choice of $f$.


Let us connect the above argument to the real numbers. We can make a simple mapping $g:\mathcal P(\mathbb N)\rightarrow\mathbb R$ that takes a given subset of $B=\{n_1,n_2,...\}\in\mathcal P(\mathbb N)$ of natural numbers and maps it to $$ g(B)=10^{-n_1}+10^{-n_2}+...=\sum_{n\in B}10^{-n} $$ For instance $B=\{2,4,6,8,...\}$ would map to $g(B)=0.010101\overline{01}$. This mapping is injective meaning that different sets $B$ map to different real numbers $g(b)$. So $\mathcal P(\mathbb N)$ has the same cardinality as the subset $g(\mathcal P(\mathbb N))$ of the real numbers meaning that we have the cardinality inequalities $$ |\mathbb N|<|\mathcal P(\mathbb N)|=|g(\mathcal P(\mathbb N))|\leq|\mathbb R| $$ In fact a different choice of $g$ shows that $|\mathcal P(\mathbb N)|=|\mathbb R|$, but that is a different story.