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 general feeling was, and for a long time remained, that one had several children in order to keep just a few. As late as the seventeenth century . . . people could not allow themselves to become too attached to something that was regarded as a probable loss. This is the reason for certain remarks which shock our present-day sensibility, such as Montaigne’s observation, “I have lost two or three children in their infancy, not without regret, but without great sorrow.””
—Philippe Ariés (20th century)
“The vain man does not wish so much to be prominent as to feel himself prominent; he therefore disdains none of the expedients for self-deception and self-outwitting. It is not the opinion of others that he sets his heart on, but his opinion of their opinion.”
—Friedrich Nietzsche (1844–1900)