Cantor's diagonal argument: Difference between revisions
imported>Greg Woodhouse (ref. to halting problem) |
imported>Sébastien Moulin m (categories) |
||
Line 10: | Line 10: | ||
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>\Psi</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>\Psi</math>. This contradiction shows that <math>2^{\mathbb{N}}</math> cannot be countable. | ||
[[Category:CZ Live]] | |||
[[Category:Mathematics Workgroup]] |
Revision as of 11:57, 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 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.