1
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Neither. Can you form a bijection from the reals to the natural? $\endgroup$ – PepperSausage Aug 26 '14 at 19:55
  • $\begingroup$ @PepperSausage what do you mean by bijection? $\endgroup$ – Enthusiastic Engineer Aug 26 '14 at 19:57
  • 3
    $\begingroup$ This is a famous question. Maybe try reading at this link and searching on mathSE a little. There have been many questions on this. en.m.wikipedia.org/wiki/Cardinality $\endgroup$ – ClassicStyle Aug 26 '14 at 20:03
  • 1
    $\begingroup$ @EnthusiasticStudent It can be proved that for a list of real numbers, where they have a specific place in the sequence (e.g. $2.5$ is $1^{st}$, $\pi$ is $2^{nd}$, etc.) there will be a real number missing from the list. This is roughly what PepperSausage means by making a bijection between them. So there are more real numbers than natural numbers. $\endgroup$ – Jam Aug 26 '14 at 20:11
  • 1
    $\begingroup$ @TonyK: Concept 1 appears to be what Cantor's Diagonal Argument refutes. Concept 2 works so well for finite sets, so maybe it is somewhat subtle, I don't really know anymore :) After all one gets so used to these concepts. $\endgroup$ – String Aug 26 '14 at 21:22
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.