Exploring Infinity Part 2 :Cantor’s Diagonal Argument

In the previous article, we have discussed the types of infinity and how some of them are larger than the others. We have also seen how sizes of countable infinity goes against our intuition when we say that the total number of distinct even integers (or odd integers) are equal to the total number of integers .

APPROACH USED IN CANTOR’S ARGUMENT

.We have formally proved two infinite sets A and B to be equal only when:

  • Each and every element of set A has a corresponding unique element on the other set B.
  • Each and every element of set B has a corresponding unique element on the other set A.

Cantor’s argument proves that although the  entire set of whole number W exhaustively corresponds to some real number in R, the converse is not true i.e. there is always infinitely many real numbers that cannot be related to an integer/natural number even for a finitely chosen interval.

CANTOR’S DIAGONAL ARGUMENT

Let us establish a random correspondence between whole numbers and real numbers :

cantor 1

The sequence of real numbers cannot be put in order due to the fact, it cannot be determined exactly what comes after real 0. Not 0.0000001! Not 0.00000000000000000000000000000000001. (We can continue putting trillions and googolplexes of zeroes in between and there will still be room for more). Hence, the chosen sequence has to be random.

Let us generate an unique real number X  from the finite list of real numbers with a specific rule Q, such that formed X is not included in the given list of real numbers. For this, we go with a diagonal approach that ensures that the number chosen is, in fact, unique and most definitely not included in the list i.e. the number X is formed by selecting one number in decimal place , such that the position chosen is unique to that real number in the list. The best way of ensuring that we choose an unique place is proceeding diagonally from the left i.e. for real no corresponding to 0, we choose its tenth’s place. For 1, we choose it’s   hundredth place and so on .

We will also add one to each of the chosen digit during finding the value of X, and if it is 9, we will consider it as 0. Picturing this visually will help.

cantor 2

The new number X, obtained is  0.097233. X doesn’t correspond to any whole number on the list. If we apply this diagonal rule Q to any list of real and whole number pairing , we will always obtain an unique real number. If the above list was infinitely long, we would be able to still come up with  X that is different from the list.

WHY THE NUMBER X IS UNIQUE AND GUARANTEED TO BE DIFFERENT FROM THE EXISTING LIST

The number X formed through rule Q applied on the list, is characterized by uniqueness with respect to the list of real numbers. The unique position chosen for each rule number, during the formation of X in the list ensures that two numbers never clash with each other. Adding a 1( 0 for 9), ensures that the X formed will most definitely be different, at least to that number.

Let us consider a smaller list of two reals 2.34 and 5.63. To obtain an unique number different from the entire list, we should do something that makes it different from each of the numbers individually first  .i.e. we take a decimal place and add one to it.

Thus, we can say that by this rule, 0.40 obtained is most definitely different from 2.34(we take 0.30 from 2.34 and add one to the digit 3). Similarly, 0.04 is different from 5.63.After forming the numbers, we add them up and since, the places chosen is unique to each number, adding them doesn’t interfere with their place values.

Adding the two, 0.40 + 0.04 = 0.44 , we get a number different from both 2.34 and 5.63. This can be applied to lists of any length.

RULES

When we say, “rule” we are essentially referring to a special kind of function, the one used in the above argument to generate a different and unique real number from an existing set. The approach we have used is the left diagonal approach where we proceed from the left. For a finite list, we need not stick to this rule and can come up with many more and still be able to find different real numbers.

TOTAL RULES POSSIBLE

For a set of 3 whole-real pairs, the places chosen respectively are tenths, hundredth, thousandth to generate a unique number. We could also go with configurations hundredth, tenth, thousandth and thousandth,tenth, hundred  i.e. all permutations of tenths, hundredth, thousandth = 3! = 6 unique numbers.  For 5 whole-real pairs, there are 5! methods. Besides, there can be theoretically infinite such rules applicable for each of these pairs. Thus, we can see, that for lists of sizes as low as 3, we have left out an infinite number of real numbers. Thus, we can conclude that real numbers is way larger than the countably infinite sets.

To end this article on an interesting note, there are as many numbers existing between two arbitrarily chosen real numbers as there are on the entire real number line! This means unlike the integer number line, the real number line can be resolved till infinity.

Thinking in terms of geometry, a countably infinite set is a collection of infinite number of points plotted individually, whereas the set of real number is a line. For a chosen interval of real numbers, geometrically it is therefore, a line segment. The above proof tells that a line will always resolve to a larger numbers of infinite points, that a set of infinite points plotted individually. Also, by the above proof, a line and line segment has equal number of points(through the bijection principle).

In the following article(s), we shall discuss an interesting example that re-explores the bizarre nature of infinite through two examples : -Banach-Tarski Paradox and Hilbert’s Hotel Paradox.

Advertisements

2 thoughts on “Exploring Infinity Part 2 :Cantor’s Diagonal Argument

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 )

Google+ photo

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

Connecting to %s