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:
“What journeyings on foot and on horseback through the wilderness, to preach the gospel to these minks and muskrats! who first, no doubt, listened with their red ears out of a natural hospitality and courtesy, and afterward from curiosity or even interest, till at length there “were praying Indians,” and, as the General Court wrote to Cromwell, the “work is brought to this perfection that some of the Indians themselves can pray and prophesy in a comfortable manner.””
—Henry David Thoreau (1817–1862)
“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)