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 raised a simple prayer
Before we left the spot,
That in the general mowing
That place might be forgot;
Or if not all so favored,
Obtain such grace of hours
That none should mow the grass there
While so confused with flowers.”
—Robert Frost (1874–1963)
“I think middle-age is the best time, if we can escape the fatty degeneration of the conscience which often sets in at about fifty.”
—W.R. (William Ralph)