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 conclusion suggested by these arguments might be called the paradox of theorizing. It asserts that if the terms and the general principles of a scientific theory serve their purpose, i. e., if they establish the definite connections among observable phenomena, then they can be dispensed with since any chain of laws and interpretive statements establishing such a connection should then be replaceable by a law which directly links observational antecedents to observational consequents.”
—C.G. (Carl Gustav)
“The vain man does not wish so much to be prominent as to feel himself prominent; he therefore disdains none of the expedients for self-deception and self-outwitting. It is not the opinion of others that he sets his heart on, but his opinion of their opinion.”
—Friedrich Nietzsche (1844–1900)