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:
“It has been the struggle between privileged men who have managed to get hold of the levers of power and the people in general with their vague and changing aspirations for equality, for justice, for some kind of gentler brotherhood and peace, which has kept that balance of forces we call our system of government in equilibrium.”
—John Dos Passos (1896–1970)
“Whether changes in the sibling relationship during adolescence create long-term rifts that spill over into adulthood depends upon the ability of brothers and sisters to constantly redefine their connection. Siblings either learn to accept one another as independent individuals with their own sets of values and behaviors or cling to the shadow of the brother and sister they once knew.”
—Jane Mersky Leder (20th century)