Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Cantor's diagonal argument

Note: in order to fully understand this article you may want to refer to the set theory portion of the table of mathematical symbols.

Cantor's diagonal argument is a proof devised by Georg Cantor to demonstrate that the real numbers are not countably infinite. (It is also called the diagonalization argument or the diagonal slash argument or the diagonal method [Kleene].)

Contrary to what many mathematicians believe, the diagonal argument was not Cantor's first proof of the uncountability of the real numbers, but was published three years later. His original argument did not mention decimal expansions, nor any other numeral system.

Since this technique was first used, similar proof constructions have been used many times in a wide range of proofs. These are also known as diagonal arguments by analogy with the argument used in this proof.

1 Real numbers

Cantor's original proof shows that the interval [0,1] is not countably infinite.

The proof by contradiction proceeds as follows:

• (1) Assume (for the sake of argument) that the interval [0,1] is countably infinite.
• (2) We may then enumerate all numbers in this interval as a sequence, ( r₁, r₂, r₃, ... )
• (3) We already know that each of these numbers may be represented as a decimal expansion.
• (4) We arrange the numbers in a list (they do not need to be in order). In the case of numbers with two decimal expansions, like 0.499 ... = 0.500 ..., we chose the one ending in nines. Assume, for example, that the decimal expansions of the beginning of the sequence are as follows:

• (5) We shall now construct a real number x in [0,1] by considering the k^th digit after the decimal point of the decimal expansion of r_k.

The digits we will consider are indicated in bold and illustrate why this is called the diagonal proof.

• (6) From these digits we define the digits of x as follows.

• if the k^th digit of r_k is 5 then the k^th digit of x is 4
• if the k^th digit of r_k is not 5 then the k^th digit of x is 5

For the example above this will result in the following decimal expansion.

• (7) The number x is a real number (we know that all decimal expansions represent real numbers) in [0,1] (clearly).
• (8) Hence we must have r_n = x for some n, since we have assumed that ( r₁, r₂, r₃, ... ) enumerates all real numbers in [0, 1].
• (9) However, because of the way we have chosen 4's and 5's as digits in step (6), x differs in the n^th decimal place from r_n, so x is not in the sequence ( r₁, r₂, r₃, ... ).
• (10) This sequence is therefore not an enumeration of the set of all reals in the interval [0,1]. This is a contradiction.
• (11) Hence the assumption (1) that the interval [0,1] is countably infinite must be false.

It is a direct corollary of this result that the set R of all real numbers is uncountable. If R were countable, we could enumerate all of the real numbers in a sequence, and then get a sequence enumerating [0, 1] by removing all of the real numbers outside this interval. But we have just shown that this latter list cannot exist. Alternatively, we could show that [0, 1] and R are the same size by constructing a bijection between them. This is slightly awkward to do, though possible, for the closed interval [0, 1]; for the open interval (0, 1) we might use defined by .

Politics	Business	Finance

Topics: Cantor's Diagonal Argument Set Numbers Real Proof Decimal...

---

Cantor setThe Cantor set introduced by German mathematician Georg Cantor, is a remarkable construction involving only the real numbers between zero and one. The Cantor set is defined by repeatedly removing the middle thirds of line segments. One starts by removing Cantor Fitzgerald SecuritiesCantor Fitzgerald Securities is an investment bank specializing in bond trading. It owns the eSpeed network. Its New York office, on the 101st-105th floors of One World Trade Center, lost 685 employees in the September 11, 2001 Terrorist Attack, considera Cantor dustCantor dust named after the mathematician Georg Cantor, is the two-dimensional version of the Cantor set. In the limit, starting from a square the construction produces a set with an infinite number of square sections each having zero area — the sum of al Cantor's diagonal argumentSet theory Note: in order to fully understand this article you may want to refer to the set theory portion of the table of mathematical symbols. Cantor's diagonal argument is a proof devised by Georg Cantor to demonstrate that the real numbers are not cou Cantor-Bernstein-Schroeder theoremIn set theory, the Cantor-Bernstein-Schroeder theorem named after Georg Cantor, Felix Bernstein, and Ernst Schroder, states that, if there exist injective functions f : A → B and g : B → A between the sets A and B then there exists a bijective f CantorThe word Cantor can mean more than one thing: Cantor is another name for a Hazzan, a member of the Jewish clergy Cantor is the title of a member of a student society who is the main singer at a cantus Famous people named "Cantor" include: Eddie Cantor, si Cantor function Cantor's theorem Cantor's first uncountability proof Cantor space Cantor distribution Cantor (crater)