On Classes in General

1. A class (Menge, ensemble) is said to be determined by any test or condition which every entity (in the universe considered) must either satisfy or not satisfy; any entity which satisfies the condition 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 numbers 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 living 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 b of a given class are regarded as interchangeable 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 reciprocally each element of the second class is paired with one and 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, 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 number is double some particular natural number; thus:

1,2,3, ...,

2,4,6, ...

Again, the class of points on a line 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 O 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 ownership between the class of soldiers and the class of shoes which they wear; we have here what may be called a two-to-one correspondence 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 conditions mentioned in the definition of one-to-one correspondence are essential.

5. Obviously if two classes can be put into one-toone correspondence with any third class, they can be put into one-to-one correspondence with each other.

6. A part ("proper 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 subclass (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 oneto-one correspondence 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 Paradoxien des Unendlichen (published posthumously 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-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:

(1) 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 null class).

By hypothesis, there is a part, A', of A' which can be put into one-to-one correspondence with the whole of A'; therefore the class composed of A'and A? will be a part of A which can be put into one-to-one correspondence with the whole of A.

(2) If any one element is excluded from an infinite class, the remaining 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, A1, of A, which can be put into one-to-one correspondence with the whole of A, and is therefore itself infinite. If this part A1 does not contain the element 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 A1, and by replacing x by y in A1 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 class 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, or a class containing merely a single element (these classes being obviously finite according to the definition of § 7).

This result will 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 numbers we have the relation of "less than" and the operations of addition and multiplication;* 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. The ordinary algebra of real or complex numbers is a combination of the two.

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.

General Properties of Simply Ordered 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 (& >a, which means the same thing), may be read: "a precedes b" (or "b follows 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 containing 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 orb < a.

Postulate 2. If a < b, then a and b are distinct.

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 is false.?

(For, if a< b and b< a were both true, we should have, by 3, a< a, whence, by 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 familiar 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 will 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).

It will be noticed that in the first of these examples the correspondence between the two series can be set up in only one way, while 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 definitions of a few useful technical terms.

Definition 1. In any series, if a< x and x< b, then x is said to lie between a and b.

Definition 2. In any series, if a< x and no element exists between a and x, then x is called the element next following a, or the (immediate) successor of a. Similarly, if 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.

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 element, but no last; (3) those that have a last element, but no first; and (4) those that have both a first and a last.

For example, the class of all the points on a line between A and B, arranged from A to B, has no first point, and no last point, since if any point C of the class be chosen there will be points of the class between C and A and also between 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.

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 will 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 in postulates 1–3 (§ 12). The existence of any one of these systems is sufficient to show that the postulates are consistent, that is, that no two contradictory 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.

(1) K = the class of all the natural numbers (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).

(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 adjacent sides; then of two points which have unequal x'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 all 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 x's, or in case of equal x's, in order of magnitude of the y's, or in case of equal x'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 numerator, and the second number, n, called the denominator, are relatively 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 whenever the product m × q is less than the product n × 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 denominators 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.