Cantor's theorem: Difference between revisions

Revision as of 23:36, 15 October 2003

Revision as of 07:45, 16 October 2003

Line 8:

To show that ''B'' is not in the image of ''f'', suppose that ''B'' ''is'' in the image of ''f''. Then for some ''y'' in ''A'', we have ''f''(''y'') = ''B''. Now consider whether ''y'' ε ''B'' or not. If ''y'' ε ''B'', then ''y'' ε ''f''(''y''), but that implies, by definition of ''B'', that ''y'' '''not''' ε ''B''. On the other hand if it is ''y'' '''not''' ε ''B'', then ''y'' '''not''' ε ''f''(''y'') and therefore ''y'' ε ''B''. Either way, we get a contradiction.

== History ==

Though it is called "Cantor's Theorem", Cantor never gave a proof in precisely this form. His first proof of the non-denumerability of the reals was was published in 1883 ("Foundations of a general theory of manifolds"). This does not resemble the theorem at all.

In a famous paper published in 1891 ("Ueber eine elementare Frage der Mannigfaltigkeitslehre"), where the diagonal proof first appears, there is a another proof later in this paper, where he notes that if f is a function defined on X whose values are 2-valued functions on X, then the 2-valued function G(x) = 1-f(x)(x) is not in the range of f.

Russell has a very similar proof in ''Principles of Mathematics'' (1903, section 348, where he shows that that there are more [[propositional function]]s than objects. "For suppose a correlation of all objects and some propositional functions to have been affected [sic], and let phi-x be the correlate of x. Then "not-phi-x(x)," i.e. "phi-x does not hold of x" is a propositional function not contained in this correlation; for it is true or false of x according as phi-x is false or true of x, and therefore it differs from phi-x for every value of x." He attributes the idea behind the proof to Cantor.

[[Ernst Zermelo]] has a theorem (which he calls "Cantor's Theorem") that is identical to the form above in the paper that became the foundation of modern set theory ("Untersuchungen über die Grundlagen der Mengenlehre I"), published in 1908. See [[Zermelo set theory]].

==Consequences==