# Hi! I’m Yen.  I remember Georg Cantor once sai…     Hi! I’m Yen.  I remember Georg Cantor once said that “The essence of mathematics lies in its freedom”

Cantor’s diagonal argument: The best known example of an uncountable set is the set R of all real numbers, Cantor’s diagonal argument shows that this set is uncountable.

In his 1891 article, Cantor considered the set T of all infinite sequences of binary digits (i.e. consisting only of 0es and 1s). First, he constructively shows the following theorem:  If s1, s2, … , sn, … is any enumeration of elements from T, then there is always an element s of T which corresponds to no sn in the enumeration. To prove this, given an enumeration of arbitrary members from T, like e.g.

• s1 =(0,0,0,0,0,0,0,…)
• s2 =(1,1,1,1,1,1,1,…)
• s3 =(0,1,0,1,0,1,0,…)
• s4 =(1,0,1,0,1,0,1,…)
• s5 =(1,1,0,1,0,1,1,…)
• s6 =(0,0,1,1,0,1,1,…)
• s7 =(1,0,0,0,1,0,0,…)

He constructs the sequence s by choosing its nth digit as complementary to the nth digit of sn, for every n. In the example, this yields:

• s1=(0,0,0,0,0,0,0,…)
• s2=(1,1,1,1,1,1,1,…)
• s3=(0,1,0,1,0,1,0,…)
• s4=(1,0,1,0,1,0,1,…)
• s5=(1,1,0,1,0,1,1,…)
• s6=(0,0,1,1,0,1,1,…)
• s7=(1,0,0,0,1,0,0,…)
• s =(1,0,1,1,1,0,1,…)

By construction, s differs from each sn, since their nth digits differ (highlighted in the example). Hence, s cannot occur in the enumeration.  Based on this theorem, Cantor then uses an indirect argument to show that:  The set T is uncountable. He assumes for contradiction that T was countable. Then (all) its elements could be written as an enumeration s1, s2, … , sn, … .

Applying the above theorem to this enumeration would produce a sequence s not belonging to the enumeration. This contradicts the assumption, so T must be uncountable.