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:
“At that,
his small size,
keen eyes,
serviceable beak
and general truculence
assure his survival—”
—William Carlos Williams (1883–1963)
“There is the name and the thing; the name is a sound which sets a mark on and denotes the thing. The name is no part of the thing nor of the substance; it is an extraneous piece added to the thing, and outside of it.”
—Michel de Montaigne (1533–1592)