A Buggy Argument to #real numbers = #natural numbers

A real line is a line whose points correspond to real numbers.
1. Let N_1 be the number of points on a real line
2. Let N_2 be the number of points in [-1,1] interval over a real line.
3. Let N_3 be the number of points in (-1,1) interval over a real line.
4. Let N_4 be the number of points in a unit square.

N_1 seem to be infinitely greater than N_2 and N_2 seem to be some twoish greater than N_3. N_4 seem to be quite a lot bigger than N_3. Georg Cantor created a paradise, a theory of sets which suggests N_1 = N_2 = N_3 = N_4. Now this is something hard to digest at the first sight, but that’s the way it is.

Later on, Russell proved that the Cantor’s theory of sets is inconsistent i.e. it’s axioms are self-contradictory. This doesn’t mean that the above mentioned equalities do not hold, one may use ZFC theory of sets ( which is immune to various paradoxes which Cantor’s theory faced ) to arrive at the same result. Though ZFC hasn’t witnessed a paradox yet and is widely believed to be consistent, we still do not know whether it is a consistent theory of sets or not since Godel‘s second incompleteness theorem states that the consistency of a formal system S can be proved within the system only if it is inconsistent ( or equivalently we can say that if a system is consistency then it’s consistency can not be proved within the system) and hence forbids us from proving the consistency of ZFC within ZFC.

Let \mathbb{N} be the set of natural numbers and M be the set of all the subsets \mathbb{N}. Cantor proved that |\mathbb{N}| < |M|. With this proof he also contributed a technique known as Diagonalization, very useful tool in theoretical computer science.
Other day I was playing with the sets, \mathbb{N}, M and arrived at a mapping f:\mathbb{N} \rightarrow M as described below. One may trivially show that f^{-1} exists and hence f is a bijection between \mathbb{N} and M ( i.e. |\mathbb{N}| = |M| )!!

Description of f:
i=1;n=1;
while(1) {

  • A be the set of all those set S \subseteq \mathbb{N} with \displaystyle\sum_{s \in S}s=i;
  • for each Z \in A{

    • map Z to n;
    • n++;

    }

  • i++;

}

Few example mapping by the function f:-
{1}->1,
{2}->2,
{1,2}->3, {3}->4,
{1,3}->5, {4}->6,
{2,3}->7, {1,4}->8, {5}->9,
{1,5}->10, {2,4}->11, {1,2,3}->12, {6}->13,
{1,6}->14, \ldots

Now given that Cantor gave a clean proof for |\mathbb{N} < |M|, something has to be wrong with argument given above which claims |\mathbb{N}| = |M|. What is it?
Note that I have detailed f as an infinite loop mapping. One may instead detail f as a function which takes a set Z as input and outputs f(Z), a natural number.

PS: You can post your doubts/comments/solutions in the comments section or mail them to me.

4 Responses to A Buggy Argument to #real numbers = #natural numbers

  1. Rajeev says:

    The argument is wrong. |M| = 2 ^ |N| , hence i and n cannot iterate over all M.
    There are as many numbers in N and N^2 , but infinitely many more in a^N.

  2. amehta says:

    The argument is of course wrong :D
    In case |M| = 2 ^ |N|, any ways i can iterate over all M.
    The puzzle asks you to find one element of M which is not mapped to any element of N with the above mapping.

  3. Yuri says:

    The function is not defined on subsets of N of infinite cardinality

  4. amehta says:

    @Yuri: That’s right. Function doesn’t map sets of infinite cardinality to any element in the set of natural numbers. For eg. Set of all even numbers is not mapped (this is because sum of elements in this set is infinite).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.