Cantor's Diagonal Argument - General Sets

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 the drawing room [of the Queen’s palace] hung a Venus and Cupid by Michaelangelo, in which, instead of a bit of drapery, the painter has placed Cupid’s foot between Venus’s thighs. Queen Caroline asked General Guise, an old connoisseur, if it was not a very fine piece? He replied “Madam, the painter was a fool, for he has placed the foot where the hand should be.”
    Horace Walpole (1717–1797)

    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)