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:
“In former times and in less complex societies, children could find their way into the adult world by watching workers and perhaps giving them a hand; by lingering at the general store long enough to chat with, and overhear conversations of, adults...; by sharing and participating in the tasks of family and community that were necessary to survival. They were in, and of, the adult world while yet sensing themselves apart as children.”
—Dorothy H. Cohen (20th century)
“I would rather have as my patron a host of anonymous citizens digging into their own pockets for the price of a book or a magazine than a small body of enlightened and responsible men administering public funds. I would rather chance my personal vision of truth striking home here and there in the chaos of publication that exists than attempt to filter it through a few sets of official, honorably public-spirited scruples.”
—John Updike (b. 1932)