Cantor's theorem: Difference between revisions

Revision as of 12:15, 4 June 2004

Revision as of 02:55, 24 June 2004

Line 1:

[[Category:Set theory]]

In [[set theory]], '''Cantor's theorem''' states that the [[power set]] ([[set]] of all [[subset]]s) of any set ''A'' has a strictly greater [[cardinality]] than that of ''A''. In particular, the set[[power of all subsetsset]] of a [[countable set|countably infinite]] set is '''un'''countably infinite.

==The proof==

The proof is a quick [[diagonal argument]]. Let ''f'' be any one-to-one function from ''A'' into the [[power set of all subsets]] of ''A''. It must be shown that ''f'' is necessarily not surjective. To do that, it is enough to exhibit a subset of ''A'' that is not in the image of ''f''. That subset is

:<math>B=\left\{\,x\in A : x\not\in f(x)\,\right\}.</math>