Cantor's diagonal argument: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Sébastien Moulin
m (categories)
imported>Greg Woodhouse
m (missed "to the")
Line 1: Line 1:
Cantor's diagonal method 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. More generally, it is a recurring theme in [[computability]] theory, where perhaps its most well known application is the negative solution [[halting problem]].
Cantor's diagonal method 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. 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]].


==The Argument==
==The Argument==

Revision as of 12:14, 30 March 2007

Cantor's diagonal method 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.

The Argument

To any set we may associate a function by setting if and , otherwise. Conversely, every such function defines a subset.

If power set is countable, there is a bijective map , that allows us to assign an index to every subset S. Assuming this has been done, we proceed to construct a function such that the corresponding set, cannot be in the range of .

For each , either or , and so we may simply such that .

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.