現代数学の系譜11 ガロア理論を読む12

596 ：現代数学の系譜11 ガロア理論を読む：2015/03/21(土) 14:16:17.25 ID:ooXUMShZ.net

>>595
関連
http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
（文字化けご容赦、修正しません）
In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method,
was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers.[1][2][3]
Such sets are now known as uncountable sets, and the size of infinite sets is now treated by the theory of cardinal numbers which Cantor began.

The diagonal argument was not Cantor's first proof of the uncountability of the real numbers;
it was actually published much later than his first proof, which appeared in 1874.[4][5]
However, it demonstrates a powerful and general technique that has since been used in a wide range of proofs, also known as diagonal arguments by analogy with the argument used in this proof.
The most famous examples are perhaps Russell's paradox, the first of Godel's incompleteness theorems, and Turing's answer to the Entscheidungsproblem.

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)), has a larger cardinality 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:

T = { s ∈ S: s ? f(s) }.

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); cf. picture.