A Buggy Argument to #real numbers = #natural numbers
July 21, 2010 4 Comments
A real line is a line whose points correspond to real numbers.
1. Let be the number of points on a real line
2. Let be the number of points in [-1,1] interval over a real line.
3. Let be the number of points in (-1,1) interval over a real line.
4. Let be the number of points in a unit square.
seem to be infinitely greater than
and
seem to be some twoish greater than
.
seem to be quite a lot bigger than
. Georg Cantor created a paradise, a theory of sets which suggests
. 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 be the set of natural numbers and
be the set of all the subsets
. Cantor proved that
. 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, and arrived at a mapping
as described below. One may trivially show that
exists and hence
is a bijection between
and
( i.e.
)!!
Description of :
i=1;n=1;
while(1) {
-
be the set of all those set
with
;
-
for each
{
-
map
to n;
- n++;
}
-
map
- i++;
}
Few example mapping by the function :-
{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,
Now given that Cantor gave a clean proof for , something has to be wrong with argument given above which claims
. What is it?
Note that I have detailed as an infinite loop mapping. One may instead detail
as a function which takes a set
as input and outputs
, a natural number.
PS: You can post your doubts/comments/solutions in the comments section or mail them to me.



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.
The argument is of course wrong
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.
The function is not defined on subsets of N of infinite cardinality
@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).