User:RJGray/Cantor's argument

New lead

edit

In mathematical logic, the theory of infinite sets was first developed by Georg Cantor. Although this work has become a thoroughly standard fixture of classical set theory, it has been criticized in several areas by mathematicians and philosophers.

Cantor's theorem implies that there are sets having cardinality greater than the infinite cardinality of the set of natural numbers. Cantor's argument is presented with one small change. It is also shown how to improve Cantor's argument by using a definition he gave later. This produces an argument that uses only five axioms of set theory.

Cantor's set theory was controversial at the start, but later became largely accepted. In particular, there have been objections to its use of infinite sets.

Cantor's argument

edit

Cantor's first proof that infinite sets can have different cardinalities was published in 1874. This proof demonstrates that the set of natural numbers and the set of real numbers have different cardinalities. It uses the theorem that a bounded increasing sequence of real numbers has a limit, which can be proved by using Cantor's or Richard Dedekind's construction of the irrational numbers. Because Leopold Kronecker did not accept these constructions, Cantor was motivated to develop a new proof.[1]

In 1891, he published "a much simpler proof … which does not depend on considering the irrational numbers."[2] His new proof uses his diagonal argument to prove that there exists an infinite set with a larger number of elements (or greater cardinality) than the set of natural numbers N = {1, 2, 3, …}. This larger set consists of the elements (x1x2x3, …), where each xn is either m or w.[3] Each of these elements corresponds to a subset of N—namely, the element (x1x2x3, …) corresponds to {n ∈ N:  xn = w}. So Cantor's argument implies that the set of all subsets of N has greater cardinality than N. The set of all subsets of N is denoted by P(N), the power set of N.

Cantor generalized his argument to an arbitrary set A and the set consisting of all functions from A to {0, 1}.[4] Each of these functions corresponds to a subset of A, so his generalized argument implies the theorem: The power set P(A) has greater cardinality than A. This is known as Cantor's theorem.

The argument below is a modern version of Cantor's argument that uses power sets (for his original argument, see Cantor's diagonal argument). By presenting a modern argument, it is possible to see which assumptions of axiomatic set theory are used. The first part of the argument proves that N and P(N) have different cardinalities:

  • There exists at least one infinite set. This assumption (not formally specified by Cantor) is captured in formal set theory by the axiom of infinity. This axiom implies that N, the set of all natural numbers, exists.
  • P(N), the set of all subsets of N, exists. In formal set theory, this is implied by the power set axiom, which says that for every set there is a set of all of its subsets.
  • The concept of "having the same number" or "having the same cardinality" can be captured by the idea of one-to-one correspondence. This (purely definitional) assumption is sometimes known as Hume's principle. As Frege said, "If a waiter wishes to be certain of laying exactly as many knives on a table as plates, he has no need to count either of them; all he has to do is to lay immediately to the right of every plate a knife, taking care that every knife on the table lies immediately to the right of a plate. Plates and knives are thus correlated one to one."[5] Sets in such a correlation are called equipollent, and the correlation is called a one-to-one correspondence.
  • A set cannot be put into one-to-one correspondence with its power set. This implies that N and P(N) have different cardinalities. It depends on very few assumptions of set theory, and, as John P. Mayberry puts it, is a "simple and beautiful argument" that is "pregnant with consequences".[6] Here is the argument:
Let   be a set and   be its power set. The following theorem will be proved: If   is a function from   to   then it is not onto. This theorem implies that there is no one-to-one correspondence between   and   since such a correspondence must be onto. Proof of theorem: Define the diagonal subset   Since   proving that for all   will imply that   is not onto. Let   Then   which implies   So if   then   and if   then   Since one of these sets contains   and the other does not,   Therefore,   is not in the image of  , so   is not onto.

Next Cantor shows that   is equipollent to a subset of  . From this and the fact that   and   have different cardinalities, he concludes that   has greater cardinality than  . This conclusion uses his 1878 definition: If A and B have different cardinalities, then either B is equipollent to a subset of A (in this case, B has less cardinality than A) or A is equipollent to a subset of B (in this case, B has greater cardinality than A).[7] This definition leaves out the case where A and B are equipollent to a subset of the other set—that is, A is equipollent to a subset of B and B is equipollent to a subset of A. Because Cantor implicitly assumed that cardinalities are linearly ordered,[8] this case cannot occur. Cantor's first proof that cardinalities are linearly ordered appeared in 1883. It uses his well-ordering principle "every set can be well-ordered", which he called a "law of thought".[9] The well-ordering principle is equivalent to the axiom of choice.[10]

Around 1895, Cantor began to regard the well-ordering principle as a theorem and attempted to prove it.[11] In 1895, Cantor also gave a new definition of "greater than" that correctly defines this concept without the aid of his well-ordering principle.[12] By using Cantor's new definition, the modern argument that P(N) has greater cardinality than N can be completed using weaker assumptions than his original argument:

  • The concept of "having greater cardinality" can be captured by Cantor's 1895 definition: B has greater cardinality than A if (1) A is equipollent to a subset of B, and (2) B is not equipollent to a subset of A.[12] Clause (1) says B is at least as large as A, which is consistent with our definition of "having the same cardinality". Clause (2) implies that the case where A and B are equipollent to a subset of the other set is false. Since clause (2) says that A is not at least as large as B, the two clauses together say that B is larger (has greater cardinality) than A.
  • The power set   has greater cardinality than   which implies that P(N) has greater cardinality than N. Here is the proof:
  • (1) Define the subset   Define   which maps   onto   Since   implies   is a one-to-one correspondence from   to   Therefore,   is equipollent to a subset of  
  • (2) Using proof by contradiction, assume that   a subset of   is equipollent to   Then there is a one-to-one correspondence   from   to   Define   from   to   if   then   if   then   Since   maps   onto   maps   onto   contradicting the theorem above stating that a function from   to   is not onto. Therefore,   is not equipollent to a subset of  

Besides the axioms of infinity and power set, the axioms of separation, extensionality, and pairing were used in the modern argument. For example, the axiom of separation was used to define the diagonal subset   the axiom of extensionality was used to prove   and the axiom of pairing was used in the definition of the subset  

Notes to be added

edit
  1. ^ Dauben 1979, pp. 67–68, 165.
  2. ^ Cantor 1891, p. 75; English translation: Ewald p. 920.
  3. ^ Dauben 1979, p. 166.
  4. ^ Dauben 1979, pp.166–167.
  5. ^ Frege 1884, trans. 1953, §70.
  6. ^ Mayberry 2000, p. 136.
  7. ^ Cantor 1878, p. 242. Cantor 1891, p. 77; English translation: Ewald p. 922.
  8. ^ Hallett 1984, p. 59.
  9. ^ Moore 1982, p. 42.
  10. ^ Moore 1982, p. 330.
  11. ^ Moore 1982, p. 51. A discussion of Cantor's proof is in Absolute infinite, well-ordering theorem, and paradoxes. Part of Cantor's proof and Zermelo's criticism of it is in a reference note.
  12. ^ a b Cantor 1895, pp. 483–484; English translation: Cantor 1954, pp. 89–90.

References to be added

edit
  • Cantor, Georg (1878), "Ein Beitrag zur Mannigfaltigkeitslehre", Journal für die Reine und Angewandte Mathematik, 84: 242–248
  • Cantor, Georg (1891), "Ueber eine elementare Frage der Mannigfaltigkeitslehre" (PDF), Jahresbericht der Deutsche Mathematiker-Vereinigung, 1: 75–78
  • Cantor, Georg (1895), "Beiträge zur Begründung der transfiniten Mengenlehre (1)", Mathematische Annalen, 46: 481–512, doi:10.1007/bf02124929, archived from the original on April 23, 2014 {{citation}}: Unknown parameter |deadurl= ignored (|url-status= suggested) (help)
  • Cantor, Georg; Philip Jourdain (trans.) (1954) [1915], Contributions to the Founding of the Theory of Transfinite Numbers, Dover, ISBN 978-0-486-60045-1
  • Dauben, Joseph (1979), Georg Cantor: His Mathematics and Philosophy of the Infinite, Harvard University Press, ISBN 0-674-34871-0
  • Ewald, William B. (ed.) (1996), From Immanuel Kant to David Hilbert: A Source Book in the Foundations of Mathematics, Volume 2, Oxford University Press, ISBN 0-19-850536-1 {{citation}}: |first= has generic name (help)
  • Hallett, Michael (1984), Cantorian Set Theory and Limitation of Size, Clarendon Press, ISBN 0-19-853179-6
  • Moore, Gregory H. (1982), Zermelo's Axiom of Choice: Its Origins, Development & Influence, Springer, ISBN 978-1-4613-9480-8