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 fact is that the most effective way of utilizing human energy is through an organized rivalry, which by specialization and social control is, at the same time, organized co-operation.”
—Charles Horton Cooley (1864–1929)
“We love the indomitable bellicose patriotism that sets you apart; we love the national pride that guides your muscularly courageous race; we love the potent individualism that doesn’t prevent you from opening your arms to individualists of every land, whether libertarians or anarchists.”
—Tommaso Marinetti (1876–1944)