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.

Do NOT follow this link or you will be banned from the site!