ji^ V ,^'- ?■(■ II*? ' * CORNELL UNIVERSITY LIBRARY Gift Of Emily Doty Harris MATHEMATICS _ Cornell University Library QA 248.H94 1917 The continuum, and other types of serial 3 1924 001 587 082 Cornell University Library The original of tiiis book is in tine Cornell University Library. There are no known copyright restrictions in the United States on the use of the text. http://www.archive.org/details/cu31924001587082 rryr ¥T-( y-«.#->kXTm¥XTT tt ti» , "^^"TMENT OF MATHEMATICS THE CONTINUUM ^omummmm AND OTHER TYPES OF SERIAL ORDER WITH AN INTRODUCTION TO CANTOR'S TRANSFINITE NUMBERS BY EDWARD V. HUNTINGTON ASSOCIATE PROFESSOR OF MATHEMATICS IH HARVARD TINITBBSITT SECOND EDITION HARVARD UNIVERSITY PRESS CAMBRIDGE, MASS., U.S.A. 1917 COPYRIGHT, 1917 HABVABD UinVERBITT PRESS PREFACE TO THE SECOND EDITION The first edition of this book appeared in 1905 as a reprint from the Annals of Mathematics, series 2 (vol. 6, pp. 151-184, and vol. 7, pp. 15— i3), under the title: The Continuum as a Type of Order: an Exposition of the Modern Theory; with an Appendix on the Transfinite Numbers (The Publication Office of Harvard University, Cambridge, Mass.). An Esperanto translation by R. Bricard, under the title: La Kontinuo, appeared in 1907 (Paris, Gauthier-Villars). The following reviews (of the original or of the translation) may be noted: by O. Veblen, in Bull. Amer. Math. Soc, vol. 12 (1906), pp. 302-305; by P. E. B. Jourdain, in the Mathe- matical Gazette, vol. 3 (1906), pp. 348-349; by C. Bourlet, in Nouvelles Annales de MatMmatiques, ser. 4, vol. 7 (1907), pp. 174-176; and by Hans Hahn, in Monatsheftefiir Math. u. Physik, vol. 21 (1910), Literaturber., p. 26. The author is indebted to Professor Veblen and to Professor Hahn for calling his attention to errors in § 62. The principal modifications in the present edition are the following: § 38 and § 64 have been enlarged; § 62 has been rewritten, and § 62o has been added; the bibliographical notes have been brought more nearly up to date; through- out Chapter VII [formerly called the Appendix (§ 73-§ 91)] the term "normal series" has been replaced by the term " well-ordered series " (for reasons explained in a footnote to § 74) ; and in § 89a a brief account has been inserted of Hartogs's recent proof of Zermelo's theorem that every class can be well-ordered. CONTENTS PAOK iNTBODrcnON 1 CHAPTER I On Classes in general SECTION 1-6. One-to-one correspondence between two classes 4 7-10. Finite and infinite classes 6 11. The simplest mathematical systems 8 CHAPTER II On simply obdeeed Classes, oh Semes 12-15. Definition of a series: Postulates 1-3 . . 10 16. Ordinal correspondence between two series 11 17-18. Properties of series. Successor. Predecessor . . .12 19. Examples of series 13 20. Examples of systems which are not series 16 CHAPTER III Discrete Series: Especially the Type u op obe Natural Numbers 21-22. Definition of a discrete series: Postulates N1-N3 19 23. Theorem of mathematical induction 20 24r-27. Properties of discrete series. Progressions, or series of type u 21 28. Examples of discrete series; the natural numbers .... 23 29. Examples of series which are not discrete 23 30-36. On numbering the elements of a discrete series. Sums and products of the elements 25 37-40. On denumerable classes 30 vi CONTENTS CHAPTER rv Dense Series: Especially the Type rj op the Rational Numbers 41-43. Definition of a denumerable dense series: Postulates fl'l-H2 34 44-45. Properties of denmnerable dense series. Series of tjrpe jj. 35 46-50. Segments. Limits ... 37 51. Examples of denumerable dense series; the rational numbers 39 52. Examples of series which are not dense 41 53. On the arithmetical operations among the elements of a dense series , ... .... 43 CHAPTER V CoNnNuous Series: Especially the Type d or the Real Numbers 54-55. Definition of a linear continuous series : Postulates C1-C3 . 44 56-62. Properties of linear continuous series. Series of type d . . 45 62a. Digression on the theory of sets of points . . 52 63. Examples of linear continuous series; the real numbers 52 64. Examples of series which are not continuous . . .55 65. On the arithmetical operations among the elements of a con- tinuous series . . . 57 CHAPTER VI Continuous Series op More than One Dimension, with A Note on Multiply Ordered Classes 66-70. Definition of n-dimensional continuous series. Series of type 6" .... ... 58 71. The one-to-one correspondence between the points of all space and the points of a line 60 72. Note on multiply ordered classes 62 CONTENTS yii CHAPTER VII Wbll-obdehed Series, with an Intkoduction to Cantor's Transfinite Numbers 73-76. Definition of a well-ordered series : Postulates 4-6 .... 63 77-85. Examples and properties of well-ordered series . ... 66 86. The transfinite ordinal numbers; w, fl, etc. . .... 73 87-91. The transfinite cardinal numbers; No, Ni, etc 74 Index op technical terms 81 THE CONTINUUM AND OTHER TYPES OF SERIAL ORDER INTRODUCTION The main object of this book is to give a systematic elementary account of the modem theory of the continumn as a type of serial order — a theory which underhes the definition of irrational num- bers and makes possible a rigorous treatment of the real number system of algebra. The mathematical theory of the continuous independent vari- able, in anything like a rigorous form, may be said to date from the year 1872, when Dedekind's Stetigkeit und irrationale Zahlen ap- peared;* and it reached a certain completion in 1895, when the first part of Cantor's Beitrage zur Begrundung der transfiniten Mengen- lehre was published in the Mathematische Annalen.f While all earUer discussions of continuity had been based more or less consciously on the notions of distance, number, or magnitude, the Dedekind-Cantor theory is based solely on the relation of order. The fact that a complete definition of the continuimi has thus been given in terms of order alone has been signaUzed by Russell J as one * Third (unaltered) edition, 1905; English translation by W. W. Beman, in a volume called Dedekind's Essays on the Theory of Numbers, 1901. t Georg Cantor, Math. Ann., vol. 46 (1895), pp. 481-512; French translation by F. Marotte, in a volume called Sur les fondements de la thSorie des ensembles transfinis, 1899; English translation by P. E. B. Jourdain, Contributions to the Founding of the Theory of Transfimte Numbers, Open Coiirt Publishing Co., 1915. For further references to Cantor's work, see § 74. An interesting con- tribution to the theory has been made by O. Veblen, Definitions in terms of order alone in the linear conUnuum and in weUrordered sets, Trans. Ameir. Math. Soc., vol. 6 (1905), pp. 165-171. t B. Russell, Principles of Mathematics, vol. 1 (1903), p. 303. See also A. N. Whitehead and B. RusseU, Principia Mathematica, especially vol. 2 (1912) and vol. 3 (1913), where an elaborate accoimt of the theory of order is given in the symboUc notation of modem mathematical logic. 1 2 TYPES OF SERIAL ORDER of the notable achievements of modern pure mathematics ; * and the simplicity of the ordinal theory, which requires no technical knowl- edge of mathematics whatever, renders it pecuUarly accessible to the increasing number of non-mathematical students of scientific method who wish to keep in touch with recent developments in the logic of mathematics. The present work has therefore been prepared with the needs of such students, as well as those of the more mathematical reader, in view; the mathematical prerequisites have been reduced (except in one or two illustrative examples) to a knowledge of the natural niunbers, 1, 2, 3, . . . , and the simplest facts of elementary geom- etry; the demonstrations are given in full, the longer or more difficult ones being set in closer type; and in connection with every definition numerous examples are given, to illustrate, in a concrete way, not only the systems which have, but also those which have not, the property in question. Chapter I is introductory, concerned chiefly with the notion of one-to-one correspondence between two classes or collections. Chapter II introduces simply ordered classes, or series,t and ex- plains the notion of an ordinal correspondence between two series. Chapters III and IV concern the special types of series known as discrete and dense, and chapter V, which is the main part of the book, contains the definition of continuous series. Chapter VI is a supplementary chapter, defining multiply ordered classes, and continuous series in more than one dimension. Chapter VII gives a brief introduction to the theory of the so-called " well-ordered " series, and Cantor's transfinite numbers. An index of all the technical terms is given at the end of the volume. * The fundamental importance of the subject of order may be inferred from the fact that all the concepts reqmred in geometry can be expressed in terms of the concept of order alone; see, for example, O. Veblen, A system of axioms for geometry, Trans. Amer. Math. Soc., vol. 5 (1904), pp. 343- 384; or E. V. Huntington, A set of postulates for abstract geometry, expressed in terms of the simple relation of inclusion, Math. Ann., vol. 73 (1913), pp. 522- 559. t The word series is here used not in the technical sense of a sum of numeri- cal terms, but in a more general sense explained in § 12. INTRODUCTION 3 It will be noticed that while the usual treatment of the con- tinuum in mathematical text-books begins with a discussion of the system of real nimibers, the present theory is based solely on a set of postulates the statement of which is entirely independent of numerical concepts (see § 12, § 21, § 41, and § 54). The various number-systems of algebra serve merely as examples of systems which satisfy the postulates — important examples, indeed, but not by any means the only possible ones, as may be seen by in- spection of the lists of examples given in each chapter (§§ 19, 28, 51, 63). For the benefit of the non-mathematical reader, I give a detailed explanation of each of the number-systems as it occurs, in so far as the relation of order is concerned (see § 22 for the integers, §51, 3 for the rationals, and §63, 3 for the reals) ; the operations of addition and multiplication are mentioned only incidentally (see §§31, 53, and 65), since they are not relevant to the purely ordinal theory.* In conclusion, I should say that the bibliographical references throughout the book are not intended to be in any sense exhaus- tive; for the most part they serve merely to indicate the sources of my own information. * The reader who is interested in these extra-ordinal aspects of algebra may refer to my paper on The Fundamental Laws of Addition and MvUiplwation in Elementary Algebra, reprinted from the Annals of MaihenuUics, vol. 8 (1906), pp. 1-44 ( PubUeation OflSce of Harvard University) ; or to my Fundamental Propositions of Algebra, being monograph IV (pp. 149-207) in the volume called Monographs on Topics of Modem Maihemalics relevant to the Elementary Field, edited by J. W. A. Young (Longmans, Green & Co., 1911). A more elementary treatment may be found in John Wesley Yoimg's Lectures on Fundamenial Concepts of Algebra and Geometry (MacmiUan, 1911). CHAPTER I On Classes in General 1. A class (Menge, ensemble) is said to be determiDed by any test or condition which every entity (in the universe considered) must either satisfy or not satisfy; any entity which satisfies the condi- tion is said to belong to the class, and is called an element of the class.* A null or empty class corresponds to a condition which is satisfied by no entity in the universe considered. For example, the class of prime niunbers is a class of numbers determined by the condition that every number which belongs to it must have no factors other than itself and 1. Again, the class of men is a class of Uving beings determined by certain conditions set forth in works on biology. Finally, the class of perfect square numbers which end in 7 is an empty class, since every perfect square number must end in 0, 1, 4, 5, 6, or 9. 2. If two elements a and 6 of a given class are regarded as inter- changeable throughout a given discussion, they are said to be equal; otherwise they are said to be distinct. The notations commonly used are a = b and a ^ b, respectively. / 3. A one-to-one correspondence between two classes is said to be established when some rule is given whereby each element of one class is paired with one and only one element of the other class, and 1 reciprocally each element of the second class is paired with one and I only one element of the first class. For example, the class of soldiers in an army can be put into one- to-one correspondence with the class of rifles which they carry, * H. Weber, Algebra, vol. 1, p. 4. For the sake of uniformity with Peano's Formvlaire de Maihematiques, I translate Menge, or MannigfalHgkeit, by class instead of by collection, mass, set, ensemble, or aggregate — all of which terms are in use. For recent discussions of the concept class, see the articles cited in §83. 4 §4 CLASSES IN GENERAL since (as we suppose) each soldier is the owner of one and only one rifle, and each rifle is the property of one and only one soldier. Again, the class of natural numbers can be put into one-to-one correspondence with the class of even numbers, since each natural number is half of some particular even number and each even nimiber is double some particular natural number; thus: 1, 2, 3, . . . , 2, 4, 6, * Again, the class of points on a Une AB three inches long can be put into one-to-one correspondence with the class of points on a line CD one inch long; for example by means of projecting rays drawn from a point as in the figure. 4. An example of a relation between two classes which is not a one-to-one correspondence, is furnished by the relation of owner- ship between the class of soldiers and the class of shoes which they wear; we have here what may be called a two-to-one correspond- ence between these classes, since each shoe is worn by one and only one soldier, while each soldier wears two and only two shoes. The consideration of this and similar examples shows that all the con- ditions mentioned in the definition of one-to-one correspondence are essential. * That the class of square numbers can be put into one-to-one correspond- ence with the class of all natural numbers was known to Galileo ; see his Dialogs concerning two new Sciences, translation by Crew and de Salvio (1914), pp. 18-40. 6 TYPES OF SERIAL ORDER §5 5. Obviously if two classes can be put into one-to-one corre- spondence with any third class, they can be put into one-to-one correspondence with each other. 6. A part (" -proTper part," echter Teil), of a class A is any class which contains some but not all of the elements of A, and no other element. A svbdass {Teil) of A is any class every element of which belongs to A ; that is, a subclass is either a part or the whole. 7. We now come to the definition of finite and infinite classes. „— An infinite class is a class which can be put into one-to-one corre- spondence with a part of itself. A finite class is then defined as any class which is not infinite. This fundamental property of infinite classes was clearly stated in B. Bolzano's Puradoxien des Unendlichen (published post- humously in 1850), and has since been adopted as the definition of infinity in the modern theory of classes.* 8. An example of an infinite class is the class of the natural numbers, since it can be put into one-to-one correspondence with the class of the even numbers, which is only a part of itself (§ 3). Again, the class of points on a line AB is infinite, since it can be put into one-to-one correspondence with the class of points on a segment CD of AB (by first putting both these classes into one-to- * See G. Cantor, CreUe's Journ.fiir Math., vol. 84 (1877), p. 242; and espe- cially R. Dedekind: Was sind und was sollen die Zahlen, 1887 (English trans- lation by W. W. Beman, under the title Essays on the theory of Numbers, 1901); § 10 CLASSES IN GENERAL 7 one correspondence with the class of points on an auxiliary line HK, as in the figure). The class of the first n natural numbers, on the other hand, is finite, since if we attempt to set up a correspondence between the whole class and any one of its parts, we shall always find that one or more elements of the whole class will be left over after all the elements of the partial class have been assigned (see § 27). 9. The most important elementary theorems in regard to infinite classes are the following: (Df If any subclass of a given class is infinite then the class itself is infinite. For, let A be the given class. A' the infinite subclass, and A" the subclass of all the elements of A which do not belong to A' (noting that A" may be a nuU class). By hypothesis, there is a part, A'l, of A' which can be put into one-to-one correspondence with the whole oiA'; therefore the class composed of A'l and A" wiU be a part of A which can be put into one-to-one correspondence with the whole of A. (2) 7/ any one element is excluded from an infinite class, the remain- ing class is also infinite. For, let A be the given class, x the element to be excluded, and B the class remaining. By hypothesis, there is a part, Ai,oiA, which can be put into one-to-one correspondence with the whole of ^1, and is therefore itself infinite. If this part Ai does not contain the ele- ment X, it will be a subclass in B, and our theorem is proved. If it does contain x, there will be at least one element y which belongs to B and not to Ai, and by replacing x by y in Ai we shall have another part of A, say A2, which will be an infinite part of A and at the same time a subclass in B. 10. As a corollary of this last theorem we see that no infinite dass can ever be exhausted by taking away its elements one by one. For, the class which remains after each subtraction is always an infinite class, by § 9, 2, and therefore can never be an empty class, compare B. Kussell, Principles of Mathematics, vol. 1, p. 315, and Whitehead and Riissell, Prindpia MathemaOca, vol. 2 (1912), pp. 187-192. See also § 27 of the present paper. 8 JYPES OF SERIAL ORDER § 11 or a class containing merely a single element (these classes being obviously finite according to the definition of § 7). This restdt wUI be used in § 27, below, where another, more familiar, definition of finite and infinite classes will be given. The further study of the theory of classes as such, leading to the introduction of Cantor's transfinite cardinal numbers, need not concern us here; the definitions of the principal terms which are used in this theory will be found in chapter VII. 11. After the theory of classes, as such, which is logically the simplest branch of mathematics, the next in order of complexity is the theory of classes in which a relation or an operation among the elements is defined. For example, in the class of nmnbers we havq the relation of " less than " and the operations of addition and multiphcation;* in the class of points, the relation of collinearity| etc.; in the class of human beings, the relations " brother of,''' " debtor of," etc. If we use the term system to denote a class together with any relations or operations which may be defined among its elements we may say that the simplest mathematical systems are: (1) a class with a single relation, and (2) a class with a single operation. The most important example of the first kind is the theory of simply ordered classes, which forms the subject of the present paper; the most important example of the second kind is the theory of abstract groups.f The ordinary algebra of real or complex i numbers is a combination of the two.f * As M. B6cher has pointed out [Bull. Amer. Math. Soc, vol. 11 (1904), p. 126], any operation or rule of combination by which two elements determine . a third may be interpreted as a triadio relation; for example, instead of sajfing that two given numbers a and b determine a third number c called their sum (a + b = c), we may say that the three elements a, b, and c satisfy a certain relation R (a, h, c). t For a bibliographical account of the definitions of an abstract group, see Trans. Amer. Math. Soc., vol. 6 (1905), pp. 181-193. t For a definition of ordinary algebra by a set of independent postulates, see Trans. Amer. Math. Soc., vol. 6 (1905), pp. 209-229, or my two monographs cited in the introduction. For a similar definition of the Boolean algebra of §11 CLASSES IN GENERAL 9 We proceed in the next chapter to explain the conditions or " postulates " which a class, K, and a relation, ■< (or " R "), must satisfy in order that the system (K, <) may be called a simply ordered class. logic, see Trans. Amer. Math. Soc., vol. 5 (1904), pp. 288-309 [compare a recent note by B. A. Bernstein, Bull. Amer. Math. Soc, vol. 22 (1916), pp. 458- 459]; also papers by H. M. Sheffer, Trans. Amer. Math. Soc, vol. 14 (1913), pp. 481-488, and B. A. Bernstein, Univ. of California Publications in Math., vol. 1 (1914), pp. 87-96, and Trans. Amer. Math. Soc, vol. 17 (1916), pp. 50- 62. CHAPTER II Genbeal Peopebties of Simply Okdehed Classes OR Series 12. If a class, K, and a relation, < (called the relation of order), satisfy the conditions expressed in postulates 0, 1-3, below, then the system (K, -<) is called a simply ordered class, or a series* The notation a < b or (b > a, which means the same thing), may be read: " a precedes 6 " (or " b foUows a "). The class K is said to be arranged, or set in order, by the relation ■< , and the relation ■< is called a serial relation within the class K. Postulate 0. The class K is not an empty class, nor a class con- taining merely a single element. This postulate is intended to exclude obviously trivial cases, and will be assumed without further mention throughout the paper. Postulate 1. If a and b are distinct elements of K, then either^ a < b or b < a.^ Postulate 2. If a < b, then a and b are distinct.t Postulate 3. If a < b and b < c, then a < c.§ The consistency and independence of these postulates will be established in § 19 and § 20. 13. As an immediate consequence of postulates 2 and 3, we have Theorem I. If a < b is true, then b < a isfalse.\\ * " Einfach geordnete Menge:" G. Cantor, Math. Ann., vol. 46 (1895), p. 496; " series: " B. Russell, Principles of Mathematics, vol. 1 (1903), p. 199, t This postulate 1 has been called by Russell the postulate of cannexUy; loc. cit., p. 239. t Any relation ■< which satisfies postulate 2 is said to be irreflexive throughout the class; this term is due to Peano; see Russell, loc. cit., p. 219. § Any relation ■< which satisfies postulate 3 is said to be transiiive tiirough- out the class. This term has been in common use since the time of DeMorgan. II Any relation ■< which has this property is said to be asymmetrical through- out the class; see RusseU, loc. dt., p. 218. 10 § 16 SIMPLY ORDERED CLASSES OR SERIES 11 (For, if o < 6 and b < a were both true, we should have, by 3, a < a, whence, hy 2, a ^ a, which is absurd). If desired, this theorem I may be used in place of postulate 2 in the definition of a serial relation. 14. The general properties of series may now be summarized as follows: If a and b are any elements of K, then either a = b, or a <. b, or b <. a, and these three conditions are mutually exclusive; further, if a < b and b < c, then a < c. -^ These are the properties which characterize a serial relation within the class K* 15. As the most famUiar examples of series we mention the following: (1) the class of all the natural numbers (or the first n of them), arranged in the usual order; and (2) the class of all the points on a line, the relation " a < b" signifying " a on the left of b." Many other examples Avill occur in the course of our work. 16. If two series can be brought into one-to-one correspondence in such a way that the order of any two elements in one is the same as the order of the corresponding elements in the other, then the two series are said to be ordinally similar, or to belong to the same type of order (Ordnungstypus).^ For example, the class of all the natural numbers, arranged in the usual order, is ordinally similar to the class of all the even numbers, arranged in the usual order (compare § 3). Again, the class of all the points on a line one inch long, arranged from left to right, is ordinally similar to the class of all the points on a line three inches long, arranged from left to right (compare §8). * A serial relation may also be described as one which is (1') connected; (2') irreflexive; (3') transitive for distinct elements; and (4') asymmetrical for distinct elements; these four properties [(3') and (4') being weaker forms of postulate 3 and theorem I respectively] are readily shown to be mde-pendemt. See a forthcoming paper by E. V. Huntington cited in § 20, below. t Cantor, Math. Ann., vol. 46 (1895), p. 497. 12 TYPES OF SERIAL ORDER § 17 It will be noticed that in the first of these examples the corre- spondence between the two series can be set up in only one way, whUe in the second example, the correspondence can be set up in an infinite number of ways. This distinction is an important one, for which, unfortunately, no satisfactory terminology has yet been proposed.* 17. Before giving further examples of the various types of simply ordered classes, it will be convenient to give here the defi- nitions of a few useful technical terms. Definition 1. In any series, if a •< a; and x < b, then x is said to lie between a and 6.t Definition 2. In any series, if a < a; and no element exists between a and x, then x is called the element next following a, or the (immediate) siiccessor of a. Similarly, U y •< a and no element exists between y and a, then y is called the element next preceding a, or the (immediate) predecessor of a.X For example, in the class of natural numbers in the usual order every element has a successor, and every element except the first has a predecessor; but in the class of points on a line, in the usual order, every two points have other points between them, so that no point has either a successor or a predecessor. Definition 3. In any series, if one element x precedes all the other elements, then this x is called the first element of the series. Similarly, if one element y follows all the others, then this y is called the last element. 18. With regard to the existence of first and last elements, all series may be divided into four groups : (1) those that have neither a first element nor a last element; (2) those that have a first ele- ment, but no last; (3) those that have a last element, but no first; and (4) those that have both a first and a last. * Cf. Trans. Amer. Math. Soc., vol. 6 (1906), p. 41; or O. Veblen, Bull. Amer. Math. Soc, vol. 12 (1906), p. 303. One might speak of a determinate correspondence and an indeterminate correspondence (Bricard). t For an elaborate analysis of this concept, see a forthcoming paper called " Sets of independent postulates for betweenness," by E. V. Huntington and J. R. Kline, Trans. Amer. Math. Soc. t See footnote t under § 31. § 19 SIMPLY ORDERED CLASSES OR SERIES 13 For example, the class of all the points on a line between A and B, arranged from A to B, has no first point, 1) A B and no last point, since if any point C of 2) A • — B the class be chosen there will be points of 3) A • B the class between C and A and also be- 4) A • • B tween C and B. If, however, we consider a new class, comprising all the points between A and B, and also the point A (or B, or both), arranged from A to B, then this new class will have a first element (or a last element, or both). The four cases are represented in the accompanying diagram. Examples of series 19. In this section we give some miscellaneous examples of simply ordered classes, to illustrate some of the more important types of serial order. Most of these examples wiU be discussed at length in later chapters. In each case a class K and a relation ■< are so defined that the system (K, < ) satisfies the conditions expressed' ia postulates 1-3 (§ 12). The existence of any one of these systems is suflacient to show that the postulates are consistent, that is, that no two con- tradictory propositions can be deduced from them. For, the postulates and all their logical consequences express properties of these systems, and no really existent system can have contradictory properties.* f (1) K = the class of all the natural munbers (or the first n of them), with < defined as " less than." This is an example of a " discrete series " (see chapter III). (2) K = the class of all the points on a line (with or without end-points), with -< defined as " on the left of." This is an example of a " continuous series " (see chapter V). * On the consistency of a set of postulates, see a problem of D. Hilbert's, translated in BuU. Amer. Math. Soc, vol. 8 (1902), p. 447, and a paper by A. Padoa, L'Enseignement Mathhnatique, vol. 5 (1903), pp. 85-91. Also D. Hilbert, Verhandl. des. S. intemat. Math.-Kongresses in Heidelberg, 1904, pp. 174^185; French translation, Ens. Math., vol. 7 (1905), pp. 89-103; English translation, Mmist, vol. 15 (1905), pp. 338-352. 14 TYPES OF SERIAL ORDER §19 (3) K = the class of all the points on a square (with or without the points on the boundary), with < defined as follows: let x and y represent the distances of any point of the square from two adja- cent sides; then of two points which have unequal a;'s, the one having the smaller x shall precede, and of two points which have the same x, the one having the smaller y shall precede. In this way aU the points of the square are arranged as a simply ordered class. (4) By a similar device, the points of all space can be arranged as a simply ordered class. Thus, let x, y, and z be the distances of any point from three fixed planes; then in each of the eight octants into which all space is divided by the three planes, arrange the points in order of magnitude of the a;'s, or in case of equal a;'s, in order of magnitude of the y's, or in case of equal a;'s and equal y's, in order of magnitude of the z's; and finally arrange the octants themselves in order from 1 up to 8, paying proper attention to the points on the bounding planes. (5) K = the class of all proper fractions, arranged in the usual order. This is an example of a series called " denumerable and dense " (see chapter IV). ^ '" By a proper fraction (written m/n) we mean an ordered pair of natural numbers, of which the first number, m, called the numera- tor, and the second nmnber, n, called the denominator, are rela- tively prime, and m is less than n; and by the " usual order " we mean that a fraction m/n is to precede another fraction p/q when- ever the product m X g is less than the product n "X. p. The class as so ordered clearly satisfies the conditions 1-3, as one sees by a moment's calculation. (6) K = the class of all proper fractions arranged in a special order, as follows: of two fractions which have unequal denomina- tors, the one having the smaller denominator shall precede, and of two fractions which have the same denominator the one having the smaller numerator shall precede. In contrast with example (5) , this series is of the same type as the series of the natural numbers arranged in the usual order, as the following correspondence will show (compare § 42) :* * Cf. G. Cantor, loc. dt. (1895), p. 496. 1 19 SIMPLY ORDERED CLASSES OR SERIES 15 1 2 3 4 5 6 7 8 9 10 11 1 1 2 1 3 1 2 3 4 1 5 2 3 3 4 4 5 5 5 5 6 6 These two examples, (5) and (6), illustrate the obvious fact that the same class may be capable of being arranged in various different orders. (7) As another example, let K be a class whose elements are natural nimibers affected with other natural numbers as subscripts; for example, li, 64, etc.; and let the relation of order be defined as foUows: of two nmnbers which have unequal subscripts, the one having the smaller subscript shall precede, and of two numbers which have the same subscript, the smaller number shall precede. The system may be represented thus, the relation < being read as " on the left of: " li, 2i, 3i, . . .; I2, 22, 32, . . .; Is, 2$, 3$, ...;... . This is an example of what Cantor has called, in a technical sense, a " well-ordered series " (see chapter VII). (8) An example of a somewhat different character is the follow- ing: * let K be the class of all possible infinite classes of the natural numbers, no number being repeated in any one class; f and let these classes be arranged, or set in order, as follows: any class a shall precede another class h when the smallest number in a is less than the smallest number in h, or, if the smallest n niunbers of a and h are the same, when the (n -|- l)st niunber of a is less than the (n -h l)st number of 6. A moment's reflection shows that this system satisfies the condi- tions for an ordered class; it will appear later that it belongs to the type of series called continuous (see § 63, 5). A more familiar example of the same type is the following: (9) K = the class of all non-terminating decimal fractions be- tween and 1, arranged in the usual order. (Compare § 40.) * B. Russell, Principles of Mathematics, vol. 1, p. 299. t For example, the class of aU prime numbers, or the class of all even num- bers, or the class of all even numbers greater than 1000, or the class of all perfect cube numbers, or the class of all numbers that begin with 9, or the dass of all numbers that do not contain the digit 5, would be an element of K. 16 TYPES OF SERIAL ORDER §20 By a non-terminating decimal fraction between and 1, we mean a rule or agreement by which every natural number has assigned to it some one of the ten digits 0, 1, 2, . . . , 9, excluding, however, the rules which would assign a to every niunber after any given number (these excluded rtdes giving rise to the terminating deci- mals) . * The digit assigned to any particular number n is called the nth digit of the decimal, or the digit in the nth place. By the " usual order " within this class, we mean that any decimal a is to precede another decimal b when the first digit of a is less than the first digit of b, or, if the first n digits of a and 6 are the same, when the (n + l)st digit of a is less than the (n + l)st digit of 6 (the digits being taken in the order of magnitude from to 9). All these examples of simply ordered classes have been chosen from the domains of arithmetic and geometry; among the other examples which readily suggest themselves the following may be mentioned : (10) The class of all instants of time, arranged in order of priority. (11) The class of all one's distinct sensations, of any particular kind, as of pleasure, pain, color, warmth, sound, etc., arranged in order of intensity. (12) The class of aU events in any causal chain, arranged in order of cause and effect. (13) The class of all moral or commercial values, ^arranged in order of superiority. (14) The class of all measurable magnitudes of any particular kind, as lengths, weights, volumes, etc., arranged in order of size. Examples of systems (K, < ) which are not series 20. In this section we give some examples of systems (K, < ) which are not series because they satisfy only two of the three con- ditions expressed in postulates 1-3 (§ 12). The existence of these systems proves that the three postulates are independent — that is, that no one of them can be deduced from the other two. (For, * It should be noticed that what we are here required to grasp is not the infinite totaUty of digits in the decimal fraction, but simply the rule by which those digits are determined. §20 SIMPLY ORDERED CLASSES OR SERIES 17 if any one of the three properties were a logical consequence of the other two, every system which had the first two properties would have the third property also, which, as these examples show, is not the case.) In other words, no one of the three postulates is a re- dundant part of the definition of a serial relation.* (1) Systems not satisfying postulate 1 (namely: if a 5^ 6, then a < b orb < a). (a) Let K be the class of all natural numbers, with ■< so defined that a precedes b when and only when 2a is less than b. (6) Let K be the class of all human beings, throughout history, with -< defined as " ancestor of." (c) Let K be the class of all points (x, y) in a given square, with (xi, j/i) < (x2, 2/2) when and only when Xi is less than X2 and 2/1 less than j/2. In all these systems, postulates 2 and 3 are clearly satisfied, t (2) Systems not satisfying postulate 2 (namely: ii a < b, then af^b). (a) Let K be the class of all natural numbers with a < b signify- ing " a less than or equal to 6." (6) Let K be any class, with a < b signifying " a is co-existent with 6." Both these systems satisfy postulates 1 and 3. (3) Systems not satisfying postulate 3 (namely: if a -< 6 and b < c, then a < c). (a) Let K be the class of all natural numbers, with ■< meaning " different from." * This method of proving the independence of a set of postulates is the method which has been made famUiar in recent years by the work of Peano (1889), Padoa, Fieri, and HQbert (1899). For a discussion of the " complete independence " of these postulates in the sense defined by E. H. Moore (1910), see a forthcoming paper by E. V. Huntington, Complete existential theory of the postulates for serial order, Bull. Amer. Maih. Soc. (1917). t Another very interesting example of a system of this kind is the so- called " conical order " studied by A. A. Robb in his book: A Theory of Time and Space (Cambridge, Eng., 1914). 18 TYPES OF SERIAL ORDER §20 (6) tet X be a class of any odd number of points distributed at equal distances around the circumference of a circle, with a , wa = w% ... * * Cantor, loc. cU. (1897), p. 242. It should be noted that thia notation has recently been abandoned, the subscripts under the a'a being now used for another purpose; see § 83. \ 68 TYPES OF SERIAL ORDER §80 And so on ad infinitum; but none of the well-ordered series thus constructed will contain more than a denumerable infinity of elements (compare § 38). 80. In order to understand one further matter of notation, con- sider a well-ordered series of the tj^e represented, say, by 0)3.5 -I- w^7 + 01 + 2. Here the plus signs indicate that the series is made up of four parts, in order from left to right; the first part consists of a series of type 01^ taken five times in succession; the second part consists of a series of type co^ taken seven times in succession; the third part is a single series of type &>; and the last part is a finite series containing two elements. — And so in general the notation W.VO + Uf-Kvi + £0''-^J'2 + . . . + V^, where ju is a positive integer, and the coefficients vq, vi, va, . . . , v^ are positive integers or zero, is to be interpreted in a s imil ar way.* It will be noticed that in the case of a progression, or of any well- ordered series of the types described in §§ 78-79, the whole series is ordinally similar to each of its upper segments (§ 47) ; that is, if we cut off any lower segment from the series, the type is not altered. This is not true in the case of the well-ordered series of the types described in the present section. General properties of well-ordered series 81. The fundamental properties of well-ordered series are devel- oped very carefully and clearly in Cantor's memoir of 1897; the following theorems may be mentioned as perhaps the most im- portant: (1) Every subclass in a well-ordered series is itself a well-ordered series. (2) If each element of a well-ordered series is replaced by a well- ordered series, and the whole regarded as a single series, the result will be still a weU-ordered series (compare the examples in §§ 78- 79). (These two theorems follow at once from the definition in § 76, 1.) * Cantor, loc. cit. (1897), p. 229. §83 WELL-ORDERED SERIES 69 Definition. The part of a well-ordered series preceding any given element a is called a lower segment {Ahschnitt) of the series (compare §47).* (3) A well-ordered series is never ordinally similar to any one of its lower segments, or to any part of any one of its lower segments. (4) If two well-ordered series are ordinally similar, the ordinal correspondence between them can be set up in only one way (com- pare §§ 26, 45, 61, and §§ 53, 65). (5) Any subclass of a well-ordered series is ordinally similb,r to the whole series or else to some one of its lower segments. (6) If any two weU-ordered series, F and G, are given, then either F is ordinally similar to G, or F is ordinally similar to some definita lower segment of G, or G is ordinally similar to some definite lower segment of F; and these three relations are mutually exclusive. In the first case, F and G are of the same type; in the second case, F is said to be less than G; and in the third case, G is said to be less than F. 82. By virtue of this theorem 6, the various types of well-ordered series, when arranged " in the order of magnitude " (as defined in the theorem), farm a series (§ 74) with respect to the relation " less than "; and, as Cantor has shown, this series is itself a well-ordered series. Moreover, by theorem 2, every possible collection of types of well-ordered series, arranged in order of magnitude, will be itself a well-ordered series. Classification of the well-ordered series 83. The classification of the well-ordered series is a characteristic feature of Cantor's theory; since, however, the method of pro- cedure, when pushed to its logical extreme, has led to controversy, * Most writers, including Russell, translate Ahschnitt by segment (without qualifying adjective); but since the word " segment " is aheady used in several different senses (see, for example, Veblen, Trans. Amer. Math. Soc, vol. 6, p.- 166, 1905), it has seemed to me safer to use the longer term " lower segment," about which there can be no ambiguity. 70 TYPES OF SERIAL ORDER §83 the whole scheme is regarded with a certain measure of suspicion.* The classification is as follows: First, every well-ordered series in which the number of elements is finite is said to belong to the first class of well-ordered series. Now take all the types of series belonging to the first class, and arrange them in order of magnitude (§ 82) ; the result is a well- ordered series of a certain type, called co (compare § 24). Then every well-ordered series whose elements can be put into one-to- one correspondence (§ 3) tvith the elements of w is said to belong to the SECOND CLASS. In particular, the series of type w are the smallest series of the second class. Next, take all the types of series belonging to the second class, and arrange them in order of magnitude; the resulting series is a well-ordered series of a certain type, called wi (or Q). * On the paradoxes of Burali-Forti, Russell, and Richard, and other ques- tions of mathematieal logic, see, for example, C. Burali-Forti, Bend, dd circ. mat. di Palermo, vol. 11 (1897), pp. 154^164; E. Borel, Legons sur la th&orie des fonctions (1898), pp. 119-122, especially the second edition (1914), pp. 102- 174; also a remark in LdouvUk's Joum. de Math., ser. 5, vol. 9 (1903), p. 330; D. Hilbert, Jahresher. d. D. Math.-Ver., vol. 8 (1899), p. 184; B. Russell, Pririn ciples of Mathematics (1903), chapter 10; E. W. Hobson, Proc. Land. Math. Soc, ser. 2, vol. 3 (1905), pp. 170-188; A. Schonflies and A. Korselt, Jahresher. d. D. Math.-Ver., vol. 15 (1906), pp. 19-25 and 215-219; P. E. B. Jourdain and G. Peano, Bivista di Matematica, vol. 8 (1906), pp. 121-136 and 136-157; G. H. Hardy, A. C. Dixon, E. W. Hobson, B. Russell, P. E. B. Jomdain, and A. C. Dixon, Proc. Lond. Math. Soc, ser. 2, vol. 4 (1906), pp. 10-17, 18-20, 21-28, 29-53, 266-283, and 317-319; B. Russell, Bev. de Mitaphys. et de Mm., vol. 14 (1906), pp. 627-660; J. Richard, Acta MathemaMca, vol. 30 (1906), pp. 295- 296, and Ens. Math., vol. 9 (1907), pp. 94r-98; E. B. WUson, Evil. Amer. Math. Soc, vol. 14 (1908), pp. 432-443; A. Schonflies, E. Zermelo, and H. Poin- cai6. Acta Mathematica, vol. 32 (1909), pp. 177-184, 185-193, and 195-200; A. Koyrg and B. Russell, Beu. de M&taphys. et de Mor., vol. 20 (1912), pp. 722- 724 and 725-726; H. Dingier, Jahresher. d. D. Math.-Ver., vol. 22 (1913), pp. 307-315; N. Wiener, Messenger of Mathematics, vol. 43 (1913), pp. 97-105; a curious paper by H. Glause, Bend, del aire. mat. di Palermo, vol. 38 (1914), pp. 324-329; and the recent treatises by Schonflies, Konig, and HausdorfE, cited in a footnote to § 73; especially Whitehead and Russell, Prineijna Mathe- matica, vol. 1 (1910), pp. 63-68. On the controversy especially connected with Zermelo's " multiplicative axiom," see the references under § 84. On the problem of consistency see references under § 19. §84 WELL-ORDERED SERIES 71 Then every well-ordered series whose elements can be put into one- to-one correspondence with the elements of ui is said to belong to the THIRD CLASS. In particular, the series of type wi are the smallest series of the third class. And so on. In general, every well-ordered series whose elements can be put into one-to-one correspondence with the elements of w, (where v is any positive integer) is said to belong to the {v + 2)th class; and the series of type co, will be the smallest series of that class.* Moreover, by an extension of the device already employed several times, we can define a class of well-ordered series whose smallest type would be denoted by w^, or even w„^; and so on, ad infinitum; so that when we speak of the nth class of well-ordered series, n need not be a positive integer, but may itself denote the type of any weU ordered series. 84. In order to justify this classification, it is necessary to show that the classes described are really all distinct, so that no well- ordered series belongs to more than one class; and further, that well-ordered series belonging to each class actually exist, so that no class is " empty." Cantor has completed this investigation only as far as the first and second classes; each of the examples men- tioned above is a weU-ordered series of the first or second class (since the number of elements in each case is at most denumerable, in view of § 38) ; no similar example of a series of even the third class has yet been satisfactorily constmcted.f Problems concerning * The notation w„ for the smallest type of the {v + 2)th class was intro- duced by Russell, Principles of Mathematics, vol. 1 (1903), p. 322; compare Jourdain, Phil. Mag., ser. 6, vol. 7 (1904), p.' 295. The symbols u and il were first used in this connection by Cantor in Math. Ann., vol. 21, pp. 577, 582 (1883). t The question whether every .class can be arranged as a well-ordered series, was first proposed by Cantor ia 1883 {Math. Ann., vol. 21, p. 550). The con- troversy centers about two papers by E. Zermelo; Beweis doss jede Menge wohlgeordnet werden kann. Math. Ann., vol. 59 (1904), pp. 514r-516; Never Beweis fur die Moglichkeit ciner WoMordnung, Math. Ann., vol. 65 (1907), pp. 107-128. See, for example, J. KOnig, A. Schonflies, F. Bernstein, E. Borel, and P. E. B. Jourdain, Maih. Ann., vol. 60 (1905), pp. 177, 181, 187, 194, 465; J. Hadamard, R. Baire, H. Lebesgue, and E. Borel, Bvll, de la Soc. Math, de 72 TYPES OF SERIAL ORDER §85 the existence of the higher classes, and the question whether every collection can be arranged as a well-ordered series, are still being actively debated (see § 89). 85. The various classes of well-ordered series can also be defined by purely ordinal postulates, as Veblen has shown how to do in his recent memoir.* Thus, a well-ordered series of the first class is any well-ordered series which satisfies not only the postulates 1-6 of § 74, but also the further conditions 7i and 8i, namely: Postulate 7i. Every element except the first has a predecessor (§ 17) . Postulate 8i. There is a hist element (§ 17). The type w is then defined by postulates 1-6 with 7i and 8'i, -where 8'i, is the contradictory of 8i: Postulate 8'i. There is no last elemervt. Next, a well-ordered series of the second class is any well-ordered series, not of the first class, which satisfies 72 and 82, namely: Postulate 72. Every element except the first either has a predeces- sor or is the upper limit of some subclass of type w {asjiist defined). Postulate 82. There is either a Uist element, or a subclass of type w which surpasses any given element of the series.f The type «i (or U) is then defined by postulates 1-6 with 72 and 8'2, where 8'2 is the contradictory of 82. Postulate 8'2. There is no last element; and every subclass of type u has an upper limit in the series. France, vol. 33 (1905), pp. 261-273; G. Peano, Rivista di Matematica, vol. 8 (1906), p. 145; J. Konig, Math. Ann., vol. 61 (1905), pp. 156-160, and vol. 63 (1906), pp. 217-221; H. Poincar^, Rev. de Mitaphys. et de Mm:, vol. 14 (1906), pp. 294r-317; H. Lebesgue, BvU. de la Soc. Math, de France, vol. 35 (1907), pp. 202-212; G. Vivanti, Rend, del circ. mat. di Palermo, vol. 25 (1908), pp. 205- 208; G. Hessenberg, CreUe's Joum. fur Math., vol. 135 (1908), pp. 81-133, 318; E. Zermelo, Math. Ann., vol. 65 (1908), pp. 261-281; and the recent treatises by Schonflies, Konig, and HausdorS cited in a footnote to § 73, espe- cially Whitehead and RuBsell, Principia Mathematica, vol. 3 (1913), p. 3. For a third proof by F. Hartogs (1915), see § 89a. * O. Veblen, Trans. Amer. Math. Soc, vol. 6, p. 170 (1905). t That is, if x is any element of the given series, there is an element y in the subclass for which x -K y. §86 WELL-ORDERED SERIES 73 Similarly, a well-ordered series of the third class is any weU- ordered series, not of the first or second class, which satisfies Is and 83, namely: Postulate 73. Every element except the first either has a predeces- sor, or is the upper limit of some svbclass of type u, or is the upper limit of some subclass of type wi. Postulate 83. There is either a last element, or a subclass of type w which surpasses any given element, or a subclass of type «i which surpasses any given element. The type W2 is then defined by postulates 1-6 with 73 and S's, where, as before, S's denotes the contradictory of 83: Postulate S's. There is no last element; every subclass of type u> has an upper limit in the series; and every subclass of type coi has an upper limit in the series. And so on. The establishment of definite sets of postulates like these seems to me an essential step toward the solution of the diffi- cult problems connected with this subject. For example. Cantor's proof that a series of type Q is non-denumerable is simply a dem- onstration that no denumerable series can satisfy the eight postu- lates here numbered 1-6, 72, and S'a. The transfinite ordinal numbers 86. It is now easy to explain what is meant by the ordinal nunv- bers (Ordnungszahlen), in the generalized sense in which Cantor now uses that term: they are simply the various types of order ex- hibited by the well-ordered series.* In other words, according to the^ theory of Russell, the ordinal number corresponding to any given well-ordered series is the class of all series which are ordinally similar I to the given series; any one of these ordinally similar series may be^ taken to represent the ordinal number of the given series.f The ordinal nmnbers of the first class (§ 83) are the^mte ordinal numbers, with which we have always been famihar; the ordinal * Cantor, Zeitschrift fiir Philos. und phOos. Kritik, vol. 91 (1887), p. 84; and Math. Ann., vol. 49 (1897), p. 216. t Russell, Principles of Mathematics, vol. 1 (1903), p. 312. 74 ( TYPES OF SERIAL ORDER §87 numbers of the second or higher classes are the transfinite ordinal mimbers created bv Canto r, which constitute, in a certain true sense, " eitie Fortselzung der realen gamen Zahlenreihe iiber das Unendliche hirums." * The smallest of the transfinite ordinals is w. By the mxm, a + 6, of two ordinal numbers, a and h, is meant simply the type of series obtained when a series of type a is followed by a series of type 6 and the whole regarded as a single series.f Clearly a + fe wiU not always be the same as 6 + a (for example, 1 + CO = w, while w + 1 is a new type) ; but always {a-'rh) + c = a + (6 + c). By the prodiict, ah, of an ordinal number a multiplied by an ordi- nal number h, is meant the type of series obtained as follows: in a series of type b replace each element by a series of type a, and regard the whole as a single series; the result will be a well-ordered series (by § 81, 2), and the type of this well-ordered series is what is meant by afe.J Clearly ab will not always equal ba (for example, 2w = £0, while «.2 is a new type); but always (ab)c = a{bc), and also a(Jb + c) = ab + ac, although not (& -f c)a = ba + ca. The definition of a*, where a and b are general ordinal munbers is too comphcated to repeat in this place. § Enough has at any rate been said to give at least some notion of the nature of the artificial algebra which Cantor has here so ingeniously constructed. The transfinite cardinal numbers 87. For the sake of completeness I add here a brief note on the meaning of some of the terms in Cantor's theory of the (general- ized) cardinal numbers.] | This theory has nothing to do with series, or ordered classes, but is a development of the theory of classes as such (§ 11) ; nevertheless the difficulties met with in this theory are closely analogous to the difficulties we have pointed out * Math. Arm., vol. 21 (1883), p. 545. t Math. Ann., vol. 21 (1883), p. 550. t In Cantor's earlier definition of the product ab, a was the muItipUer {loc. cU., 1883, p. 551); the order was changed in his later articles, bo that o is now the muItipUcand (see he. cit., 1887, p. 96, and 1897, pp. 217, 231). § Cantor, Math. Ann., vol. 49 (1897), p. 231; Hausdorff, loc. cit. (1914), p. 147. 11 The standard account of this theory is in Cantor's article of 1895. §88 WELL-ORDERED SERIES 75 in the theory of the ordinal numbers (§ 84), and it is impossible to read the literature of either theory without some acquaintande with the other. 88. If two classes can be brought into one-to-one correspondence (§ 3), they are said to be equivalent {dquivalent). For example, the class of rational niunbers is equivalent to the class of positive integers (compare § 19, 6) ; or the class of points on a line is equiv- alent to the class of all points in space (§ 71). The cardinal number (Machtigkeit) of a given class A is then defined as the class of all those classes which are equivalent to A* The finite cardinal numbers are the cardinal numbers which belong to finite classes; the transfinite cardinals are those which belong to infinite classes (§ 7). According to this definition, if two classes A and B are equivalent, their cardinal numbers will clearly be identical. If a class A is equivalent to a part of a class B, but not to the whole, then A is said to be less than B; m. this case the cardinal number of A wiU be less than the cardinal number of B. We cannot, however, afiirm that all cardinal numbers can be arranged as a series, in order of magnitude, for while postulates 2 and 3 (§ 74) clearly hold with regard to the relation "less than" as just defined, postulate 1, which may be called the principle of comparison (VergUicKbarkeit) for classes, has never been proved. In other words, non-equivalent classes may possibly exist, neither of which is " less than " the other; but see § 89a.t On the other hand, Cantor has proved that when any class is given, a class can be constructed which shall have a greater cardi- nal number than the given class, t * The tenn Machtigkeit was first used by Cantor in CreUe's Jowm.fUr Math., vol. 84, p. 242 (1877). Power, potency, multitude, and dignity are some of the English equivalents. The term Cardinalzahl was introduced in 1887. Cf. Cantor, loe. cit. (1887), pp. 84 and 118. The notion of a cardinal number as a doss is emphasized by Russell; Principle of Mathematics, vol. 1 (1903), p. 312. t Compare E. Borel, Legons sur la thSorie des fonctions (1898), pp. 102-110. t Cantor, /. d. D. Math.-Ver., vol. 1 (1892), p. 77; E. Borel, loc. ctt. (1898), p. 107; C. S. Peirce, Monist, vol. 16 (1906), pp. 497-502. 76 TYPES OF SERIAL ORDER § 89 For example, let C denote the class of elements in a linear con- tinuum, say the class of points on a line one inch long (compare § 71) ; and let C denote the class of all possible " bi-colored rods " which can be constructed by painting each point of the given line either red or blue. Then the class of rods, C", has a higher cardinal nmnber than the class of points, C, as may be proved as follows: In the first place, C is equivalent to a part of C; for example, to the class of rods in which one point is painted red and aU the other points blue. Secondly, C is not equivalent to the whole of C; for, if any alleged one-to-one correspondence between the rods and the points were proposed, we could at once define a rod which would not be included in the scheme: namely, the rod in which the color of each point x is opposite to the color of the point x in the rod which is assigned to the point x of the given line; this rod would differ from each rod of the proposed scheme in the color of at least one point. (Cf. § 40.) The class C' has therefore a higher cardinal nimiber than the class C. It is not known, however, whether there may not be other classes whose cardinal niunbers lie between the cardinal numbers of C and C. 89. Of special interest are the cardinal niunbers of the various tj^es of weU-ordered series; but when we speak of the cardinal number of a series, it must be understood that we mean the cardinal number of the dass of elements which occur in the series, without regard to their order. The cardinal numbers of the finite well-ordered series are the finite cardinal numbers, with which we have always been familiar. The cardinal number of a series of type w (§ 24) is denoted by the Hebrew letter Aleph with a subscript 0:* No. This xo will then be the cardinal number of any well-ordered series of the second class (§ 83), since all the series of the second class are, by definition, equivalent. The cardinal number of a series of type wi (or 12) is denoted by Ni; this will then be the cardinal number of any well-ordered series of the third class. * Cantor, Math. Ann., vol. 46 (1895), p. 492. §89a WELL-ORDERED SERIES 77 And so on. In general, the cardinal number of a series of type Wp is denoted by K; this will then be the cardinal number of any well-ordered series of the {v + 2)th class. If we assume the series of classes of ordinal numbers (§ 84). we thus obtain a series of cardinal numbers Xi, Ni, . . . , Nu, • • • > arranged in order of increasing magnitude; this series will be a well-ordered series with respect to the relation " less than," and ordinally similar to the series of ordinal numbers; but all the diffi- culties that are involved in the one series are involved ia the other. In particular, it requires proof to show that two Alephs, as N„ and Nh-1, are really non-equivalent, and that no other cardinal number hes between them. Cantor has shown merely that No is the smallest transfinite cardinal number, and that Ni is the mmiber next greater.* Again, the vexed question: can the cardinal number of the linear continuum (§ 54) he found among the Alephs ? is equivalent to the question: can the class of elements in the continuum be arranged in the form of a well-ordered series f (See § 89o.) It is usually supposed that the cardinal number of the continuum wUl prove to be Ni. 89a. In this section we reproduce, in brief outline, Hartogs's recent proof of Zermelo's theorem that every class can be arranged as a well-ordered series.^ Let there be given any non-empty class, M. First, consider aU possible weU-ordered series, G, H, . . . , whose elements belong to M, and let N be the class composed of these series, together with the null series, 0. Next, within this class N, group together aU the well-ordered series G', G", . . . which are similar to G into a subclass, g; group together all the well-ordered series H', H", . . . which are similar to H into a subclass, h; etc. These subclasses, g, h, . . . (one of which is the null class) are now to form the elements of a series, L, whose rule of order is the following: A subclass g is said to precede a subclass h {g < h),ii * Math. Ann., vol. 21, p. 581 (1883). t F. Haxtogs, Vber das Problem der Wohlordnung, Math. Ann., vol. 76 (1915), pp. 438-443. 78 TYPES OF SERIAL ORDER § 89a any one of the well-ordered series belonging to g is similar to a lower segment of any one of the well-ordered series H belonging to h. (It is clear that it makes no difference which G is taken from g, or which H is taken from h, etc., since aU the (?'s in g are similar to each other, and all the H's in h are similar to each other, etc.) From this definition it follows that if any two of the subclasses, say g and h, are distinct, then either g < hov else h < g, and not both; also that ii g, h, i are three subclasses such that g < h and h < i, then g ■< i. In other words, the subclasses g,h, . . . form a series, L, with respect to the rule of order stated. Moreover, the series L thus constructed is a well-ordered series. The proof is as follows: Let g be any element of L, and let G be any one of the well-ordered series belonging to g. Then the elements of L which precede g stand in a one-to-one correspondence (preserving order) with the lower segments of G. But the lower segments of G form a well-ordered series; hence, no matter what element g may be chosen, the elements of L preceding g form a weU-ordered series. From this it follows that the series L itself must be well-ordered. For, if L were not weU-ordered, it would contain at least one regres- sion, r (§ 76), so that if fl' is any element of r, then the elements of r preceding g would form a series having no first element; but this is impossible, since the elements of r preceding g are part of the elements of L preceding g, and hence are part of a well-ordered series, and as such must have a first element. The whole series L is therefore a weU-ordered series. Further, each of the weU-ordered series G, H, . . . which can be formed out of elements of M, is s imil ar to some lower segment of L. In particular, the weU-ordered series G is similar to that lower segment of L which is determined by the subclass g to which G belongs. For, as we have just noted, there is a one-to-one corre- spondence (preserving order) between the subclasses that precede g and the lower segments of G, and there is also a one-to-one corre- spondence (preserving order) between the lower segments of G and the elements of G. Considering now the elements of L, without regard to their order, we see at once that the elements of L cannot he placed in one-to-one correspondence mth the elements of M, nor with the elements of any part of M. For, suppose the contrary ; then M, or some part of M, would be capable of being well-ordered, so that we should have a well-ordered series, formed out of elements of M, and similar to L; but this is impossible, since we have proved that every such weU- ordered series is similar to some lower segment of L, and no lower segment of L can be similar to L itself. § 90 WELL-ORDERED SERIES 79 Finally, if we assume the principle of comparison between classes (§ 88), there is only one alternative left, namely: it must he pos- sible to place the elements of M in one-to-one correspondence with the elements of a part of L. But since L is well-ordered, every part of L is well-ordered; hence we have the theorem that whatever class M may be, its elements can always be so arranged as to form a well-ordered series.* 90. We speak next of the sums and products of the cardinal numbers.f The sum A + B oi two classes A and B which have no common element is the class containing all the elements of A and B to- gether. If o and b are the cardinal numbers of two such classes A and B, the sum, a + b,oi these two cardinals is then defined as the cardinal number of A + B. Clearly a + b = b -\- a, and (a-{-b) + c = a+{b-\- c). The product, AB, of two classes A and B which have no common element is the class of aU couples (a, jS), where a is any element of A, and /3 any element of B. If a and b are the cardinal numbers of two such classes, the prod- uct, db, of these two cardinals is then defined as the cardinal num- ber of AB. Clearly, ab = ba, {ab)c — a{bc), and a{b + c) =■ ab -\- ac. linally, A^ denotes the class of aU coverings (Belegungen) of B by A, where a " covering " of B by A is any law according to which each element of B determines uniquely an element of A (not ex- cluding the cases in which various elements of B may determine the same element oi A).t The &"■ power of a, a*, where a and b are the cardinal numbers of any two classes A and B, is then defined as the cardinal nimiber of A^. Clearly a''a' = 0*+", (a*)° = a'°, and (abY — a'b". In this way Cantor has constructed an artificial algebra of the cardinal numbers, analogous to the algebra of the ordinal numbers, * Hartogs's paper shows that the following three principles are equivalent: (1) the principle of comparison between classes; (2) the principle that every class can be weU-ordered; and (3) the much discussed " multipUcative axiom" of Zermelo. See references under § 84, especially Whitehead and RusseU, Prindpia Mathemaiica, vol. 1 (1910), p. 561. t ZeUschr.f. Phil. u. phUoa. KrUik, vol. 91 (1887), pp. 120-121; Maih. Ann., vol. 46 (1895), p. 485. X Maih. Ann., vol. 46 (1895), p. 487. 80 TYPES OF SERIAL ORDER § 91 but resembling much more closely the familiar algebra of the finite integers. Perhaps the most famous result obtained in this algebra is the formula* c = 2'*o, where c stands for the cardinal number of the continuum, and 2«a is determined according to the rule just stated for the powers of cardinal numbers. It becomes an important question, therefore, to decide whether 2''o = Ni or not (compare § 89, end). 91. In conclusion, it may be well to repeat that when we speak of a cardinal number, we always mean the cardinal number of some given chiss; and when we speak of an ordinal number, we always _mean the ordinal number of some given well-ordered series. Whether these new concepts will find important appMcations in practical problems is a question for the future Uii dtuidu. (The elementary parts of Cantor's work have already proved useful, indeed almost indispensable, in the theory of fimctions of a real variable.f) * Math. Ann., vol. 46 (1895), p. 488. t See, for example, R. Baire, Legons sur les fondUms discontinues (1905) ; E. Borel, Lemons sur la ihSorie des fonctions, 2nd edit. (1914); E. W. Hobson, Theory of Functions of a Real Variahle (1907); J. Pierpont, Lectures on the Theory of Functions of a Real Variable (1905, 1912); etc.; also the treatises cited under § 73. INDEX OF TECHNICAL TERMS The prinoipal bibliographical footnotes will be found under the introduction, and under §§ 73-74, and §§ 83-84. Alephs, § 89. Between, § 17. Binary fractions, § 30. Bound (upper and lower), § 56. Cardinal numbers, § 88. Class, § 1. (See empty, null, finite, infinite, denumerable, simply and multiply ordered, well-ordered, equivalent.) Classes of transfinites, §§ 86, 89. Closed (series), § 62. (set of points), § 62a. Cluster point, § 62a. Compact (series), § 41. (set of points), § 62o. Comparison (of classes), § 88. Consistency (of postulates), § 19. Continued fractions, § 71. Continuous (series), §§ 54, 62, 67. Continuum, §§ 61, 72. problem, § 89. Correspondence (of classes), § 3. (of series), § 16. Covering, § 90. Decimal fraction, §§ 19 (9), 40, 63 (4). Dedekind's postulate, §§ 21, 54, 75. Dense (series), §§ 41, 54, 62. (set of points), § 62o. Dense-in-itself (series), § 62. (set of points), § 62a. Denumerable (class), § 37. (series), § 41. Derived set, § 62a. Digits, § 30. Dimensionality, §§ 67-71. Discrete (series), §§ 21, 26. Distinct (elements), § 2. Element (of a class), § 1. (See dis- tinct, equal, first, last, rational, irrational, principal, limit.) Empty (class), § 1. Equal (elements), § 2. Equivalent (classes), § 88. Finite (classes), §§ 7, 27. (series), § 27. (numbers), §§ 86, 88. First (element of a series), § 17. Fraction, § 19. (See proper, decimal, binary, ternary, continued.) Framework (of a series), §§ 59, 67. Fundamental (segment), § 46. (sequence), § 62. Independence (of postulates), § 20. Induction, § 23. Infinite (classes), §§7, 27. (numbers), §§ 86, 88. Integral (numbers), §§ 22, 34, 63 (3). Irrational (elements), § 59. (numbers), § 63 (3). 81 82 INDEX OF TECHNICAL TERMS Last (element of a series), § 17. Less than, §§ 82, 88. Limit (series), §§ 49, 56, 74. (set of points), § 62a. Linear (continuous series), § 54. Mathematical induction, § 23. Multiply ordered (class), § 72. Multiphcative axiom, § 89a. Natural numbers, §§ 19 (1), 30, 36. Normal (series), § 74. Normally ordered (class), § 74. NuU (class), § 1. Nxmibers, § 63 (3). (See natural, inte- gral, fractional, rational, irrational, real, cardinal, ordinal, finite, trans- finite.) Numeration, § 30. Operations, §§ 11, 53, 65. on natural numbers, §§ 31, 35. • on transfinites, §§ 86, 90. Order, §§ 12, 16, 72, 82. Ordinal numbers, § 86. Ordinally similar (series), § 16. Origin, § 26. Part (of a class), § 6. Perfect (series), § 62. (set of points), § 62a. Point sets, § 62a. Postulates, §§ 12, 21, 41, 54, 74, 85. consistency of, § 19. independence of, § 20. Powers (of nimabers) . See operations. (cardinals), § 88. Predecessor, § 17. Principal (element of a series), § 62. Products. See operations. Progression, §§ 24, 85. Proper fraction, §§ 19 (5), 42. Rational (elements), § 59. (numbers), §§ 51, 63 (3). Real (numbers), §§ 63 (3). Regression, § 25. Relation, §§ 11, 12, 13. Section (of a continuous series), § 68. Segment, § 47. (fundamental), § 46. (upper and lower), § 47. (well-ordered series), § 81. Self-representative, § 28. Sequence, § 62. Series, § 12. (See discrete, dense, denumerable, continuous, linear, finite, closed, dense-in-itself, per- fect, well-ordered, similar.) Sets of points, § 62a. Similar (series), § 16. Simply ordered (class), § 12. Skeleton (of a series), §§ 69, 67. Subclass, § 6. Successor, § 17. Sums. See operations. System, § 11. Ternary fractions, § 52 (3). Transfinite numbers, §§ 86, 88. Types of order, § 16. Type 0,, §§ 24, 85. V §25. *u+ w, § 26. 'I, §44. e, §§61, 62. e», §69. «^ CO", §§ 78, 79. «„ §§79, 83,85. n, §§83, 85. Well-ordered (series), §§ 74, 76. PRINTED AT THE HABVABD UNIVEBBITT PBESS CAMBBIDGE, MASS., U.S.A.