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:
“You don’t want a general houseworker, do you? Or a traveling companion, quiet, refined, speaks fluent French entirely in the present tense? Or an assistant billiard-maker? Or a private librarian? Or a lady car-washer? Because if you do, I should appreciate your giving me a trial at the job. Any minute now, I am going to become one of the Great Unemployed. I am about to leave literature flat on its face. I don’t want to review books any more. It cuts in too much on my reading.”
—Dorothy Parker (1893–1967)
“Music sets up ladders,
it makes us invisible,
it sets us apart,
it lets us escape;
but from the visible
there is no escape.”
—Hilda Doolittle (1886–1961)