General Sets
A generalized form of the diagonal argument was used by Cantor to prove Cantor's theorem: for every set S the power set of S, i.e., the set of all subsets of S (here written as P(S)), is larger than S itself. This proof proceeds as follows:
Let f be any function from S to P(S). It suffices to prove f cannot be surjective. That means that some member T of P(S), i.e., some subset of S, is not in the image of f. As a candidate consider the set:
For every s in S, either s is in T or not. If s is in T, then by definition of T, s is not in f(s), so T is not equal to f(s). On the other hand, if s is not in T, then by definition of T, s is in f(s), so again T is not equal to f(s). For a more complete account of this proof, see Cantor's theorem.
Read more about this topic: Cantor's Diagonal Argument
Famous quotes containing the words general and/or sets:
“The man who would change the name of Arkansas is the original, iron-jawed, brass-mouthed, copper-bellied corpse-maker from the wilds of the Ozarks! He is the man they call Sudden Death and General Desolation! Sired by a hurricane, dam’d by an earthquake, half-brother to the cholera, nearly related to the smallpox on his mother’s side!”
—Administration in the State of Arka, U.S. public relief program (1935-1943)
“To the extent to which genius can be conjoined with a merely good human being, Haydn possessed genius. He never exceeds the limits that morality sets for the intellect; he only composes music which has “no past.””
—Friedrich Nietzsche (1844–1900)