vol 4: Glossary
Site map
Directory
Search this site
Home
1: About
2: Synopsis
3: Development
Next:
Previous: Glossary: Toc
... to restore theology to the mainstream of science
Cantor's diagonal method
[Hazewinkel, Diagonal process] [Borowski, Diagonal process]
Cantor used this 'diagonal argument' to show that the set of real numbers between 0 and 1 is not countable. By countable, we mean equinumerous with the (infinite) set of natural numbers generated by Peano's axioms. The method is a quite general one for generating elements not in a given set.
We agree that a set is infinite if it can be placed into one to one correspondence with a proper subset of itself. The set of natural numbers N = {0, 1, 2, ...} is proven to be infinite by placing into correspondence with the set of even numbers e = {0, 2, 4 ...} which is a subset of the natural numbers:
Are there sets bigger than the natural numbers? At first glance, we might feel that the set of fractional numbers is much bigger than the set of natural numbers, since there are many fractions between each pair of natural numbers. Closer examination, however, reveals that the set of natural numbers and the set of fractions are equinumerous.
To show this, we first devise a method of ordering the fractions, using the sum of numerator and denominator as the key. We notice that there are, for instance, five fractions whose numerator and denominator add up to six. They are 1/5, 2/4, 3/3, 4/2 and 1/5. With this insight, we can order all the rational numbers according to the following scheme:
Any rational number, n/m will appear in this arrangement in the row corresponding to the sum n+m. The integers also appear in factional form, and the same fraction will appear in different forms such as 2/3, 4/6 and so on. We set up a correspondence between natural numbers and fractions by running along the rows of our ordering of the fractions, eliminating duplicates as we go, to get the following arrangement:
This correspondence shows that the set of positive rational numbers can be placed in one-to-one correspondence with the set of natural numbers. The fractions are countable. We now use the diagonal argument to show that the real numbers are not countable by showing that it is impossible to put them into one to one correspondence with the aggregate of natural numbers.
Let us assume to the contrary, that we have established a correspondence between the natural numbers and all the real numbers (expressed as decimals) between 0 and 1 as illustrated:
Now, by changing each of the bold digits (that is, the nth digit in the nth decimal representation of a real number) we can create the decimal representation of a new real number not in the correspondence, thus showing that the real numbers cannot be put into correspondence with the natural numbers, and thus represent a higher order of infinity.
Further reading
Books
| Borowski, Ephraim J, and Jonathan M Borwein, HarperCollins Dictionary of Mathematics, Harper Collins 1991 'It is the immodest hope of the authors that this dictionary will not only prove valuable as a reference book for students of mathematics at all levels from secondary schools to a master's degree, but also offer much to interest a more general readership.' Amazon back |
| Hallett, Michael, Cantorian set theory and limitation of size, Oxford UP 1984 Jacket: 'This book will be of use to a wide audience, from beginning students of set theory (who can gain from it a sense of how the subject reached its present form), to mathematical set theorists (who will find an expert guide to the early literature), and for anyone concerned with the philosophy of mathematics (who will be interested by the extensive and perceptive discussion of the set concept).' Daniel Isaacson. Amazon back |
| Hazewinkel, Michiel, and (managing editor), Encyclopaedia of Mathematics (6 volumes), Kluwer Academic and Toppan 1995 'The Encyclopaedia of mathematics aims to be a reference work for all parts of mathematics. It is a translation with updates and editorial comments of the Soviet Mathematical Encyclopaedia published by 'Soviet Encyclopaedia Publishing House' in five volumes in 1977-85.' Amazon back |
Links
| PlanetMath.org Cantor's diagonal argument 'Maths for the people by the people' back |
Click on an "Amazon" link in the booklist at the foot of the page to buy the book, see more details or search for similar items
Related sites:
Concordat Watch
Revealing Vatican attempts to propagate its religion by international treaty
