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:
“As a general truth, it is safe to say that any picture that produces a moral impression is a bad picture.”
—Edmond De Goncourt (1822–1896)
“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)