Ordinal Algebras (Studies in Logic and the Foundations of Mathematics, 19)

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 auxiliary operation which plays some part in our discussion is the unary operation of conversion. The method applied in this monograph in the development and presentation of the theory of ordinal addition is the abstract algebraic method which was applied for analogous purposes in an earlier work of the author, [17] (see bibliography at the end of the monograph). Instead of studying relation types and their ordinal sums directly, we concern ourselves in Chapter 1 with abstract algebraic systems formed by a set A of arbitrary elements, an operation 2 on finite and simple infinite sequences of elements of A , an operation + on couples of elements of A , an operation * on single elements of A , and a distinguished element 0 of A.

INTRODUCTION

3

w e single out a certain class of such algebraic systems called the ordinal algebras, by stipulating that the elements and operations which constitute these systems satisfy some relatively simple postulates of an arithmetical character. We then develop the arithmetic of ordinal algebras. Loosely speaking, from postulates defining ordinal algebras we derive consequences concerning elements and fundamental operations of an arbitrary ordinal algebra (regarded as fixed throughout the discussion), without going into the proper algebraic study of ordinal algebras, i.e., without discussing relations between various algebras, methods of constructing these algebras, etc. I n Chapter 2 we show that the postulates defining ordinal algebras are satisfied if we take for A the set of all reflexive relation types (i.e. isomorphism types of reflexive relations), for 2 and + the familiar operations of ordinal addition, for * the operation of conversion, and for 0 the type of the empty relation. I n other words, the set A of reflexive types, with 2, +, *, and 0 thus specified, forms an ordinal algebra (and the same holds for various subsets of A , e.g., for the sets of all types of partially ordering and simply ordering relations). Hence it follows immediately that all the results obtained in Chapter 1 apply to arbitrary reflexive types and their ordinal sums. With certain modifications in the notions involved the results can be extended to arbitrary relation types. Many results in this monograph were originally established by Adolf Lindenbaum and partly by the author for order types and subsequently extended by the author to arbitrary relation types; they were first stated without proof in [S]. Most of the remaining results appear here in print for the fist time; this does not apply, of course, to various familiar elementary theorems of an auxiliary character. The algebraic treatment of the subject is new. This treatment has necessitated providing virtually new proofs for almost all the results discussed. 2, The following theorems and corollaries in this work were established 8) for order types by Lindenbaum around 1926; 1.27-1.29, 1.37, 1.38 and its converse, 1.39, 1.46, and 1.49-1.51. Theorems 1.40-1.44 were obtained in

4

INTROD17CTION

The monograph is provided with two appendices. Appendix A, by Chen-Chung Chang, contains the solution of some arithmetical problems formulated in Chapter 1. Appendix B, by Bjarni Jbnsson, concerns the general operation of relational addition. It introduces the notion of a relation type which is indecomposable relatively t o a given set A of relations (or relation types), i.e., of a type which cannot be represented as a sum of types over a relation belonging to the set A , unless all the terms of the sum except one are equal to 0. The main result of the appendix is a unique decomposition theorem by which, relatively to any given set A of relations satisfying certain general conditions, every reflexive relation type can be uniquely represented as a sum of indecomposable types over a relation belonging to the set A . This result generalizes three special unique decomposition theorems which were previously found (by Chang, Jhnsson, and the author of the monograph) and which can be obtained from the general result by taking for A the set of all cardinal relations or the set of all square relations or, finally, the set of all simply ordering relations. It may be mentioned that the first two of these special theorems are of crucial importance for the theories of cardinal addition and square addition. As a consequence of those theorems (and the commutativity of the operations involved), both cardinal addition and square addition easily reduce to the addition of cardinal numbers; hence the theories of these two operations-as opposed to the theory of ordinal addition - have a very elementary character and are indeed mathematically trivial. The author takes this opportunity to express his warm gratitude to Dr. Chang and Professor Jbnsson for enriching the contents of the same period by the author. Most of these results are stated without proof (and sometimes in a slightly different formulation) in [ 8 ] , pp. 320 f. The proofs of 1.27, 1.37, and 1.46 can be found in [14], pp. 3-7, and [15], pp. 167-169; the proofs of other theorems in this group were not previously published. For those of the remaining results which are not entirely due to the author the question of authorship will be cleared up in remarks or footnotes accompanying the theorems involved.

INTRODUCTION

5

the monograph with their interesting results. Warm thanks are also due to Dr. Chang and Mr. William Hanf for their help in preparing this book for publication. The technical work on the book was largely done during the period when the author, Hanf, and, for a short time, Chang were engaged in a research project in the foundations of mathematics sponsored by the National Science Foundation, U.S.A.

CHAPTER 1 ORDINAL ALGEBRAS AND THEIR ARITHMETIC In the following discussion we shall use some fundamental notions of general set theory; thus, e.g., the notions of an element and a subset (the membership relation E and the inclusion relation C),and those of union and intersection. The notion of an ordinul, the relations < and < between ordinals, and the operations + and . on ordinals are assumed to be known. The ordinals will be represented by variables x , 1,p, v, _...In this chapter we shall deal exclusively with finite ordinals (which may be identified with natural numbers) and with the smallest infinite ordinal, w . In formulating theorems involving some ordinals p, v, ..., the assumptions p ~ wv , ~ w... , will usually be omitted; the formulas p < o , v < w , ... will be used to express the fact that the ordinals p, v, ... are finite. In the sums p + v and products p - v involved, p will always be a finite ordinal ; as is well known, p + w = w for every p < w , and p . w = w for every p < o provided p # 0. In a difference p - v the ordinals p and v are assumed to satisfy the formula v

8

CHAPTER

1

DEFINITION 1.1. An ORDINAL ALGEBRA is a system ( A , 2,+, *, 0) formed by a set A of arbitrary elements, an operation 2 on finite and simple infinite sequences of elements of A , a n operation + on couples of elements of A , a n operation * on single elements of A , and a distinguished element 0 of A . A is assumed to be closed under the operations 2, +, *, and the following postulates are assumed to hold for arbitrary elements a, b, c, a,, b,, c,, ... of A : (I) [POSTULATE OF ELEMENTARY SUMS]. zx,,a,= 0 and &lax= a,. (11) [ASSOCIATIVE POSTULATE]. If putw and Y Q w , then

(111)

[DIRECTED REFINEMENT POSTULATE].

If x < o a x =b + C and

c f 0, then theye are two elements d , e and a n ordinal pu<w such that a,+d = b, up= d e, and e ap+l+x= c.

z
+

+ Xx,,

(IV) [REMAINDER POSTULATE]. If a,= b,+a,+l for every x < o , then there is a n element c such that ax= b,,, + c for every x <w . (v) [INVOLUTION POSTULATE]. a* * =a. (VI) [DUAL ISOMORPHISM POSTULATE]. ( a+ b)* =b* +a*. 3,

zA<,

In connection with this definition it should be pointed out that the symbols 0, +, Q are used in the monograph in two or 3) It is interesting to compare the ordinal algebras discussed in this paper with the cardinal algebras studied in [17]. There is much analogy between the two kinds of algebras-both in the defining postulates and in deeper arithmetical consequences of these postulates. The main difference consists in the fact that in ordinal algebras, as opposed to cardinal algebras, the operation is not commutative. It may seem intriguing that, although the commutative law is invariably used in arguments from the arithmetic of cardinal algebras, numerous conclusions of these arguments can be established (by means of different methods) for ordinal algebras as well. The situation clears up to some extent when one notices that the refinement postulate, which is one of the fundamental postulates for cardinal algebras (cf. [17], pp. 3ff.), is replaced in the definition of ordinal algebras by a much stronger statement -the directed refinement postulate. Also, the presence of a dual isomorphism in ordinal algebras partly makes up for the lack of the commutative law.

+

ORDINAL ALGEBRAS A N D THEIR ARITHMETIC

9

more Werent senses. Thus 0 is used to denote (i) the ordinal 0, (ii) the zero element of an ordinal algebra, (iii)the empty relation (or set), and (iv) the relation type of the empty relation. We believe it will always be clear from the context in which sense a given symbol is actually used.

It can easily be shown that in the arithmetic of ordinal algebras the element 0, the operation +, and the operation z]on finite sequences are definable in terms of the operation 2 restricted to infinite sequences; the proof is based upon Postulates (I), (11), (IV) of Definition 1.1 and Theorem 1,32(i) below. Thus ordinal algebras could be treated as algebraic systems formed by a set A , an operation z]on infinite sequences, and a unary operation *. On the other hand, it was pointed out by J6nsson that 2 cannot be defined in terms of + , *, and 0 . 4 ) As is well known, this can be shown by constructing two ordinal algebras % = ( A , z],+, *, 0) and % ' = ( A , +, *, 0 ) in which A , +, *, and 0 have the same meaning but the operations and differ. We take for A the set ~ , and cZe2.The operation consisting of five elements 0, el,,, c ~ ,cZs1, + is defined by means of the formulas: a+O=O+a=a for every a E A ; C ~ . ~ + C ~ , ~ = where = C ~ , ~ i, j , k, and 1 assume either of the two values, 1 and 2. The operation * is determined by the formulas : O* = 0 and C,:~=C~.~. 2x<pa,is defined recursively in case p < w . We put

x,

z
a x

=

C X < ,

ax

if p is the smallest finite ordinal such that a,+, if' no such p exists,

2,<,

a x

=0

for every v < o ;

= a,+ c1.1

where n is the smallest ordinal for which a, is different from 0. The definition of z ]'differs from the definition of z]only in that ~ . proof that the systems in the last formula cl,l is replaced by c ~ ,The and %' thus defined are actually ordinal algebras in the sense of 1.1 presents no difficulty. In this respect ordinal algebras differ from cardinal algebras; compare 4, 1171, p. 11.

10

1

CHAPTER

Postulates (I), (11),(V), (VI) of 1.1 have a very simple and familiar algebraic content ; they are obviously satisfied in those special ordinal algebras with which we shall concern ourselves in Chapter 2 of this paper, and do not lead by themselves to any mathematically interesting consequences. On the contrary, the directed refinement postulate, (III),and especially the remainder postulate, (IV), are of a less obvious and deeper nature. The great deductive power of our postulate system, which will be exhibited by the developments of this section, is essentially due to the presence of these last two postulates. All the ordinal algebras which will be discussed in Chapter 2 satisfy the following postulate closely related to 1.1 (11):

(11') [GENERAL ASSOCIATIVE POSTULATE]. If p,,=o, ,..., px , . . . is an infinite strictly increasing sequence of finite ordinals (i.e., ,ux<,ux+l<w lor everu x t o ) , then C X < O

ax =

I%<"

IA
As was pointed out by Hanf, Postulate (11')is not derivable from the postulates listed in 1.1. To show this Hanf considers the algebras % = ( A , 2, +, *, 0) and %'=(A, +, *, 0) constructed by J6nsson and described above in connection with the problem of the defhability of 2. In these algebras he replaces the operations z\ and 2 by the operation Z'' defined as follows: if ,u<w or if ,u=w and there is an ordinal j l t w such that aA+x=cl,lfor every x < o , then

z,

otherwise

I:<,ax

=

2x<,

ax;

ZLpax = z:

z",

The algebra defined is clearly an ordinal algebra. However, it does not satisfy (11'); for, by letting a2.x= c ~ , ~a2.x+l , = c ~ , and ~ , px = 2 - x ,

we have z < a J

a, = c1.2 #

X
x
apx+a= c1.1-

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

11

Only a few consequences of Postulate (11')are known which are relevant for our discussion (cf. the remarks following Theorem 1.38 below); hence the inclusion of this postulate in 1.1 would needlessly restrict the applicability of most of the results obtained.

DEFINITION1.2. Given an ordinal algebra % = ( A , 2, +, *, 0)) we put: (i) zz<pa,= (&Pa,*)* for every ordinal ,u and every sequence of elements a,, ..., a,, ... ( x
z:<,,

(1)

Of

o* = o*

and therefore (O+O*)*=O**.

Hence, by l.l(V),(VI), (2)

o+o*=o.

(1) and (2) give immediately (iii). (i)is obtained by induction on v. For v = 0, 1 it follows from (iii), l.l(I),(V), and 1 4 i ) . If it holds for v=v' and v=v", it also holds for v=Y'+v" by l.l(II),(VI) and l.Z(i). Hence it holds for every V<W.

Finally, (ii) is a direct consequence of l.l(V),(VI) and l.Z(ii), and the proof is complete.

THEOREM 1.4 [DUAL ISOMORPHISM THEOREM]. If % = ( A , 2,+, * ,0) i s an ordinal algebra, then %* is also an ordinal algebra which is

12

CHAPTER

1

isomorphic to 8 ;in fact, the function f defined by the formula f ( x )=x* for every x E A m a p s 8 isomorphically onto 8*. PROOF:by l.l(V),(VI), 1.2, and 1.3(iii). Theorems 1.3 and 1.4 imply a duality principle which facilitates the discussion of ordinal algebras. Consider a property P of ordinal algebras formulated exclusively in terms of fundamental notions 2, + , *, 0. If in the formulation of this property we replace respectively 2 and by C* and +*, we obtain the dual property P*. By Theorem 1.4, whenever the property P applies to an ordinal algebra 8, the dual property P* also applies to 8; if, in particular, P holds for every ordinal algebra 8, the same is true of P*.By Theorem 1.3(ii), instead of replacing + by + * in formulating P*,we can simply reverse the order of terms in each expression of the form a + b involved in the formulation of P; by Theorem 1.3(i) the same applies to expressions Zx+ a, provided the ordinal ,u is assumed to be finite. All the subsequent definitions and theorems in this section concern an arbitrary ordinal algebra % = ( A , 2, + , *, 0). This algebra i?l is treated as fixed throughout the discussion and is not referred to explicitly. The lower case Roman letters a, 6 , c, ... (possibly provided with subscripts) represent arbitrary elements of the set A . From every definition, or theorem, we obtain the dual definition, or theorem, by replacing all the symbols without stars by the corresponding symbols with stars and conversely. The duality principle (extended to defined notions) secures automatically the validity of all the dual theorems thus obtained. Without formulating the dual definitions and theorems explicitly, we shall apply them freely in the discussion; when referring to them, we shall use the reference numbers of the original definitions and theorems providing these numbers with stars.

+

In the immediately following theorems (up to 1.22) we formulate various simple and rather trivial consequences of our postulates and definitions. When applying these theorems and the underlying definitions in the subsequent discussion, we shall frequently omit explicit references.

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

xx42

THEOREM 1.5.(i) a,=a,+a,. (ii) ,1 v a x = Ex<, a, + a, =a0 + (iii) ~ , t o a x = a o +Z x < a I a l + x . PROOF:by l.l(I),(II).

I,<

a,,,

for

13

every v < 0 -

THEOREM 1.6. a+O=O+a=a.

PROOF: O+a=a is a consequence of l.l(I),(II); hence a+O=a follows by duality. THEOREM 1.7. a + ( b+ c) = ( a+ b )+ c. PROOF:by 1.5(i),(ii). I n view of Theorem 1.7 we shall usually omit parentheses in expressions of the form a (b c), a [b (c d ) ] , etc.

+ +

+ + +

DEFINITION1.8. a . v = ~ , < , a (i.e., a . v = ~ , , , b , where b,=a for every x
PROOF:by an induction on p based upon 1.6 and l.lO(i),(ii),(iii).

THEOREM 1.12. (a+ b ) - p+a =a+ (b+ a ) - p and (a+ b) .( p+ 1) = a+(b+a).p+b for every p<w. PROOF:by aninduction o n p based upon 1.6, 1.7, and l.lO(i),(iii). Theorem 1.12 can be extended to finite sums & p a x . THEOREM 1.13. If a+b=b+a, then a , p + b = b + a - p and a . p + b - v = b . v + a - p (i)

for a n y p < o and

V
(ii) ( a + b ) - p = a - p + b - p for every p<w. PROOF: by an easy induction based upon 1.7 and l.lO(iii).

14

CRaPTER

1

THEOREM 1.14. If a.w=b+c and c # O , then there are elements d, e and a n ordinal pu
i f and only if there i s a n element c such

THEOREM 1.16. The following conditions are equivalent : (i) a<* b, (ii) there i s a n element c such that c+a=b, (iii) a*gb*. PROOF:by 1.3(ii), 1.4, 1.15, and 1.15*.

THEOREM 1.17. a
~xipa,~~x,,ax.

, a-p
THEOREM 1.21. (i) Ifb ~ ~ x , , a , a n d b # ~ x , , a x , t h e n b ~ ~ , , a , for some pu
(ii) If ~ g * z ~ and < ~c #aO , ~then Z;,,a,+,<* c for some p < w . PROOF:by l.l(III), 1.5(ii), 1.6, 1.7, 1.15, and 1.16. COROLLARY1.22. (i) I f b g a . o and b#a.co, then b < a . p for some p < o . (ii) If c g * a . w and c#O, then a . w < * c . PROOF:by 1.8 and 1.21. From now on the remainder postulate, l.l(IV),will be essentially involved in our discussion. Some of the subsequent theorems (e.g., 1.31, 1.32, 1.34, 1.35, and 1.48) will still be of a very elementary nature - in spite of the fact that, in our axiomatization of ordinal

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

15

algebras, their proofs seem to depend essentially on the remainder postulate. Gradually, however, the developmente will assume a less obvious and deeper character. THEOREM 1.23. If a,=b,+a,+,

foreveryx<w, then G<wb,+lgax

for every x < w .

PROOF: by l.l(IV).

THEOREM 1.24. If a,=b+a,+, for every x < w , then b . w g a o = u x every x<w. PROOF: By l.l(IV), with bx replaced by b, there is an element c such that ax= b o + c

for

for every x < w , and in particular

a, = b .w + C. Hence the conclusion follows at once. In several subsequent theorems we shall establish various fundamental properties of two important relations between elements a, b of an ordinal algebra. The two relations are respectively expressed by the formulas

a+b=b and b + a = b . They niay be referred t.0 as absorption to the left and absorption to the right. Actually these relations were already involved in some of the preceding theorems. E.g., by l.lO(iv), a . w absorbs (to the left) a as well as every finite multiple of a ; in view of Theorem 1.25 below, the conclusion of 1.24 expresses the fact that a, absorbs b. THEOREM 1.25 [ABSORPTION THEOREM]. a+b=b if and only if a-wgb. PROOF: If a+b=b, then a . c o < b by 1.24. If, conversely, u . o g b , we have for some c a-o+c=b and hence, by l.lO(iv),

a + b =a +a .o+ e = a - w + c = b.

16

CHAPTER

1

THEOREM 1.26. (a+ b ) .w G a + (b+ a ) .w a d a+ ( b + a ) (a + b ) . w . PEOOF:By l.lO(iv) we have

+

+

(a+ b) + [a+ (b+a) -01 = a [(b+ a ) (b + a ) -01 =a + (b + a ) .W.

Hence, by 1.25, with a and b respectively replaced by a + b and a+ (b+a).w, (a+ 6 )- w
+

For analogous reasons, and consequently

(b + a ) - w G b + (a + b ) w

a + ( b+ a ) . w
This completes the proof.

THEOREM 1.27

[TWO-SIDED ABSORPTION THEOREM].

a+ b + c = b

if and only if a+b=b+c=b. PROOF:Assume that

(1)

a+ b+c= b.

Let (2)

for every x < w .

b,=b+c.x

By an easy induction on x we obtain from (1) and ( 2 ) : for every x < w .

b,=a+b,+,

Hence, by 1.24, b,,=b, for every x < w and in particular b,=bl. In view of (2) this implies (3)

b=b+c,

and formulas (1) and (3) give (4)

a+b=b.

Thus (1) implies (3) and (4). The implication in the opposite direction is obvious.

ORDINAL ALGEBRAS AND THEIR ARITH116ETIC

17

COROLLARY1.28. If a
G

and d. Hence

a=d+a+c and therefore, by 1.27, a=a+c=b.

THEOREM 1.29. If a g a * or a * g a , then a=a*. PROOF:By l . l ( V ) and 1.16, a g a * implies a*<*a, and a*
implies a g * u * . Hence the conclusion follows by 1.28.

THEOREM 1.30. If b < a - w , b g * a . w , and b#O, then b=a.w. PROOF:by 1.22(ii) and 1.28. THEOREM 1.31. (i) a+b=O if and only if a=b=O. a
(ii) follows directly from (i).

z,<,

THEOREM 1.32. (i) ax= 0 if and only if a, = 0 for every ilc p. (ii) a . p = O if and only if a=O or p=O. PROOF: rf we have

zx
aa+1+x

=0

for every A< p

and hence, by 1.31(i), (2)

a,=O for every i l t p .

If, conversely, (2) holds and p < w , we obtain (1) by an easy induction on p. In case ,u=o we conclude from (2) that O=a,+O

hence, by 1.23,

for every A < o ;

G<&,< 0

18

CHAPTER

1

and, by applying 1.31(ii), we again arrive at (1). The proof of (i) is thus complete; (ii) is but a particular case of (i). The next two theorems are closely related to the directed refhement postulate l.l(II1).Theorem 1.33 was proposed by the author and its proof was provided by Hanf. THEOREM 1.33

[GENERAL DIRECTED REFINEMENT THEOREM].

If

and if for every x < o there is a pu
and two strictly increasing infinite sequences of finite ordinats ... and vo= 0, vl, ..., v,, ... such thut

po= 0, p1, ..., p,,

a,

and

=

2~
cp,+a

b, = ;r;l
for every x < o .

PROOF 6 , : The three infinite sequences satisfying the conclusion of the theorem will be defined recursively. I n doing this, we shall make implicit use of the axiom of choice since, at each stage of the recursive definition, we shall pick elements satisfying certain formulas (from non-empty collections of such elements). Given two finite ordinals TC and e, suppose we have defined ordinals px for every x < n and v, for every x < e as well as elements cA for every A
...
(2)

a, = x A < p x + l - p x

(3)

b,

=

O=v,,
for every x < n ;

x ~ < ~ ~for+ every ~ - ~< ~e; &,+A

x

In this proof we apply the so-called method of iteration, which was 5) frequently used in the discussion of cardinal algebras; see [17], p. 17. This method is often combined with an application of the remainder postulate; compare the proofs of Theorems 1.52 and 1.54 below. (The proof of 1.52 suggests also the way in which the present proof could be modified t o make the use of the axiom of choice explicit.)

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

(4)

some element e, ( for and az+l= e + &
be = &<m

s
19

be+l+A.

(1)-(4) are trivially satisfied for n = e = 0 if we set ,uo= yo = 0 and take bo for e in (4). We wish now to determine two finite ordinals ~ tand ' e' with n'>n and e'>e, and to define ordinals ,u, with n < x
and (6)

For what follows we pick an element e satisfying the two formulas of (4). Using (6) and the second formula of (a), and applying Postulate l.l(III),we find elements d', e' and an ordinal o'<w such that

and (9)

&<m

b e + l + l = e'+

G < m

az+a/+l+a.

Using now ( 5 ) and (9), and applying Postulate l.l(II1) again, we find elements d " , e n and an ordinal d"'w for which

be+,+A+d"

(10)

%
(11)

be+l+oll= d"+e",

and (12)

= e',

G<ma n + o t + i + a = ew+ s < a , b p + a t f + g + ~ *

We now put: (13)

(14)

n'=z+o'+ 1 and e'=e+a"+ p,+1fx

= p,+

I + x for E < u',

p,+0/+1= ,u*+o'+o"+2,

1,

20

CHAPTER

1

We denote by (1')-(4') the conditions obtained from (1)-(4) by replacing n, e, and e by n', e', and e", respectively. (1') follows from (1) and (14),(15), and (13). To show (2') we first notice that we have by (16) and (14) an+, = cpn+x = G i ~ ~ + l + , - p n + , ~ ~ n + , + l

for every x < d . Furthermore, from ( 8 ) and (10) we obtain

be+l+l+dw

an+,#= d'+&
and hence, in view of (16) and (14),

+

a n + o f = cpn+a/

~

~

<

- z
cpn+ot+ a l ~ 1 + A + cpn+o/+ ull + I CPn+d+l

*

Thus (2') is established; (3') follows in a similar way from (15), (16), (7), and the first formula of (4). Finally, the formulas of (4') result directly from (11) and (12), making use of (13), (14), (15), and (16). It is clear that the three infinite sequences (rug, ...,p,, ...), (vo, ..., v,, ...), (co, ..., cl, ...) thus defined satisfy conditions (2) and (3) for arbitrary finite ordinals n and e; also that the first two of these sequences are strictly increasing. Hence the conclusion of the theorem follows immediately.

THEOREM 1.34 [FINITE DIRECTED REFINEMENT THEOREM]. If a +c = b +d, then there is an element e such that either a = b + e and e + c = d or else a + e = b and c = e + d . PROOF:In case d=O the conclusion is obviously satisfied if c is taken for e. Hence we can assume that (1)

d#O.

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

a1

We put: (2)

fo=a, f i = c , and f 2 + x =

0 for every x < w .

Hence we obtain with the help of 1.32(i)

L
and therefore (3)

By 1,l(III),formulas (1) and (3) imply the existence of two elements g, h and an ordinal puto which satisfy the conditions: (4)

From (2) and (4) we conclude, by means of 1.31(i)and 1.32(i), that h = O = d in case p s 2 . Hence, by (l),either p=O or p = l . If p=O, we obtain from (2) and (4) a = b + h and h + c = d ; if p = l , we get a + g = b and c = g + d . Thus the conclusion is satisfied if we take either h or g for e.

COROLLARY1.35. (i) If a g b + d , then a
b =e + a - w = (e+a )+ a . w

where, by 1.31(i), (2)

e+a#O.

22

CHAPTER

1

By (1) and (i) we have Hence, by 1.35(ii), (3)

e + a g b and c F o g b .

e+agc!'w or c T o g e + a .

From (2) and (3), by applying 1.22*(ii), we obtain c ?w < e

whence for some d

c + o +d

(4)

+a

=e +a.

Formulas (1) and (4) lead directly to (ii). Thus (i) implies (ii); the implication in the opposite direction is obvious.

THEOREM 1.37. The following conditions are equivalent : (i) a + b + c = b ,

(ii) a.w
(iii) there is an element d such that a.w+d+c?w=b. PROOF:(i) implies (ii) by 1.27, 1.25, and 1.25*. Assume that. (ii) holds. We have then for some e and f (1)

a . o +e =f

+c +o= b.

Hence, by applying 1.34, we conclude that there is an element g such that either (2)

a . w + g = J and e = g + c + o

or else (3)

a.o=f+g

and g + e = c T o .

I n the first case we derive (iii) (with d = g ) directly from (1) and (2). I n the second case we can assume that g # 0 (for otherwise ( 2 ) holds again). We thus have by (3) g g * a - o , g g c F o , and gfO.

Hence, by 1.22(ii) and 1.22*(ii),

a . o < * g and c + o < g .

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

23

By applying 1.36 we conclude that for some h ct, +h + a . 0 =g.

(4)

Formulas ( 1 ), (3), and (4) imply

b =f +g

+ e = ( f +c yo)+ h + ( a .w +e ) = a . w + e + h +f + C ~ W .

Hence condition (iii) is satisfied by d = e + h + f . Finally, if (iii) holds, we have

a + b + c =a + a . + d~ + C?O

+ c = a . w +d +C ~ W =b.

Thus (iii) implies (i), and the proof has been completed. If a+b+C=C and ( U + b ) . W = ( b + U ) . W , then THEOREM 1.38. a+ c = b + c = c . PROOF:By 1.25, the h t formula of the hypothesis implies that

(a+b ) . 0 g c .

(1)

By 1.26 and the second formula of the hypothesis we have (2)

b + (a + 6 ) w Q (b +a) * W = (a + 6 ) . W.

Obviously, (3)

(a+ b ) - w Q * b + (a+ b ) * ~ .

By 1.28, formulas (2) and (3) give

+

b + (a+ b ) * W = ( a b ) * W . Hence, by 1.25, (4)

b w < (a+ b ) * W.

From (1) and (4) we get

b*o
and, by applying 1.25 again, we arrive at (5)

b+c=c.

The conclusion follows directly from ( 5 ) and the hypothesis.

24

CHAPTER

1

The problem naturally arises whether Theorem 1.38 can be improved by removing the premise

(a + b) * o = (b + a ).o from its hypothesis. As is easily seen, this is equivalent to the problem whether Corollary 1.28 remains valid if we replace in its hypothesis the formula b 4 * a by b g a (or the formula a ~ byb a Q * b). I n other words, we ask the question whether the relation <, which is reflexive and transitive by 1.17 and 1.18(i), is also antisymmetric and hence whether it establishes a partial ordering in the set of all elements of the ordinal algebra discussed. The answer to this question is negative. We can prove that there is no ordinal algebra, with more than two digerent elements, i n which the relation g is antisymmetric. I n fact, assume that in some ordinal algebra the relation Q is antisymmetric. It suffices to show that in this algebra any two elements distinct from 0 are identical. Let thus a#O and b#O. We put C=

(a+ b)*w.

Clearly, with the help of l.lO*(iv),

(a+c)Ta < (a+ c)+w +a < [(a+ C)+O +a]+ c = (a + C)+O and consequently, by the antisymmetry of

(a+ c):O+a

=

Q

,

[(a+ C ) + O + a ]+ c.

Hence, by 1.35*(ii), we conclude that i.e.,

a g * c or c < * a ,

a g * (a+ b) .O or (a + b ) . o G * a .

However, by 1.22(ii), the fkst of the last two inequalities implies the second. We thus have (a

and since

a
+ b)

* OQ

*a;

+ b < (a+b)

-0,

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

we obtain by 1.28

26

(a + b) .w = a,

whence by l.lO(iv)

a +b +a =a. Therefore b+a<*a; obviously we also have a<*b+a. Since the relation g is assumed to be antisymmetric, the same applies by duality to < *. Therefore the last two formulas yield a=b+a

and hence

b
By symmetry, we can show in an entirely analogous way that agb, so that finally the elements a and b prove to be identical. As is readily seen, the argument just outlined also shows that there i s no ordinul algebra, with more than two diflerent elements, in which the operation + is commutative or in which the formula a* =a holds identically. I n special ordinal algebras discussed in Chapter 2 the question in which we are interested can be answered directly since we can easily exhibit two elements a and b for which the formula

(a + b) .w = b + (a+ b).o

(i) fails. If we then put we obtain

c = (a+b) - w ,d =b + (a+b).w, a+b+c=c and b+c#c, c*
By analyzing the proof of Theorem 1.38 we notice that the

26

CHAPTER

1

theorem remains valid (and its proof simplifies) if in its hypothesis the formula

(a+ b ) .W = (6 +a) .w

(W

is replaced by (i). Moreover in this case the converse of the theorem also holds; i.e., we can show that the formula (iii)

a+c=b+c=c

implies both (i) and (iv)

a +b + c = c .

In fact, assume that (iii) holds. We obtain then directly (iv) as well as b+a+c=c. Hence, by 1.25, (a+b).w
and ( b + a ) . w < c ;

therefore, by 1.26 (with a and b interchanged),

b + (a + b ) . W < c and consequently, by 1.35(ii), (v)

(a+ b ) . o
On the other hand, we obviously have (vi)

(a+ b ) . W G * b + (a+ b ). W Q * a+ b + (a+ b ) .o= (a+ b ) - 0 .

By 1.28, conditions (v) and (vi) imply (i), and the proof is complete. If we decide to include Postulate (11') in the postulate system for ordinal algebras (cf. the remarks following Definition l.l), we easily derive from it, with the help of l.l(I1) and 1.8, the following corollary:

(A)

(a+ b) - w = u + (6 + a ) . W .

(A) is clearly an improvement of 1.26. With a and b interchanged, (A) implies that formulas (i) and (ii) are equivalent. Consequently,

ORDINAL ALGEBRAS

mn

THEIR ARITHMETIC

27

by means of (A) we can obtain the converse of Theorem 1.38 in its original form, i.e.: (€3)

If a+c=b+c=c,

then a+b+c=c

and ( a + b ) . o = ( b + a ) . w .

(A) and ( B ) are the only known consequences of Postulate (11’) which are of some interest for our discussion. Another simple consequence of (11‘)is:

(C)

( a - p ) . w = a . w for every p

with O<,uu<w.

However, we shall succeed in obtaining this consequence without the help of (11’);cf. Theorem 1.48 below. On the other hand, from the example of Hanf on p. 10 we easily see that there are ordinal algebras in which both (A) and (B) fail and that therefore these two statements cannot be derived from the postulates of 1.1 alone.

THEOREM 1.39. If a-,u+b
(1)

I n case O
we can write

a * ( , ! -l ) + a + b = b , and we obviously have

( a .( p - 1 )+ a ) .o=( a + a . ( p - 1 ) )-0). Hence by 1.38 we obtain (2)

a+b=b.

I n case p = o,the hypothesis gives immediately a.o
whence, by 1.25, we again arrive at ( 2 ) . From (2) the conclusion follows by an easy induction on v.

28

1

CHAPTER

THEOREM 1.40. If a . o < b . p and p < w , then a . w < b . PROOF:We argue by induction on p. The theorem obviously holds for p = 0, 1. Assume that it holds for some given p, 0 < p
a - w < be ( p

+ 1) = b * p+ b.

Hence, by 1.35(i), either (1)

a *Q b~- p

or else, for some c, (2)

a-co=b.ptc,

c < b , and c # 0 .

I n case (1) the conclusion follows by our inductive premise. I n case (2) we have for some d (3)

c+d=b.

Moreover, (2) implies by 1.22(ii) a.w<*c;

hence, by (3),

a*o+d<*c+d=b.

(4)

On the other hand, we obtain with the help of (2)

b
(5)

(4) and (5) give by 1.28

a *W,+d =b, and this again implies the conclusion.

THEOREM 1.41 [FIRST CANCELLATION LAW FOR EQUATIONS]. If a + c . p = b + c - p and p < o , then a + c = b + c . PROOF:By 1.34 the hypothesis implies the existence of an element e such that (1)

a = b + e or a + e = b

and

e +c . p =c - p .

(2) (1) gives

(3)

a +c

= b -t( e + c )

or a

+ (e +c) = b + c.

ORDINAL ALGEBRAS A N D THEIR ARITHMETIC

29

From (2) we obtain, by applying successively 1.25, 1.40, and again 1.25, e.coQc.p, e.co
and e+c=c.

(4)

The conclusion follows directly from (3) and (4).

THEOREM 1.42 [FIRST CANCELLATION LAW FOR INEQUALITIES]. If a + c p < b + c . p and O
Hence for some d

+

( a c .p )

+ (c +d )

=(b

+c +c. ./A)

By 1.34 this implies the existence of an element e such that either a + c - p + e = b + c . , u and c + d = e + c

(1)

or else a+c.,u=b+c.p+e

(2)

and e + c + d = c .

I n the first case we have a + c - p 4b +c-,u,

and we obtain the conclusion by our inductive premise. I n the second case we conclude by 1.27 that c+d

Hence by ( 2 ) a+c*p=

=e + c =

c.

b + c . ( p- 1) + c + e = b + c * (11- 1) + c = b +c*,u.

Consequently, by 1.41,

a + C = b +c,

and this again yields the conclusion. The proof of (i) has thus been completed; (ii) follows directly from 1.41.

30

CHAPTER

1

1.41 and 1.42 can be slightly improved:

THEOREM 1.43. (i) If a + c + d + c - p = b + c + d + c - p and p < w , then a+c+d = 6 + c + d . (ii) If a + c + d + c - p < b + c + d + c . p and p u w , then a + c + d
hence

a+ ( c + d ) * 2 = a + c +d+c

+d

=

+ +

+

b c d + c d= b

+ ( c + d ) . 2,

and by applying 1.41 again (this time with ,u=2), we arrive at the conclusion of (i). (5)obviously holds for p=O. If p # O , we apply 1.42(i) to the hypothesis of (ii) and obtain

a+ c+d+c
+ c+d +c,

+ +

(a+c+ d ) (c f ) = (b + c + d ) +c.

Hence, by 1.34, there is an e such that either (2)

a+c+d+e=b+c+d

and c+f=e+c

or else (3)

a + c + d= b +c + d + e and e + c + f

= c.

( 2 ) directly implies the conclusion of (ii). From (3) we get by 1.27

hence by (1)

c+f=c,

u+c+~+c=~+c+~+c and, by applying part (i) of our theorem (with p= l ) , we again arrive at the conclusion. Finally, (iii) is a simple consequence of (i).

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

31

TEEOREM1.44. In order that (i) a.o
(1)

= b.

Let

for every x < o .

b,=afc,+,

(2)

From ( 1 ) we obtain

a*(%+1 ) + ~ , + 1 = a * ( x +l ) + a + c , + , = b ; hence, by 1.41*,

= a +a

a +c,,

+c,+,

and consequently, by ( 2 ) , b,=a+b,+,

for every x < w .

By 1.24 this leads to (3)

a . w
On the other hand, ( 1 ) with x = 1 and ( 2 ) with x = 0 give (4)

b, =a + c1 = b.

(3) and (4)imply (i). Thus our theorem holds in both directions.

By the theorem just proved, the coth multiple a . w is a least upper bound of the sequence of finite multiples a . p , p < o ; we cannot say that a . w is the least upper bound of this sequence since the relation Q is not antisymmetric. The question naturally arises whether, in general, the sum C < o a xof an infinite sequence is a least upper bound of the sequence of partial sums G < a a , , puto. The answer turns out to be negative. A counter-example can easily

32

CHAPTER

1

be constructed in every ordinal algebra which has an element c with c z c . 2 . I n fact, by putting we obtain

ao=cFw,

and ax+,=c for every x < o ,

L < p a x < a ofor every p < w ,

although the formula Zx,,ax
proves to fail. If, in addition, we put we have

bO=c?w,

and bx+,=O for every x < w ,

Cx
and nevertheless

b, for every p < 0

Z%
bx.

Thus two infinite sums may be different although any two corresponding partial sums are equal. 6, As is seen from 1.25, 1.39, 1.40, and 1.44, the fact that b absorbs a (to the left) can be expressed by any one of the following equivalent conditions: (i)

(ii) (iii)

(iv) (v)

(4 (Vii) (Viii)

04

a+b=b, a+b
A n example of two infinite sums of order types with these properties 6) is given in [14], p. 12. The observations in the last paragraph of the text exhibit a difference between ordinal and cardinal algebras; compare [l?], pp. 23f.

ORDINAL ALOEBFbAS AND THEIR ARITHmTIC

33

I n formulas (iii)-(vi) and (viii) we take for p an arbitrary finite ordinal different from 0. From 1.27, 1.37, 1.44, and 1.44* we conclude that each of the following conditions expresses the fact that b absorbs both a to the left and c to the right: (i)

(fi)

(iii) (iv) (v> (vi)

a+ b= b+c= b, a b +c= b, a.w
THEOREM 1.45 If a . p < b . p and

+

[SECOND CANCELLATION LAW FOR INEQUAIJTIES].

O < p < w , then a g b . PROOF: We proceed by induction on p. The case p = 1 is obvious. Assume that the theorem holds for a given p, O
Hence, for some c,

a.(p+1)
a - p+ (a+ c) = b .p + b.

By applying 1.34 we conclude that either (1)

a - p < b - p and b g * a + c

or else (2)

b . p g a . p and a + c g * b .

I n case ( 1 ) the conclusion a
b
and a fortiori (4)

b
From ( 2 ) and ( 4 ) we obtain by 1.28 b=a+c, and this again implies the conclusion. The proof has thus been completed.

34

CHAPTER

1

THEOREM 1.46 [SECOND CANCELLATION If a . p = b - p and O
LAW FOR EQUATIONS].

a . p < b e p and b - p < * a - p ;

consequently, by 1.45 and 1.45*,

a g b and b<*a. Hence the conclusion follows by 1.28.

THEOREM 1.47. If a.p
a .p = a hv.

In case p < o , (1) can be written in the form

a . ( p- v ) + a . v = a v.

Hence, by applying 1.39 (with b replaced by a ’ v , and p replaced by p - v ) , we obtain (2)

a . v + a .v =a . v, i.e., ( a -2). v = a v. a

An application of 1.46 to the latter formula yields a . 2 = a , i.e., a+a=a; and hence, by using 1.39 for the second time (with b=a, p= 1, and v = n - 1) we arrive at the conclusion. I n case p = o , we have by l.lO(iv)

a .v +a . p =a ‘ p . From this and (1) we derive (2) and, by arguing as before, we again obtain the conclusion.

ORDINAL ALOEBRAS AND THEIR ARITHMETIC

35

THEOREM 1.48. If O < p < w , then a . w = ( a . p ) . w . PROOF:By l.lO(iv), we have a.p+a-w=a.w

and therefore, by 1.25,

( a .p ) - w
0.

Hence, by 1.22(i), either (1)

a.w=(a.p).0

or else, for some

Y<W,

(a - p )* w
The latter formula obviously implies

a . ( p .Y +p ) = ( a .p) .(Y + 1)
By applying 1.47 (with ,ti and z replaced by p.y+p and p), we conclude that a = a - p , and this again leads to ( l ) , i.e., to the conclusion of t,he theorem. THEOREM 1.49. If a-,u=b.v, p < w , Y # O , then a + b = b + a .

and either p f O or

Y
PROOF:If one of the ordinals p and Y, say p, equals 0, we obtain from the hypothesis b = 0, and the conclusion is obvious. Otherwise we write a+a- (p- 1) = b + b - (Y- 1). By 1.34, this implies the existence of an element c such that either a = b + c and c + a - ( p - l ) = b . ( v - l )

(1)

or else

a+c=b and a - ( p - l ) = c + b - ( v - l ) .

(2)

Since the two possibilities are symmetric, we consider only (1). We then have C+

(b +c) * ( p- 1) + b = c + a *(p- 1) + b

Hence, by 1.12 and the hypothesis, (c

+ b ) p =a * p *

.

= b (Y-

1)

+b = b *Y.

36

CHAPTER

1

and consequently, by 1.46,

c+b=a.

(3)

From ( 1 ) and ( 3 ) we obtain

a+ b = (b+ C) + b = b

+ (C +b ) =b +a,

and the proof is complete.

If a.,U=b*Y Where ,U and THEOREM 1.50 [EUCLID’S THEOREM]. v are two relatively prime finite ordinals, then, for some c , a = c . v and b = c PROOF:I. We start with the special case p = 2 , v=3. Thus we have a p .

(1)

a . 2 = b . 3 , i.e., a + a = b + ( b + b ) .

Hence, by 1.34, there is an element d such that either (2)

a + d = b and a = d + b + b

or else (3)

a=b+d and d + a = b + b .

In case ( 2 ) we have Therefore, by 1.27, i.e., by (2), (4)

a=(d+b)+a+d.

a=a+d, a=b.

Hence, by ( l ) , a.2=aa3

and consequently, by 1.47, and (4), a = a - 3 and b=a.2.

Thus the conclusion is satisfied by c=a. I n case ( 3 ) we apply 1.34 to the formula d + a =b +b. We obtain an element e such that either (5)

d = b + e and e + a = b

37

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

or else (6)

d + e = b and a = e + b .

Assume that (5) holds. We have by (3) and (5) a=b+d=e+a+d.

Hence, by 1.27 and ( 5 ) , a=e+a=b.

Thus we have again arrived at (4) and, by arguing as before, we obtain the conclusion. Assume now that (6) holds. From (l),(3), and (6) it follows that

(e + d ) . 3 = e + d +e + d + e + d = e + b+ b + d = a +a = b . 3. Hence, by 1.46 and (6), (7)

b=d + e = e + d .

By applying 1.34 again, we conclude that there is an element f for which either (8)

d=e+f=f+e

or (9)

e=d+f=f+d.

Our further argument in both cases (8) and (9) is entirely analogous. We restrict ourselves to the discussion of (8). By (6)-(8) we have

a = e + b = e f e+ d = e + e + e + f = e . 3 + f ,

while (3), (7), and (8) give

a= b + d = e -td + d = e + e + f + e + f = e . 3

Thus

a = e . 3 + f =e . 3 + f . 2 ,

and hence, with the help of 1.13(ii), (10)

+ f a

a =a +f = e . 3 + f . 3 = (e + f) 3 = d .3.

2.

38

CHAPTER

By (1) and (10)

1

6 . 3 = a * 2 = (d * 3 ) * 2 = (d * 2) * 3

and consequently, by 1.46, b~d.2.

(11)

Formulas (10) and (11) show that the conclusion of our theorem is satisfied by c = d . Thus the theorem has been established for p = 2 and v = 3 . 11. Turning now to the general case, we proceed by induction. Let n be an arbitrary finite ordinal. We assume that the theorem holds for arbitrary a's, b's, $9, and Y'S with p + v
p+y=n.

We want to show that the conclusion is satisfied in this case as well. If p=v, we must have p=v= 1 (since p and Y are relatively prime), and the conclusion obviously holds. We can thus assume that p 2. One of the numbers p and Y, say v, is even, and we have (13)

Y=2*Y',

2
Y'
By (13) and the hypothesis,

u - p= 6 - Y= ( b * 2 ) - Y' ; moreover, p and Y' are relatively prime and, in view of (12), p+v'
a=d.v' and b - 2 = d . p .

Purthermore, by (12) and (13), p + 2 < n , and clearly p and 2 are relatively prime (since p = 2 . Y' - 1). Therefore, by applying the inductive premise to (14), we obtain an element c such that b=c.p, d = c . 2 , and a=(c.2).v'=c.v.

ORDINAL ALGEBRAS AND THEIR ARITHMETIG

39

We have still to consider the case when v-p> 1. By hypothesis we have

(

a.p+[[b.(V-p-l)J.p=b.Y+b.[(~-p-l)~p]= (15) =b*[v+(v-p- l)-p]= [b-(p+l)]*(v-p).

Moreover, the hypothesis implies by 1.49

a+b=b+a;

hence by 1.13(i) (16)

a + b * ( v - p - l)=b.(v-p-

l)+a.

From (15) and (16) we derive by 1.13(ii) (17)

[u+b*(v-p- 1)]-p= [ b * ( p +l)].(v-p).

It is well known that, whenever p and v are relatively prime, p and v-p are also relatively prime. I n view of (12) we have p

+ (v-p)

<7r.

Hence, by applying our inductive premise to (17),we obtain an element d such that a + 6 . (v-p- 1) = d . ( Y - p )

(18)

and (19) Again, p and p + 1 are relatively prime ; and, since Y -p > 1, we have

p+fp++)
Therefore we can apply the inductive premise to (19).We conclude that there is an element c for which b = c . p and d = c - ( p + 1).

(20)

From (20)and the hypothesis we get a . p = b .v = ( c . p ) .Y = (c *v). p ,

and hence by 1.46 (21)

cL=c.v.

By (20) and (21) the conclusion is again satisfied, and the proof has been completed.

40

CHAPTER

1

The first part of this proof can be somewhat simplSed by use of 1.41. From the remarks at the end of this chapter (concerning directed refinement algebras) it will be seen, however, why we have abstained from applying 1.41 in the proof of 1.50.

COROLLARY1.51. The following two conditions are equivalent: (i) a . p = b . v for some p u t w and v < w provided either p#O or v#O; (ii) a = c . v ' , and b = c . p ' for some element c and some ordinals v ' < o and p ' < w . PROOF: Assume that (i) holds and let TL be the greatest common divisor of ,u and v ; clearly n#O. We then have ,u=p'.z, v=v'.n for some p' and v' which are relatively prime and not both zeros. By (i) we obtain (a* p') .7t= (b * Y ' ) *TC ; hence by 1.46 a ' p ' = b-v', and, by applying 1.50, we arrive at (5). The implication in the opposite direction is obvious. I n 1.49 we have established a sufficient condition for two elements a and b to be commutative, i.e., to satisfy the formula a+ b= b + a .

We shall now give a few further results in the same direction.

THEOREM 1.52. If a . p + b = b + a . v ,

O
a+ b =b +a.

PROOF:It suffices to prove the theorem under the assumption

~ (since p the theorem under the alternative assumption p ~ v

v

will then follow by duality).

Consider any two elements x and y such that

z

(2)

+y f y +z.

By (1) we can write x+ [ z * ( p - l ) + y ] = y + z . v .

ORDINAL ALGEBRAS AND THEIR AJXITHMETIC

Hence, by 1.34, there is an element z for which either

x = y + z and x + z - ( p - l ) + y = z . v

(3)

or else

and z.(p- l ) + y = z + z . v .

y=z+z

(4)

If (3) holds, we have by 1.12 ( z + y ) * p = z + (y + z ) * ( p- 1) + y = z + z * (p- 1) + y = z * v .

Hence, in case p=v, we obtain by 1.46 z+y=z

and therefore, by (3),

x+ y = (y

+z ) +y =y + ( z +y) y + =

2;

this obviously contradicts ( 2 ) . In case v
Y-

1) + z - v + y =x.r ;

hence, by 1.27, x*v+y=x.Y

and therefore, by 1.41* (with a=y, b=O, c = x , and p = ~ ) ,

z+y=z.

(5)

Consequently z ' p + y = z ~(p- 1) +z+y =z.(p- 1) + z = z . p

whence, by (l), 2.p = y

+2

*

Y =y

+2 p +x *

*

(Y

-p).

This gives by '1.27 z.p=y+z.p

and hence by 1.41 x =y + z .

(6)

Formulas ( 5 ) and (6) together clearly contradict (3). Thus (3) cannot hold, and we have (4). We conclude that z.p+z=

5.(p - 1)

+ (z+2)=z -(p- 1) +y

41

42

CHAPTER

1

and therefore (7)

z.p+Z=Z+z.Y.

Moreover, (8)

s+z#z+z;

for otherwise we would have by (4)

+

z+ y = x + (z+ z) = (x+z) x= y + 2 , which is impossible in view of (2). Thus we have proved that (1) and (2) imply the existence of an element z which satisfies (4), (7), and (8). Hence, using the axiom of choice, we can correlate an element f(s,y) with any two elements z and y in such a way that, whenever x and y satisfy (1) and (Z), the element z=f(z,y) satisfies (4), (7), and ( 8 ) ; in case either (1) or (2) fails, f(x,y) is chosen in a quite arbitrary way. To summarize, we have: for any elements z and y, ifz.,u+y==y+s.vand z+y#y+z, then y = z f(z,y), zap +f(x,y) = f(z, y) +x.v, and x +f@, Y) # f ( z , y ) 3.

+

+

We now return to the given elements a and b which satisfy the hypothesis of our theorem. Assume that the conclusion does not hold, i.e., that

a+ b # b+a.

(10)

We define recursively an infinite sequence of elements b,, bl, by putting (11)

...,b,, ...

b,=b, and b,+l=f(a, 6,) for every x < o .

With the help of the hypothesis and (9)-(11) we obtain by an induction on x b,=a+b,+, for every x < w . Hence, by 1.24 and 1.25, (12)

a . w < b and b=a+b.

Consequently, by 1.39 and the hypothesis, (13)

b = a .p + b = b +a . Y = b +a.

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

43

Formulas (12) and (13) together obviously contradict (10). Thus our assumption has been refuted, and the proof is complete. By analyzing this proof, we can somewhat improve the conclusion of 1.52: under the assumption that p # v we can show that in this case either a+b=b+a=a+a=a or else a + b = b +a=b.

COROLLARY1.53. If a . p + b en =be n + a . v , 0

hence 1.53 is a generalization of 1.49. The problem naturally arises whether this result can be further improved, e.g., by showing that two elements a and b are commutative if a-p+b.n=b.e+a.v

where p , v, n, and e are arbitrary finite ordinals different from 0. This problem is still open; a partial solution has been obtained by Chang and is presented in Appendix A. A still further improvement of 1.53 would consist in showing that the commutativity of a, and b is implied by the formula

z,,,

+

(a*pu, b . n,)=

za<7( b ea + a*va)

where IJ, px,nu,,z, el, va are finite ordinals and are different from 0.

IJ,

,uo,nu-l,t,Po,

v7-1,

The following theorem will serve as a lemma in the proof of

1.65 below.

44

CHAPTER

1

THEOREM 1.54. If a + 6 = b + c , then either (i) a+b=b or else (ii) there are elements d, e and an ordinal y t w such that a = d + e , b = a . y + d = d + c . p , and c = e + d . PROOF:Consider an arbitrary element x satisfying the conditions : (1)

and (2)

a+x=z+c

1

for any elements u, v and any ordinal p< w , if a=u+v and c = v + u , then z # a . p + u .

By 1.34, (1) implies the existence of an element y such that either a = x + y and c=y+z

(3)

or else

x=a +y= y + c.

(4)

(3) clearly contradicts (2) (for u = x , v=y, and p=O). Hence (4) holds. Consequently, by means of the axiom of choice, we can correlate an element f ( z ) with any element x in such a way that, whenever x satisfies (I) and (Z), we have

x = a + f ( z )=f(z)s c .

(5) (2) and (5) imply: (6)

{

for any elements u, v and any ordinal p < o , if a=u+v and c = v + u , then f ( z ) # a . p + u .

For, if we had ( 5 ) would give

+

f ( x )= u - p u,

z=a.(p+ l ) + u , in contradiction to (2). Thus we have shown that there is a function f (on and to the set A ) such that

(7)

for every x, (1) and (2) imply ( 5 ) and (6).

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

45

By hypothesis, the element b satisfies formula (1) with z==b. Assume that this element satisfies also condition (2); i.e., that part (ii) of the conclusion of our theorem fails. (Notice that, by 1.12, the formulas b=a.p+d and b=d+c.p are equivalent whenever a = d + e and c = e +d.) Define recursively an i n h i t e sequence of elements b,, ..., b,, ... by putting

b,=b, b,+,=f(b,) for every x < o . Using ( 7 ) and the assumptions concerning b, we obtain by induction on x b,=a+b,+, for every x < o . Hence, by 1.24 and 1.25, we conclude that a . o g b and b=a+b,

i.e., that part (i) of the conclusion holds. This completes the proof. I n the next part of this section we shall study a comprehensive set RC of elements of an ordinal algebra called the set of recursive elements. I n 1.55-1.62 we define this set and formulate its fundamental properties. I n 1.65, under the assumption that at least one of two elements a , b belongs to RC, we establish a necessary and sufficient condition for a and b to be commutative; this condition provides us with a method of constructing all commutative couples (a, b ) in which either a or b is in RC. DEFINITION1.55. The set RC i s the intersection of all subsets X of A satisfying the following conditions: (i) for every element a, if the formulas a = x + y and y#O always imply x EX, then a E X ; (ii) for every element a, if the formulas a = x + y and x # O always imply y EX, then a E X ; (iii) for any elements a and b, if a E X and b E X , then a+ b E X . An element a i s called RECURSIVE if a E RC. THEOREM1.56. (i) If, for every x and y, the formuZas a = x + y and y#O imply x E RC, then a E RC.

46

CHAPTER

1

(ii) If, for every x and y , the formulas a = x + y and x # O imply y E RC, then a E RC. (iii) If a E R C a n d b E R C , then a + b E R C . PROOF: by 1.55. COROLLARY1.57. (i) 0 E RC. (ii) I f , for every x and y, the formula a = x + y implies that x = O or y=O, then a E RC. PROOF: (i) by 1.56(i); (ii) by (i) and 1.56(i).

An element a f O which satisfies the hypothesis of 1.57(ii) is called indecomposable. Such elements exist in the special ordinal algebras which will be discussed in Chapter 2 (in Theorems 2.9 and 2.10). In fact, it turns out that in these special algebras every element a#O can be represented in the form a=b+c+d where c is indecomposable.

THEOREM 1.58. RC* = RC. PROOF: According to our general convention, RC* is the set

of recursive elements in the dual algebra a* (cf. the remarks following Theorem 1.4). Hence, by comparing 1.55 and 1.55* and by using 1.3(ii))(iii))we obtain the formula RC=RC* at once. COROLLARY 1.59. a E RC if and only if a* PROOF: by 1.4 and 1.58.

E RC.

THEOREM1.60. (i) If a E RC and b g a , then b E R G . (ii) If a E R C and b<*a, then b E R C . PROOF:(i) Let X be the set defined by the condition: (1)

z

E X if and only if x

E RC

for every

XQZ.

Clearly, (2)

if z E X , then z

E RC.

Let z be an element for which the formulas z = x + y and y # 0 always imply x E X . Hence, by (2) and 1.56(i), we have z E RC. If X Q Z and x # z , then z = x + y for some y i 0 . Therefore X E X

47

ORDINAL ALGEBRAS A N D THEIR ARITHMETIC

and again x E RC. Consequently, x E RC for every (l), z E X. We have thus shown that

XGZ;

i.e., by

X satisfies condition 1.55(i).

(3)

Let now z be an element for which the formulas z = x + y and x#O always imply y E X . Let X G Z ; then z = x + y for some y. If x = x’+ y’ and x’# 0, we have z = x’+ (y’ + y) and hence y‘ + y E X ; since y’
X satisfies condition 1.55(ii).

(4)

Finally, let u and v be any elements of X . If X G U + V , then, by 1.35(i), either x g u or, for some w, x = u + w and W G V . In the f i s t case x E RC by (1); in the second case u E RC by (2)) w E RC by (1)) and hence x E RC by 1.56(iii). Consequently, u + v E X by (1) and therefore

X satisfies condition 1.55(iii).

(5)

By applying 1.55, we conclude from (3)-(5) that RC is a subset of X. Hence, with the help of (1) and the hypothesis, we immediately obtain the conclusion of part (i) of our theorem. Part (ii) follows from (i) by 1.58. THEOREM 1.61. (i) If a, E RC for every x
using 1.57(i) and 1.56(iii). If p = w , we consider any two elements

x and y such that

&pa,=x+y and y # 0 . (1) With the help of 1.1(III) we conclude from (1) that (2)

x=

s,, a,+d

for some d d a, and v < p.

Here v<w and hence, as was stated above,

48

CHAPTER

1

Moreover, a, E RC by hypothesis and therefore d E RC by 1.60(i). Consequently, by 1.56(iii) and (2),

x ERC.

(3)

Thus (1) always implies (3). Hence, by 1.56(i), we arrive at the conclusion of (i). Part (ii) of the theorem is but a particular caae of (i).

THEOREM1.62. The system %&=(RC, 2, +, *, 0 ) (where the operations 2, +, * are assumed to be restricted to elements of RC) is an ordinal algebra and hence an ordinal subalgebra of %. PROOF:By 1.55 and 1.57(i), RC is a non-empty subset of A ; by 1.56(iii), 1.59, and 1.61(i), RC is closed under the operations +, *, and With the help of 1.60(i),(ii)we easily check that Postulates l.l(I)-(VI) are satisfied if all the elements involved in the hypotheses of these postulates are assumed to, and all the elements involved in the conclusions are required to, be members of RC. Hence the conclusion follows by Definition 1.1.

2.

THEOREM 1.63. If a E RC and a=a+b+a, then a=O. PROOF:Let X be the set defined by the condition:

7)

E X if and only if z = O or z # z + u + z for every u. We want to show that the set X satisfies all the conditions stated (1)

z

in 1.55.

Let z be any element for which

(2)

the formulas z=x+ y and y # 0 always imply x

E X.

+ +

If z does not belong to X , we have by (1) z # 0 and z = z u z for some u; by putting x = z and y = u z in (2), we then conclude that z does belong to X . Thus (2) implies that z E X ; in other words,

+

(3)

X satisfies 1.55(i).

I n an entirely similar way we show that (4)

X satisfies 1.55(ii).

') For order types Theorem 1.63 and its generalization established in Appendix A were first obtained by A. C. Davis; see [4].

ORDINAL ALUEBRAS AND THEIR ARITHMETIC

49

Let now x and y be any two elements such that x+ y is not in X. Thus, by (11,

x+y#O

(5)

and for some u z+ y = x+ y + u + s + y.

(6) By (5) we have

x # O and y#O.

(7)

From (6) we get

+

x+ y = (x+y +u +2) + (y + u + 2 y).

Hence, by 1.34, there is an element v such that either X=x+y+U+Z+V

or else

y = v+ y + u + z +y.

From this we conclude by 1.27 that (8)

either x = z + ( y + u ) + x or else y = y + ( u + x ) + y .

( I ) , ( 7 ) , and (8) imply that either x or y does not belong to X . Therefore, by contraposition, we have x +y E X whenever both x E X and y E X ; in other words,

X satisfies 1.55(iii).

(9)

By (3), (4), (9), and 1.55, the set RC is a subset of X. Hence, by (1) and the hypothesis, we arrive a t the conclusion.

COROLLARY1.64. If a

E

RC, a.p
and v < p (or a.,u=a.v

and p # v ) , then a=0.

PROOF:By 1.47 we obtain

a = a . 2 =a + 0 +a.

Hence the conclusion follows by 1.63.

As a natural generalization of 1.63 and 1.64 we may mention the following statement :

If a

E

RC

and a.p=&p(a+b,)+a,

then a=O.

50

CHAPTER

I

The problem whether this statement actually holds has been solved sf€irmatively by Chang; the solution is given in Appendix A.

THEOREM 1.65. Let a E RC (or b E RC). I n order that a + b = b + a i t i s necessary and sufficient that either (i) a = b . w + c + b * w for some element c, or else (ii) b=a.o+c+a*w for some element c, or finally (5) a =c .p and b = c .v for some element c and some ordinals ,u<(o and v<w. PROOF:By 1.27 and 1.37, each of the conditions (i) and (5) implies a+b=b-ta; the same is obviously true of (iii). To prove the implication in the opposite direction, consider the sets Y and X determined by the following stipulations: (1)

[

y E Y if and only if, for every x , the formula y + z = z +y # z implies that either y + z = y or else y = w . p and 2=w.v for some element w and some ordinals puto and v < o ;

X if and only if, for all u, y , and v, the formula x = u + y + v E Y.

[ implies that y x

(2)

E

We shall show that the set X satisfies conditions (i)-(iii) of Definition 1.55. Let s be any element for which (3) the formulas s = x

+y

and y # 0 always imply that z E X.

Let u, v, y , and z be any elements such that s=u+y+v

(4)

and

yfz=zfy#z.

(5)

By applying 1.54 (with a= c = y and b = z ) , we conclude from (5) that there are elements d , e and an ordinal z < w such that (6)

y =d

+ e = e +d

-

and z =y n + d = d + y .n.

ORDINaL ALGEBRAS AND THEIR A R I T H ~ T I O

By (4) and (6), s =u + d

(7)

51

+(e+ w).

If e=O, we have by (6)

y = y. 1, z = y * ( n + l ) ,

(8)

and consequently we obtain: (9)

(

y = w . p and z=w.v for some element w and some ordinals p<m and v < o .

If e # 0, we have by (3) and (7) u+d EX. Since u+d=u+d+O, we conclude from (2) that d E Y . By (1) (with y = d and z = e ) and (6), this implies that either

d+e=d

(10)

or else

d+e=e

(11)

or, finally,

d =f .p' and e = f .Y' for some element f and some ordinals (12) ( $ < o and d < w .

If (10) holds, we apply (6) and obtain, rn before, (8) and (9). If (11) holds and, in (6), n=O, we obtain (13)

y+z=y.

If, however, n#O, we derive from (6) and (11) by means of 1.13(ii) and 1.39:

Y=d+Y, z= d+ y .n=d +y +y ' (n- 1) =y +y .(n- 1) =y .n; and hence we obtain (9). Finally, if (12) holds, we get from (6) y =f * (p'

+Y'),

2 =f

so that (9) is again satisfied.

.((p' +Y ' ) en+$),

52

CHAPTER

1

Thus we have shown that, under the assumption (4)) formula (5) implies for every z that either (9) or (13) holds; consequently, by ( l ) , (14)

y

E

Y.

Since (4) always implies (14), we conclude from (2) that s E X . Thus, every element s which satisfies (3) belongs to X ; consequently, (15)

the set X satisfies condition 1.55(i).

I n an entirely analogous way we show that (16)

the set X satisfies condition 1.55(ii).

Consider now any two elements s, t such that (17)

s E X and t E X .

Let (18)

s+t= us- y+v,

and let z be any element satisfying (5). Again, by applying 1.54 to ( 5 ) , we arrive at (6). From (6) and (18) we get s+ t = (u+d)

+ (e +v).

Therefore, by 1.34, there is an element f such that either

or else

s=u+d+f t =f + e +v.

Hence, by (2) and (17)) d E Y or e E Y . I n either case we conclude by ( 1 ) and (6) that one of the three conditions (lo), ( l l ) ,and (12) is satisfied. By arguing as above we infer that either (9) or (13) holds, and we arrive at (14). Thus, (14) follows from (18) for any u, y, and w ; therefore, by (2)) (19)

S+tEX.

I n this way we have shown that (17) always implies (19); in other words, (20)

the set X satisfies condition 1.55(G).

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

53

By applying Definition 1.55 we conclude from (15), (16), and (20) that the set X contains all elements of RC. As is easily seen from (2), X is a subset of Y,consequently, RC is also a subset of Y . I n particular, we have by hypothesis a E RC and therefore a E Y . Hence, by (l), if

a+ b= b+a, then one of the following three conditions must be satisfied:

a+ b = b +u=a,

(21) (22)

(23)

a+ b = b+a= b,

{

a = c + p and b = c . v for some element c and some ordinals p < o and v<w.

By 1.27 and 1.37, (21) implies condition (i) of our theorem, and

( 2 2 ) implies (ii); (23) coincides with (iii). The proof has thus been

completed.

As is easily seen, the assumption a E R G plays no role in the proof that each of the conditions (i)-(iii) of 1.65 implies the commutativity of a and b. On the other hand, examples in special ordinal algebras show that, without this (or some other) additional assumption, the implication in the opposite direction in general does not hold. We shall return to this problem in Chapter 2.

By omitting in Definition 1.55 one or two of the conditions (i)-(iii), we arrive at some interesting subsets of RC. I n particular we can consider the set RC' which is defined as the intersection of all subsets X of A satisfying 1.55(i), and which proves to be the smallest set satisfying this condition; the elements of RC' can be referred to as recursive in the narrower sense. A number of the preceding theorems remain valid if RC is replaced in them everywhere by RC'. This is obvious in the case of 1.63-1.65 since RC' is a subset of R C ;but this also applies to 1.56(i),(iii), 1.57(i),(G), 160(i),(ii),and 1.61(i),(ii). Each of the following two conditions proves to be necessary and sufficient for a E RC': (i) for every b, the formulas b<*a and b # O imply the existence of an indecom-

64

OHAPTER 1

posable element c such that c
To conclude, we shall discuss briefly some algebraic generalizations of the results so far obtained. It may be noticed that, in the whole preceding discussion, when establishing properties of finite sums we did not use arbitrary sums of infinite sequences, but only special sums of this kind, in fact, the wth multiples. Hence, for the purposes of this study, we can modify, and actually generalize, the notion of ordinal algebras by treating an ordinal algebra as a system formed by a set A , by three operations under which A is closed -a binary operation + , a unary operation *, and another unary operation, the formation of wth multiples-and finally by a distinguished element 0 of A . For these generalized ordinal algebras we define recursively the sum of a finite sequence by putting As special cases of finite sums we obtain finite multiples, a.p. We also define the relations < and < * as well as the set RC by repeating without changes Definitions 1.15, 1.15*, and 1.55. As postulates characterizing ordinal algebras in the new sense we choose the following postulates and theorems from the preceding discussion: 1.6, 1.7, 1.34, l.lO(iv), 1.14, 1.24, l.l(V), and l.l(V1); the part of l.lO(iv) involving a.p and the part of the conclusion of 1.24 involving a, can be omitted and afterwards derived as theorems. (For some restricted purposes it might be useful to include the formula (a + b ) .w = a + (b+ a ) . w

65

ORDJNAL ALGEBRAS AND THEIR A R F F H ~ T I C

in the postulate system; cf. the remarks following 1.38.) It turns out that all the results of this chapter which do not involve sums of arbitrary infinite sequences remain valid when applied to generalized ordinal algebras. Some of the more interesting results so far obtained can be extended to a still wider class of algebras, which, for the lack of a better term, may be referred to as directed refinement algebras. These are algebraic systems formed by a non-empty set A and a binary operation + under which A is closed, and characterized by the following three postulates:

(I+) @+)

+

+

a ( b + c ) = (a+ b ) c. If b = a + b + c , then b = a + b . a + c = b +d, then a = b and c =d or else there is an element or a + e = b and c = e + d .

(III+) (eIsuch f that either a = b + e and e + c=d

Postulate (III+)is a somewhat weaker form of Theorem 1.34. The two statements are obviously equivalent for every algebra ( A , +) with a zero element 0 such that a + O = O + a = a for every a E A ; however, a directed refinement algebra may have no such element. For the algebras discussed we define recursively finite multiples a . p with p#O, and we introduce the relations Q and < * by means of the following stipulations :

a < b if and only if either a = b or else a + c = b for some c ; a < * b if and only if either a= b or else c + a = b for some c.

These definitions of < and < * differ slightly from the corresponding definitions for ordinal algebras. The difference is again caused by the fact that directed refinement algebras are not assumed to have zero elements; if we accepted here the original definitions, we could not show, e.g., that a
56

CHAPTER

1

very small and obvious changes. Among the results of the present chapter (involving only finite sums and multiples) which we have been unable to extend to directed refinement algebras we may mention Theorems and Corollaries 1.39, 1.41-1.43, 1.52, and 1.53; we shall return to this question shortly. Obviously, if ( A , 2, +, *, 0) is an ordinal algebra, then ( A , +) is a directed refinement algebra. Further instances of such algebras can be found among semigroupe, i.e., algebraic systems ( A , +) in which the ordinary associative law and the two ordinary cancellation laws hold: a+(b+c)=(a+b)+c; if a+c=b+c or c+a= =c+b, then a=b. In fact, every free semigroup with arbitrarily many generators is a directed refinement algebra. To construct a free semigroup with 01 generators, where u is an arbitrary cardinal different from 0 (finite or infinite), we start with an arbitrary set A of power a. Let S be the set of all finite non-empty sequences x in which all the terms xo, xl, ... belong to A . Given two such sequences, 1: and y, of types L<w and p
-

ORDINAL ALGEBRAS AND THEIR ARITHMETIC

57

types Y, v
CHAPTER 2 ORDINAL ADDITION OF RELATION TYPES I n this chapter we want to show how the results obtained in Chapter 1 can be applied to the arithmetic of relation types. We begin with recalling some familiar notions of the theory of relations. 8) By a binary relation or, simply, a relation we understand an arbitrary set of ordered couples. Thus, the empty set 0 is a relation; the cardinal (Cartesian) product A x B of any two sets A and B is a relation. The union R u S and the intersection R n S of any two relations R and S are again relations; the same applies to the union UieIRi and the intersection Ri of any (non-empty) system of relations Ri correlated with elements of a set I . The field F(R) of a relation R is the set of all elements x such that, for some y , (x,y ) E R or (y, x) E R. Two relations R and S are called strictly disjoint, in symbols R ) ( S , if their fields are disjoint, i.e., P(R)n P(S)=O. A relation R is called reflexive if (x,x) E R for every x E F(R). We assume it to be known what is meant by a partially ordering, simply ordering, and well ordering relation. I n addition to general set-theoretical operations (like formation of unions and intersections), some special relation-theoretical operations are known which, when performed on relations, yield new relations. Thus the converse 3 of a relation R is the set of all couples (x,y) such that ( y , x) E R. The ordinal sum of two relatiom R and S is the relation R+X defined by the formula

nitI

R+S=R u

xu

[F(R)x F ( S ) ] .

For notions of the theory of relations which are involved in the sub8, sequent discussion see [20], vol. 1, pp. 231 ff., and vol. 2, pp. 291 ff.; cf. also [2], pp. 9 f. However, our notation differs in several details from that in [20] and [2]. In particular, relation types are referred t o in [20] as relation numbers.

60

CHAPTER

2

The ordinal sum Ex<,R, of a sequence of relations R,, ..., R,,... with x t p (where p is an arbitrary ordinal) is defined by the formula

zx

=ux<,

Rx u L

A < ,

[ F (R,) x F (RAH-

zes

A still more general notion is that of the sum R, of a system of relations R, over a relation S (with the index e' ranging over the

elements of F ( S ) ) ;we define this sum by putting

2i.s Ri = 'Jicp(s)

-

Ri u U<<. j>ts.i+j [ F (RJ x i~ (Rj)I

If, in particular, S is the G relation between ordinals which are smaller than a given ordinal p, then and, in case p = 2 ,

I,<, R,

1i.s

R, =

2i.s

Rj= ROS-R,.

The general relational sums C,sR, will play a very restricted part in our further discussion. Some rather simple properties of the notions defined above are formulated in the following theorems 2.1-2.8, in which the variables R, S , T , ... represent arbitrary relations and the variables x , A, p, ... range over arbitrary ordinals.

THEOREM 2.1 (i) For any reflexive relations R and S , the relation R n S i s reflexive, and we have

F(R n S )= F(R)n F(S).

(ii) For any sequence of a type p # 0 of reflexive relations R,, the relation n, R, i s reflexive, and we have F (%)

(nw<,Rx) = n,<,

...,R,, ...,

F (Rx)*

For any reflexive relations R and 8, the formulas R ) ( S and

R n S = 0 are equivalent.

PROOF:By the definition of the field of a relation, we obviously

have

F(R n 8 ) C F(R)n F ( X )

ORDINAL ADDITION O F RELATION TYPES

61

for any relations R and S. If, on the other hand, the relations R and S are reflexive and

x

E

F ( R )n F ( S ) ,

then

(x, X > and therefore x

E

E

R nS

P(R n S ) .

Hence the conclusion of (i) follows at once. The proof of (2) is quite analogous; (iii) follows from (i) and from the definition of strictly disjoint relations. THEOREM 2.2. (i) R + 0 =0 + R = R. (ii) R + ( S T )= ( R+ S ) T . (iii) R C R+S and S C R+S. (iv) If R C T and S C U , then R + S S T + U . (v) If T C R + S and T ) ( R , then T Z S ; if T C R + S and T ) ( S , then T C R. (vi) R + S ) ( T if and only if R ) ( T and S ) ( T . (vii) If the relations R and S are reflexive, the relation R+S is also reflexive; in case R ) ( S , the converse holds as well. PROOF : quite elementary.

+

+

2.3. Assume that R + S = T + U and R)(X. W e then THEOREM have : (i) R)( U or S ) (T ; (ii) R = ( Rn T )+ ( R n V ) and S= ( S n T )+ (S n U ) , provided the relations R, S , T , and U are reflexive. PROOF: Let (1)

v==[ P ( S )n F ( T ) ]x

[ F ( R )n P(U)].

Hence obviously

V C P ( T )x P ( U ) C T + U and therefore, by hypothesis, (2)

V C R+S=R U S U [P(R)x F ( S ) ] .

62

CHAPT%R

2

We also have, by ( 1 ) and the hypothesis,

F7 C P(X) x F(R)and P(R)n P(X)=O; consequently,

V n R = V n S = V n [ F ( R ) x F(S)]=o.

(3)

(2) and (3) imply

v=0.

Hence, by (l),

P(R)n F( U )= 0 or F ( S )n P ( T )= 0,

i.e.,

R ) ( U or S ) ( T .

Thus (i) has been established. To obtain (ii), notice that, by hypothesis and 2.2(iii),

R _c T + U = T u U u [ P ( T )x F(U)]; also, by 2.1(i),

R n [ P(T)x P(U ) ]Z [P(R) n P(T)]x [P(R) n P(U ) ]= =P(Rn T ) x F(R n U ) .

Therefore i.e., (4)

R C (Rn T)u (Rn U ) u [F(Rn T)x P(Rn V ) ] ,

R C (Rn T ) + ( Rn U ) .

On the other hand, by 2.2(iv),

( R n T ) + ( R nV ) C T + U whence by hypothesis (5)

(Rn T)+(Rn U ) _C R+S.

Since R ) ( S , we clearly have

R n T ) ( S and R n U ) ( S and therefore, by 2.2(vi), (6)

@nT)+(Rn U))(S.

63

ORDINAL ADDITION OF RELATION T W E S

By 2.2(v), formulas ( 5 ) and (6) imply ( R n T ) + ( R nU ) C R . Together with (4), this gives

R = ( R n T ) + ( R nU ) . I n an entirely analogous way we show that

S = ( S n T ) + ( S nU ) , and the proof is complete.

THEOREM 2.4. (i) For every relation R and every sequence of relations So, ...,S,, ... with x < p , p#O, we have U,,,(RtS,)

= R+

U,,, S, and U,<,(S,+R)

(ii) I f , moreover, the relations So, ...,S,, n,,,(R+s,)

= R+n,,,,s,

... are

and n,,,(s,+R)

=

U,,,S,+R.

refiexive, then =

n,,,s,+R.

PROOF:(i) By the definition of an ordinal sum, we have u,<,(R+sx)

=

U,<,(RUS,U [ F ( R )xF(S,)I);

hence

Ux<,(R-tSx) = RUU,<,~xUU,,, [ F ( R ) x F ( S x ) l =R u s x u [ F (R)x F (S,)l = RUU,<,S,U [F(R)xF(U,,,S,)l,

ux<,

ux<,

so that finally

U,<,(R+S,)

= R+U,<,S,.

The second formula in the conclusion of (i) is obtained analogously. (ii) By 2.2(iv) we have

R+n,,,S,CR+S, and hence

for every x c p ,

64

CHAPTER

2

66

ORDINAL ADDITION OF RELATION TYPES

(1) and (8) yield the first formula in the conclusion of (ii), i.e.,

n,<,(R+S,)

= R+n,<,&

The second formula in (ii) is derived in an entirely analogous way, and the proof is complete.

Zc,

THEOREM 2.5. (i) IX<, R,=O and R,= Ro. (ii) ZX<,+" R, = R,+ ;rx
z<,

z<,

THEOREM 2.6. If the relations B,,, ..., R,,... with x < o , S,and T a r e reflexive, Z,,,R,=S+T, Rx)(Rdfor any x and ilwith x < A < o , S ) ( T , ard T#O, then there is an ordinal p < o such that

Zx<,R,+

(R, n 8) = 8, (R, n T )+

and

R,

z<, R,+l+X

=T,

+ (R, n T).

= (R, n S )

PROOF: The formula (1)

R,)(T

must fail for some p < w . For otherwise we should have, by 2.5(iv) and the hypothesis,

R,)(T and S + T ) ( T . Hence

( S + T ) n T=O;

and since, by 2.2(iii),

T CS+T, we could conclude that T = 0, which contradicts the last premise of the hypothesis.

66

CHAPTER

2

Let p be the smallest ordinal for which (1) fails. Thus y t w and, by 2.5(iv),

z<, Rx )( T .

(2)

By 2.5(c),(iv) and the hypothesis, ( 3)

z\x<,+l

Rx+

R,+l+,

= X+T

and (4)

R x ) ( z < wRP+l+X.

&4+l

Hence, by 2.3(ii) and 2.5(v), (5 )

Z<,+lRx =

(G<,+1

Rx n 8)+ ( % < p + l

Rx n TI.

By 2.5(i),(ii),(iv) we have

ZX<,+l Rx = %<, Rx+R,

(6)

and (7)

Z X < ,

Rx)(R,.

Formulas (5) and ( 6 ) imply

I;<,RX+R,

= (Z
whence, by (7)) 2.3(ii), 2.5(v), and 2.1(i),

Rp = (Rp n Z x < p + i Rx n 8 )+ (Rp n s < p + i Rx n T ) . Since, by ( 6 ) and 2.2(iii),

R, c 2 X < , + l Rx >

(8)

we conclude that (9)

R,= (R, n S )+ (R, n T ) .

From (3), ( 6 ) ) and (9) we obtain by means of 2.2(ii): (10)

[C<,Rx+(R,n S)l+ [(R,n T ) + zx<m R,+l+xl = S + T .

We have, by hypothesis, S ) ( T whence (11)

R, n X )( T and X )( R, n T.

67

ORDINAL ADDITION OF RELATION TYPES

(2) and (11) give by 2.2(vi)

z<, R,+ (R, n W ( T ;

by combining this formula with (10) and by applying Z.Z(iii),(v), we get (12)

z,,R,+(R,nS)

C S and TC(R,nT)+Z<,R,+,+,.

From (3) and (4) we conclude by 2.3(i) that either (13)

z
Rx)(T

or else (14)

%
R,+l+X)(~.

Formulas (8) and (13) clearly imply (1); since ,u is an ordinal for which (1) fails, (13) must fail as well, and hence (14) must hold. (11) and (14) yield by 2.2(vi)

(R, n T)+ Z x < m R,+l+,)(S. Again, by combining this formula with (10) and by applying 2.2(iii),(v), we arrive at (15)

c zx<Jl R,+ (R, n 8) and

@/I

n T )+ z ; < w R,+I+X c T .

Formulas (12) and (15) yield (16)

%<, R,+

(R, n 8) = f l and (R, n T )+

z<, R,+1+,

=T.

From (9) and (16) we see that the ordinal p satisfies all the conditions stated in the conclusion of our theorem.

THEOREM 2.7. If R, =8%4-R,,, for every hc <w and if all the relations So,..,, S,, ... are reflexive, then R, =

s<, S,+Af

nA<, RA

for every x < w . PROOF: Let x be any given h i t e ordinal. By an easy induction (on p), we derive from the hypothesis: (1)

R,

=

ZA<, fix+,+ R,+,

for every p < 0 .

68

2

CHAPTER

The derivation is based upon 2.2(i),(ii) and 2.5(i),(ii). (1) implies by 2.2(iv):

z

Consequently,

Ra C R, for every p < O.

up<,cz<,Sx+,+ n,<, RA) c Rx,

therefore, by 2.4(i),

up<,( 2 k p S X + d + whence, by 2.5(iG), (2)

na<m

Ra c Rx

z<,sx+,+ na<,RA c Rx.

Similarly, (1) implies by 2.2(iv) and 2.5(iv)

Rx C 2:l
RX

c

np<m

c G < w &+A

+Rx+,) = G

< w Sx+A+

L

u

Rx+p

Since (1) holds for every x < o and p < o , we easily conclude by means of 2.2(iii) that

R,

C R,

for every

and that consequently np<w

R,,,

=

A<x

na<, Rk

By combining this formula with (3), we arrive at

c

+ na<,Ed.

=

ZA<*&+A + n,<, R,

R, ZA
for every x t o ; this completes the proof.

-

THEOREM 2.8.

-

(i) E = R ;

R +S =Z + 2 ; (iii) the formulas R ) ( S and &)(gare always equivalent; (iv) i f the relation R i s reflexive, the relation 2 i s also reflexive.

(ii)

ORDINAL ADDITION O F RELATION TYPES

69

PROOF:obvious, by the definitions of the notions involved. Given two relations R and S, a function f is said to m a p R isomorphically onto S i f f maps F(R)onto F ( S )in a one-to-one way and if, in addition, for any two elements x , y E F(R),the formulas

<x,Y> E R and ( f ( 4f (,Y ) ) E are equivalent. If such a function f exists, the relations R and S are called isomorphic, in symbols R S. Clearly, R LZ R for every relation R ; R S implies S R for any relations R and S ; R E S and S T imply R T for any relations R, S , and T. I n other words, isomorphism regarded as a relation between relations is an equivalence relation. Consequently, we can correlate a relation type z(R) with every relation R in such a way that, for any relations R and 8,the formulas

T ( R= ) t ( S ) and R

S

are equivalent. 9 Instead of saying “relation type” we sometimes say simply “type”. Small Greek letters LX, p , ... are used to represent arbitrary relation types. The type of the empty relation 0 is itself denoted by 0. We extend to relation types various terms originally defined for relations (or even for arbitrary sets). Thus, e.g., a type a is respectively called finite, denumerable, or reflexive if it is the type of a finite, denumerable, or reflexive relation. Types of simply ordering relations are referred to as order types; types of well ordering relations can be identified with (finite and transfinite) ordinals. The set of all reflexive relation types will be denoted by RT and the set of all order types will be denoted by OT. We are not concerned here with set-theoretical foundations of our study and with difficulties which arise if one attempts to carry through the discussion within a particular axiomatic system of set theory. Thus we use freely the notion of a relation type without defining it in a formal way; we assume that relation types can be combined in sets, and we do not hesitate to speak of the set of all relation types and of comprehensive subsets of this set. I n this connection the remarks made in [17], p. 154, can be repeated literally.

70

CHAPTER

2

For any two relations R and S the formulas

-

-

R G S and R E S

are obviously equivalent. Hence we can define the converse (or inverse) a* of a relation type a by stipulating that a* is the common type of all relations S such that @ ) = a . Given any two strictly disjoint relations R and S, we have, as is easily seen,

R+SrT if and only if there are relations R' and S' such that

R'+S'=T, R')(S', R r R', and S r S'.

Hence we can define the ordinal sum a +,!3 of two types LY and as the common type of all relations T which can be represented in the form T=R+S where R)(X, z ( R ) = a , and t(S)=P. For any two relations R and S we can construct two strictly R and S S ' ; for disjoint relations R' and S' such that R instance, we can define R' as the set of all couples

<(x, o>, E R, and S' as the set of all couples

<<x, 1>, (Y, 1)) with

Y> E S -

(2,

Hence we conclude that the operation + is always performable in the domain of relation types; i.e., for any two types a and P, a + p is a uniquely determined relation type. I n an entirely analogous way we define the ordinal sum Ex<,01, of a sequence of types ixo, ..., a,, ... with x < p ( p an arbitrary ordinal), and the sum Zissaiof a system of types ai over a relation S (with i ranging over the elements of F ( S ) ) . The applicability of the results established in Chapter 1 to the operations on relation types just defined is secured by the following fundamental theorem :

ORDINAL ADDITION OF RELATION TYPES

71

THEOREM 2.9. The system %%=(RT,2, +, *, 0) (with t A , operation 2 restricted to finite sequences and sequences of type o) is an, ordinal algebra. PROOF:By 2.5(v), 2.2(vii), and 2.8(iv), the set RT is closed under the operations 2, +, and * ; it is also obvious that RT contains the type 0 as an element. From 2.5(i), 2.5(ii), 2.6, 2.7, 2.8(i), and 2.8(ii) we easily see that Postulates (I)-(VI) listed in Definition 1.1 (with small Roman letters replaced by small Greek letters) are satisfied in the system 8%. I n showing this, we pass several times from formulas involving ordinal sums of relations to the corresponding formulas involving sums of types ; we make use here of the fact that the relations involved are strictly disjoint, and we apply 2.2(vi), 2.5(iv), and 2.8(E). We also apply 2.l(i),(ii). For illustration we shall outline the proof of Postulate l.l(IV). By the hypothesis of this postulate, for every relation R and every finite ordinal x the formula t ( R )= 01,

(1)

leads to

t ( R )= B x + 61,+1;

the latter formula implies the existence of two relations S and T such that R=S+T, S ) ( T , t(S)=B,, and t(T)=a,+,. Hence, by means of the axiom of choice, we conclude that there exist two functions F and G which correlate the relations R(R, x ) and G(R,x ) with every relation R and every finite ordinal x in such a way that, under the assumption ( l ) ,the following formulas hold (2)

(3)

R= F(R,x ) +G(R,x ) and F(R, x ) ) ( G(R,x ) , t ( F ( R ,x ) ) = &

and z(G(R,x ) ) = d ~ , + ~ .

Consider now any relation R for which (4)

t ( R )=ao.

72

CHAPTER

2

We define recursively two infinite sequences of relations, Ro,... R,,. .. and So, ...)S,, ..., by putting for every x < w (5)

Ro= R , R,+, =G(R,,x), and AS,=F(R,,x).

By an induction on x, using the fact that (1) implies (2) and (3), we derive the following formulas from (4) and ( 5 ) :

R,=S,+R,+, for every x < w ,

(6)

S,)(R,+, for every

(7)

(8)

x
t ( R , ) = a , and t(S,)=/l, for every x < w .

Let (9)

z(na,,&)

=

Y;

from 2.l(ii) it follows that y is a reflexive type. By 2.7, (6) implies (10)

R, = G < , X x + ~ +n,,, Ra for every x < w .

From ( 6 ) we easily conclude by 2.2(iii) that S, any x and il with x t i l t w ; hence, by (7), (11)

C R, C R,+,

for

Sx)(Sa for X < A < O .

We also have

fLm R, C

therefore, by (7),

S,)(

nlcoRa for every x < w

whence, by 2.5(iv), (12)

%cmfix+l)(na,,Ra for every

x

< 0.

From (10)-(12) we get t

(R) = %<, Z ( S x + , ) + t (L, Rd ;

hence, by (8) and (9), we obtain the conclusion of Postulate l.l(IV), i.e., a, = ~ < o ( 6 , + , + y for every x < w . Thus, by 1.1, the system proof is complete.

%Z

is an ordinal algebra, and the

ORDINAL ADDITION OF RELATION TYPES

73

THEOREM 2.10. Let A be any non-empty subset of RT satisfying the following conditions : EA ; (a) if 01, E A for every x
(c) if

LY

EA,

then

(Y*E

A.

2, +,

Under these assumptions the system % = ( A , *, 0 ) (with restricted as in Theorem 2.9) is a n ordinal algebra the operation

2

and in fact a n ordinal sub-algebra of the algebra %X discussed in Theorem 2.9. PROOF:Since O + @ = p for every type and the set A is not empty, premise (b) clearly implies that 0 E A . Given two types E A and y E A , we let (xo==/l, a,=y,

and ( Y ~ + ~ = for O every x < o .

Then obviously 2 X a u

a, = B + Y

and hence, by (a), + y E A . Thus the set A is closed under binary addition ; similarly, it is closed under addition of finite sequences. All the postulates (1)-(VI) of 1 . 1 are satisfied in the system %. As regards the non-existential postulates, (I), (11), (V), and (VI), this follows immediately from 2.9 (since A is a subset of RT). In deriving the existential postulates, (111) and (IV), we again apply 2.9 and make an essential use of premise (b). Hence, according to Definition 1.1, the system '?2l is an ordinal algebra.

As examples of sets A which satisfy the hypothesis and hence also the conclusion of 2.10 we may mention the sets of all order types, all types of partially ordering relations, all at most denumerable types and, more generally, all types with the power not exceeding a given infinite cardinal p. Clearly, the intersection of arbitrarily many sets satisfying the hypothesis of 2.10 also satisfies this hypothesis. From 2.9 and 2.10 we see that all the theorems established in Chapter 1 remain valid if the variables occurring in these theorems

74

CHAPTER

2

are assumed to range over arbitrary reflexive relation types or, more generally, over elements of an arbitrary set A satisfying the hypothesis of 2.10. We have, of course, to assume that all the notions introduced in Chapter 1 and defined there in terms of fundamental operations of an ordinal algebra have been extended to the arithmetic of relation types and hence can be applied to the algebras discussed in 2.9 and 2.10. The notions which we have in mind are the operation of forming multiples (Definition 1.8), the relations Q and < * (Definition 1.15, Theorem 1.16)) and the notion of a recursive element, i.e., an element of the set RC (Definition 1.55). The operation of forming multiples is a particular case of a more general operation, in fact, of ordinal multiplication. By the ordinal product R.8 of two relations R and S we understand the set of all ordered couples ((2, u>,

(Y, v>>

where either (2,y ) E R and u=v E F ( S ) or else x, y and ( u , v) E S. As is easily seen, the formulas

E

F ( R ) ,u f v ,

R r R ' and X r S ' always imply

R.8

G R'aS'.

Hence we can define the ordinal product a./3 of two types in such a way that, for any relations R and S , we have

LY

and

0

z ( R . 8 )= z ( R ). t ( S ) . We could also define 0 1 . easily be shown that

in terms of relational addition ; for it can a.B=Z.SYi

whenever S is a relation of type /3 and we have yi= a for every If, in particular, 01 is an element in the algebra 3% of 2.9 or in one of the algebras 8 of 2.10, and p is an ordinal not greater than w , then the ordinal product a . p coincides with the pth multiple of a as defined in 1.8.

i E .#'(A').

ORDINAL ADDITION O F RELATION T W E S

75

Given two relations R and S , we say that R is an initial, or final, portion of S if there is a relation T such that R ) ( T and R+T = S , or T f R = S , respectively. For two types oc and /? we write oc
If R and S are any two relations, T is a non-empty finite simply ordering relation, and R.T S - T , then R S. lo) 10) I n proving 2.9 we use the axiom of choice (possibly restricted to denumerable families of sets). Hence the theorems of Chapter 1 in their application to relation types seem to depend upon the axiom of choice; and this holds also for the translations of these theorems which do not involve relation types, but apply to relations themselves. Actually, however, all the theorems in question can be established for relation types directly, by following the lines of argument applied in Chapter 1 and without using the general result stated in 2.9. It turns out then that most theorems of Chapter 1 -in fact, all those in which only finitely many different elements are involved -can be proved for relation types without the help of the axiom of choice. This holds, e.g., for 1.52-1.54 and 1.65, even though the axiom of choice plays an essential part in the abstract algebraic proofs of these results outlined in Chapter 1. Compare analogous remarks (concernkg theorems on cardinal algebras and their implications for cardinal numbers) in [17], pp. 239 ff., and [16]; these remarks fully extend to ordinal algebras and relation t)ypes.

76

CHAPTER

2

It is less easy to get an insight into the relation-theoretical content of those results of Chapter 1 which involve the set RC, i.e., the notion of a recursive element (defined in 1.55). We want to discuss the matter more closely and in fact to show that recursive elements in ordinal algebras of 2.9 and 2.10 admit a rather simple characterization in terms of some familiar relation-theoretical notions. A relation R is called dense if F ( R ) has at least two distinct elements and if, for any x and y with

(x,y)

E

R and x z y ,

there is an element x such that

<x, x>

E

R, ( z , y> E R, x # z , and

z # y.

A relation S is called scattered if there is no dense relation R included in S (R C S). By a scattered relation type we understand, of course, the type of a scattered relat,ion.

2.11. Let D%=(OT, 2, +, *, 0) (with the operation restricted as in Theorem 2.9). T h e n DZ i s an ordinal algebra and the set RC of all recursive elements in this algebra coincides with the set of all scattered order types. PROOF (in outline): 0% is clearly an ordinal algebra by 2.10. Let SC be the set of all scattered ordered types. This set satisfies the following conditions :

2

TmoREM

If

( and If (2) { and

(x

(1)

E OT

and if, for all types

L,?

and y , the formulas (x ESC.

y # O imply that ,6 ESC, then

LY =

/? + y

O T and if) for all types ,L? and y , the formulas OL = /? + y B + O imply that y ESC, then LY ESC.

LY E

p ESC,

ESC. Conditions (1)-(3) reduce to certain conditions (1’)-(3’) which concern relations themselves (and not relation types) and can easily be derived from the definitions of the notions involved. For instance, (1) reduces to the following condition: (1’) If R is a simply ordering relation and if every initial portion of R which is different from R is scattered, then R is scattered. (3)

If

01

ESC and

then

L Y + ~

ORDINAL ADDITION O F RELATION TYPES

77

From (1)-(3) we see that XC is one of the sets X (included inOT) which satisfy conditions (i)-(iii) of 1.55. Since, by 1.55, RC is the common part of all such sets X, we obtain

RC

(4)

C XC.

On the other hand, we can establish the following properties of the set R C : (5)

(6)

(7)

(

If 01 is an ordinal, then 01 E RC. If 01 is an ordinal, then a* E R G . If S is a relation such that t(S)E R C and if a type di E R C is correlated with every i E F ( S ) , then C.s6iE RC.

(5) is obtained by transfinite induction. In fact, assume that is an ordinal such that 6 E R C for every ordinal smaller than a. Hence, for any types /Iand y , the formulas a =,!?+y and y # 0 imply B , E R C ; and therefore, by 1.56(i), 01 E RC. ( 6 ) follows from ( 5 ) by 1.59. To prove (7), consider the set X of all order types a satisfying the condition : if z(S)= 01 and if 6, E RC for every i E F ( S ) . then CSsE RC. Using some elementary properties of ordinal sums x*s6i, we show without difficulty that the set X satisfies conditions 1.55(i)-(S); hence ( 7 ) follows by 1.55. Consider conditions (5)-( 7 ) with RC replaced by X everywhere. It is known that SC is the common part of all sets X satisfying these conditions; see [13], p. 196. Since, as we have shown, RC is one of such sets X, we conclude that OL

(8)

XC C RC.

Formulas ( 4 ) and (8) imply at once the identity

RC =XC, which is the conclusion of our theorem.

To obtain now (in Theorem 2.13) a simple characterization of recursive elements in the algebra of all reflexive relation types, we need the notion of an indecomposable type. A relation R is said to be indecomposable (under ordinal addition) if R+O and,

78

CHAPTER

2

for any relations S and T , the formula R=S+T and S ) ( T imply that S= 0 or T = 0. A relation type cx is called indecomposable if it is the type of an indecomposable relation; or, what amounts to the same, if a # 0 and if, for any types B and y , the formula cx = ,6 y implies that B = O or y=O (cf. the remark following 1.57). The following theorem was established by Jbnsson and the author:

+

THEOREM 2.12.11) Every reflexive type the form a = 2i.s 4

cx

can be represented in

where S i s a simply ordering relation and where ai is a n indecomposable reflexive type for every i E F ( S ) . This representation i s unique in the following sense: if 01

= 2j.TEj

is another representation of cx with the same properties, then there is a function f which maps S isomorphically onto T in such a way that di= qci,for every i E P(X). PROOF: We restrict ourselves to indicating a rough idea of the proof. Let R be a relation with t ( R )= a . P is called a portion of R if it is an initial portion of a final portion of R. It is shown that any two different portions of R which are indecomposable are strictly disjoint. Let S be the set of all ordered couples (P, Q) where P and Q are two indecomposable portions of R such that either P = Q or else, fcr some relation U , P + U + Q is a portion of R, P)(U + Q , and U ) ( Q. We show that R admits the following representation : Moreover, it turns out that S is a simply ordering relation and that F ( S ) consists of all indecomposable portions of R ;the representation (1) proves to be uniquely determined by these two 11) This theorem was mentioned in [17], p. 249, footnote 33. J6nsson has recently obtained a much more general result which comprehends 2.12 as a particular case; this new result, together with a detailed proof, will be found in Appendix B.

79

ORDINAL ADDITION OF RELATION TYPES

properties of S. By passing from relations to relation types, the proof of the theorem is completed.

THEOREM 2.13. Let %X be the ordinal algebra of 2.9. Then the set RC of all recursive elements in %% coincides with the set of all reflexive types cx which can be represented in the form

where S i s a scattered simply ordering relation and where di i s a n indecomposable reflexive type for every i E P(S). PROOF (in outline): Let SC be the set of all reflexive types a which have the representation described in our theorem. We first show that SC satisfies conditions (1)-(3) from the proof of 2.11, with OT replaced by RT. In proving (1) and (2) we make essential use of 2.12; the proof of (3) is almost obvious. From (1)-(3)) by applying 1.55, we immediately derive formula (4) stated in the proof of 2.11. In turn we show that the set RC satisfies the following two conditions : (5)

If

(Y

is an indecomposable reflexive type, then cx

(6)

If

(Y

is a scattered order type, then cx

E

E RC.

RC.

( 5 ) is a simple consequence of 1.55; cf. 1.57(ii). To obtain ( 6 ) we show by means of 1.55 that every recursive element in the algebra DZ of 2.11 is also a recursive element in the algebra 8% of our theorem; hence (6) follows from 2.11. 'E'inally, by arguing as in the proof of 2.11, we show that RC satisfies condition ( 7 ) stated in that proof. By (5)-(7) we obtain at once formula (8) from the proof of 2.11; and formulas (4) and (8) lead directly to the conclusion of our theorem.

We notice that the only indecomposable order type is the ordinal 1 and that, for every reflexive relation S , Hence it is seen that 2.13 is a direct generalization of 2.11.

80

CHAPTER

2

The most important result of Chapter 1 concerning recursive elements is Theorem 1.65 which contains a characterization of commutative couples ( a , 6 ) (i.e., couples with a + 6 =6 f a ) , and provides a general method of constructing all such couples, under the assumption that at least one of the elements a and 6 is recursive, By 2.11 and 2.13 this result applies to commutative couples ( a , /?) of reflexive relation types in which at least one of the types a and /? is a scattered order type or, more generally, is a n ordinal sum of indecomposable types over a scattered simply ordering relation. The author showed by another method that the same result holds for couples ( a , /?)of order types in which a or /? is a t most denumerable. On the other hand, Lindenbaum constructed two non-denumerable and non-scattered order types a and ?!, which are commutative, but do not satisfy any of the conditions (i)-(iii) (with a, 6 , c replaced by a, ,8, y ) of 1.65. 12) Like the set RC, its subset RC' which was briefly discussed in the remarks following 1.65 also admits a simple characterization in terms of familiar relation-theoretical notions. I n the ordinal algebra 0% of all order types (cf. 2.11), RG' proves to coincide with the set of all ordinals, i.e., types of well ordering relations; in the algebra %% of all reflexive types (cf. 2.9) it coincides with the set of all types a which can be represented in the form where p is an arbitrary ordinal and all the 8,'s are indecomposable reflexive types. l a ) The results of the author concerning the coincidence of scattered order types with recursive types in the seme of 1.55 and the commutativity of two order types (in case one of them is scattered or denumerable) were obtained around 1930 but were not published; the counter-example of Lindenbaum was constructed in the same period. A general Characterization of, and construction method for, arbitrary commutative couples of order types has recently been given by Aronszajn in [l]. From the main theorem in [ 11 the results concerning scattered and denumerable order types as well as Lindenbaum's counter-example can easily be derived. Aronszajn's results, however, cannot be formulated within the arithmetic of ordinal algebras.

ORDINAL ADDITION OF RELATION TYPES

81

Without going into details, we want now to discuss some extensions of the main results of this chapter, i.e., Theorem 2.9 and its consequences, to various related systems. The assumption that all the relations and relation types involved are reflexive plays an essential role in the proof of Theorem 2.9 and of some of the auxiliary theorems (2.1, 2.3, 2.6, 2.7) upon which this proof is based. As was pointed out to the author by Jhnsson, it can readily be shown by means of examples that Postulates l.l(II1) and l.l(IV) do not hold for arbitrary relation types and that consequently Theorem 2.9 fails if the set RT is replaced in it by the set T of all relation types. 13) For instance, let R be the relation consisting of the only couple (0, l), and let S be the relation consisting of the three couples ( 0 , l), a 2 > , and (0,2); put and L Y ~ + ~ = Ofor x < w .

a,,=y=z(R), al=B=t(S),

As is easily seen, the types a,,, hypothesis of 1.1(111), i.e., &
a x

=

..., a%,..., @,

and y satisfy the

B +Y ;

however, the conclusion of l.l(II1)does not apply to these types. I n order to extend Theorem 2.9 (and all its consequences) to arbitrary relations, we have to modify the notion of a relation type. The following procedure can, e.g., be applied. Instead of relations R, we consider relational systems ( B , R ) where B is an arbitrary set and R is a relation included in B x B. The systems ( B , R) and (C, S) are called strictly disjoint if B n C = 0. By the convekse of the system ( B , R ) we understand the system ( B , 3). The ordinal sum of two systems, ( B , R) and ( C , S ) , is defined by the formula

(B,R)+(C,S)

= (BUC, RUSU(BxC)).

The ordinal sum of a sequence of systems is defined analogously. In [S], pp. 321 f., a remark is made to the effect that Theorems 1.27 15) and 1.37 hold for arbitrary relation types; this remark is correct only if the notion of a relation type is modified in the way indicated below.

82

CHAPTER 2

Two systems ( B , R) and ( C , S ) are called isomorphic if there is a function f which maps B onto C in a one-to-one way so that, for any elements x,y of B, the formulas
E

R and ( f ( 4 ,f ( Y D E s

are equivalent. By relation types in the new sense we understand the isomorphism types of the relational systems just discussed. To these relation types we extend in an obvious way the operations * , + , 2 ; the type of the system ( B , R) where B = R = 0 is denoted by 0. By repeating with slight changes the proof of Theorem 2.9 (and of the auxiliary theorems on which this proof depends), we can now show that the set T of all relation types in the new sense forms an ordinal algebra under 2, +, *, and 0 ; and the same applies to every subset A of T which satisfies conditions (a)-(c) of 2.10. Consider now systems (R, f ) where R is a binary relation and where f is an arbitrary function such that the domain of f is F(R) and the range of f is included in an arbitrary set E (regarded as fixed throughout the discussion). Two such systems (R, f ) and ( S , g) are called strictly disjoint if the relations R and S are strictly disjoint. The system (2, f ) is called the converse of the system (R, f). By the ordinal sum of two strictly disjoint systems ( R , f ) and ( S , g ) we understand the system ( T , h ) where T is the ordinal sum of R and S, and h is the function, with the domain F(R)u F ( S ) , determined by the conditions: h ( i ) = f ( i )for i E F(R),and h(i)=g(i) for i E P(S). Two systems ( R , f ) and ( S , g) are called isomorphic if there is a function h which maps R isomorphically onto S in such a way that f(i)=g(h(i))for every i E F(R). We introduce types corresponding to this kind of isomorphism, and for these types we define in an obvious way the operations *, + , 2 and the element 0. Given any set A of relation types, let A'E)be the set of types of all systems (R, f ) just described in which t ( R )E A . As is easily seen, whenever the system

% = ( A , 2, f , *, 0)

is an ordinal algebra, the same applies to the system

WE)=(A(E), 2, +, *, 0).

83

ORDINAL ADDITION OF RXLATION TYPES

If, in particular, ‘3%is the algebra of all reflexive types discussed in 2.9, then ‘3S‘E’is also an ordinal algebra; if DZ is the ordinal algebra of all order types and E is the set of all indecomposable reflexive types, then, with the help of 2.12, QFE’is shown to be isomorphic to ‘3%. In order to extend these results to arbitrary (not necessarily reflexive) relations, we replace the systems (R,f ) by the systems ( B , R,f ) where B is an arbitrary set and R is a relation included in B x B. The results obtained in this section can be generalized by referring the discussion, not to binary relations, but to elements of an abstract ,relation algebra. 14) We first extend to these elements various notions previously defined for binary relations. Thus, using U , n, and C to denote respectively Boolean addition, Boolean multiplication, and the relation of inclusion, we say that an element a is reflexive if [ ( a u ; ) ; 11 n 1’ C a . Two elements a and 6 are called strictly disjoint if

[(au

a); 11 n [(bu K) ;11

=

0.

The ordinal sums a+b and X x i p a x are defined by the formulas a + b = a u b u [(au

Z<@ ax =

a) ;1 ;( b u z)] ,

a, lJUX
a

;1 ;(al u

a.

The elements a and 6 are said to be isomorphic if there is an element c such that

-c ; c Z l ’ ,

-

-

c ; c C l ’ , c ; l = ( a u G ) ; l , and c ; a ; c = b .

When‘ applied to proper relation algebras formed by all binary relations between elements of a given set, the notions just defined coincide with those originally introduced for binary relations. la) For the definitions of an abstract relation algebra and of various related notions see [3]. (The opportunity is taken to correct a n error in [3], p. 383. It is not correct t o say that every non-empty set E of equivalence elements which is closed under . and ;is a modular lattice with ;as join and . as meet. However, the statement becomes correct if we assume in addition that a ; 1 = 6 ; 1 holds for any two elements a, b of E . )

84

CRAPTER

2

The type z(a) of an element a can be defined as the set of all elements isomorphic to a ; the type of the element 0 is itself denoted by 0. We define the converses and ordinal sums of types (K*,or+ 8, C
+

APPENDIX A SOME ADDITIONAL THEOREMS ON ORDINAL ALGEBRAS BY

CHEN-CHUNG CHANG In this appendix we shall prove a few theorems on ordinal algebras which will present a complete solution of one of the problems mentioned in Chapter 1 of this monograph and a partial solution of another. Throughout the appendix we shall use the notation and symbolism of the main body of the monograph. The first few theorems, A.l-A.4, concern the notion of commutative elements and are related to 1.52 and 1.53. (A.l and A.2 can be regarded merely as lemmas for A.3.) THEOREM A.l. I / a + b + a = b + a , then a + b = b or a+a=a. PROOF:By 1.25, the hypothesis yields a*o
hence, by 1.35(i), either (1)

a.w
or else, for some element c, (2)

a . o = b + c , c
If (1) holds, we obtain by 1.25 a+b=b. If (2) holds, we have c
86

APPENDIX A

THEOREM A.2. If a + b + a + a + b = b + a + b + a, then a + b = b + a. PROOF:We write the hypothesis in the form b

+ (a+b+a)

=

+

(a+ b + a ) ( a + b ) .

Hence, by applying 1.34, we conclude that there exists an element c such that either

b =a + b + a + c and c +a +b +a = a

(1)

+6

or else

b+c=a+b+a=c+a+b.

(2)

In case (1) holds, we obtain by 1.27 b=a+b and u + b = a + b + a whence

b=b+a, and the conclusion follows immediately. In case (2) holds, we get with the help of the hypothesis

~+~+~+b+b=~+a+b+a+b=a+bfa+afb =b+a+b+a=b+b+c and thus (C

+ c + a )+ (b+ b )= (6 + b ) + C.

By applying 1.54 to the latter formula, we see that either

b+b=b+b+c

(3)

or else there are elements d and e such that c+c+a=d+e

(4)

and c=e+d.

From ( 3 ) we derive by 1.41* Therefore, by

(a),

b=b+c. b =a + b $-a

and hence, by 1.27, we obtain directly the conclusion.

ADDITIONAL TEEOREMS O N ORDINAL ALGEBRAS

87

If (4)holds, we have d+e=e+d+e+d+a;

(5)

by 1.27, this implies

d +e= e +d +e.

(6)

Therefore, by A . l , either e + d = d or e + e = e . If e + d = d , we get c = d by (4);hence, by using (4)again, we obtain

c+c=d+e+d=c+c+a+c and thus

c+c= c +c+a+c.

(7)

If e + e = e , we have by (4) e+c=e+e+d=e+d=c and

c+c=e+d+e+c=e+c+c+a+c,

so that we again arrive at (7). By 1.41*, (7) implies

c = c +a+c.

Hence, with the help of (2), a+b+a=b+c=b+c+a+c=c+a+b+a+c.

Therefore, by 1.27,

a+b+a=c+a+b+a

and consequently, by (2), (8)

a+ b +a=a+ b + a + a .

By comparing (8) with the hypothesis, we obtain

a+b+a+b=b+a+b+a, i.e.,

(a+ b ) - 2= (b + a ) . 2.

An application of 1.46 to the latter formula immediately leads to the conclusion.

88

APPENDIX A

THEOREM A.3. If a+a+b=b+b+a, then a+b=b+a. PROOF:By 1.34 and the hypothesis, there exists an element c

such that either (1)

a+a=b+b+c

and c + b = a

b+b=a+a+c

and c + a = b .

or else (2)

Since the two conditions are symmetric, we restrict ourselves to the discussion of (1). We have then clearly (C

+b + + b = (b+b) + C)

C.

By applying 1.34 again, we conclude that there is an element d for which either (3)

c+b+c=b+b+d

and d + b = c

b+b=c+b+c+d

and d + c = b .

or else (4)

If (3) holds, we have hence, by 1.27,

d+b+b+d+b=b+b+d; b+b+d=b+b+d+b

and consequently, by 1.41 * , (5)

b+d

=b

+ d +b.

From (l), (3), and (5) we obtain

b+a=b+c+b=b+d+b+b=b+d+b+b+b= =b+c+b+b=b+a+b. Rence, with the help of the hypothesis, b+b+a=b+b+a+b=a+a+b+b, i.e.,

-

b . 2 + ~ a= *2 + b 2.

By 1.63, the latter formula implies the conclusion.

ADDITIONAL THEOREMS ON ORDINAL ALGEBRAS

89

If (4) holds, we get d+c+d+c=c+d+c+c+d. By A.2, this implies d+c=c+d.

(6)

From (l), (4),and (6) we obtain a+b=c+b+b=c+d+c+b=d+c+C+b=b+C+b=b+a, and the conclusion holds again. The proof has thus been completed. THEOREM A.4. If a.p+b.n=b.e+a.v O u t n G e t w , then a+b=b+a.

where O
PROOF:If either p = v or n=e, the conclusion follows by 1.53. Therefore we can assume that putv and rice.

(1)

The hypothesis of the theorem yields

+

+

a . p + b .ZC=b .Z b .(e - n) a * v

(2)

and

b

(3)

e +a - (v -p ) + a + p=a . p +b en.

From (2) we conclude by 1.54 that either a*p+-b*Z=b*n

(4)

or else there are elements d and e for which (6)

-

a p =d

+e

and b

(e-n)+a .v= e +d.

I n case (4) we obtain by 1.39 a.v+b-n=b.n=a.p+b.n

whence by hypothesis a.v

+b .n= b .Q +a -v,

and the conclusion again follows by 1.53. In case (5) we apply l.l(II1) with a,=a for x < p , a,=O for

90

APPENDIX A

p < x < o , b = d , and c = e . From the first equation of (5) we then

easily conclude that there are two elements f, g and an ordinal

A, I < p , such that a=f+g,

(6)

d = a . I + f , and e=g+a.(p-A-

1).

From (6) and the second equation of ( 5 ) we obtain (7)

{ f + b(@ n)+ a -

-Y= f

+e + d = f +g + a . ( p - I

+

+

- 1 ) a.A f = a + a . ( p- A - 1) + a . I + / = a - p+f.

Hence a.v<*a.p+f.

(8)

On the other hand, by (6) and ( l ) , (9)

a . p + f
+ g=a . p +a = a . ( p+ 1) < a . Y.

By 1.28, formulas (8) and (9) imply u.p+f=a.v.

Hence, by (7),

f + b . (@ - z) + a .Y = a .v;

therefore, by 1.41,

f + 6 . (Q - TC)+ u = u ;

consequently, by 1.39,

[f

and

+ b .(@

-

n)].@

+a = a

[f + b . (Q - 7c)]-Q + a . p = a . p

(10)

We have thus inferred from (2) that either the conclusion holds or else there is an element f satisfying (10). I n an entirely analogous manner we infer from (3) that either the conclusion holds or else there is an element h such that 6 en+ [a. (Y- /A) + h ].Y =b en.

(11)

By

(lo), ( l l ) ,

and the hypothesis we have

+

[f + b . (@- 7C)l-e+a * p b . n+ [a.(Y - p )

+ h ] .Y = b

-@

+a . Y .

ADDITIONAL THEOREMS O N ORDINAL ALGEBRAS

91

Hence, by 1.34, there is an element c for which either

+

+

+

[ f b . (e - z)] .e a ' p c = b

(12)

.e

or else c

(13)

+ b .TC+ [a

*

(V

+ h]* Y=u .V .

- /A)

If (12) holds, we get with the help of 1.45

[f + b . (e - n)].e G b .e and f + b . (e-n) Q b ; on the other hand, by ( l ) ,

b < * b . (e -n) < * f

+ b . (e-n)

and therefore, by 1,28, f + b . (e-n)= b.

(14) (10) and (14) lead to

b.e+a.p=a.p

whence, by 1.39,

+

+

b .n a . p = a .,u= b .e a ' p , b -7t+ a * p+ u * (V -/A) = b .e +a ' p+ a . (V - p ) , b . n + a . v = b -e+ a.v. Consequently, by hypothesis, a */A + b .?t= 0 .n+a ' v ,

and the conclusion follows by 1.53. I n a similar way the conclusion is derived from (13), and the proof is complete. The theorem just proved clearly comprehends 1.53 as a particular case. I n the remarks following 1.53 the problem was raised whether the formula a . ,U +-b .7t= b .e a . Y,

+

where p, v, 7t, and implies

e are any finite ordinals different from 0 , always a+b

=

b +a.

92

APPENDIX A

The problem is still open; however, in view of A.4, it remains unsolved only in the case when either p @ or p>v and n < p . The discussion of this remaining problem seems to present considerable difficulties. A. 3 contains the affirmative solution of the problem in a very simple special case, in fact, in case p=e=2 and v = n = 1 ; the proofs of A.3 and of the auxiliary theorems A . l and A.2 illustrate the methods which may be tried in attacking the general problem. It may be noted that some generalizations of A.3 are known which provide the solution of the problem for the case ,LA=@> 2 and v = n = 1 as well as for the case p = v + 1 and Q = n + 1; the proofs of t,hese generalizations are involved. The next theorem, A.5, is of some interest in itself and leads to an interesting consequence, A.6, concerning recursive elements.

THEOREM A.5. If a.,u=c++,,, (a+b,)+a+d and 0 < p < w , then there ezist ordinals 1 and Y, with A

a-nc=c+C,,(a

a + a - (n- 1 ) = (c +a

+b,) +a+d

+ b,) +

If n = 1, formula ( 1 ) yields

a = c + a + 6, +a +d. Hence, by applying 1.27 twice, we get

a = a + b, + a

(a+ b,+J

+a + d ] .

ADDITIONAL THEOREMS ON ORDINAL ALGEBRAS

93

and we see that the conclusion of the theorem is satisfied if we let 0 , v = 1, and e-a. Thus we can assume that

A=

n ~ l i.e., , O
(2)

By applying 1.34 to (1)) we conclude that there is an element e such that either (3) a + e = c +a or else

+ 6,

and a . (n- 1) = e +

&n-l

(a+ b,+J +a +d

+ bo+ e and e +a. (n- 1)= z
+a + d =a+ [b,+Z',<,~,(~+~,+,)+~+dl. If (3) holds, then, by our inductive premise and in view of ( 2 ) , the second half of (3) leads directly to the conclusion. I n case (4)holds, we apply 1.27 to the Grst half of (4)and obtain (4)

(

a =c+a

a=a + b, + e. Next, by using 1.34, we conclude from the second half of (4) that, for some element f , either (5)

(6)

e =a

or else

+f

and f + a . (n- 1) = bl

+

+

(a b,+,) f a + d

+ +

a = e +f and a . (n- 1) =f b, 2x
+

Thus we see that (6) implies the conclusion. Consider now (7). I n view of (2) we can write the second half of (7) as

a+ a . (n- 2) =f + [b,+

&<*-2

(a+ b x + 2 ) +a+&].

Hence, by applying 1.34 again, we infer that, for some element g, either f = a + g and a . (n- 2) = g + b,+ or else (8) (9)

a = f + g and g + a . (n- 2 ) = bl+

&
(a+b,+,) +a+d

2x
94

APPENDIX A

If (8) holds and x > 2, then, by our inductive premise, the second half of (8) leads to the conclusion; in case x= 2 , (5) obviously implies g = O and therefore yields (9). Hence we can restrict ourselves to the discussion of (9). By ( 7 ) and (9) we have e+f=f+g and, by applying 1.54, we conclude that either

e+f=f=f+g

(10)

or else there exist two elements h, k and a finite ordinal e such that (11)

e = h + k , g = k + h , and f = ( h + k ) . e + h .

In case (10) holds, we see from ( 7 ) that a = / and consequently

a * ( n - 1) = a+6,+~:,,,_,(n+bx+,)+a+d =Zx
by the inductive premise, this again leads to the conclusion. Therefore assume that ( 1 1 ) holds. ( 5 ) , ( 7 ) and (11) yield (12)

[ a =a +b, + e ee. +(ef+ e) ++ eh.+e +6, h+e ,e .(e + 1) +h =

=

=

1

=

whence by 1.41*

e +h= e -t-h+b, + e

(13)

and therefore by 1.39*

e +h= e +h+b,+ e +b,

+ e +b,+e.

Adding k on the right to both sides of the last equation, we obtain with the help of (11) e+e

= (e

+ h+ b,+ e ) + (b,+e + b,+e + k ) .

Hence, by 1.34, it follows that, for some element I , either or else

e = e +h+ b,+ e + I

+ + e +b, + e + k ;

e = I b,

ADDITIONAL TECEOREMS ON ORDINAL ALGEBRAS

95

by applying 1.27 several times, we conclude that either

e = e + h+ b,+ e ,

(14)

+ +e

e = e b,

e=e+k. Formulas (13) and (14) obviously imply (15), so that (15) holds in either case. Moreover, from (12) and (14) we get

+

a= e . (e l ) ,

(17)

while (12) and (16) give a=a+k=e.(e+ whence by (11) (18)

l)+h+k

a = e - (e+ 2).

Thus we have (15) and either (17) or (18). In other words, the conclusion is satisfied if we let 1 = 0 and either v = e + 1 or v = Q + 2. This completes the proof of the weaker theorem.

11. Returning now to the original theorem, we assume that its hypothesis is satisfied. From what we have shown in I it follows then that there are ordinals il and n, with 1 < p and O
(21)

By (19) and the hypothesis we have (22)

e (nqp)= c

+ z i p ( e -n+b,) +6.n +d.

96

APPENDIX A

We define a new sequence of elements b: with i t n - p by putting (23) (24)

b : = e + b , if x < p and i = ( n - l ) . ( x + l ) - l , b : = ~if ~ # ( n - l ) - ( x + l ) - l for every x < p .

In view of (21), it is easily seen that conditions (23) and (24) uniquely determine b: for every ~ < n . p .From (22), (23), and (24) we obtain e . ( n * p )= c + %<(n-l).p (e b:) e .n d

+ + +

and hence, by (21) and (24),

e . ( n . p ) = c+~,,,.,,

(e+bJ+e+ [e.(n-p-l)+d].

From this last formula we see that the hypothesis of our theorem

is satisfied if a, b,, d, and p are respectively replaced by e, b:, e . ( n - p - l ) + d , and n-p. Hence, by the result established in part I of our proof, there are ordinals A’ and v’, with A’
e=e’.v’ and e’=e’+b;,+e‘.

From (23), (24), and (25) it follows that either for some x < p (26)

e‘ = e’ + e‘ v‘ + b, + e‘,

or else (27)

e‘=e‘ + e‘= e‘. 2.

By 1.27 formula (26) implies (27), so that (27) holds in either case. (25) and (27) obviously imply e = e . 2 and hence, by 1.47, e (T = e .t for any two finite ordinals (T and t which are different from 0. Consequently, we can replace n in (19) by any ordinal v with O
ADDITIONAL THEOREMS OW ORDINAL ALQEBRAS

97

ordinals ,u and v with 0 < v <,u<w , there exist elements a, b, with x t p , c , and d such that

a -,u =c +

s

and v is the only ordinal for which there are an element e and an ordinal A<,u satisfying the formulas

a=e.v and e = e + b , + e . We obtain such elements a, b,, c, and d by considering, for instance, the type f of the Q relation between real numbers and by letting a = ( l + f + l ) . v , b o = ( f + 2 ) . ( p - v ) + f , 6,=f for x # O , and c = d = O . THEOREMA.6. If a

E

RC, ~ . ~ = c + ~ , ~ ~ ( a + b , ) + a and +d,

p ~ w then , a=O.

PROOF:In case p = 0 the conclusion is obvious. In cme 0
(1)

and

e = e + b,+ e.

(2)

By hypothesis, a ERG. Therefore, by 1.60 and (1)) e E RC. Hence, by 1.63 and (2), e = O and finally, again by (I), a=O. In case p = w we proceed indirectly, i.e., we assume that a# 0. Then a+d#O, and the hypothesis gives a+d<*a.w.

Consequently, by 1.22(ii), a.w<*a+d

i.e., for some element f ,

a +d=f +a .w.

(3)

The hypothesis yields also c

+ c,,, ( a+ 6,) Q a . w

98

APPENDIX A

whence, by 1.22(i), either

c+%,,(a+b,)

(4)

=a - w

or else, for some finite ordinal p', C + ~ , < , ( a + b , ) G a-p'.

(5)

If (4) holds, we obtain by (3) and the hypothesis a -0=a *0+ f +a .w.

(6)

Now, since a E RC, we also have a . o E RC by 1.61(ii). Hence, by 1.63, (6) implies that a.o=O and that, consequently, a=O. If (5) holds, we have for some element g

a .p'

=c

+ z,

+ +g = c + Gcrr(a+ b,) + C,, (a + b,+pJ) + g,

( a 6,)

i.e., (7)

a-p'

= c+s,,,(a+b,)+a+d'

where

d'

= b,,

+ s<, (a+ b,+pl+l) + 9.

Since ,u' is finite, we are confronted in ( 7 ) with the situation discussed in the earlier part of the proof, and we again obtain a=O. Thus the assumption that a p O leads to a contradiction, and the proof is complete. A.6 is clearly a generalization of 1.63 and presents the affirmative solution of the problem formulated in Chapter 1 in a remark following 1.64. In the ordinal algebra of all reflexive types (cf. 2.9) A.6 holds for arbitrary ordinals ,LA, and not only for p < o .

APPENDIX B A UNIQUE DECOMPOSITION THEOREM FOR RELATIONAL ADDITION BY

BJARNI J6NSSON The principal result of this appendix involves a set A of reflexive relation types and states that, under suitable conditions on A , every reflexive relation type can be uniquely represented a sum of indecomposable relation types, the summation being carried out over a relation whose type belongs to A . (The notion of indecomposability involved in the discussion is of course defined relative to the set A.) Three particular cases of this theorem were previously known. The f i s t of them, for the set of all order types, was jointly obtained around 1944 by Tarski and the author of this appendix and coincides with Theorem 2.12 in the main part of the monograph; the second, for the set of so-called cardinal types, W R S found around 1945 by the author; the third, for the set of what can be called square types, has been recently proved by Chang and Tarski. This lead Tarski to raise the question of formulating and establishing a general unique decomposition theorem which would comprehend the three results as special cases. Our result constitutes a solution of this problem. la) The terminology and symbolism introduced in the main part of the monograph will be employed here. I n addition, by a subrelation of a relation R we understand a relation of the form R n ( B x B ) where B is some set; as is easily seen, S is a subrelation of R if and only if

S = R n [ P ( S )x F ( S ) ] . 16) The result was first stated (without proof) in the abstract [7]; the abstract contains some remarks which have not been included h this appendix.

100

APPENDIX B

By a subtype of a relation type a we mean the type of a subrelation of R where a = t ( R ) . We shall also need a generalization of the notions of an indecomposable relation and of an indecomposable relation type (defined in Chapter 2 ) . A relation R is said to be indemposable under a set K of relations if R # 0 and if the conditions

R = G e g T T iS, E K , T i ) ( T jfor every i, j E F ( S ) with i # j jointly imply that there exists at most one element i E F ( S ) such that T,#O. Similarly, a relation type a is said to be indecomposable under a set A of relation types if LY # 0 and if the conditions a=

zi,spi and

t (8)E

A

jointly imply that there exists at most one element i E F ( S ) such that &#O. The set of all reflexive relation types which are indecomposable under a set A of relation types will be denoted by I ( A ) . I n the following theorems B.1-B.4 (which partly generalize 2.1-2.5) we formulate certain elementary properties of general relational addition.

THEOREM B.l. (i) x R O = X . o R i = O . (ii) If j E F ( R ) , and if'S,=O whenever i E F ( R ) and i#j, then X,RSi=Sj. (iii) Sj _C L s R S ifor every j E F ( R ) . (iv) If Ti C S j for every i E F ( R ) , then X,.Ti C x.BSI. (v) x.RTi)(Xif and only if T i ) ( # for every i E F(R). (vi) I f T = then G,,-,Uj= Uj. (vii) If B is the set of all elements i E F ( R ) such that S,#O and if T = R n ( B x B ) , then x*RSi=zi,TSi. (viii) T * ( .Si) = X , R ( TSJ. . PROOF : obvious.

zsR#%, x,R

zjaT

zi,

THEOREM B.2. If T=x,.Si. and if Si)(Sjwhenever i, ~ E F ( R )

and i # j , then we have: (i) T n [S(SJ x F ( S , ) ] = S i for every i E F ( R ) ; (5) T n [ F ( S , )x F ( S j ) ]= P(S,)x F ( S j )whenever i # j and(i,j) E R ;

(iii) T

n [ F ( S i )x F ( S j ) ] = O whenever i, j

PROOF : obvious.

E

F ( R ) , and (i, j ) $ R .

101

DECOMPOSITION THEOREM FOR RELATIONAL ADDITION

THEOREM B.3. If all the relations S , with i E F(R) are reflexive, is also reflexive. Conversely, if the relation then the relation Z s R S ii s reflexive, and if Si)(Xj whenever i,j E P(R)and izj, then all the relations A, with i E F ( R ) are reflexive. PROOF:The first part of the theorem is obvious, the second part follows from B.2(i).

xsRSi

THEOREM B.4. If C+,RTi=Zk.S U,, all the relations T i with i E F ( R ) and U , with k E F(S) are reflexive, and T , ) ( T , whenever i , j E F ( R ) and i # j , then Ti=Xk,s(Tin U,) for every i E F ( R ) . PROOF:

By B.l(iii) we have

Ti = Ti n 2 k . S

so that (l)

Ti=

ukeF(S)(Tin

uk)

u,

UU<E.Z)eS.k+Z(Tin

>

[F(uk)xF(uZ)l)*

Using B.l(iii), B.2(i), and 2.1(i), we see that, if (k, 1) E S and k # l , then Ti

[(F( uk) x

( uZ)l = =

=

CF

IF

( uk)

x

( ul)l

CFVi)n F ( Uk)l x [ F (Ti)n F ( UJl F ( T i n U , ) x F ( T , n UZ),

and we conclude by (1) that

Ti = s , s (Tin uJ* Next we prove a refinement theorem which will subsequently be used to obtain unique decomposition theorems for the addition of reflexive relations (B.6) and the addition of reflexive relation types (B.9).

THEOREM B.5 [GENERAL REFINEMENT THEOREM FOR RELATIONAL ADDITION]. Let K be a set of reflexive relations with the following properties (a) there exists a n R E K such that R#O; (b) if R E K and S i s isomorphic to a subrelation of R , then S E K ; (c) if X E K for every finite subrelation S of R, then R E K ; (d) if R E K , Si E K for every i E F ( R ) , and S,)(Xj whenever a', j E F ( R ) and i#j, then c.,Si E K.

102

APPENDIX B

Suppose R is a reflexive relation, I is a non-empty set, and Si E K for every i E I . If R = Zkm8iQi,k for every i E I , and if Qi,k)( Qi,l whenever i E I , k, 1 E F ( S J and k # l , then there exist reflexive relations T , Wi,kwith i E I and k E F(S,), and U , with f E F ( T ) which satisfy the following conditions : (i)

T E K , and WiVkE K for all i E I a.nd k E F(S,); (ii) R=C,.,U,, and U,#O for every f E F ( T ) ; (iii) T = for every i E I ; (iv) QiSk= zj,w,,U, for all i E I and k E F(S,); (v) U j ) ( U,, whenever f , g E F ( T ) and f # g ; (vi) WiSk)(Wi,, whenever i E I , k, E E F(S,), and k f l . PROOF:Observe that by B.3 all the relations QiSkwith i E I and k E F(S,) are reflexive. Consider the set C of all functions f on I such that f ( i ) E F(S,) for every i E I, and for each f E C let

z.S6Wd.k

U , = n i e r Qi.m-

(1)

Let the relation V and the set D be defined by the conditions: (2)

( f , g) V if { every i I. E

and only if f , g E C and ( f ( i ) , g ( i ) ) € 8 , for

E

f

(3)

E

D if and only if f E C and U,#O.

Also let

T = V n (Dx D),

(4)

and for each i E I and k by the condition: (5)

(f4g)

E

E

F ( S J let Wi.k be the relation defined

WiaEif and only if ( f , g ) E T and f ( i ) = g ( i ) = k .

By our hypothesis we have = ' k e P ( S 4 l 'k.i&

for every i (6)

E

U(k.I)eSi.k+Z

[F(&6.k)

x F(Qi,t)l

I and, consequently,

= nieI

(ukeP(S')

Qik

U(k.Z)eSr,k+2 [F(&i.k)

F(&i.t)l)

DECOMPOSITION THEOREM FOR RELATIONAL ADDITION

For each i

E

103

I and (k, Z) E S let ~ Yi.k.l

=

x

LP(&i.k)

(Qi.t)1

9

and use B.2(i),(ii) to infer that Y ; , k , k = Qi,k

Y4,k.I =

F (QiSk) X F

for every i E I and k E E”(s,), whenever i €1,0,I> E Si, and k # 1.

(Qi,$)

By (2) and (6) we therefore have

R = U(r.o)sv nitr Yi.tci),m or, equivalently,

R = Ujtc nisIQijci)u U
R=

U t c m U,UU
(Rn[ w J , ) x W g ) 1 ) .

For any ordered couple ( f , g) E V with f # g we can choose an element j E I such that f ( j ) # g ( j ) and use (1) and B.2(ii) to infer that

F ( U , ) x F(U0)c F ( Q m )x FP&7(?7) c R. Together with ( 7 ) this gives

R = U,t,,p

u, u U < f . I ) E Y . f * Q [F(U,) x F(U0)l = Xf.7 u,,

and using (3), (4)) and B.l(vii) we conclude that

R=

2f.T

uf.

Thus (ii) holds; (v) and (vi) readily follow from (1) and (5). Now suppose i E I and k E F(X,). By (ii) and B.4 we have (8)

&i.k = L \ f . T ( Q i . k

uf)-

It follows from (1) that Q k n U,= U , in case /(a)= k , but Qimkn U , = 0 in caae f ( i )# E . By ( 5 ) , ( 8 ) , and B.l(vii) we therefore have and (iv) holds.

Q6.k

=

X,.W*,~ ui,

104

APPENDIX B

Next we prove (iii). Suppose i E I , and consider any functions f, g ED. Then f E F(Wi,,a) and g E F(Wisos) by (4) and (5). If (f, g ) E T, then (f(i), g(i)) E S ( by (2) and (a), and it follows by (6) that ( f , g) E W,,,,,, in case f(i)=g(i), while

(f, 9 ) E F ( W i , f d x F(Wi.u,d in cilse f ( i ) # g ( i ) , so that in either c&8e

( f , g>

(9)

z . S i Wi.k*

Conversely, aasume that (9) holds. If f ( i )=g(i), then (f, g) E Wi,l,6 by (vi) and B.2(i). If f(i)#g(i), then (f(i), g(i)) E S by ~ (9), (vi), and B.2(iii), and it follows by (l), (3) and B.2(ii) that 0

For every

+ F(U,)xII’(Uu)CP(Q,,,,,,)xP(Q,,,,it)

iEI

cR.

we therefore have

F ( U , ) XP(U,) Z R n CP(Qi.t(iJ xp(Qj.o(lJl’ so that

Rn

(QjA(9)) x

F (Qj,U(9Jl

f

0;

but by B.2(iii) this implies that ( f ( j ) , g ( j ) ) €Xi. Using (2) and (4) we conclude that ( f , g) E T, and (iii) holds. Observe that by (b), (d), (iii), and (vi) the two parts of condition (i) are equivalent. I n proving that this condition is satisfied we shall first consider the caae in which I has a finite number n of elements. For n= 1 the conclusion is trivial; for, if I consists of just one element i, then V is isomorphic to Sj by (2), hence T is isomorphic to a subrelation of S , by (a), so that T E K by (b). Suppose m is a positive integer and assume that (i) holds in the case in which n=m. If n=m+ 1, then we consider arbitrary elements j E I and k E F(X,) and let I’ be the set of all elements i E I with i # j . Repeating the construction given at the beginning of the proof with I replaced by 1’,we consider the set C’ of all functions f on I‘ such that f(i) E F(S,) for every i E 1’,let (10)

u;= nw

Qi.,(i)

DECOMFOSITION T H E O RE M FO R RELATIONAL ADDITION

105

for every function f EC’, and define the set D’ and the relations V’ and T‘ by the conditions: (11)

77’ if and only i f f , g ( every (f’g) i It; E

E

C and (f(i), g(i)) E Si for

E

f

(12)

E

D‘ if and only if f EC’ and U;#O; TI= V’ n (D’ x D’).

(13)

By our inductive hypothesis we have T’ E K. For each function f E F ( W i s k we ) let h(f) be the function on I‘ such that h ( f ) ( i ) = f ( i )for every i E I. From (1)-(5) and (10)-(13) we see that h maps the set F ( W i J in a one-to-one way into the set D’= F ( T ’ ) and that, if f , g E P(Wi,k), then the conditions
E

Wj&, < f ( i )g?( i ) ) ESi for every i

EI

f , and < h ( f ) , h ( g ) ) E T ’

are equivalent. Hence h maps Wi,k isomorphically onto a subrelation of T’.Consequently Wick E K by (b). Thus we see that, if (i) holds for n = m , then it also holds for n = m + 1. It follows by induction that (i) holds whenever I is finite. Dropping the assumption that I be finite, we consider a finite subrelation P of T.Then there exists a finite subset I’ of I such that, i f f and g are any distinct members of F ( P ) ,then f ( i ) # g ( i ) for some i E I . Again we let C‘ be the set of all functions f on I’ such that f ( i ) E F(S,) for every i E I f , and define the relations U; with f EC’, the set D’, and the relations V‘ and T‘by the conditions (10)-(13). By the particular case of (i) which has already been proved we then have T’ E K. For each function f E F(P)let h(f) be the function on I‘ such that h(f)(i)=f(i) for every i E I f . From (1)-(4) and (10)-(13) we see that h maps the set F(P)in a one-to-one way into the set F(T’)and that, if ( f , g ) E P ,then ( h ( f ) ,h ( g ) ) E T‘. Conversely, suppose f and g are distinct members of F ( P ) , and assume that (h(f),h(g)) ET’.We can then find an element j E I such that f ( j ) # g ( j ) , and by ( 1 1) and (13) we have ( f ( j ) , g ( j ) ) E S ~It. follows by ( l ) , (3), and B.2(ii) that 0

f

F(U,)xF(U,)CF(&i.tn)XP(&i.Pcn)CR.

106

APPENDIX B

For every i so that

E1

we therefore have

F ( U d x F(UU)c

n [F(Qi.to)x F(Q4.UdIY

Rn [F(Qi.fdXFfQi.B(i.))l

+ 0,

but by B.2(iii) this implies that (f(i),g ( i ) ) €Xi. Using (2) and (4), we infer that ( f , g) E T and hence ( f , g) E P. Thus h maps P isomorphically onto a subrelation of T‘, and we have P E K by (b). Since this holds for every finite subrelation P of T, we conclude by (c) that T E K, and the proof is complete. Several equivalent formulations of the set of premises (a)-(d) in B.5 are known. Thus, for instance, we can respectively replace (b) and (d) by the following conditions:

(b’) if R E K and S is isomorphic to a finite subrelation of R, then S E K; (d’) if R and all the relations Si with i E F ( R ) are finite members 01 K and if S,)( Sj whenever i , j E F ( R ) and i # j , then CeRSi E K. Condition (b’) is clearly weaker than (b), but it is easily seen that the two conditions are equivalent on the basis of (c); the same applies to conditions (d) and (d‘). It is less obvious that condition (c) can be replaced by the following condition which is equivalent to (c) on the basis of (b) or (b’): (c‘)

if i is any subset of K which i s simply ordered by set inclusion, then U R E R L E K. 16)

If in B.5 we take for K the set of all reflexive relations, then

the premises (a)-(d) are clearly satisfied, and we obtain a simplified la)

For the equivalence of (c) and (c’) see Theorem 1.2 and its proof in

[18], pp. 578 f. It may be mentioned that Theorem 1.2 gives a simple metamathematical characterization of those sets K of relations which satisfy

B.5(b),(c). I n fact, such sets K prove t o coincide with the sets of models of arbitrary (possibly infinite) systems of first-order universal sentences, with a two-placed predicate ae, the only non-logical constant. I t would be interesting to obtain a simple metamatliematical characterization for the sets K which satisfy B.5(b), (c),(d).

107

DECOMPOSITION THEOREM FOR RELATIONAL ADDITION

form of the refinement theorem, which, however, is not adequate for our purposes.

THEOREM B.6. If K i s a set of reflexive relations which has the properties (a)-(d) listed in Theorem B.5, then every reflexive relation R can be represented in the form

R

= G.T

u

E F ( T ) are indecomposable U,)( U , whenever f , g E F(T)and f i g . This representatiort is unique in the following sense: if

where T

E

K , all the relations U , with f

under K , and

R = 2i.V

w,

is unother representation with the same properties, then there exists a function h which maps T isomorphically onto V in such a way that U,= W,,, for every f E F ( T ) . PROOF: Roughly speaking, we are going to apply B.5 to all possible representations of R as a sum of pairwise strictly disjoint non-empty relations over a relation belonging to K . More precisely, we choose a set I , relations S , E K with i E I , and relations Qr,k# 0 with i E I and k E F ( S J which satisfy the following three conditions : (1) (2)

(3)

I

Qi,k)(Qtvl

R = L,sd QCmk for every i E I ; whenever i E I , k, I E F(S,), and 1;

zk,S,Q;

f

1;

if R = is any representation of R with S' E K , Q;# 0 for every k E F ( S ) , and QL)(Qi whenever lc, 1 E F ( S ' ) and k#E, then there exist an element j E I and a function h mapping S' isomorphically onto S , in such a way that Q;=Qi,h(k, for every k E F( S') .

That this set 1 is non-empty follows from conditions (a)and (b). In view of (1) and (2) we infer from B.5 that there exist relations T,Ur+,,with i E I and I% E F(S,), and U , with f E F ( T ) which satisfy conditions (i)-(vi) listed there. Since K has the property B.5(b), we see from B.l(vii) that in order to prove that u, is

108

APPENDIX B

indecomposable under K it is sufficient to consider decompositions

uo = 2.v, Q;

(4)

where V , E K, Q;#O for every k E P(V,), and Qd)( Q; whenever k, I E P(V,) and k f I , and to show that under these conditions P(V,) consist5 of just one element. Clearly we may also assume that P(7,) n F ( T )= 0. For every f E F(T)with f # g let 7 , be the relation consisting of just the one ordered couple
U , = &.v,Q; and V , E K for every f~ F ( T ) .

Letting

S' = 2 i . T V,, we therefore infer from B.l(vi) and B.5(ii) that

R=

2,sQ;.

Since K has the property B.5(d), we see that S' E K. Furthermore, in view of B.5(ii),(v), we also have Qi# 0 for every k E P(S'),and Qi)(Q; whenever k, I E F (S') and k # 1. We can therefore apply (3) to obtain an element j E I and a function h mapping S' isomorphically onto S, in such a way that Q;=Qi,h,k,for every k E F(S'). By B.5(iii) there exists 2 E F ( T ) such that g E P ( W j J . Using (a), B.l(iii), and B.5(iv), we therefore see that, for every k E F(V,), Qi. h(k) =

QL C ug C Qi. 1 ;

and, since Q j . M r , # O , we use (2) to conclude that h ( k ) = l . This shows that F(Tr,) must consist of just one element, as was to be proved. Finally suppose we have two representations of R with the required properties :

R = 2t.T

u, = 2 . v w,.

By B.4 we then have

U,= W, =

z,y( U, n W,) for every f

E

F(T),

( U ,n W,) for every g E F ( V ) ,

DECOMPOSITION THEOREM FOR RELATIONAL A D D ITION

109

and it readily follows that there exists a one-to-one function h which maps F(T)onto P(8)in such a way that U,= Who,for every f E P(T). Furthermore, if f and g are distinct members of F(T), hhen it follows by B.2(ii),(iii) that the conditions

( f ,g> E T , P(U,)x F(U,) R, P ( K ( , , )x F(Jc(,,) c R, ( h ( f ) h(gD , E

c

are equivalent, so that h maps T isomorphically onto Y . The proof has thus been completed. Passing now to relation types we f i s t state, in B.7 and B.8, several elementary properties of relational addition of types.

THEOREM B.T. (i) ~ R O = z i , O c r i = O . If j E F(R), and if a,=O whenever i (ii)

xaa(

E

F(R) and i# j , then

= ai.

(iii) If j E F(R), then cri is a subtype of z , R a i . then is a (iv) I f , for every i E F(R)lL Y ~ is a subtype of #Ii, subtype O f z j , R b i ’ ( v ) If T=z:,.,Si, and if Si)(Si whenever i , j E F(R) and i # j , then G.R Z,s$~j = 29.T L*i* (vi) If B i s the set of all elements i E F(R) such that ai#O, and if S = R n ( B x B ) , then (vii)

z,Bmi

x,R~6=x,scri.

I X * ( Z < , R B i )= z i , B

(@. B 6 ) ’

PROOF:Parts (i), (ii), (v), (vi), and (vii) axe easy consequences of B.1, while (iii) and (iv) readily follow- from the definitions of the notions involved.

THEOREM B.8. (i) 0, 1 E RT. E RT if and only if cri E RT for every i E F(R). (ii) If z(R) E RT, then zi,R1=z(R). (iii) (ic) a . O = O . c r = O and rn.l=cr. (v) If cr E RT, then l.cr=a. PROOF:obvious,

x,Rai

We now obtain the main result of this appendix:

THEOREM B.9

[UNIQUE DECOMPOSITION

THEOREM FOR RELA-

110

APPENDIX B

Let A be any set of reflexive types satisfying the TIONAX, ADDITION]. following conditions : (a) 1 E A ; (b) if a E A and p i s a subtype of a , then /3 E A ; E A for every finite subtype ,L? of a , then a E A ; (c) if (d) if t ( R )E A and a{ E A for every i E P ( R ) ,then EA. Under these assumptions every reflexive type a can be represented in the form a = Xi.RBi

x,R~i

where t ( R )E A , and b5 E I ( A ) for every i E F ( R ) . This representation is unique in the following sense: if is another representation of the S a m kind, then there exists a function h which maps R ismorpitically onto S in such a way that pi= yh,{)fm every i E F(R). PROOF: by B.6. Using the terminology introduced in Chapter 3 , p. 82, we can formulate the last part of the preceding theorem more simply: if 01

=2t.R

Pi = 25.8 ~j

are two representations of LS: of the kind discussed, then the systems
DECOMPOSITION THEOREM FOR RELATIONAL ADDITION

111

tion of B.9 to the sets A, and RT does not lead to any interesting consequences since the resulting decompositions of a reflexive type are trivial. We want now to discuss some more interesting applications of B.9 to special sets of relation types. A relation R is called a cardinal relation if, for all x and y, the formula (s, y) E R implies that x=y. Given any set B , let B" be the set of all ordered couples (2,s) with x E B. Clearly every cardinal relation R uniquely determines a set B such that R = Bc; in fact, B= F(R). Conversely, every relation R of the form R = B" is a cardinal relation. The relational sum X , S , over a cardinal relation R = Bc obviously coincides with the union 8,. By a cardinal type we understand of course the type of a cardinal relation. The set of dl cardinal types is denoted by C T . For sums a,of relation types over a cardinal relation R = B" we introduce a special notation by putting

ud,

zg.B

The operation 2' is referred to as cardinal addtition. As a particular case we obtain the binary cardinal addition; in fact, given any two relation types ,!? and y , we put ,!?+"y = E ; € B

OLi

where B is a set consisting of two elements, say 0 and 1, and where a,,=,!? and a l = y . I n the next few theorems, B.10-B.13, we state some elementary properties of the sets CT and I ( C T ) and the operations 1' and -I-". The proofs are obvious and will be omitted.

THEOREM B.lO. (i) 0, 1 E C T . (ii) If ai E CT for every i E B, then z c B u ge C T . (iii) If a , ,!? E C T , then a ,!? E C T . notion of indecomposability a variant of the unique decomposition theorem was stated by FraYssB in [ 5 ] ; however, it applies exclusively to finite relations and, apart from this restriction, its conclusion is not entirely analogous to that of B.6 or B.9.

112

(iv) If (v) If

APPENDIX B bc

E C T and /3 i s a subtype of a, then @ E C T . E C T for every finite subtype p of a, then a E CT.

r.

r.

Theorem B.7 extends automatically to the operation Thus, in particular, the associative law holds for Moreover, in opposition to the general relational addition, cardinal addition satisfies the commutative law : THEOREM B.ll. Let h. be a function which maps a set B onto a set G in a one-to-one way, and let pi and yi be types correlated with elements i E B and j E C in such a way that pi= Y,,(~,for every i E B. Then Z c B

Pi = Z e C P i .

THEOREM B.12. For any given relation types (i) O L + " / ? = @ + ~ ~ ; (p+" y ) = ( a+"I y; (ii) (iii) r x + " O = a ; (iv) if a ~ . ~ / 3 = 0then , a=@=O; (v) a.( p +C y ) = a . p + c a.y .

+"

K,

,8, and y ,

+"

THEOREM B.13. a E I ( C T ) if and only if afO and the formula a = p i c y always implies that /?=0 or y = 0. By specializing the unique decomposition theorem B.9, we obtain

B.14. l8) Every refixive type a can be represented in THEOREM the form a = Z C I ( C T )(B. xs)

where x s E CT for every 5, in the following sense: if

E

I ( C T ) . This representation i s unique

( B . 4)

=Z€I(CT)

i s another representation of the same kind, then z p = I , for every p E I(CT). PROOF:All the types belonging to the set CT are of course I*) Theorem B.14 and B.15 were first published, in a slightly different form, in [17], pp- 249 ff.(and credited there to the author of this appendix).

DECOMPOSITION TBXOREM FOR RELATIONAL ADDITION

113

reflexive. By B.10 this set satisfies the premises of B.9 for A =CT. By applying B.9 we therefore obtain a representation of any given reflexive type a :

(i)

=xca

Y4

where yi E I(CT) for every i E A . For every E I(CT) let B, be the set of all elements a' E A with yi=/?. Using B.7(v),(vii), B.8(iv), and B.ll, we easily obtain from (1) a = Z c I ( C T 1 ( C : e B p yi) = Z i c l ( C T )( Z t e B g 8 ) =zeI(CT)

( B * Z : € B p '1,

and letting xp=t(BOp) we see with the aid of B.8(iii) that is the desired representation of a. The unicity of this representation readily follows from B.9.

Consider now an arbitrary algebraic system ( A , +) formed by a non-empty set A and a binary operation -k under which A is closed. Let E be an arbitrary set, let F be the set of all functions on E to A, and, given any two functions f , g E P,let f 4. g be the function h E F determined by the formula

h(z)= f ( z )+g(z) for every x

E

E.

The system ( F , i) thus obtained is called the cardinal (or direct) power of ( A , +) with the exponent E , in symbols ( A , +)&. Using this notation we formulate the following important consequence of B.14:

THEOREM B.15. The system (RT, +") i s isomorphic to a cardinal power of the system (CT, +"), and in fact (RT, E (CT, c)r m ) .

+")

+

P R O O F : By B.14 every reflexive type sentation of the form

(1)

a = 2;cI(CTl

(B

*

x,)

OL

has a unique repre-

114

APPENDIX B

where xs E CT for every #? E I(CT). This formula clearly establishes a one-to-one correspondence between all types in RT and all functions on I(CT) to CT. Let (2)

=ZrItCm

(B.4

be the representation of another reflexive type a'. Using B.i'(v), B.11, and B.12(v), we obtain from (1) and (2) mSCLy'

= z ; r I ( C T ) [#?+)9+".;)1

where, by B.lO(iii), xs+"xk E CT for every p E I(CT). Hence we conclude that the correspondence (between elements of RT and functions on I(CT) to C T ) given by (1) establishes an isomorphism between (RT, +") and (CT, +c)IccT). This completes the proof.

As is easily seen, the algebraic system (CT, +") involved in B.15 is isomorphic to the system (C, +) where C is the set of all cardinal numbers and + is the ordinary addition of cardinals. Hence (mainly as a consequence of the well-ordering theorem) the algebraic structure of (CT, +") and the arithmetical properties of this system are very simple. The importance of B.15 consists in the fact that, as is well known from abstract algebra, various properties of algebraic systems automatically extend to cardinal powers of these systems, and hence in particular various familiar properties of (CT, +") automatically extend to (RT, +"). Three examples of such properties are explicitly stated in the following THEOREM B.16. Suppose 01, 8, y E RT, and let v be a finite cardinal type digwent from 0. We than have: (i) if a = ~ y + " ( , ! I + ~ y ) , then ol=a+",8=a+"y; (ii) if y i s finite and a+"y=#?+"y, then a=#?; (iii) if a . v = B . v , then a=,!?.

B. 16(iii) apparently expresses a property of ordinal multiplication, and not of cardinal addition. Actually, however, ordinal multiplication by a finite cardinal type can be defined recursively in terms of +' by means of the formulas L y e

0 = 0,

Ly

.(v+"

1)= Ly .Y+" a.

115

DECOMPOSITION TEEOREM FOR RELATIONAL ADDITION

We may mention still some further properties that extend from (CT, +") to ( R T , +"). Given any two types 01 and p, let m g c p mean that n f " y = p for some type y. As is known, the set CT is simply ordered and, in fact, well ordered by the relation <". Consequently, the set CT is lattice-ordered by <', and in this lattice-ordering every non-empty subset of CT has a greatest lower bound, and every subset of CT which is bounded above has a least upper bound. Now it turns out that, although the properties of simple ordering and well-ordering do not extend from the system
A relation R will be called a square relation if it is of the form R = B x B for some set B. The set B is of course uniquely determined by R since B = F(R). For relational sums Ri over a square relation R = B x B we introduce a special notation by putting

x,B

Z r B Ri=

Clearly X r B Ri =

We also put

ud

BRi

2 i . B x B Ri.

Ui.irB.i+j

S i-OT= x

E B

LF

(Ri)

(Rj)l

'

Ri,

where B is a set consisting of two elements, say 0 and 1, and where R,=S and R,=T. The operations 2' and may be called square addition and binary square addition, respectively. It is obvious how the notion of a square relation type and the operations 2 and +* on arbitrary relation types should be defined. The set of all square types is denoted by ST. For this set ST and the operations 2 and +a we can repeat, practically without changes, all the remarks and arguments concerning CT, and +c; the results thus obtained are summarized as follows:

2

THEOREM B.17. 19) The theorems B . l k B . 1 6 (as well a8 the Theorems B.17 and B.18 are recent results which were obtained 19) jointly by Chaw and Tarski and appear here in print for the first time.

116

APPENDIX B

r,

auxiliary theorems B.10-B.13) remain valid if we replace in them CT by ST, 2" by and +" by +' everywhere.

THEOREM B.18. (i)

We have (CT,

+") z (ST,+'),

(RT,

+") z
and hence also

(ii)

PROOF:Each of the two systems (CT, +") and (ST, + 8 ) is easily seen to be isomorphic to the system of all cardinal numbers with the ordinary addition of cardinals; hence (i) follows at once. By €3.15 and B.17 we have (RT, +") g (CT, +c)l(cT) and
for every relation type oc E RT. As is easily seen, / ( a )E I ( X T ) and g ( a ) E I(CT) for every 01 E RT. Also, if 01, fi E RT and 0 1 # f i , then f(oc)#f(b) and g(a)#g(/3) by B.lS(ii) and B.17. Consequently, f maps I(CT) onto a subset of I(ST), and g maps I(ST) onto a subset of I(C'T),both in a one-to-one way, and it follows by the Cantor-Bernstein theorem that there exists a function h which maps I(CT)onto I ( S T )in a one-to-one way; in fact, we can easily give an explicit definition of such a function. This completes the proof.

It may be noted that Theorem B.15 and the analogous result for square addition (implicitly stated in B.17) remain valid if and +' are replaced in them by and respectively; the same applies to Theorem B.18. The statements thus obtained clearly generalize the original theorems and imply the latter as particular cases. These generalizations presuppose, of course, that the notion of a cardinal (direct) power has been extended to

+"

r,

DECOMPOSITION T E E O RE M FOR RELATIONAL A D D ITION

117

algebraic systems ( A , 2) where 2 is an operation which is performable on arbitrary systems of elements of A and yields new elements of A . As a third example of a set of relation types to which B.9 applies we want to mention the set OT of all order types. The relation types indecomposable under OT, i.e., the elements of I(OT), coincide with the indecomposable types as defined in Chapter 2 of this monograph (see the remarks preceding 2.12). The set A =OT clearly satisfies all the premises of B.9; hence, by applying B.9 to this set, we obtain the unique decomposition theorem stated in Chapter 2 as 2.12. However, the binary ordinal addition + discussed in Chapter 2 is not commutative, and the same applies a fortiori to the general ordinal addition, i.e., to the relational addition over a simply ordering relation R. Therefore the unique decomposition theorem for ordinal addition cannot be given the simple form in which the analogous result for cardinal addition was stated in B.14, and it does not yield any consequences as powerful as B.15; in particular, the system (RT,+) is not isomorphic to a cardinal power of (OT,+). (A remote analogue of B.15 is mentioned in Chapter 2, p. 83). Speaking loosely, Theorem 2.12 is very helpful in extending to arbitrary relation types results which have been obtained for order types (compare, e.g., the proof of 2.13), but, as opposed to B.14, it does not seem to provide us with a general and automatic method of extending such results. It should be noted that the cardinal addition +', the square addition +", and the ordinal addition + are the only binary operations which we obtain from general relational addition by restricting ourselves to relations R whose field consists of exactly two elements. In fact, from the definition of relational addition it easily follows that no generality is lost by taking R to be reflexive, and a reflexive relation whose field consists of two elements is clearly either a cardinal relation, a square relation, or a simply ordering relation. (We disregard here the dual ordinal addition + * ; cf. 1.2 or 1.3(5).)Among the three binary operations two, +c and $-', are commutative while the third, +, is not. The

x,R~i

x,R~i

118

APPENDIX B

arithmetics of +’ and (based mainly upon B.15 and the analogous result for square addition) are simple ; the arithmetic of +, which constitutes the main topic of this monograph, is rather involved and difficult. In this connection the following metamathematical result has been obtained by Tarski : Assume that by the elementary theory of an operation we understand the totality of laws which hold for this operation and are formulated within the first-order predicate logic ; then the elementary theories of +’ and +‘ are decidable while the elementary theory of + is undecidable. I n other words, there is a mechanical method which permits us to decide in each particular case whether a given elementary statement holds for the operation +’ or +#; however, no such method exists or will ever be found for the operation + . 20) I n addition to the sets discussed so far, there are many other sets of reflexive relation types which have the properties (a)-(d) listed in B.9. As examples we may mention the three sets consisting, respectively, of the types of all reflexive and transitive relations, all reflexive and symmetric relations, and all reflexive and antisymmetric relations. Obviously, the intersection of two or more sets having the properties in question again has these properties. This leads to two further examples, the set of all types of equivalence relations and the set of all types of partially ordering relations. The question naturally arises how many sets there are which satisfy the hypothesis of €3.9. The answer is given in the following theorem, which is a joint result of Chang and the author of this appendix :

THEOREM B.19. The family C of all subsets A of RT which satisfy conditions (a)-(d) of B.9 has the power of the continuum. For notions involved in the last remarks consult [19]. Instead of 20) “the elementary theory of a n operation” the term “the arithmetic of an operation” is also employed; throughout this monograph, however, the term “arithmetic” is used in a wider and looser sense. In view of R.15 and B.18 the decidability of the theories of and easily reduces t o the results in [lo], 1111, and [12]; the undecidability of the elementary theory of can be derived from a joint result of W. Szmielew and Tarski stated in [19], pp. 86 f., by means of a general method developed in Part I of [19].

+’

+”

+

DECOb4POSITION THEOREM FOR RELATIONAL ADDITION

119

PROOF:Let F be the set of all finite relation types, From B.g(c) it clearly follows that, for any sets A and B in C , the formula A n F = B n F implies A = B. Hence C has the same power as a family of subsets of F . Since the set P is denumerable, the family of all its subsets has the power of the continuum, and therefore C has a t most the power of the continuum. 21) It remains to be shown that C has at least the power of the continuum. To this end, given any finite ordinal v, we denote by (xv the type of the relation consisting of the couple ( v + 2 , 0) and of all the couples <,u,p) w i t h p ~ v f 2and
120

APPENDIX 3

in particular true for A=CT, as can be proved, e.g., by showing that there is a one-to-one correspondence between the decompositions (under a cardinal relation) of an arbitrary relation R and the decompositions of the corresponding reflexive relation R u F(R)".In fact, the equations

are equivalent, and we obtain in this manner all possible decompositions of R. With the aid of this observation it is easy to show that the conclusion of B.6 holds if K is the set of all cardinal relations and R is an arbitrary relation, and this in turn yields the conclusion of B.9 for the case when A =CT and a is an arbitrary relation type. I n consequence B.14 can also be extended to arbitrary types, and B.15 remains valid if we replace in it RT by the set T of all relation types. 22) The situation in regard to the set XT of all square types is somewhat more involved. It is possible to show that every relation type a can be written in the form where all the types pi with i E B are indecomposable under the set ST. However, this decomposition need not be unique. In fact, for any given finite ordinal v, let a, be the type of the relation consisting of all ordered pairs ( x , A) such that x < ii
+"

&2=

a 3 +'&3j

and that both a2 and a3 are indecomposable under ST. Turning now to the set OT, let be the < relation between all ordinals less than the given (finite or transfinite) ordinal v. It is easily seen that 186 = p 2

and that both

+ 182 +182 =p 3 + p3

p2 and P3 are indecomposable under OT. Thus p6 has

Actually Theorems B.14 and B.15 as they were first formulated and 22) proved in [17] (cf. footnote 18, p. 112) were not restricted to reflexive types.

DECOMPOSITION T H E O RE M FOE RELATIONAL ADDITION

121

two essentially different representations as a sum of types which are indecomposable under OT. On the other hand there are types which have no such representation at all; is a type of this kind. These examples show that the situation becomes quite involved when we pass from reflexive to arbitrary relation types. However, the device used in a similar situation in Chapter 2, pp. 8if., works here as well: instead of considering relation types, we consider types of relational systems %= ( B , R) with R C B x B. The notion of a sum XaR (Bi,Si> of relational systems bi= ( B i ,Xi> over a relation R, and the notion of a relational system indecomposable under a set K of relations can be defined in an obvious way, as can the corresponding notions for types of relational systems. With certain obvious modifications in the notation, all the theorems of this appendix are valid for arbitrary relational systems and for the types of such systems; in fact, the aame proofs can be used with only minor changes which require no new ideas. We can also avoid repeating the long proof of B.5 by noticing that there is a one-to-one correspondence between the decompositions of an arbitrary relational system ( B , R) and the decompositions of the corresponding reflexive relation R u B". In fact, the equations

Ru

=

&Ti,

( B , R) =

zi.s( F (Ti), R n Ti)

are equivalent, and we obtain in this manner all possible decompositions of the system ( B , R). With the aid of this observation we easily obtain the generalization of B.6 to arbitrary relational systems, and this in turn yields the required generalization of B.9. To obtain a further extension of Theorem B.9 and of most of our other results, we use a very general conception of relations and relational systems. 23) We need here certain auxiliary notions. Consider any system of sets Bi indexed by a given set I . By the %*) This general conception was suggested by Tarski. The observation that the main results of the appendix can be extended to the general relational system and their types was made independently by Chang and the author of the appendix.

122

APPENDIX B

ndCI

cardinal product of the sets Bi, in symbols B,, we understand, aa usual, the set of all systems (bJicr such that bi E B, for every i E I . In cme all the sets Bi are equal to a given set C, we let

T]cieI Bi = C'. C' is called the cardinal power of the set C with the exponent I (it is simply the set of all functions on I to C ) . We recall that a binary relation is an arbitrary set of ordered couples, i.e., of two-termed sequences or, what amounts to the same, of systems indexed by the set consisting of two elements, 0 and 1. If we agree to identify an ordinal v with the set of all ordinals smaJler than v (as is often done in an axiomatic development of set theory), we can also say that a binary relation is an arbitrary set of systems indexed by the ordinal 2. For this reason binary relations are referred to as relations of rank 2. A binary relation between elements of a set B (i.e., a relation whose field is included in B ) is simply an arbitrary subset of B2.Similarly, a ternary relation, i.e., a relation of rank 3, is any set of systems indexed by the ordinal 3 ; a ternary relation between elements of a set B is any subset of B3. I n general, given any set D,by a relation of rank D we understand an arbitrary set R of systems indexed by D; the set of all the terms of all systems in R is called the field of R and is denoted by P(R).By a relation of rank D between elements of B we understand an arbitrary relation R of rank D for which P(R)C B or, in other words, an arbitrary subset of BD.For any given relation R we denote by R- the set of all systems which belong to R and are not constant (i.e., in which not all terms are identical). Let us now fix a set I and a system of sets ( D J i C I We . shall consider relational systems

formed by an arbitrary set B and a system of relations ( R J d E I such that Ri C B"

DECOMPOSITION TEJ3OREM FOR RELATIONAL ADDITION

123

for every i E I . If we denote by S ( X ) the set of all subsets of the set X , we can say that a relational system 2' 3 is an ordered couple ( B , R) where B is an arbitrary set and The set B may be called the universe of the system 8; I is the index set of 8,and the system of sets Di is the rank system of 8. (In case some of the relations Ri are empty, the relational system does not determine its rank system uniquely.) A relational system ( B , R4)i,I is called reflexive if, for every i E I , Ri contains as elements all the constant systems belonging to BDi. By the 5um Ib,GYb of relational systems =
@b

over a relational system

% = ( B ,Ri>C€I, with b ranging over the elements of 3, we understand a new relational system such that

(3 = ( E ,T i ) i c I ,

E= and, for every element i

E

UbeFCb

I,

It is easily seen that this notion of a relat,ional sum is a natural extension of the corresponding notion for binary relations. The remaining notions involved are extended in an obvious manner, and it turns out that the proofs of B.5and B.6 can be used without any essential changes to establish a refinement theorem and a unique decomposition theorem for arbitrary relational systems. As the final result of our discussion we obtain a unique decomposition theorem for types of arbitrary relational systems, under any set A of types of reflexive systems which satisfies conditions analogous to conditions (a)-(d) of B.9.

BIBLIOGRAPHY N. ABONSZAJN. Characterization of t y p a of order satisfying a, + al = = a, a,. Fundamenta Mathematicae, vol. 39, 1952, pp. 65-96. G. BIREHOFF.Lattice theory. Revised edition, New York 1948. L. H. CHINand A. TARSKI. Distributive and modular laws in the arithnzetic of relation algebras. University of California Publications in Mathematics, New Series, vol. 1, 1951, pp. 341-384. A. C. DAVIS.Cancellation theorems for products of order types. I . Bulletin o f the American Mathematical Society, vol. 58, 1952, p. 63. R. FRAZSSE. O n a decompo&ion of r e k t i o m which generalizes the ~ u m of ordering relatiom. Bulletin of the American Mathematical Society, vol. 59, 1953, p. 389. F. HAXJSDORFF. Grundzuge der Mengenlehre. Leipzig 1914. (Reprinted New York 1949.) B. J ~ N S S O NA. unique decompouition theorem for binary relations. Bulletin of the American Mathematical Society, vol. 61, 1955, p. 44. A. LINDENBAUM and A. TARSKI.Communication sur les recherche de la- thkorie des ensembles. Comptes Rendus des SBances de la Sociht6 des Sciences et des Lettres de Varsovie, Classe 111, vol. 19, 1926, pp. 299-330. R. C. LYNDON.The repreenkction of relational algebras. Annals o f Mathematics, vol. 51, 1950, pp. 707-729. A. MOSTOWSKI.O n direct products of theories. Journal of Symbolic Logic, vol. 17, 1952, pp. 1-31. A. MOSTOWSKI and A. TARSKI.A r i t h m & h Z c h 8 c s and types of well ordered systems. Bulletin of the American Mathematical Society, vol. 55, 1949, pp. 65 and 1192. M. PRESBUROER. Uber die voi%tand&~keit e i n a gewiseen Systems der Arithmetik ganzer Zahlen, in welchem die Addition aL einzige Operation hervortritt. Comptea-rendus du Premier Con@& des Mathematicien des Pays Slaves, Warsaw 1930, pp. 92-101 and 395. A. SCHOENFLIES. Entwickelung der Mengenlehre und ihrer Anmndungen. Part 1, Leipzig and Berlin 1913. W. S I E R P I ~ KSur I . la division des types ordinam. Fundamenta Mathematicae, vol. 35, 1948, pp. 1-12. W. SIERP&SKI.Zurys tewji mmgodci. (An outline of set the-, in Polish). Part 1, third edition, Warsaw 1928.

+

E2l 131

r41 [51

1121

126

BIBLIOQRAPHY

[l6] A. TABSKI.Axiomatic and dgebraic mpe.& of two theorem o n s u m of cardinals. Fundaments Mathematioae, vol. 35, 1948, pp. 79-104. [17] A. TARSKI. Cardinal algebras. With an appendix by B. J ~ N S S Oand N A. TAESKI:Cardinal products of womorphisnz types. New York 1949.

Contributions to the theory of models. I . Indagationes Mathe[18] A. TARSKI. matime, vol. 16, 1954, pp. 572-581.

Undecidable Theories. [19] A. TARSKI,A. MOSTOWSKI,and R. M. ROBINSON. Amstardam 1953. [20] A. N. WHITEHEADand B. RUSSELL.Principia MathemcrtiCa. Second edition. Vol. 1, Cambridge 1925. Vol. 2, Cambridge 1927.

INDEX (i) To avoid repetitions, words and successions of words are often replaced by dashes, each dash replacing one word. (ii) Synonyms of a term and symbols for a term, insofar ee they are actually used in the book, are given in brackets. SpecSc contexts in which a term occurs are indicated in parentheses. (iii) Numbers following the name of an author indicate those pages on which either the author himself is mentioned or a work of his is referred ta. Absorption theorem, 15f; - [(to) absorb] to the left, to the right, 15, 32f. Abstract algebra, - -ic (method, proof, system), 2, 75, 83, 114 Addition of cardinals, 4, 114; - [sum] of elements (in tbn algebra) [a+b, &,,ax], 2f., Sf., 64f., 83, and pmsint, see also: Boolean - ; - [-] ordmals [p++v], 7 and pmsinz; - [ -1 - relations, (relational)systems, types, see: Cardinal -, Ordinal -, Relational -, Square Algebra [ -ic system], 2f., 113 ff., see also: Abstract -, Cardinal -, Directed refinement -, D u d -, Isomorphic -9, Ordinal -, Relation -, Sequence Antisymmetric (relation), 24f., 118 Arithmetic, - of an operation, 118; - - cardinal algebras, 8 ; - - ordinal algebras, 3, 8f.; - - ordinals, 1; - - (relation) types, 1, 59, 74f. ARONSZAJN, N., 80, 125 Associative law, 56, 112; - postulate, 8, see also: General - At most denumerable (type), 73 Axiom of choice, 18, 76, and p s i m Binary cardinal addition [+c], 2, lllff.,117; - operation [operation on couples], 2, 8, 54f., 113, 117; - ordinal addition [+I. 2, 1 1 7 , m d - A , see also : Ordinal addition ; - relation, see : Relation ; - square addition [+'I, 2, 115ff. BERKEOFB, G., 1, 59, 126 Boolean addition [U], multiplication (n], operation, 84 Cancellation law, 28f., 33t, 56f. CANTOE,G., 1, 125 Cantor-Bernstein theorem, 116 Cardinal [- number], 4, 76,114; - addition [ + c , r ] , 2, 4, lllff.; - algebra, Sf., 18, 32, 76; - power (of a set, on algebra) [CI, B ] , 113ff., 122; - [Cartesian] product (of sets) [A x B , r J c e I B , ] 59,122; , - relation, 4, 111, 117; - type, 111, 114, see also: Set of - -s

128

INDEX

Cartesian product, see: Cardinal product m a , C. C., 4f., 43, 48, 50, 85, 99, 115, 118, 121, 125 CHIN, L. H., 83, 125 Closed (aset - under an operation), 8, 54f., 113 Commutative couple (of elements, types) [ - elements, types], 40, 43, 45, 53, 80, 85; - law, 8, 112; - operation, 4, 8, 25, 117 Concatenation [-I, 56 Constant (non-logical -), 106; - system, 122f. Continuum, 118f. Converse of a relation (R], 59, 68, and passim; - - a (relational) system, 81f.; - [inverse] of a type [a*],70, 84, and p a a i m ; - of an element [a*], 2f., 8f., and passim Conversion [operation of forming converses, *], 2f., Sf., and pmsim; see also: Converse Countably complete, 84 Couple [ordered -, ordered pair, two-termed sequence], 7, 59, 122, and pamim ; see also : Commutative DAVIS, A. C., 48, 125 Decidability, decidable (theory), 118 Decomposition (of a relation, a relational system), 120f.; see also: Unique - theorem Dense (relation), 76 Denumerable (relation, type), 69,73, 80 Difference (of ordinals) [p-Y], 7 and pa&m Directed refinement algebra, 40, 55ff.; - - postulate, 8, 10, 18, 81; - theorem, 18, 20 Disjoint (elements, sets), 59, 84; see also: Strictly Distinguished element, see : Zero Domain (of a function), 7, 82 Dual (definition,notion, property, theorem), 12; - algebra [ - of an algebra, %*I, 11, 46; - isomorphism, - - postulate, 8; - - theorem, 11; - (ordinal) addition [+*, 11, 117 Duality principle, 12

x*],

Element [member], 7 and passim; EW also: Commutative -8, Disjoint, Indecomposable -, Isomorphic -8, Operation on -8, Recursive -, Reflexive - , Type of an -, Zero Elementary theory (of an operation), 11 8 Empty (relation, set), see: Zero Equivalence relation, 69, 118 Euclid's theorem, 36 Existential (postulate), 73 Exponent (of a cardinal power), 122

INDEX

129

Family (of sets), 118f. Field (of a relation) [ F ( R ) J59, , 122, and paaim Final portion, 75, 78 Finite directed refinement theorem, 2 0 ; - multiple, 15, 31, 54f.; - ordinal [natural number], 7, 69, and passim; - relation, 69; - sequence, 2, 7, 56, and pasaim; - sum [sum of a - sequence, zx.,pax],2, 54, and passim; - type, 69 First cancellation law for equations, 28; - - - - inequalities, 29 First-order predicate logic, 118; - - - universal sentence, 106 Formalized theory, 56 Formation of multiples [operation of forming multiples], 54, 74; em rtlso: Multiple FRA~SS&, R., 111, 125 Free [ -1y generated] semigroup, 56 Function, 7, 82, 113, 122, and passim; - value, 7 General associative postulate, 10, 26f.; - directed refinement theorem, 18; - refinement theorem for relational addition, 101, 106f. Generalized ordinal algebra, 54f. Greatest lower bound, 115 &F,

w., 5, 10, 18, 27

HAUSDORFF, P., 1, 126

Inclusion [ - relation, L], 7, 83 Indecomposable element, 46, 53f. ; - relation, 77f.. 100, 107f. ; - (relational) system, 121; - type, 4, 77ff., 99, 100, llof., 12M,, see also : Set of reflexive types - under a set A Index set, 123; -ed (system), see: System -ed by a set 1 Induction, m a i m Infinite ordinal, see: Transfinite ordinal; - sequence, 2, 7, and pasaim; - s u m [sum of an - sequence, 2, 31f., and pmeim Initial portion, 75, 78 Intersection (of relations, sets) [Rn S , tlielRi],7, 59, and Papeim Inverse of a type, see : Converse , Involution postulate, 8 Isomorphic algebras [ - algebraic systems, '$33, - mapping of algebra& - representation of algebras, isomorphism of algebras, llf., 84, 113f., 116f. ; - elements, 83f. ; - relations [ R SJ, - mapping of relations, isomorphism of relations, 69, 75, 78, and p s i m ; - (relational) systems, 82, 110 Isomorphism, see: Dual -, Isomorphic; -- type, see: Type

zx.cwa,],

130

INDEX

J~N~O B.,N4,, Bf., 56, 78, 81, 99, 112, 120f., 125f. Juxtaposition, 56f.

-

Lattice, - - ordered (set), - ordering, 115 Law, sea: Associative -, Cancellation -, Commutative Least upper bound, 31, 115 LINDENBAUM, A., 3f., 80f., 125 LYNDON, R. C., 84, 125 Map (to - in a one-to-oneway, isomorphically), 12, 69, 78, 107, 110, 116 Mechanical method, 2, 118 Member, see: Element; -ship relation [E], 7 Metamathematical (characterization,result), 106,118f.;metamathematics, 56 Method, see: Abstract algebraic, Mechanical - ; - of iteration, 18 Model, 106 MOSTOWSKI, A., 118, 125 Multiple (vth - of an element a, a type a) [vea,v.011, 13, 31, 54, 74, and paseim v], Multiplication of elements, see : Boolean - ; - [product] of ordinals 7, and pmsim; [ -1 - relations, types, see: Ordinal -

-

-

Natural number, see: Finite ordinal Non-binary relation, 1, 122f. Non-logical constant, 106 One-to-one (correspondence, way of mapping), 69, 114, 116, 12Of. Operation on couples, see: Binary -; - - elements (in an algebra), see: Addition of elements, Boolean, Converse, Multiple; - - ordinals, 7; - - relations, 59f., see also: Cardinal addition, Converse, Ordinal addition, Ordinal multiplication, Relational addition, Square addition ; - - sets, see: Cardinal power, Cardinal product, Intersection. Union; - - single elements, see: Unary -; - - (relational) systems, 81f., 123; - - types, Iff., 70, 84, see also: Cardinal addition, Converse, Multiple, Ordinal addition, Ordinal multiplication, Relational addition, Square addition. See moreover : Arithmetic of an - ,Closed, Commutative -, Elementary theory Order type, 1, 3, 69, 73, 79f., 117; see also: Ordinal algebra of - -8, Set of - -a Ordered (set), see: Lattice - -, Simply -, Well -; - couple, - pair, see: Couple; - triple, see : Triple Ordering, sea: Lattice - -, Partial -, Simple -, Well - Ordinal, 1, 7, 60, 69, 80, 122, and paasim; - o,7 and p s i m ; - addition [- sum] (ofrelations, relational systems, types) [R+S, L C r R x ;a+b,

z,,

INDEX

131

ax], Z f f . , 59f., 70f., 81ff., 117; - algebra, 3, 781.. 24f., 8%., and ph, see also: Generalized - -; - - of order types [DO],76, 80; _ - - reflexive types [%a],71ff., 79f., 98; - multiplication [ product] (of relations, types) [ R - S ,a - p ] , 74,114; - subalgebra, 48, 73

Partial ordering, -1y - (relation), 3, 24, 59, 73, 118; - sum, 31f. Portion (final -, initial -), 75, 78 Postulate, - system, 3,8f., 54f., 71,73,81; - of elementary sums, 8; see also: Directed refinement -, General associative -, Remainder Power (of a set, a type), 56, 73, 119; - of the continuum, 118f.; see also: Cardinal PRESBWOER. M., 118, 125 Predicate (two-placed -), 106; - logic, 118 Product of ordinals, see: Multiplication; - - relations, types, see: Ordinal -. , - - sets, see: Cardinal Proper relation algebra, 83f. Rank (of a relation), 122; - system, 123 Recursive definition, -1y defined (notion, operation, sequence), passim ; - element, 45, 76f., 79f., 92, see also: Set of - -s; - - in the narrower sense, 53, see also: Set of - -s - - - Kefhement postulate, 8, see also: Directed - -; - theorem, 101, 106f., see also: Directed - Reflexive element, 83f.; - relation, 3, 59, 69, 81, and passim; - (relational) system, 123; - type, 3f., 69, 78, 81 99, 110, 118ff., see also: Ordinal algebra of - -s, Set of - -s Relation [binary -1, 1, 4, 59f., 75, 83, 122f., and pmsim; see also: Antisymmetric, Cardinal -, Equivalence -, Indecomposable -, Isomorphic -9, Operation on -s, Partially ordering, Reflexive -, Scattered, Simply ordering, Square -, Strictly disjoint, Symmetric, Transitive, Well ordering; - <, - <*,14, 24f., 54f., 74f., and paaim Itelation algebra, 83f.; - number, see: Type; - of an arbitrary rank, 122f.; - -theoretical (notion, operation), 59, 76, 80; - type, me: Type Relational addition [ - sum; addition, s u m over a relation S] (of relations, relational systems, types) [&,.s R,,x,sa,], If., 4,60,70, 109f., 121, 123, and p o X 8 k , see also : General refinement theorem, Unique decomposition j > , (B, Ri>iE1],Slf., 121ff. theorem; - system [system; ( B , R ) , (8, Relatively prime (finite ordinals), 36ff. Remainder postulate, 8, 10, 14f., 18, 81, 84 ROBINSON, R. M.,118, 126 RUSSELL,B., 1 , 59, 126 Scattered (relation, type), 76, 79f.

132

INDEX

SCHOENFLIES, A., 1, 126 Second cancellation law for equations, 34; - - - - inequalities, 33 Semigroup, 66f. Sequence, 27, 56f., and passim,see also : Operation on -8, Term of a - ; algebra, 56f. Set, passim, see also: Operation on -8; - of cardinal types [CT], lllff.,; - - order types [OT], 69, 73, 76, 117; - - recursive elements [RC], 45ff., 76f., 79f., 97; - - - - in the narrowed sense [RC'], 53, 80; - - reflexive types [RT], 69, 71, 73, 109,118; - - - - indecomposable under a set A [ I ( A ) ] 100, , 110, 112ff., 116f. Set theory, 1, 7, 69; - - theoretical foundations, 69; - - - operation, 59 SIERPI~SKI, W., 1, 4, 32, 125 Simple infinite sequence, 2, 7, and passim; - ordering, simply ordered (set), simply ordering (relation), 3f., 59, 75, 78f., 106, 115, 117 Square addition 21. 2,4,115ff.; - relation 4, 115, 117; - type, 115, 120, see also: Set of - -s Strictly disjoint (elements, relations, relational systems) [R)(S], 59, 70, 81ff., and pa-ssim; - increasing (sequence), 10, 18 Subalgebra (ordinal -), 48, 73 Subrelation, 99f. Subset, passim Subtype, 100, 109f., 122 Sum of elements, ordinals, relations, (relational) systems, types, see: Addition, Ordinal addition, Relational addition ;see also : Finite -, Infhite Symmetric (relation), 118 System, see : Algabrsic - , Postulate -, Rank -, Relational - ; - indexed 1, 7, and pdssim by a set I SZMIELEW, W., 118

TARSKI, A., 2ff., Sf., 18, 32, 69, 75, 78, 81, 83. 99, 106, 112, 115, 118, 12%

125f. Term of a sequence, p-termed sequence, 7 and passim; see also : Couple, Triple Ternary relation, 122 Theorem, pa-ssim; see also: Absorption -, Cantor-Bernstein -, Directed refinement -, Dual, Dual isomorphism -, Refinement --, Unique decomposition -, Well-ordering Theory of ordinal addition, 2, 4; - - relations, 1,59, see also: Decidability, Elementary -, Formalized -, Set Three-termed sequence, see : Triple Transfinite induction, 77; - [infinite] ordinal, 7, 69, 120 Transitive (relation), 24, 118 Triple [ordered -, three-termed sequence], 7 Two-placed predicate, 106

INDEX

133

Two-sided absorption theorem, 16 Two-termed sequence, see: Couple Type [relation -, relation number], - [isomorphism -, relation -1 of a relation [T (R)], Iff., 59,69f., 74f.. 81, and paaim, see abo: Cardinal -, Denumerable, Indecomposable -, Order -, Reflexive -, Scattered, Square - ; - [isomorphism -, relation -1 of a (relational) system, 82, 121, 123; - of an element [t(a)], 84. See moreover: Operation on -8, Zero Unary operation [operation on single elements], 2, 8f., 54 Undecidability, undecidable (theory), 118 Union (ofrelations, sets) [R u S, Uicr RJ,7, 59, and p & m Unique decomposition theorem for relational addition, 4, 101, 109ff., 117, 123; - representation, - -1y represented (relation, type), 4, 78, 107, 110,112

Universal sentence, 106 Universe (of a relational system), 123 Variable, 7, 60, and p a a i m Well ordered (set), - -ordering, theorem, 114 WHITEHEAD,A. N., 1, 59, 126

-

(relation), 1, 59, 69, 80, 115; -

--

Zero [O] [ - element, distinguished element (in an algebra)], 2, Sf., 54f.. 84, and passim; - [O] [empty (relation. set)], 9 and p&m; - [O] [ordinal -1, 9 and p & n ; -- [O] [type -1, 9, 69, 82, 84, and pa&m