Ordinal Algebras

O R D I N A L ALGEBRAS BY ALFRED TARSKI Professor of Mathematics, University of California, Berkeley WITH APPENDICES B Y CHEN CHUNGCHANG Instructor i n Mathematics, Cornell University AND BJARNI JONSSON Assistant Professor of Mathematics, Brown University 1 9 5 6 NORTH-HOLLAND P U B L I S H I N G COMPANY AMSTERDAM INTRODUCTION An important task in creating the general theory of binary relations is to develop the arithmetic of relation types, i.e., to study operations by means of which the isomorphism types of complicated relations can be obtained from those of simpler ones. This arithmetic may eventually become a powerful instrument which will give us a better insight into the structural variety of relations. At present, however, it is still in the initial stages. All that could be found until recently in the literature of the subject were: the definitions of fundamental arithmetical operations ; the most elementary and obvious consequences of these definitions; some scattered arithmetical results of a deeper character concerning order types (i.e. types of simply ordering relations), which form a rather narrow class of relation types; and, finally, the detailed development of the arithmetic for a still narrower class of relation types, in fact, for ordinals (i.e., types of well ordering relations). 1) For non-binary relations the arithmetic of relation types practically does not exist. One of the fundamental arithmetical operations on relation types is relational addition. This operation is performable on an arbitrary system of relation types which are indexed by the elements forming the field of a given relation; therefore we speak of the addition of relation types over a given relation. If the field of this relation has just two different elements, relational addition ~ Fundamental arithmetical operations on order types and ordinals 1) were f i s t defined and discussed by G. Cantor. The definitions of these operations, together with various consequences and a systematic development of the arithmetic of ordinals, can be found in various treatises of set theory, e.g. in [6], [13], and [15]. The operations were extended to arbitrary relation types by A. N. Whitehead and B. Russell; cf. [20], vol. 2, pp. 291 ff. Some new notions in this domain were introduced by G. Birkhoff; see [2], pp. 7 ff. (where references to earlier papers can also be found). 2 INTRODUCTION becomes a binary operation. Actually there are three distinct binary operations which can thus be obtained as particular cases of general relational addition; in fact, cardinal addition, square addition, and ordinal addition. Among these three operations, ordinal addition proves to be the only one which presents a considerable mathematical interest. The main purpose of this monograph is just the development of the theory of ordinal addition for arbitrary relation types. It will be seen from our discussion that a substantial body of results is now available in this domain. Most of the results we shall establish have very simple formulations, but their proofs are usually far from being obvious and sometimes are really involved. Also various problems in the theory of ordinal addition, with equally simple formulations, are still open, and no mechanical method for solving such problems will ever be found. We are primarily interested in binary ordinal addition and its immediate recursive generalization, the ordinal addition of finite sequences. It turns out, however, that the study of finite sums is greatly facilitated by application of certain results concerning infinite sums, in fact, ordinal sums of simple infinite sequences. For this reason we discuss here sums of simple infinite sequences as well, but only insofar as the properties of these sums are involved in the study of finite addition. Another a