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:
“We will win this war because we are willing to sacrifice 10,000,000 lives. How many lives is the White Man willing to sacrifice?”
—Jerome Cady, U.S. screenwriter, and Lewis Milestone. General Mitsubi (Richard Loo)
“Almsgiving tends to perpetuate poverty; aid does away with it once and for all. Almsgiving leaves a man just where he was before. Aid restores him to society as an individual worthy of all respect and not as a man with a grievance. Almsgiving is the generosity of the rich; social aid levels up social inequalities. Charity separates the rich from the poor; aid raises the needy and sets him on the same level with the rich.”
—Eva Perón (1919–1952)