Cantor's diagonal argument: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Michael Hardy
imported>Subpagination Bot
m (Add {{subpages}} and remove any categories (details))
Line 1: Line 1:
{{subpages}}
'''Cantor's diagonal argument''' provides a convenient proof that the set <math>2^{\mathbb{N}}</math> of subsets of the [[natural number]]s (also known as its [[power set]]) is not [[countable set|countable]]. More generally, it is a recurring theme in [[computability]] theory, where perhaps its most well known application is the negative solution to the [[halting problem]].
'''Cantor's diagonal argument''' provides a convenient proof that the set <math>2^{\mathbb{N}}</math> of subsets of the [[natural number]]s (also known as its [[power set]]) is not [[countable set|countable]]. More generally, it is a recurring theme in [[computability]] theory, where perhaps its most well known application is the negative solution to the [[halting problem]].


Line 18: Line 20:


It follows that <math>\psi \not= \phi_i </math> for any <math>i</math>, and it must therefore correspond to a set not in the range of <math>F</math>. This contradiction shows that <math>2^{\mathbb{N}}</math> cannot be countable.
It follows that <math>\psi \not= \phi_i </math> for any <math>i</math>, and it must therefore correspond to a set not in the range of <math>F</math>. This contradiction shows that <math>2^{\mathbb{N}}</math> cannot be countable.
[[Category:CZ Live]]
[[Category:Mathematics Workgroup]]

Revision as of 19:58, 25 September 2007

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

Cantor's diagonal argument provides a convenient proof that the set of subsets of the natural numbers (also known as its power set) is not countable. More generally, it is a recurring theme in computability theory, where perhaps its most well known application is the negative solution to the halting problem.

Informal description

The original Cantor's idea was to show that the family of 0-1 infinite sequences is not countable. This is done by contradiction. If this family is countable then its members can be enumerated or enlisted. Such a list gives a table of digits, like in the following arbitrarily chosen example:

0, 1, 0, 1, 0, ...
1, 1, 1, 1, 0, ...
1, 0, 1, 0, 0, ...

Now, we construct a sequence s = (s1, s2, s3, ....), which is not on the list while still, for all i. This is done as follows. Take to be different from the first digit of the first member on the list. In our example the digit is 0 (in boldface) and so is defined to be 1. Take to be different from the second digit of the second member on the list (in our example ). Generally, define as different from the n-th digit of the n-th entry on the list. In other words, the sequence s = (s1, s2, s3, ....) contains "the complement in " of the diagonal of our table. It follows that that the sequence s itself is not on the list, since it is different from every member by the definition. The list was supposed to contain all the 0-1 sequences. The contradiction shows that such sequences can not be enumerated (or they are not countable).

The role of the diagonal clearly explains the name of the argument.

Formal argument

To prove that the family of all subsets of is not countable, we associate to any set a function by setting if and , otherwise. Conversely, every such function defines a subset. Observe also that every such function corresponds to a 0-1 sequence and vice-versa.

If power set is countable, there is a bijective map , that allows us to assign an index to every subset S. In other words, all the functions can be enumerated as . Assuming this has been done, we proceed to construct a function that is not in this list. Consequently, the corresponding set, cannot be in the range of .

For each , either or , and so we define . Clearly, and .

It follows that for any , and it must therefore correspond to a set not in the range of . This contradiction shows that cannot be countable.