Content deleted Content added
No edit summary |
No edit summary |
||
Line 12:
== History ==
Cantor gave essentially this proof in a paper published in 1891 ("Ueber eine elementare Frage der Mannigfaltigkeitslehre"), where the [[Cantor's diagonal argument|diagonal argument]] for the uncountability of the [[real number|reals]] also first appears (he had [[Cantor's first uncountability proof|earlier proved the uncountability of the reals by other methods]]). The version of this argument he gave in that paper was phrase in terms of indicator functions on a set rather than subsets of a set. He showed 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.
| |||