Combinatorial Set Theory: Partition Relations for Cardinals : Studies in Logic and the Foundations of Mathematics Series: 106

u

asY \

PROOF. I R ( f ) l < K implies I TI 2 K by virtue of the preceding lemma. Hence the result is a simple restatement of Theorems 13.1 and 13.2. Note that each path of limit length has at most one successor in case of a partition tree (E, S, R, T ) .

86

TREES AND POSITIVE ORDINARY PARTITION RELATIONS CH.

Iv

Hence, in cases a ) and b), the inequalities for 11s ( p ) l required in Theorem 13.1 follow from the analogous inequalities for lims ($)I here. There is a possibility of generalizing the concept of partition trees to cases when S (,f) assumes values in any partially ordered set instead of the power set of a given set E . A case in point is e.g. the following simple result observed by K. Kunen: given a cardinal K, any (K', 3)-distributive complete Boolean algebra B that satisfies the K-chain condition is atomic. To prove this result, one has t o use partition trees where S ( f ) E B. (For the definitions of the concepts here, see e.g. Sikorski [1960]; (K', 3)-distributivity here is t o be understood in the sense of ( < K', < 3)-distributivity, and not of I( K', I 3)-distributivity.)

15. END-HOMOGENEOUS SETS Let a be an ordinal and T a cardinal, and let ,fi [a] <"-+T be a coloring. Call a set X c a end-homogeneous with respect to ,f iffor every finite set u c X and for every p, v E X with max u < p, Y. we have f ( U U

(p))=.f(uu

{\I]).

(11

I f f is only a partial coloring of [u] < w i.e., iff is a function from a subset of [a] < w , then call X E end-homogeneous ~ with respect t o .f if ( 1 ) holds whenever u E [XI <", max u < p , v , and u u { p i , u u E dom ( , f ) . The partition relation a+

(8)r

(2)

means the following: for every coloring ,$ [a]""+r there is an endhomogeneous set of order type p. End-homogeneous sets are very important in establishing positive partition relations; in fact, they were already used in both proofs of Ramsey's theorem in Section 10. The following simple lemma throws some light upon the situation. LEMMA 15.1. Let r 2 1 be un integer, 7 u cardinul, ond let a, b, 1,: (( < T )be ordinuls. Assume p+(\a:);:;. (3 1 Then (r -+(p), implies

and a+ ( p 4 1), implies

(r-+(\j:):.
u+(\,:+

1

I,;.<,.

(4) (5)

An instance of relation (4) was used above in the proof of Ramsey's theorem, and relation (5) will be uskd below in the proof of the Stepping-up Lemma (Lemma 16.1).

87

END-HOMOGENEOUS SETS

PROOF. Let ,/’:[ c r ] * - t ~ be a coloring. First we verify (5). Assume to this end that cr+(fiit), holds; then there is a set X of order type p i 1 that is end-homogeneous with respect to .f: Let i be the maximal element of X, write X ’ = X \ !(),and define the coloring g: [X’]*-’+T as follows: put g ( u ) = = , f ( u u (0 )for every u E [X’]‘- ’. By ( 1 ), there is a < T and a set Y E X’of order type 11,. such that Y is homogeneous of color 5 with respect tog. i.e., g”[ Y ] ‘ - ’ = = (0.But then we have

<

, f ( i ? ) = , f ( ( r \ (max

vI)u(0)

for any I’ E [ Y u (<;]‘by the end-homogeneity of X, and the right-hand side here equalsg(z-\ (max I . ) ) = by < the definition ofg. Hence Y u (i) is a homogeneous set of order type v , . i 1 and of color with respect to ,I; which proves (5). In the proof of (4), assume first that fl is a limit ordinal. The relation ~ c - - + ( f i ) ~ implies the existence of an end-homogeneous set X 5 CI of order type with respect t o the coloring ,J [cr]‘-*r. Given an arbitrary u E [XI‘-’, put g ( u ) = = , f ’ ( u u ( v i ) for a V E Xwith v>max ( u ) ; there is such a 11, since t p X = p was assumed t o be a limit ordinal, and g ( u )does not depend on the choice of vin view ofthe end-homogeneity of X. By (3). there is a 5 < T and a set Y G X of order type Y: that is homogeneous of color 5 with respect t o the coloring g : [XIr-’+?: clearly, Y is then also homogeneous ofcolor with respect to .I:This establishes (4) in case p is a limit ordinal. If B=p i1 for some /?’,then we have t o work with the last element of X as we did in the proof of (5). It is, however, simpler t o observe that (3) implies

<

<

1,r;f

P’+(v,

in this case (indeed, by taking away the last element of p, we can take away only the last element of a homogeneous set), and so we have cr+

( ( I #
1) i 1 );

<

~

in view of ( 5 ) with p’ replacing p. The proof is complete. The following lemma, due t o ErdBs and Rado, confirms the existence of large end-homogeneous sets. It will usually be applied together with the preceding lemma t o prove the existence of large homogeneous sets. I t is, however, also important in itself: in Section 45 we shall give some applications of it concerning set mappings in cases where the corresponding partition relations would lead to weaker results. LEMMA 15.2. For any cardinals

K 2w

and i L 2 Mie hare

(E.F)+--t(K/

l)i.

(6)

88

TREES AND POSITIVE ORDINARY PARTITION RELATIONS CH.

Iv

PROOF. Writing E = (AF)+, let f : [ E l <"--+A be a coloring. We are going to define a partition tree ( E , S, R, T ) , called the canonical parfitionfreeassociated with the coloring .f: To this end, write dom(S)=

u

(7 1

'p,

US9

where p and 9 will be specified later. As we mentioned in the preceding section, we can define S by the recursion formula

k)),

S(g)=G(g,

where G has to be specified only in case dom (g) is a successor ordinal and S(g * 5 ) # 0 for any 5 <dom (g) (cf. (14.1) and the remarks made afterwards). Write dom (g)=a $ 1, and assume that S I ( a 4 1) has already been defined, i.e., that S ( h ) S E has already been defined for any h with h E dom ( S ) and dom ( h )a.~ For any such h, define s(h) as the least element in S ( h ) provided this latter is not empty (note that E is a cardinal, and so S ( h ) c E consists of ordinals); i.e., if S ( h ) # O then put s(h)= min S ( h ) . (8 ) In order to define S(g), write g'=g ^ a and put Eg' = ( S O and, for each

5 E S(g')\

(9)

/?
PP):

{~(g')',, define the coloring

,fg,.t: [E,.]<"-A

&.& 1=f (u u { t 1) for any u E [E,.]

<"'.

For any two

by putting (10)

5, q E S(g')\ {~(g')),put

E ~is .obviously an equivalence relation. The number of equivalence classes under is I the number of possibilities for the coloring &.,r, i.e., is at most =g6

where we recall that a = d o m (g'). Let S,.,,, v < p , be an enumeration of the Here . p (cf. (7)) has to be large enough so that we equivalence classes under E ~ . may enumerate all the equivalence classes (as these classes are pairwise disjoint, p = E = I El clearly suffices); if I p Jis larger than the number of these equivalence classes, then put S,,,=O as many times as necessary. Write

S(d =&@ ,)

f

and, for further reference, if S(g)#O, then write fg

=f,,.<

9

END-HOMOGENEOUS SETS

89

where 5 E S k ) ; clearly, f, does not depend on the particular choice of 5 here. By (lo), we have fe(u)=f(uu

{tl)

(14)

for any finite set u s {s(g * P ) : j < d o m (g)) and any ~ E S C ~This ) . finishes the definition of S. Choose 3 so large that S ( g ) = O for any g ~ ' p clearly, ; 9= E + suffices since, for any g with S ( g ) # O , the set {s(g p a ) : a s d o m (g))

consists of pairwise distinct elements of the cardinal E. Putting, as usual, T = { h Edom (S): S(h)#O). , we clearly have R ( h ) = { s ( h ) )for any h E 7; i.e., we have IR(h)l= 1

(15)

for any h E 7: Taking h =g' in (12), we can conclude that lims ( h ) l s AI[lhl+'l''"l

(16)

holds for any h E 7;where ims (h) denotes the set of immediate successors of h in T; in fact, exactly one immediate successor of h in T corresponds to each (nonempty) equivalence class under -,,. Noting that 1 El = E = (,IF)+, we can conclude from Theorem 14.3.b with (A!)', K, and 1replacing K , I, and a, respectively, that T has a path of length K + 1, i.e., that there is a g E T with dom (g)= K. Write 5,=s(g . first that for each M ~ KObserve (8), we obtain that

pa)

t,
5, = min S(g + a )< tP provided a <

K,

since 5pE

Sk * P I G S k " a ) \ {t,)

holds by our construction above. Hence the set X = { 5,: 1Ia s K ) . has order type K / 1. We claim that X is an end-homogeneous set with respect to f. In fact, if u E [XI and max u = 5, < t p tY , (or a= 0 and t P , E X in case u is empty), then we have a 4 1s P, 7, and so to,tYE S(g (a 41)). Hence (14) implies that

ry

f ( u u { 5 P ~ ) = f , ~ ( , ~ l , ( u ) = f (it),;) uu holds; this shows that X is indeed end-homogeneous. The proof is complete.

90

TREES AND POSITIVE ORDINARY PARTITION RELATIONS CH.

COROLLARY 15.3. Let

K

and z be cardinals with z < K and

Iv

K > (11.

Then

iI),

(2")++ ( K + and

I),

(2")++
hold.

PROOF. For (17), replace E. and K with 2" and K + , and, for (18), with z and K , respectively. (18) will be used for the proof of the Stepping-up Lemmas in the next section; (19) will be used in connection with set mappings (see Section 45), and not in order to establish a partition relation. 16. THE STEPPING-UP LEMMA

The following lemma, one of our most important tools in establishing positive ordinary partition relations, is an easy consequence of the results of the preceding section:

LEMMA16.1 (Stepping-up Lemma). Let integer, and v: ( 5
~

and W

5

be cardinals, r 1 2 an

(V:);f

ti+

holds, then we haue

K

(2"++(vci l)?<,

PROOF. We may assume that v: 2 r holds for all t < z (cf. Subsection 9.5). In this case, noting that K is infinite and r r 2 , (1) implies that T < K ; hence, we have (2"+

+(ti

i1 ),

according to (15.18) in Corollary 15.3. Hence (2) follows from (15.5) in Lemma 15.1 with (2!))+ and K replacing 01 and 8, respectively. The proof is complete. This result alone has nontrivial corollaries. As an illustration, observe that the relation

(Po)+

+

(K,I;,

which is a theorem of Erdos and Rado, follows from the trivial relation Nl+(N,)A. This is, however, not the appropriate place to go into discussing the corollaries of the above lemma, since as we shall soon see, stronger results can be obtained in the case r = 2 by more refined methods. This will be done in the next section.

91

THE S T E P P I N G U P L E M M A

The aim of the rest of this section is t o derive a result saying that certain partition relations hold simultaneously; this result will have an importan1 application in the proof of the General Canonization Lemma, given in Section 28. We start with the following

DEFINITION 16.2. Let CI and p be ordinals, N a set of integers 2 1, and cardinals. Then the partition symbol

'si

~ (Ei N

11

called the simultaneous ordinury purtition symbol and read as " a arrows simultaneously for i E N with.ri colors", is said to hold if we have the following: Given a n arbitrary coloring ,h: [ c x ] ~ + T ; for each i E N , there is a set X c CI of order type p that is homogeneous with respect to each ,fi, i E N , i.e., for any i E N there is a { < r , with .f';'[Xli= it;.T h e negation of the above symbol will, as usual, be written as ay(p):;" . We mention a few natural variations of the above symbol. Where k and 1 are integers, the relatidn

CIy (/jf,< means the same thing as

as2(pi; I j

I

<1

~ S I < I ~

The meaning of the symbol

$3( pf,,, . ..k" ., IA".

will be defined as

Note also that

.SI:m(fi):'

,

--.I!..

Ik". . . .k"

I;

ol"z(p):F"' means the same thing as a-(fi )Zw (cf. Subsection 8.6).

Using the ideas ofthe proof of Lemma 15.1, it is easy to establish the following:

16.3. Let r( 2 1) be an integer, LEMMA cardinals. Assume that

-(Pi holds with ~ = m a x{ ' s i : 2 < i < r ) . Then

CI,

b, and

I>,

v ordinals, and zi ( 2 5 ; i S r )

(3)

92

TREES AND POSITIVE ORDINARY PARTITION RELATIONS CH.

implies

Iv

aszlf+m(v+ 1 f,si
PROOF. For each i with 2 < i < r , let ,h:[ali+7, be a coloring. Put , f =

u ,f;;

Z i t r

then ,f maps a subset of [a] into 7 = maxZsicr7i.By (3), there is a set X E a of order type 4 1 that is end-homogeneous with respect to f: Write X = X'u{C}, where 5 is the maximal element of X. For each integer i with 2 < i 1 r define the coloringg,: [X']'-'+rbyputtingg,(u)=fi(uu (5))foranyu E [X']'-'.Then, by (4), thereis a set Y E X of order type v that is homogeneous with respect to each g i , 2 5 i s r . We can now conclude in exactly the same way as we did in the proof of (15.5) in Lemma 15.1that Y u { [). is a homogeneous set of order type v i1 with respect to each coloring ,h, 2 <_ i 5 r. The proof is complete. We can now prove the following:

LEMMA 16.4 (Simultaneous Stepping-up Lemma). Let r bean integer, t i ~ and w T, 2 1 (2 5 i 5 r ) cardinals, and v an ordinal. Assume that

holds. Then we have (2"+sz(,&

1);,-*

PROOF. We may assume r 2 2 and v 2 r here (in fact, if e.g. 2 1 v < r, then we can replacer with r ' = v in ( 7 ) ) . Then (6) implies that T ~ < Kfor each 7 with 2 1 i 1 r ; hence we have ( 2 " ) + + ( K / l), with ~ = m a x ~ ~according , ~ , . t ~ to (15.18). Using now the preceding lemma with a= (25))+ and p= K, we can therefore see that (6) indeed implies (7). The proof is complete. Define the operation exp by induction as follows: expo ( K ) = K

and

exp,,, (K)=exp,, ( 2 " ) ,

where K is a cardinal and n'runs over integers. The result we are aiming at (the one we shall need in the proof of the General Canonization Lemma in Section 2 7 ) is the following:

COROLLARY 16.5. Let r 2 1 be an integer and

K

~

aOcardinal. Then we have

MAIN RESULTS I N CASE r = 2 AND K IS REGULAR; COROLLARIES FOR

r23

93

PROOF. For r = 1 the assertion says K + - - + ( K + ) ~ ,which is obviously true. If (8) holds with some r.2 1, then the preceding lemma implies that

In order to complete the induction step we also have to cover the case i = 1, i.e., we have to prove (exp, (K))+ Y

+

IsrJr+l

.

( K )e x p , + , - , ( h ) 9

(10)

that is, we have to show that if we are given colorings

6 : C(expr(~))+l'+expr+ I

- i ( ~ )3

where 1 sisr + 1, then there is a set of cardinality K + that is homogeneous with respect to each f,. Obviously, there is a homogeneous set X of cardinality (expr(K))' with respect to the coloring f l . Then, using (9), we obtain that there is a set Y C X of cardinality K + that is homogeneous with respect to each f l , 2 5 i < r + 1. Then Y is homogeneous also with respect to f,. This verities (10). The proof is complete. 17. THE MAIN RESULTS IN CASE r = 2 AND K IS REGULAR; AND SOME COROLLARIES FOR r 2 3

The primary aim of this section is to study the partition relation K+ (v<);
in case K is regular. We shall again use tree arguments to establish our results. As we shall see later, more sophisticated arguments involving the canonical partition tree alone, which was defined in the proof of Lemma 15.2, would be sufficient. Our aim in defining also a different kind of tree is to give a wider illustration of tree arguments. The main theorem we are going to prove is as follows (we recall that L l ( ~is) the logarithm operation defined in Section 7):

(r

THEOREM 17.1. Let K, A,p and T be cardinals, and v: < T ) ordinals. Suppose that is regular, K 2 a,3 I I IK , 2 Ip IL I ( ~ )p,< K and, moreover, v , 2 2 jor any t t r . If P+(V<);
K

(the assumptions here allow the case T = 0 for the sake of convenience).

94

TREES AND POSITIVE ORDINARY PARTITION RELATIONS CH.

Iv

PROOF. We may assume that 12Ko,p+. In fact, if the above assumptions are satisfied with some I , then they are also satisfiedwithY=i-p+.No. Assumewearegivenacoloringf: [ti]’+l i s . We have to prove t hat there is either a homogeneous set ofcolor 0 that has order tyw (or cardinality) I or a homogeneous set of color 1 i5 for some 5 < 7 that has order type V~ i1. We distinguish two cases: a ) I < K and b) A= K. Ad ma). We use the canonical partition tree defined in the’preceding section, but we impose additional stipulations in its definition. Namely, in the preceding section, we took an arbitrary enumeration S,.,, of the equivalence classes under E~.. Here we have a better choice. We shall have dom(S)=

u

“(lit),

USK+

and we are going to define the partition tree (K, S,R,7) by transfinite recursion. Assume that S l ( a i 1 ) has already been defined for some a
and, moreover, for any and

5 < 1 4 T, set

S,..,={XES(g‘)\

{s(g’)):f({s(g‘),x))=t)7 Sk)=Sg:g(a)

(4 ) (51

*

This completes the definition of the partition tree (K, S, R, T ) . For any h E T we have s ( h ) = min ( S ( h ) ) (61 and R ( h )= { ~ ( h ) )i.e., , 171

iR(h)l=l.

Observe that for any h~ T , the sequence (s(hPa):ccsdom ( h ) ) is a strictly increasing sequence of ordinals less than K ; this easily follows from (6). Fix now h E 17; and note that for any cr
f ( M h P a ) , s(h P S ) ) ) = h ( a ) ; in fact, this follows from (4) and ( 5 ) with g = h holds. Put

s(h ~

P

( a 4 l)j since

f lE)S(h ~ f lS(h) P~(a + I))= S ( g ) N h= {tE dom ( h ) :h(<)> 0) .

(8)

MAIN RESULTS I N CASE r = 2 AND K IS REGULAR; COROLLARIES FOR

r2 3

95

We may assume here that IN,l
In fact, the contrary easily implies that (2), which we want to prove. To see this, assume that (9) fails, and define the coloring E: [ N h ] ' - + z as follows: for any ct E N h write &(or) = 5

if and only if h(or) = 1 45 .

Then (1) entails that there is an ordinal 5 < t and a set X E N, of order type v: such that X is a homogeneous set of color 5 with respect to the coloring h'. The set Y={s(h " a ) : a ~ X u { d o m ( h ) ) f

has order type v: -k 1, since, as we pointed out above, after formula (7), the sequence ( s ( h PLY):LY <dom ( h ) ) is strictly increasing. (8) implies that Y is a homogeneous set of color 1-k 5 with respect to the coloring f, showing that (2) indeed holds. Hence we have to deal only with the case when the assumption in (9) holds. In this case we can use Theorem 14.3.c with t + l ( = l i ' ~ )replacing 'L. The assumptions there hold in view of (3), (7), and (9); note also that we assumed 1 < K in the case we are discussing now; &e < K follows from p IL I ( ~and ) 1 < K, and 'L + 1

X=I\N,=

{< < I : h ( t ) = O f .

X has order type I in view of (3) and (9), and

Y = {s(g

5): 5 E xu { 1;)

is a homogeneous set of color 0 with respect to f according to (8). As Y has order type d 41, his completes the proof in casea), i.e., when R
1, (

V C1 ~

)~~~)'

(10)

in case I < K. Ad b). We have I = K in this case. We proceed similarly as in the proof of Theorem 11.3. Assume that there is no homogeneous set of cardinality K and of color 0 with respect to the coloring f : [K]'-~$'L. For every set X C K let H ( X ) be a maximal homogeneous subset of color 0 of X; the maximality of H ( X ) means that vx E X\H(X)3Y E WX)Cf({XYZ)#OI 9

(11)

96

TREES AND POSITIVE ORDINARY PARTITION RELATIONS CH.

Iv

and the assumption made just before implies

I HW)I< K .

(12)

We are going to define a partition tree (K, S, R, T). To this end, given S ( ( a + 1 ) f o r s o m e a < 9 = ~ + , whavetodefineS(g)foranygE(“+’)pprovided e S(gpa)#O (p will be specified later). Assume we are given such a g . Write g’=g pa, and put fib?’) = H(Sk’)) 9

and, noting that

R(g’)is a set of ordinals, write R(g’)=S(g‘)n (sup fi(g’)/ 1 ) ;

(13)

the point in choosing R(g’)in this way is that all elements of S(g’)\ R(g’) will then exceed any element of fi(g‘).Note that

I R(g‘)l< K

(14)

+

holds by the regularity of K in view of (12). For any x E fi(g’)and any color 1 5 with t < r , put \ R(g’):f ( { x y ) . ) =1 i5). . (15) sg,,K.x+s ={Y E To unravel the meaning of this definition, one should notice that x is an ordinal, and, as 5 < T < K (T < p [ < K] follows from (l)), the second subscript K . x 4 5 unambiguously identifies the ordinals x and 5 (the multiplication here means ordinal multiplication). If 9 is an ordinal which cannot be represented in form K . x i t for any x E fi(g‘) and t < T, then put S,.,,= 0. Writing p = K * K (ordinal multiplication again), it is clear that S,,,=O for any q 1 p . ( 1 1 ) implies that

which means that the definitions, given in (13)and (16),respectively, of R(g’) and S(g), are compatible (cf. (14.3)).Noting that W(g’)= H(S(g‘))has cardinality less than K in view of (12),we can see that there are fewer than K ordinals of the form K . x i 5 with x E A(g’)and 5 < T ; that is, there are fewer than K nonempty ones among the sets SB.,,, i.e., I ims (g’)!
MAIN RESULTS IN CASE

r = 2 AND K

I S REGULAR; COROLLARIES FOR

the dot. If S ( g ) # O , then define s ( ~ ) EB ( g " a ) and equation d a ) = K . 4 g ) i 3k)

,f(g)<7

r2 3

91

with the aid of the (18)

9

where the multiplication here again means ordinal multiplication. Note that we have dom ( g ) = a i 1 here; the functions s and fwill be defined only for those h E T for which dom (h) is a successor ordinal. The definitions of the partition tree ( K , S, R, T) and of the auxiliary functions s and f a r e complete. Apply Theorem 14.3.a with 1 4p = p + 1 replacing 1.The assumptions of this theorem are satisfied in view of (14) and (17), and in view of the fact that we have K @ < K for any K~ < K and p o < p 1; this latter assertion means the same thing as p 1 5 L,(K),which holds by our assumption p s LA(^). In fact, we have A = K in the present case, and L,(K) is infinite according to Theorem 7.2. So Theorem 14.3.a implies that T has a path of length 1 4 p i 1. Choose a h E T with dom(h)=l i p . Write x,=s(h p ( a i 1 ) ) i f a

+

+

<

for any a < p, where fwas defined in (1 8). It follows from (1 ) that there is a < 7 and a set Y C X of order type v z such that Y is a homogeneous set of color 5 withrespect to&. (15)and (18)imply that Y u (x,,; isa homogeneousset ofcolor 1 4 with respect to the coloring ,f. This set has order type v:+ 1, which completes the proof. We now turn to discussing the corollaries of the above result.

<

COROLLARY 17.2. Let K, A, p , u, and z be cardinals, and assume ASK, p , T < L ~ ( K ) < and K , a
( L A ( K ) L (P)JZ*

K

~

isWregular, (19)

PROOF. The result follows from the above theorem with the aid of the simple

relation

LA(Kk+((LA(K))m

WA1

(it is harmless to assume p 1 2 here so as t o satisfy the requirements of the above theorem). COROLLARY 17.3. Assume

7 Combinatonal

K

i s inaccessible and p , 7 < K . Then

98

TREES AND POSITIVE ORDINARY PARTITION RELATIONS CH.

Iv

PROOF. According to Theorem 17.1, one has to observe only that (P.T)++tp)f.

Note that in the present case we have L,(K)=K, and this is the case that was not covered by the preceding corollary.

COROLLARY 17.4. Assume A 2 2 , p >_ o,and T < cf ( p ) . Then @P)+

(cf ( P ) ) J 2 ’

+((JP)+,

(21)

PROOF. Write K’=A‘= (nu)’, d = ~and , p’, .r’=O. Apply Corollary 17.2 with the parameters having primes. The assumptions there are satisfied. In fact, L,.(K‘)is regular in view of Theorem 7.15 and so, using Theorem 7.17b, we obtain that o’=T
(22)

) )required , by the assumptions ofCorollary Since K’=J’, we have a’
1

(p’)J2.

Noting that we have cf ( ~ ) I L , . ( K ’ ) = L ~ .according (K’) to (22), relation (21) follows. The proof is complete. As a special case, we have

COROLLARY 17.5 (Erdos-Rado [1956]). Assume 1.22 and p 2 0 . Then

Another interesting consequence of the above theorem is COROLLARY 17.6. Assume 1.2 3, p L o,z I < cf ( p ) , and cr,

T~

< p. Then

PROOF. Noting that PI L,((?.e)+) according to Theorem 7.17.a,we can apply Theorem 17.1with (i.P)+, i.P, and p replacing K , 2, and p ; thedesired result follows from the simple relation P-+((P)?,

9

(4JZ.

COROLLARY 17.7. Assume 1. is a strong limit cardinal and p, T <1,. Then j.+(p)f.

(25)

MAIN RESULTS IN CASE r = 2 A N D K IS REGULAR: COROLLARIES FOR

r23

99

P R O O F . The case i.=w is covered by Ramsey's theorem (Theorem 10.2); therefore assume R>o.Let a = p . z . w ; then

(2")+ (PI5 -+

in view of (23). The desired result follows from here, since we have 2"
COROLLARY 17.8. Assume GCH and let A T w ,

T


and PROOF. (26) follows from (21 ) with p = E., and (27)follows from (24)with p = E., = t " l , and o,=r,=O. Using the Stepping-up Lemma (Lemma 16.1), we are now in a position to derive many interesting results from the above corollaries in the case r 2 3 . For the convenience of the reader, we recall that the operation exp is defined recursively by putting

T,

expo (O)= 2 and for any cardinal

;i and

exp, + ( i )= exp"(2')

any integer n.

GROLLARY 17.9. Assume 3.22, p>w, ~ < c( pf ) , and

let

r z 2 he an integer. Then

PROOF. For r = 2 these resultsareidentical to (21)and (23),respectively,and for r > 2 they follow by induction, with the aid of the Stepping-up Lemma. By applying the Stepping-up Lemma to (24), we get

COROLLARY 17.10. Let A, p, o, and T~ be cardinals satisfying i.23, p l w , r , < cf ( p ) , and (T, T , < p , and let r 2 2 be an integer. Then

COROLLARY 17.1 1 . Let p 2 w he a cardinal and r I2 an integer. Then

7*

100

TREES AND POSITIM ORDINARY PARTITION RELATIONS CH.

Iv

and so, a fortiori, (exp,- 1( P ) )+

+

fP + 5 .

(32)

Note that (32) can be directly obtained from the trivial relation P+

+

(P+ );

by induction, using the Stepping-up Lemma. (31) is, however, much stronger, showing that Theorem 17.1 has a special feature not contained in the Steppingu p Lemma. The positive results are in a sense weaker for r > 2 than for r = 2, since all results of the form K+(. . . )' with r 2 3 and K reguiar that we can prove are obtained by repeated applications of the Stepping-up Lemma starting with the case r = 2, except if K has some large cardinal property (for this latter remark cf. e.g. Theorem 29.5). 18. A DIRECT CONSTRUCTION OF THE CANONICAL PARTITION TREE Let K and t be cardinals, fix acoloring f: [ K ] < O + t , and consider the canonical partition tree (K, S, R, 7')associated with f; see the beginning of the proof of Lemma 15.2 for the definition. Simultaneously with this partition tree we also defined a function s: T + K . One can show that s is 1-1and onto and, moreover, that for anyg, h E T w i t h g c h we have s ( g ) s s ( h ) .(We in effect showed the latter assertion in the proof of Lemma 15.2;we omit the simple proof of the former here since we need these facts only in order to give some background to what follows.) So we can define an ordering <, of K which turns K into a tree isomorphic to (7: c ) by putting

5
(1)

and here 5 < / q implies g < q . It is obvious that the tree (K, <,) is just as applicable in proving the existence of large homogeneous sets as is the partition tree ( K, S, R, T). In fact, we shall see that there is some advantage in taking a closer look at the tree (K, if): by so doing we shall be able to prove (a strengthening of) Theorem 17.1 in case b; in the proof we gave in the preceding section we had t o define another partition tree. An important feature in considering the tree (K, <,) is that there is a simple direct definition of the partial ordering
101

A DIRECT CONSTRUCTTON OF THE CANONICAL PARTITION TREE

DEFINITION fg.1. cj Let X G K. Define the equivalence relation a--hxP

-l;

by putting

iff V u ~ [ X ] ~ ~ f ( u u ~ a ~ ) = f ( u u ~ ~( 21) )

for any a, p < K. (ii) For each a < K we define the function g,: a-2 by transfinite recursion on 5
(iii) For any a, P < K put For any a < K, introduce the notation

X u = { p : /3<,a)

= {p
g,(/?)= 1).

Note that we have

Xu.<=X , n 5 ,

(7)

where Xa,<was defined in (3). We are going to establish the basic properties of the relation

<, so defined. (ii) ( K , <,) is a tree.

LEMMA18.2. (i) I f a < @ and gs(a)= 1, then gsPa=g,. (iii) For any a, B < K and u with B < p and u E [ X , A / ~ ] <we~ haue f ( u u { B ) ) = f (uu{aj.);

(8)

that is, for any u E [ X , u {a)]
PROOF. Ad (i). Assume that gpf t=g,rt holds for some <
gs(t)=g,(5)

(10)

also holds, and the desired result will follow by transfinite induction. We have a --hxp.. according to the assumption gs(a)= 1; so we have a fortiori a =-hxp.
9

since X t , c X#,,. ~ Noting that X#,<= Xu,< in view of (9), this implies that t =hXp,t fl holds just in case 5 =xxm,t a holds; in other words, g # ( ( )= 1 just in case gu(t)=1, which proves (10).

I02

TREES AND POSITIVE ORDINARY PARTITION RELATIONS CH.

Iv

Ad (ii). First we prove that <, is a partial ordering, i.e., that it is an irreflexive, antisymmetric, and transitive relation. O . We are going to prove a stronger result: the assumptions of Theorem 17.1 with ; I = K > o imply the following: given an arbitrary coloring f : [ ~ ] ' - 1 $T, there is either a homogeneous set of color 0 that is stationary in K, or there is a 5 < T such that there is a homogeneous set of order type v: 4 1 and of color 1 i5. Symbolically, this assertion might be expressed as K+(Stat

(K), (Vc$

(11)

where Stat ( K ) denotes the set of stationary subsets of K. Here is, however, a note of caution: the notational conventions introduced in Section 8 are inadequate for explaining the meaning of this relation. For the proof, let f: [ K ] ~ - +1 i r be a coloring, and consider the tree ( K , <,>. (Strictly speaking, (K, <,) has not been defined, since dom ( f ) is a proper subset of[^]'". So put f'(u)=f(u)whenever u ~ d o m (f), and put f'(u)=Ootherwise, i.e., when u E [K)
holds for any a < K. In fact, assume on the contrary that 1 Y, 12p for some a < K . Then (17.1) implies that there is a 5 < z and a set Z E of order type vt such that f ( { y a } ) = l i ( holds for any ~ E ZIt. follows from (8) that Z u { a ) is a

A DIRECT CONSTRUCTION OF THE CANONICAL PARTlTlON TREE

103

homogeneous set of color 1 45 with respect to f . As Z u {a; has order type v,; 1, this completes the proof of the theorem in case (13) fails for some a < K. Assume therefore that (13) holds for all a < K. Put o = w if p < w, o = p is p is regular, and o = p + if p is singular. Note that o is a regular cardinal and o < K. In fact, since we assumed K > w and p < K, the case o = IC could occur only if p was singular and p + = K; but then L , ( K )Icf (p)< p, which conflicts with our assumption P < L ~ ( K ) = L , ( K( L) = K in the case considered). Put A = {a< K : cf (a)= 0 3 . A is a stationary subset of K as it contains the oth element of an arbitrary club in K. The function

h(a)= sup Y,

is a regressive function on A in view of (13). Fodor’s theorem (Theorem 5.4) implies that there is an ordinal C < K and a set B s A stationary in K such that h(a)=< holds for any a € B. Writing f,(/?)=f({a@) for any a, fl wit?/?
S, r Y,=L in particular

K = Y, for any a E C. We claim that C is a chain of the tree (K, <,).

(14)

In fact, let a, /3 E C with a
X,ny=X,ny

f({daj)= f,(4=

fm=f ( { S P ) - ) ;

the second equality here follows from (14) and (12), since if 6 E Y. = Y,, then &(a) and f,(6) coincide, and if &#Ye= Y, then f , ( S ) = f , ( 6 ) = 0 . Using (8), we obtain that f({6y))=f({6a).) since 6
104

TREES A N 6 POSITIVE ORDINARY PARTITION RELATIONS CH.

Iv

We claim that C is a homogeneous set of color 0. In fact, if /? E C then Ply,= y

(equality holds here by (14)), since Y,c /? (cf. (12)).Let now a, /?E C be such that P
B € xu\Y = xu\y.. Hencethedefinitionof ruin (12)impliesf({a/?))=O;thisshowsthat Cisin fact a homogeneous set of color 0. As C is stationary, this completes the proof of the theorem. The reader may easily see that we even proved slightly more than (11). We illustrate the situation only in a special case when K = I = K2,p = K,, T = K1. The above proof gives e.g. the following: Assume 2N0= K,;let D be a stationary set in K 2 with Ds{a
(15)

and let f: [ D I 2 - 2 be a coloring. Then there is either a set C , G D stationary in K 2 with f " C O = (0) or a set C , of cardinality K, with f"C1 = { 13. Using ideas of J. E. Baumgartner [19763, one can show that this assertion is false if we modify our assumptions by requiring that instead of (15).

Dc{a
CHAPTER V

NEGATIVE ORDINARY PARTITION RELATIONS, AND THE DISCUSSION OF THE FINITE CASE

Various methods are developed for establishing negative ordinary partition relations and, as an application of these methods, the chapter ends with a discussion of the relation K - + ( & ) ; < ~ for finite K. 19. MULTIPLICATION OF NEGATIVE PARTITION RELATIONS FOR r = 2

We start with two definitions:

DEFINITION 19.1.LetA= )( A,. For anytwodistinct JgEAwedefinethefirst <<.

discrepancy S ( J g ) = . f n g of .f and g as

m g ) = . f 4 min = 15 < a : . f ( O # g ( t ) ) .

<,), 5
called fhe lexicographic product of the orderings it. The following properties of the first discrepancy and of the lexicographic product are direct consequences of the above definitions:

if J g , h E A are pairwise distinct; i f f n h # g n h , then equality holds here;

f(5)<&0

for t s f n g if f < g .

< is an ordering of A. Furthermore, we have

>=lex(>,.:(ca),

(3) (4 1

106

NEGATIVE ORDINARY PARTITION RELATIONS CH.

where < = lex (<:: t < a ) , and <, respectively. We shall need the following

v

>: and > denote reverse orderings of <: and

LEMMA 19.3. Let (A:, <:), 4 < u, be ordered sets, and let < be the lexicographic A,. Let ti be a regular cardinal, and ordering of the Cartesian product A =

x

:
BC A a set of cardinality K. Assume that B is wellordered by <. Then there exists a sequence
f,n.fv=5,

(6)

holds whenever p < v < ti. An analogous result holds in view of (5) if 4 is replaced with

>.

PROOF. Since B is wellordered by <, we may assume that its order type is K. (Indeed, its order type is 1ti, and if it is K, then we may omit some elements of B to make its order type ti.) We construct the sequence ( f ? : Y < K ) by transfinite recursion; so as to be able to d o this, we shall also construct a sequence ( B , : y < ti) of subsets of B such that B, is a nonempty final segment of B and B,? B, for any ordinals p and v with p < v < K . Having constructed B , for all y < p, Where p is an ordinal less than IC, put FN= Byif p > 0 and B; = B if

=-

n

Y
p=O. Note that ENis a final segment of B, and it is nonempty in view of the

regularity of K. Let f, be the minimal element of E, in the ordering

and

5,=min

if,nf:

f€

HI\

<, and write

[fp;;

B, is clearly not empty, and it is easy to show that B, is a final segment of EL, and so of B. This completes the definitions of f,, C p , and B, for p < ti. Since we have f v E B, whenever p < v < K, (6) follows. Let p < v < 6 < ti. Then by (6) and (2) we obtain that

5, = f,n f"= f,n

f a 5 f"..f a =

5"

I

showing that the sequence (t?:y < ~ ) is in fact nondecreasing. The proof is complete. The simplest result illustrating how orderings can be used to establish negative partition relations is

LEMMA 19.4. Let (A, <) be an ordered set, ti a cardinal, and vo and v1 ordinals such that IAI=K and vo, v:$tp(A, <>.Then K + ( v ~ , vl)'. Here v: is the reverse of vl, i.e., v:=tp (v1, >).

MULTIPLICATION OF NEGATIVE PARTITION RELATIONS FOR

r=2

107

type K of A, and define the partition f = anyx,y E A with'x<,yput {xy)E I,ifx
PROOF. Take a wellordering

= ( l oI,, ) of [A]'asfollows:for


DEFINITION 19.5. If (A, i) is an ordered set as in the preceding lemma, then we say that ( A , <) establishes the relation K + ( V ~ v, ~ )The ~ . partition I defined in the proof is called the Sierpiriski partition of ( A , <) associated with the wellordering O and for every ( < u there is an brdered set (A:, -it)that establishes the relation K ? + ( P ? , vJ2, i.e.,for which I A,/ = K : and p z , v l $ tp
K=

n

K:,

and let p and

0

be regular cardinals such that

:
P-, ( P d < a

and

CT-+

(v:): 1

(7 )

Then K%(P,

(8)

is established b y an ordered set, and we also have

and

PROOF. Let A =

x A,, and let < be the lexicographic ordering of A; clearly A

<
has cardinality K. We are going to show that p$tp (A, <) and o*$tp (A, <), which mean that the ordered set ( A , <) establishes (8). It suffices to verity the first of these relations; the second one can be proved analogously in view of (5). Assume, on the contrary, that B G A is a set that has order type p in the ordering <.Apply Lemma 19.3with p replacing K: we obtain f, and <,(y < p) such that (6) holds. Define the partition I = (I,: < a ) of p by putting y E I, iff 5, = (. The first

108

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

c

relation in (7) implies that I, has order type 2 p t for some p,, this contradicts the assumption p, $ tp (A,, <,). This proves p $ tp (A, i ), establishing (8). Next, instead of proving (9), we are going to prove the completely analogous relation

c;

(11)

Kf*((P<)<<.,

by doing so, our notations will be slightly simpler. Define the partition J = = ( J o , J , ) as a Sierpinski partition of A : Fix a wellordering i o of type K of A, and for any f; g E A with f+,g put {fg) e J o if f i g , and put {fg) E J , otherwise. Define a partition 1 5 (1€:( < a ) of J o by putting {fg) E I, if fng= for any f; g with {fg) E J , . Putting I.=J1, we claim that the partition I ' = ( l < < < a ) establishes (11). In fact, there is no homogeneous set X such that tp(X, . TO Prove (10)-let I < , <
c

1,+t={{fg)

E J,:

fng=4',

for any 5
COROLLARY 19.7. Assume K 2 2 and I2 o.Then is established by an ordered set, and KA-%((K.

holds.

A)+, (o)J2

PROOF. Assume first that K ~ WThen . K+(K+, 0 ) 'is established by (K, <). As ( K - I ) + + ( K + ) :and I + + ( w ) : hold, the assertions follow from (8) and (9), respectively. If 2 5 K
21+(Iz+; A+)'

(14)

MUL'ITPLICATION OF NEGATIVE PARTITION RELATIONS FOR f ' =

2

109

is established by an ordered set for any A 2 w ; this relation was proved independently by W. Sierpinski [1933] and (later) by D. Kurepa. Our next result is announced only for singular 2. It remains valid also in case d is regular, but that case is completely covered by relation (17) below. COROLLARY 19.8. Assume 3, > o is singular and A= every

I":, where 3 2 A? <;.,for C
5 < cf (A). Then 2"(&),2
(i)

(15)

and,.for any cardinal p 2.1, PA% ( P + (2, )e
PROOF. We may assume that A: 2 o for each 5 < cf (A). To prove (1 5 ) , observe that the relation 2":+(3,&?,A: )' is established by an ordered set according to (14); hence, noting that 2 ~ = 2 G < c r ~=l ~ & 2 4 ,

n

t
we can conclude by (10) that

so, by the Omission Rule (see Subsection 9.3) we obtain

Choose a 1-1 function g from cf (A) into cf (3,) such that AgscC,2AL:;then

by a monotonicity property (cf. Subsection 9.6b). Hence we have 2'% (2s):Ccf (1) again by the Omission Rule. To verify (16), note that the relation p ' ~ + ( p + , A$)* is established by an ordered set according to (12), and p + - ~ ( p + ) f r ( ~so) , we have

PA=

n

PA? % (P+? (q){
S
by (9);hence, using the function g mentioned in the preceding paragraph, we get (16) by the Omission Rule. The proof is complete.

110

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

We next prove the following simple result: 19.9. Let a > 0 and THEOREM

K? 2 2 for

n

t
each 5
K?%(KLx
PROOF.^^ l A , I = ~ , a n d A = )( A,.Definethepartition(Z:: {
putting {fg)E Z: iff f n g = { for any two distinct J; g E A. Assuming that [BI2C Z: holds for some Bc A and 5
for any cardinal II > 0. T h s can be expressed alternatively by saying that holds for any cardinal K 2 2 (see Section 7 for the definition of the logarithm I.). 20. A NEGATlVE PARTITION RELATION ESTABLISHED

WITH THE AID OF GCH It is conceivable that relation (19.13) can be improved to K*%(K+,

(3M2

(1)

for any K,L Iw. This is indeed the case if K' = 2Ain view of (19.17) or, trivially, if K * IK, but we are unable to prove this in the important case 2*IK < K*. The following is the simplest instance of what we cannot settle:

PROBLEM 20.1. Can one prove without assuming GCH that %%%+19

(3)KJ2

holds? We can prove (1) under the assumption of GCH. More precisely, using the notation for partition relations with bipartite graphs, introduced in Subsection 8.8, we have 20.2. (Erdos-Hajnal-Rado [19653). Assume THEOREM such that 2" = K+. Then

K

is a singular cardinal

Ill

A NEGATIVE PARTITION RELATION WITH GCH

This clearly implies (1)in the nontrivial cases if we assume GCH. For the proof we need a lemma on set mappings. A set mapping on a set E is a function f:E-*B(E)suchthatx$ f(x)foranyxE E.AsetXcEisfreewithrespectto f if f ( x ) n X = O holds for any x E X. A more extensive study of set mappings will be given in Sections 44-46; here we need only the following:

LEMMA20.3 (Hajnal-Mate E=

u

<<1

[1975]). Let ii be a regular cardinal, and let

<

E:, where E: is a set of cardinality > I for every < 1.Let f: E + P ( E ) be a

<

set mapping such that 1f ( x ) n E,( < I holds for any x E E and < 1.Then there i s a set X free with respect to f such that X nE , is nonempty for every'(
PROOF. We may assume that the sets E , ( <1,are pairwise disjoint and have cardinality A+. In fact, if this is not already the case, we can always take smaller sets satisfying these requirements. So it means no restriction of generality to assume that E,=A+ x {t;}. We are going to construct a free set (3 1

X = { ( a t ( ) : <
such that a,
holds whenever 5 < q <

To this end, put

Z = { a < A + :cf (a)=1', ,

and define the function g , : Z - r l for any (

as follows: E f ((a5>)13,

where a E Z. As 1is regular, the assumptions on the set mapping f imply that the set after the sup sign here has cardinality
has cardinality 1+.Put

9= sup9,. ,
We are going to define the set X in (3) such that at > 9. We do this by transfinite recursion: assuming that (a,,: < 5 ) has already b&n constructed for some ( c 1, choose an at. E S,. such that

i 1

a, > max 9, sup a,, q
112

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

and such that

this is possible, as I f ((a,,q))nE:l < A holds according to our assumptions. It is easy to see that the set X in (3) so constructed is free with respect to 1: In fact, if q < <1, then (a,q) $ f ( ( a c < ) ) holds since 9
<

PROOFOF THEOREM 20.2. Let (K": 1 Iv
K+-+[K+]'"v

for each v with 1 Iv
I,.=

{{UP',: tl <

p < K + & tl Ef,(j?))

(5)

for any ordinal v with 1 j v < c f ( K ) and

We are going to define the functions ,fv. Let 5 < K', and assume that f v ( a )has already been defined for every tl < 5 and every v with 1sv
S'= { A v :q < < & A , G < ) .

SZ has cardinality

IK;

so it can be represented as a disjoint union

s"=

u

s$

ICV
such that Sz has cardinality IK , for every v with 15 v
<

XnA#O

for any A E S$ (note that f v P has already been defined and is such that I ( f v ~ 5 ) ( a ) I holds l ~ , for any a<5). We may assume that I X I S I S $ I < K ~ put ;

ADDITION OF NEGATIVE PARTITION RELATIONS FOR

r =2

I13

This construction clearly ensures that (i) there are no three distinct ordinals a, /?, t < K + such that {a/?},{ a t } , and {fit}belong to the same I, for some v with 1 Iv max { q , sup A,,)). Given such a 5, A,,~S{holdsforsomev(depending0n ()with l s v < c f hence A,,nfv(()#O, i.e., { a t j E I, for some a E A,,. Thus, for every large enough tJ < K + there is an a E A,, such that {cttj I,. This verifies (ii). (i) and (ii) establish the dedred result, completing the proof. Noting that we have (2”‘(”))+-.((cf( K ) ) + ) : ‘ ( ~ , according to (17.32),’and so, in particular, (2Cf(W))++(3)&,and we can conclude from (2) with the aid of the Transitivity Rule (see Subsection 9.8) that

holds, provided K is singular and 2“= K ’ . The strength of this result consists in that it claims the nonexistence of a homogeneous bipartite graph, since if we are not interested in bipartite graphs, then we have (8)

K d ( ” ) f , ( K + , (Cf ( K ) ) ’ ) ’

for any infinite K according to (19.12), without assuming anything about cardinal exponentiation. If we assume 2 ’ = ~ + ,then one can show that

which strengthens (8); an even stronger version of this relation can be expressed with the aid ofthe square-bracket symbol; that version and its proof will begiven below in Section 49 (cf. (49.4)). 21. ADDITION OF NEGATIVE PARTITION RELATIONS FOR r = 2

If we are given a sequence of pairwise disjoint sets ( A ? : 5 < z) and a coloring fc of (unordered) pairs on each of the At‘s, as well as a coloring f of pairs of the index set z, then there is an obvious way to define a coloring f ’of pairs of (J A S c
by putting f ’ ( { x ~ j ) = f ~ ( { xify X) ), Y E A < and x # y , and f’((xy))=f({tq)) if x E A,, y E A,,, and 5 # q. Iff and the &%eachverify a negative partition relation, 8 Combinatonal

114

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

then f ’will also verify one. With the aid of such considerations we can derive the following

THEOREM 2 1.1. Assume k.:%(&):
for 5 < T , and M P Y , t < ,.

Let

run over cardinals and put

for every v < y . Then

I f y = 2 and the relations in (1) and ( 2 ) are established by ordered sets, then ( 3 ) is also established by an ordered set.

PROOF. Let A:, 5 < 7 , be pairwise disjoint sets such that I A, I = K,, and assume that the colorings f , : [A,l2--+y verify the relations in (l),and-f: [ ~ ] ~ - + verifies y the one in (2). Write A =

u

€
A, and, as described above, define f ’ : [ A ] ’ - y by

putting f ’ ( { x y ) ) = f , ( { x y ] )if x # y and x , y ~ A for < some 5 < 7 , and f ’ ( { x y ) ) = = f ( { ( q ) ) if X E A , and y e A 4 for some & q < 7 with 5 # q . If X E A is a homogeneous set of color v with respect to f ’ for some v < y, then the set

Y = {<: X n A , # O ) has cardinality < p,,, since Y is a homogeneous set of color v with respect to f, and f verifies (2). Moreover, for every 5 E Y the set X nA, has cardinality < A,,, since X nA, is a hombgeneous set of color v with respect to A, and f c verifies (1). Hence X has cardinality
u

,
distinct x , y E A if either x , y E A , and x<,y for some 5 or x E A,, y E A,, and 5x4 for some 5, q < T. We claim that q,,a: &tp (A, <’).Assuming e.g. that X c A is a wellordered set in the ordering <‘, we can easily show that tp (X,<’)
AVVlTlON OF NEGATIVE PARTITION RELATIONS FOR r = 2

I15

again, we have I YI < po and I X n A:l
COROLLARY 21.2. Assume

KZW

is a cardinal such that

If y = 1 and cf (ti)+(cf ( K ) , A0)' is established by an ordered set, then K + ( K , 1,)' is also established by an ordered set. PROOF. The case when K is regular is trivial and uninteresting. So assume that is singular, and represent K as K = C k:, where K : < K for every 5
K t % ( d ,

(6)

(2),)'

trivially. Applying the theorem just proved with l i y replacing y, and with T=Cf(K), &,=KL:, Ar,,+,=2, p=Cf(K), and ((
is established by an ordered set (in fact, any wellordering of K~ will do), we obtain the desired result by using this relation instead of (6). The proof is complete.

COROLLARY 21.3. Assume

KLO.

Then (7 1

K%(K,Cf(K)+)2

is established by an ordered set,

PROOF. The ordered set ( c f ( ~ ) >), , where > is the reverse of the 'less than'

relation on ordinals, establishes cf (K)+(w, cf (K)+)' and so, a fortiori, (K), cf (K)')'; hence the result follows from the preceding corollary.

cf (K)%(cf

COROLLARY 2 1.4. If

K 2o

and

d(K)+(Cf(K), d(K), (~"LJ' 9

(8)

116

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

then 2'%(&

Furthermore, for any

K L o,we

K,

(9)

(Av)v<;t)2.

have

and the relation 2!fr(K+,

K)2

is established by an ordered set.

PROOF. The case K =w is trivial, e.g. (10) becomes w+(o, w, (3),)2 in this case, and we trivially have 074(3); (color every pair with a different color). So we may assume K >w. We distinguish two cases: a ) there is a p < K such that 2K= 2p,and b) we have 2 P < 25 for any p < K. Ad a). This case contains nothing new, since according to (19.14),the relation 2 p f r ( p + ,p')' is established by an ordered set. Ad b). In this case, Theorem 6 . 1 0 ~and d imply that K is a limit cardinal, cf (2K) =cf (K), and there is a strictly increasing sequence ( K ~ 5:
1

c
To prove (9), note that

, so the assertion follows from (8) by holds by (19.14) for any < < c f ( ~ )and Theorem 21.1 with 2": replacing K : and cf ( K ) replacing 'F. To establish (lo), observe that cf ( ~ ) + ( 3 ) & ~ ( ~ holds )) according to (19.18); hence we have, a fortiori cf (K)%(Cf

( K ) , cf ( K ) ,

(3)L,(cf(K)))2

'

Thus (8) holds if we substitute 1 , = 3 and y = L,(cf (K)) there; making the same substitutions in (9), we obtain (10). Finally, to show ( l l ) , note that c f ( ~ ) f , +(cf ( K ) ' , o ) is~established by the ordered set (cf (K), <), where < is the 'less than' relation between ordinals; as 2": + ( K : , K : C ) ~ is also established by an ordered set (cf. (19.14)), the desired result follows from the last sencence of Theorem 21.1 with 2 " replacing ~ K,. We now take a closer look at the range of validity of the relation 25+(ic, K)'.

COROLLARY 21.5. Assume (i)

25=2p

KIO.

for some

Then any one of the conditions p < ~ ,

ADDITION OF NEGATIVE PARTITION RELATIONS FOR

(ii) and

25= ~ > c (fK ) ,

(iii)

cf (K)+(cf

r23

117

( K ) , cf ( K ) ) ’

ensures that holds.

PROOF. The result follows from (19.14), Corollary 21.3, or (9) with y = O according as (i), (ii), or (iii) holds. If 2 5 = ~and K is regular, then the problem whether (12) holds i i a question concerning large cardinals and will be discussed later. If 25 is singular, then the above corollary gives a necessary and sufficient condition for (12) to hold. Namely, a theorem of Shelah (see Corollary 27.4 below) says that if 25 > K and K is singular, 2p<25 for every p < K, and cf (K)+(cf ( K ) ) : , then 25-+(~):. Next we turn to the same type of problem involving partitions of length three. C~ROLLARY 21.6. Assume and

if

KZW.

Then

2?%(K, K, Cf ( K ) + ) 2 , K+(K,

K)’

then

2!%(K,

K, K)’

.

PROOF. (13) follows from (9) and the trivial relation cf(K)+(cf(K), Cf(K),Cf(K)+)2.IfCf(K)
u

<
A , in a way analogous to what we did in the preceding section. An

additional problem is what color to give to triples { x y z ) E [A]’ such that x, y E A , and z E A, for some (, q < T with ( # q. If we decide to give them a new color, say y, then the advantage of this is that a homogeneous set of color v with v < t is either included in a single A , or is a transversal of the sequence (A,: (
I18

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

THEOREM 22.1. Let r 2 3 be an integer. Assume that Kg f ,(I"):.
for any t < T and

?%(A;, (A), 5" <).): where y 2 2 , I b L r + l , and & 2 r - 1 for any v < y . Put

K=

K:.

Then

g
provided i , 2 w . Assume I ; = I o ,from now on, i.e., assume

?%(U< y instead of(2). Then K

-% (U< y

holds if either I,,, I , 2 w or r 2 4 and I., 2 w, and we have provided E.,

5 Q.

K%((AJ\>
r + 1r

PROOF. Let A,, 5 < T , be pairwise disjoint sets such that IAel = K : , and let A=

u

A:. Consider the following subsets of [A]':

?
Ko={uE[A]':V<<'5[IA~nul~1]},

K , = {u E [A]': ~ < < T [ U E A J ) , K , = { u E [A]': It, q < r [ t < q & ( A , n u l = 2 & IA,nul=r-2]1,

and

K,=[AI'\(K,UK,UK,). We are going to establish the following simple

CLAIM. Let X G A and 1x1 2 r . a) If LX]'CK,UK,, then either [X]'GKo or [ x ] ' ~ K , . b )Assumer=3and [ X ] 3 ~ K o u K l u K zThen . thereisai
x, y E A , n

ADDITION OF NEGATIVE PARTITION RELATIONS FOR

12 3

1 I9

z E X \A:. Then, noting that we assumed r > 3 in the theorem, an r-element subset

{x, y, z, . . . f. of X belongs neither to K O nor to K , , which is a contradiction. Ad b). Assume, on the contrary, that x, y, z, and t are distinct elements of X with x, Y E A, and z , t E A,,, where t < q . Then (xgtf.E K , , which is again a contradiction. Ad c). Assume that u E [XI', u E K , , and x E X \u. Let t, 9.9 < z be such that t < q , u n A , # O , unA,#O, and x e A y . Let s a n d t be such that s e u n A t and t ~ u n A , . T h e n w ehave ( u u { x ) ) \ { s ) ~ [ X ] ' nK,or ( u u { x ] . ) \ ( t ) ~ [ X ] ' n K ~ according as 9 # 5 or 9 # q (at least one of these holds since 5 < q ) ;the assumption r 2 4 is used in the second case, since in case r = 3 and 9 = 5 we would obviously have (uu {x))\ { t ) E K , . We again obtained a contradiction. Ad d). The assertion follows from c) if r > 4, so assume r = 3. Let x, E Afi, i <4, be distinct elements of X, where t 0 ~ 5 , r 5 , r 5 , .As { x o x 1 x 2 ~ ~and K2 {xoxlx3~ E K , , we have to=tl 3 in the theorem, let u c X n A c be a set containing two elements, and U E X ~ A , a, set of r-2 elements. Then u u u E [Xl'n K , , which is a contradiction. The Goof of our Claim is complete. We now return to the proof of the theorem. Let f:: [Af]'+y and f : [ ~ ] ' - + y be colorings that verify the relations in (1) and (2). Define the colorings g : [A]'+y and g': [A]'+y i1 as follows: given any u E [A]', put if u E K O ,

g(u)=g'(u)= f ( { < < z: A : n u #O)) g(u)=g'(u)=.Mu)

if u E K 1, where 5 < T is the unique ordinal for which u G A,, if u E K , and, finally,

g(u)=O

and

g'(u)=y

g(u)=g'(u)= 1 if u E K,. We claim that g verifies (3);and, moreover, g verifies (5) and g' verifies ( 6 ) ,if we exchange the roles of A0 and 1,in the assumptions (i.e.,g verifies (5) ifeither A0, 1, 20 or r 2 4 and ,Il I o,and g' verifies ( 6 )if 4I o.These exchanges of roles are necessary only in order to enable us to treat these relations in a uniform way). To show this, let X first be a homogeneous set of color 0 with respect tog. We claim that, assuming (1) and (2) (and not (4)), 1x1< I o 1 b - 2 if r = 3 and IXI<max (Ao,Abf. if r > 3 . To see this, observe that we have

+

[X]'sKouK,uK,,

I20

NEGATIVE ORDINARY PARTITION RELATIONS CH. V

and we may of course assume that 1x1>r. Consider first the case r =3. Then Claim b) implies that there is a ( < z such that

I X nA ,I I1

(7)

for every q < z with q # 5, and here we may obviously assume that

I x n Agl # O .

(8 1

X n A , is homogeneous of color 0 with respect to ,[=, and so we have ~XnA~~~L,-l.

(9)

The set ( q < t :XnA,#O) is homogeneous ofcolor 0 with respect to f :hence its cardinality is 3, see below), and K+(max {A,,

A;)., . . . Y

(11)

if r 1 4 (note that (10) is valid also in case r > 3 by ( l l ) , since 1 0 + & - 2 2 2max (A,, A,) as we. assumed A,, & 2 r + 1 > 2). Let now X ,be a homogeneous set of color 1 with respect to g . Then [X]'EK,UK,UK,. Claim e) implies that there is a 5 < t suchthat

I XnAA,(
(12)

for every q < z with q # t. X nA5 is a homogeneous set of color 1 with respect to fr, and so lXnArl
ADDITION OF NEGATIVE PARTITION RELATIONS FOR

r13

121

then H is a homogeneous set of color 1 with respect to ,f Therefore (2)(or (4)) impliesthat (HltA,,andsoweobtain by using (12)that lX\A~l<(r--2).IHl< < I , , as I, was assumed t o be infinite in all cases (note that we changed the original assumptions from A, 2 w to A,> w).This together with (13) implies that ( X ( < A , . So we have shown that g verifies the relation

note that this relation depends on the assumption I , ~ w . Let now v22 and assume that X is a homogeneous set of color v with respect to g. Then [X)‘GK,UK,, and so Claim a ) implies that either [ X ] ‘ c K , or [Xl‘sK,. We have [ X ~ < Ain, both cases. In fact, in the first case { 5 < 7 : A,nX) #O is a homogeneous set of color v with respect to ,fi and in the second ca’se X c A, for some < T, and then X is a homogeneous set of color v with respect to ,fv. So we have just shown that g verifies the relation

Putting(10),(14),and(15)together,weobtain(3).If~,=Io~wandI, >w,then (5) follows from (3) since I , + I; - 2 =I, holds in that case. If r 2 4 and 1 , 2 w (note the exchange of roles of I, and I, in the assumption), then (1l), (14), and (15) give (5). We are now going to show that g’ verifies (6) if we assume I, 20 instead of I, 2 o.Suppose I, = 2,.It follows from our considerations above that g’ verifies the relation K%((IV),
% (4, K,)3

holds for all n < w (cf. (24.6)); hence we have

2K- f ,(4,

(17)

NEGATIVE ORDINARY PARTITION RELATIONS CH.

122

v

a fortiori. Note that holds trivially. Using the above theorem with (17)and (18)replacing (1) and (2), we obtain that (19) 2 5 f ,(5, K<")3 according to (3).

PROBLEM 22.2. Does the relation

2 5 f ,(4, K,)3 (20) hold? This is certainly true if %=2"" for some n < w or %=K, (see Corollaries 25.2 and 25.3 below). 23. MULTIPLICATION OF NEGATIVE PARTITION RELATIONS IN CASE r 2 3 Lemma 16.1, the Stepping-up Lemma, gives us a method to obtain positive relations for r 2 3. This is the only method that we know for proving positive relations in the case r 2 3, except if the cardinality of the set to be partitioned is countable or a large inaccessible cardinal (partition relations for large cardinals will bediscussed inchapter VII, especially in Sections 29 and 34). One would like therefore to show that the converse of Lemma 16.1 is true, i.e., that (16.2) there implies (16.1), possibly under some reasonable restrictions. This would mean, say, that the relation K+(A:);;; implies the relation (29+f,(A:+1);<,. Weshall indeed be able to show this under fairly general circumstances, though we shall not be able to give a completely unified treatment; we shall, however, have no difficulty if, say, at least two of the A,'s are infinite and one of these is regular. In the present section we prove some preliminary technical lemmas, and the main results will come in the next section. Our preparation for these results here will consist in defining a partition of ["2]' in a canonical way if we are given a partition of [K]'-', and then investigating the properties of this new partition. To this end, we shall first consider. the set "2 = { f: fis a function & dom (f) = K & ra (f) G 2;.

+

W

MULTIPLICATION OF NEGATIVE PARTITION RELATIONS IN CASE

r 23

123

Let K > O be a cardinal and r 2 3 an integer fixed throughout the discussion below. DEFINITION 23.1. (i) Let < be the lexicographic ordering of “2, i.e., if cZ denotes the usual ordering of the set 2 = (0,l} then put <=lex(<2:{
1

)I=

(~(xo,

h . ., d - x r - 2 , xr- 1 1). *

(1)

If 1 S s 5 r - 1 and k , , . . . , k,,-,are integers <2, then write (2) , E.g. K ( 0 , 1, 0) is defined in case 1 - 2 4and is the set of all {xyuz. . . j E [“2]‘such that x < * y < * v < * z < * . . , and xu
K ( k , , . . . , k , _ l ) = { ~ ~ [ K 2 ] * : q ( ~ ) ~ s = ( k .o, k, ., ._ , ) J .

K i = K ( i , . . . ,i )

(3)

with i = O or 1, where the number of arguments is r - 1 (ie., the largest possible), and K = K0uK , . (4 1

(iv) For any sequence of elements xo < *xl < * . . . < *x,_ of “2 we write 6({x0,. . . ,x,- 1j)=(xonx,,.

. . ,x,-Znx,-I);

(5)

the operation xny, the first discrepancy of x and y, was described in Definition 19.1,and it assigns to the functions x and y the least ordinal at which theif values differ. Clearly, x n y < K for x # y . (v) For any two distinct ordinals 6, and a,, write [(So, 6 , ) = 0 if 6,<6, and [(do, 6 , ) = 1 if 6, <do. If (do,. . . , S,-,) is a sequence of ordinals such that for any i < r - 2, then put

Si#Si+,

I24

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

Here K was defined in (4). Note that [(6(u)) is always defined, i.e., the inequalities analogous to those in (6) are satisfied. For, given any xo, x,, x2 E "2 with either xo<xl<x2 or xo>x,>x2, we have XO"X1

(9)

#xlnx*.

In fact, assuming (=xonxl =xlnxz, the inequalities xo<x, <x2 would mean that xo(5)<x1(5)<x2((). which is impossible since xi(5)=0 or 1 (i=O, 1, 2 ) ; xo> xl >x2 is equally impossible. To illustrate the symbol just introduced, P(0, 1, 0) is defined for r l 5 , and it denotes the set of all {xo, . . . , x,-,) E "2 with xo < *xl < * . . . < *x,- such that (a)eitherx,< . . . <x,-, o r x o > . . . > x , - ~ and (b)xo,-,xl<xInx2>xznx3< <X3n

Xq.

Given i=O or 1, write

Pi = P(i, . . . ,i ) ,

(10)

where the number or arguments of P is r - 2, i.e., the largest possible. Put P = = P, u PI. (vii) Given any partition l = ( l t : ( < r ) of [ K ] , - ' , we define a partition l * = ( I : : (
(11)

The idea is that the set ["2]'\ Po is small under reasonable assumptions; hence I* gives a partition of almost the whole of ["2]'. So, if we are given a partition I verifying the relation ~fr(;i&;f, then I* can be slightly changed so that it verify the relation 2"+(l,+ l & < rprovided , the It's satisfy certain conditions (e.g. if I,, A,> w and lois regular). The rest of this section is devoted to proving simple technical lemmas about the concepts introduced above. The main results will be given in the next section. As the lemmas coming now will inevitably be unexciting, the reader may choose to skip them and check their proofs only when they are referred to. r 2 3 will be assumed throughout the lemmas. We start with the following simple result:

LEMMA23.2. Assume 2 1 s < r , and [ X ] ' E K ( k , , ko, ..., k , - , < 2 . I f l X I > r + l then k,=. . .=k,-,.

. . ., k5-,)

for some

PROOF. We prove the assertion by showing that, for any i <s- 1, ki =O holds if and only if k i + = 0 holds. To this end, let xo < * . . . < *x, be elements of X ;then {xo, . . ., x , - ~ ; E K ( k o , . . .,k,_,)and {xl, . . ., x,) E K(ko, . . ., k s - l ) . According + ~ , this is to the former relation, k i + l = O is equivalent to X ~ + ~ < X ~while equivalent to k , = O according to the latter one.

MULTIPLICATION OF NEGATIVE PARTITION RELATIONS I N CASE r 2 3

125

LEMMA23.3. Assume that either'a) [ X I ' G K or b) r 2 4 , ( X I z r + l , and [ X ] ' c K ( O , 1, 0 ) u K . Then [ X l ' c K , or [ X l ' c K , . PROOF. Assume, on the contrary, that there are uo, u1 E [XI' such that uo $ KO, u1$ K , . We claim that 2 r + 1 holds. In fact, we assumed this in case b). In case a), we have u, E K, and u1 $ K,, and so uo # u l ;as u o , u1G X and luol =

1x1

=lu,I=r,weindeedmusthaveIXI~r+l inthiscaseaswell.Hence8\u0isnot empty;pickanelement xfrom thisset a n d w r i t e u , u u , u { x ~ = { x , , . . . , ~ , , >- ~ j , where xo < *xl < *. . . < *x, - 1 . Note that n 2 r + 1. We distinguish two cases: C a s e l . {xi, . . . , x i + r ~ , ~ ~ K f o r a l l i ~ n - r . T h e n , w r i t i n g ~ j = q ( x j , x j + , ) f o r j < n -2, we have qi = . . . = q i + r - 2 for all i s n - r, and so qo = q l = . . .*=q n - 2 , as r-2>0. Hence u l , u2 E K ~which ~ , contradicts the choice of u, and u , . Case 2. { x i , . . ., x ~ + ~ - ~ } E K1,( 0} O ,holds for some i s n - r . If i = O then {xi+l, . . ., xi+,}$K(0, 1, O)uK, and if i f 0 then {xi-l, . . ., xi+,-,}# $ K(0, 1, 0)uK. This is a contradiction, completing the proof. ,

LEMMA 23.4. Let r 2 4 and assume [XI'

GP.

Then either [ X I ' S Po or [ X l ' c P,.

PROOF. We have [ X I ' S P G K; hence [XI'S K O or [ X ] ' G K , , by the preceding lemma. Assume that the assertion to be proved fails, and let u,, u1 E [XI' such that u o $ P , and u l $ P , . Write u o u u l = { x o , . .., x , - ~ ] where x o < *. . . < * < * x , - ~ . Note that x,<. . . <x,-, (12) or x,> . . . z x , - 1 (13) according as [ X l r ~ K or o [ X I ' E K , . Write cj=c(xjnxj+l, for (C was defined in Definition 23.l(v) above; note that (9)guarantees that Cj is meaningful); the relation {xi, . . .,xi+'- ,I E P, valid for any i s n -r, implies that = . . . = - 3 . Hence c0 = . . . = c,, - 3 , as r - 3 L 1. We claim that we have

j < n -2

ci

ci+,

C(XinXj, X j n X k ) = l o

(14)

for any i, j, k with i c j < k < n . In fact, assume e.g. that co=O, i.e., that xonxl< < x ~ ~ x Z< . . . < X , , - ~ ~ X then , - ~ ;we have to show that XinXj<XjnXk.

(15)

Here XinXjsXinxi+l in view of (12) or (13), and xjn xkI min { X I n xl + :j II
126

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

The case To = 1can be dealt with similarly. (14)implies that uo, ul E P,", which is a contradiction. The proof is complete.

23.5. Let X G "2, and assume IX I 2 o.Then there is a set X' C _ X with LEMMA IXl=lXl such that [X]'zKo or [X'I'cK, provided at least one of the following conditions holds: (i) [X]'nK(O, 1)=0, (ii) [X]'nK(l, O)=O, or (iii) r 2 4 and [X]'nK(O, 1,0)=0. PROOF. Let A = 1 X I . We may suppose that tp (X, < *) = A. Assuming that the assertion of the lemma is false, we are first going to establish the following. CLAIM. Thereareelementsxo<*x, < * x 2 < * x 3 ofX s u c h t h a t x o < x l > x 2 < x 3 .

PROOF OF CLAIM. For every x E X , there are y, z E X and y', z' E X such that x ~ * y < * z x, ~ * y ' < * z ' ,y i z and y'Zz'; in fact, if X E Xdid not satisfy these requirements, then we could take X ' = {x' E X : x s *x') to verify the assertion of the lemma. Now let x, and zl beelementsof X withxo<*zl,and xoz2. Denoting by min, and max, the minimum and maximum, respectively, of a set in the ordering <, put xl= =max, { z , , y,}. Pick y,, x3 E X with Z, 5 *y, < *x3 and y 2 < ~ 3 , and write x2 =min, {z,, y2}. Clearly, we have x,<x,>x2<x3. Our claim is established. Let now x , E X, i < 4 be such as described in the above Claim, and choose pairwisedistinct x i € X for 4 1 i I r with x3<*x,. Then {x,: iSr-l)EK(O, l), violating (i), {xl: l s i ~ r ) ~ K ( 0), l , violating (ii), and, in case r 1 4 , { x ~i :s r - 1) E K(0, 1, 0), violating (iii). These contradictions prove the lemma. LEMMA 23.6. Let X E "2, assume the cardinality of X is regular, and [XI'S KOor [X]'EK,. Then there i s an X ' G X with J X ' I = J X Jand [X']'EP,. PROOF.Write IXl=A. As [X.]'~#,or K,, X is wellorde~edby < or >;hence Lemma 19.3 (and the remark immediately afterwards) implies that there exists a strictly <*-increasing sequence ( x u :a < A) of elements of X and a nondecreasing sequence (5,: a
is increasing, and so [ { x , : a
5 P(ko, . . .,k,- ) with some

,

,

MULTIPLICATION OF NEGATIVE PARTITION RELATIONS IN CASE

r 23

127

PROOF. Pick arbitrary elements x,<*. . . <*x, of X . Then the relations . . ., x,- E P(ko, . . ., k,- 1) and {x,, . . ., x,- ,} E P(ko, . . ., k,- l ) show that k i = k i + l for any i with O l i < s - 1, which completes the proof. Note that the assertion is vacuous for r = 3. {xo,

LEMMA 23.8. If [X]'G P , , then X i s j n i t e .

PROOF. Assuming the contrary, let (x,: n <w ) be a < *-increasing sequence of ~ elements of X . Then, by the definition of P,, we have x , ~ x , + , > X , + ~ ~ X , +for all n < o , i.e., we have an infinite decreasing sequence of ordinals, which is a contradiction. LEMMA23.9. Let r 2 4 , let X s " 2 be infinite, and assume [X]'&,K0 or [ X l ' s K , . Then there is an X ' c X with ( X ' / = I X I and [ X ' l ' s P , , provided at lenst one of the following conditions holds: (i) [ X ] ' n P ( O , 1)=0, (ii) [ X ] ' n P ( l , O ) = O , (iii) r > 5 and [ X ] ' n P ( O , 1,0)=0, or (iv) r 1 5 and [ X l ' n P(1,0, 1 ) =O.

PROOF. We may assume that tp(X, <*)=I following

X 1. First we estab6sh the

If xo<*xl < * . . . <*x,-, are elements O f X such that CLAIM. C(xinxi + 1 , xi + 1" xi + 2) #[(xi+ 1 "xi + 2 > xi + znxi + 3 )

for every i s s - 4 , then s 1 5 . In fact, if r l s , then choose further elements (xS-,<*)x,<*. Then (16) implies that there is a j = O or 1 for which

and

{xi: i < r )

E P(j,

(16)

. . <*x,

of X.

1 -,j)

{xi: l s i s r ) E P ( l - , j , j )

hold provided r > 4 and s 2 5, and it even implies

and with j = 0 or 1, provided r 2 5 and s 2 6. These relation violate (i), (ii) and (iii), (iv) in turn, and so s 2 6 is certainly impossible. Our Claim is established. Let now ss 5 be the largest possible value in the Claim above (note that s 2 3, since (16) vacuously holds if s = 3), and choose xo < * . . . < *x, - satisfying (1 6).

,

128

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

Write X = X ~ - ~ ,Y = X ~ - ~ , and Z = X ~ - ~ . According as a) b) xny
or

Xny>ynz

or for any zo, zl, z2 E X with z s *zo < *zl < *z2. Observe that we always have Y n zo # ZO”Z1

here in view of (9), since either yzo>zl holds by our assumption that either [XI‘ E K Oor [XI‘ E K , . When using (17)or (18), we shall always take this inequalityinto account, without explicitly saying so. We are also going to use repeatedly (19.2) and the remark on equality there. We show that case a ) is impossible. In fact, assuming that a ) holds, for any zo E X with z < *zo (17) implies that Xny>ynZ>

ZnZo=YnZo

;

the last equality here follows from (19.2). For any z1 E X with zo < *zl, we obtain similarly that Xny>ynZo>ZonZl

=ynZ1.

Hence ynz’ strictly decreases as z’ E X increases in the ordering < * provided z < *z’; this would give us an infinite decreasing sequence of ordinals, which is

absurd. Assume therefore b). Then, for any zo E X with z < *zo, (18) implies that ;

Xny
it followsfrom here by (19.2) that ynZo=ynZ. Thus, for any z1 E X with zo < * z , we obtain, similarly, Xny
(19)

Again, we have xn y = x n zo by (19.2). Hence we cannot have XnZO Z 1 n Z 2

for any z2 E X with z, < *z2, in view of the maximality of s. The first inequality cannot fail here by virtue of (19) and the equality X n y = X n Z o mentioned afterwards. Thus ZonZ1 < Z 1 n Z 2

;

here zo, zl, z2 E X were arbitrarily chosen such that z < *zo < *zl < *z2 ;therefore [ { z ’E X :z < *z’)]‘ E Po, i.e., the assertion holds with X’= {z’ E X : z < * z ’ ) .The proof is complete.

MULTlPLlCATlON OF NEGATIVE PARTITION RELATlONS IN CASE

r 2- 3

129

LEMMA 23.10. Let 1-25, XE'2, I X ( > r + l , and i = O or 1, and assume that [XI'

G K i n (Pu P(0, 1 , O ) ) .

(20)

Then [ X I r-C Po or [ X l ' c P I .

PROOF. Assume u, u E [ X I ' are such that u $ Po and u $ P I , and let x E X \ u ; write uuuu(x;=(XI:E
where xo < *x, < * . . . < *x, - Clearly, n 2 r + 1. We distinguish three cases according as {x,:/ < r ) belongs to P o , P I , or P(0, 1,O). a) Assume (x):k r ] E Po. Then XjnXj+l < X j + l n X j + ~

(211

for any , j < r - 2 ; we claim that this holds for any ,j
in view of r 2 5, and so {xi : . j - r + 3 I1 <.j we actually have

+ 31. E P(0,O);hence (20) implies that

(xi:,j-r+3~i<,j+3i € P o .

SOX , n X j + l < X ~ + ~ ~ X which , + ~ , establishes (21) for any ,j
<XjnXjil

=XjnXkr

and so [(x,: I < ~ ) . ] ' G P o . This contradicts the choice of u. b)Assume (x,:lxnz=ynz according as s=O or 1.

PROOF. As P, c K,the assertion that [ n rK O or K1 is given in Lemma 23.3.a above. To show the second assertion, let xo < * . . . < *x,- be elements of X such 9 Combinatonal

I30

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

that x = xi, y = xj, and z = xk for some i <,j < k. Considering e.g. the case s = 1, we have (xo,. . ., x , - ~i E PI and so, using (19.2), we can see that xi"xj=xj_

1n

x j > xk-

I n xk

= xinxk=xjnxk,

which completes the proof. The following result establishes a relation between the sizes of homogeneous sets with respect to the partitions I and I * , described in Definition 23.1 (vii). There is a slight difference however; here, in the definition of A* we may also take P I instead of P o :

LEMMA 23.12. Let As[I"2]'-', s=O or 1, and put A*={uE

P,: 6 ( U ) E A )

Assume [ X ] ' s A * , X # O . Then there is a D s t i with I D I + l = I X I such that [D]' - G A .

PROOF. We may assume that I X 1 2 r . Write X = . ( X ~ (:< a ) , where xt<*x,, whenever (
Given any t o <... < 5 r - 2 satisfying

t r - 2 $1
{6<,:i
Write 5,-

=( r - 2

$ 1. In case s=O, the preceding lemma implies that

{ 6 , : i < r - 1; = { x5,n x5, : i < r - 1 ) = - I ,xg,nx5,+,: i < r - 1 = 6({x,, : i < r ) ) , +

and this set belongs to A, as { xr;,: i < r ) E A*. In cases= 1, the same lemma implies that

- l )The ~ ~ proof is complete. as { x , o ~ u { ~ ~ , + l : i < rA*. For the discussion of the finite case of the ordinary partition relation, we shall need a simple lemma, our last result in this section. In order to state this lemma,

MULTIPLICATION OF NEGATIVE PARTITION RELATIONS I N CASE

r23

I31

we introduce the following notation: Po,=

u P(G, k'

(22)

where Lruns over all 0-1 sequences of length r- 2 that begin with a 0 and contain at least one 1, and PI,=

ui P ( 0

(23)

where Truns over all 0-1 sequences of length r-2 that begin with a 1 and contain at least one 0. Note that we obviously have K = P U Po u P , , ,

(24)

and the sets on the right-hand side are pairwise disjoint. Our last result here is

LEMMA23.13. Assume r 2 4 . Let m be an integer,'and let X C K be a set with IXI=2m. T h e n t h e r e i s a s e t X ' s X w i t h ) X ' [ > m + l and [ X ' ] ' ~ P ~ f o r j = O o r 1 provided at least one of the following conditions holds: (i) [ X ] ' n P l o = O , or (ii) [Xl'nP,, =O. PROOF. Write X = {xi:i < 2m), where x, < * . . . < *xzm- Assume e.g. (i), and write Si=.uinxi+l.Put i,

= min

( i < 2rn - 1 : Si > Si + j

if the set on the right-hand side is not empty, and put i, = 2m - 2 otherwise. Write X o = ( x i : i l i , ) . and X I ={xi: i , s i < 2 m ) . We claim that we have [XJC

Po

and

[X,]'G PI .

(25)

In fact, we have X i n xi + = Si < Si + = x i + I n xi + 2 for any i < i, - 1 by the definition of i, (note that hi = hi+ cannot happen in view of (9)), hence xinxj < < X j n X k holds whenever i < j < k
Si>Si+,

whenever

iO
(26)

Assumethecontrary; thenthereisaleasti w i t h i , s i s 2 m - 1 suchthat di<6,+, (cf. (9) again), and i>i, here by the definition of i,. Taking an Y E [XI]' with x , o , x i , x i + l , x i +E2Y, we can see by (19.2) that Y €PI,. This contradicts (i). Hence (26) must indeed hold in case I X , 1 2 r. Thus the second relation in (25) also follows by (19.2).As IX, I IX, I = 2m+ 1, we must have lXjl > m + 1 forj=Oor 1. Put X'= Xj with thisj. The proof of our lemma is complete in case assumption (i) holds. The handling of assumption (ii) is entirely analogous.

+

I32

NEGAllVE ORDINARY PARTITION RELATIONS CH.

v

24. THE NEGATIVE STEPPING-UP LEMMA

Relying upon the results of the preceding section, we are now in a position to prove the following lemma, which is a kind of converse to the Stepping-up Lemma (Lemma 16.1). Note that + always means cardinal addition. LEMMA24.1. (Negative Stepping-up Lemma). Let r 2 3 be an integer, let K, 7>0 and E.,>_r ( < < T ) be cardinals, und assume that (1 1

K%(A,):::.

Then we have

2"+(i:+ l ) f < , provided at least one of'the conditions a), b), c), d) or e) holds: a) 5 2 2 , K , A,, 1 , 2 w and E., is regular; b) T 2 2, K , E., 2 w, E., is regular, and r 2 4 ; c ) r 2 2 , ~ , E . ~ , 1 , 2 w u n rd2 4 ; d ) 5 1 2 , K,A,>o and r 2 5 ; e) K ~ and W & < w for all t < r . Moreotler, without assuming any qfa), b),c), d ) or e), we have

2"%(0.!+ 1),

<,,

( r + 1 h)'

(3 1

with m=21-' + 2 ' - 2 - 4 provided r 2 4 , and

2"+((ic+ l ) c < t , r +1)'

( 4)

provided i, 2 w is regular, and (5)

2K%((j-:+1):
for this last relation, one hus to assume (1) with r=3. The main interest of ( 4 )lies in the case r = 3. In fact, ( 4 )follows from ( 2 )under condition b ) if r 2 4 and 7 2 2 . I f 7 = 1 and K ~ then W ( 4 ) becomes 2"+(~+,r+l)'

PROOF. Assume that l = ( l < Recall that we defined IF as

(<7)

(r23).

is a partition of

f?=( u E P o : 6(u)E 1:;

(6) [K]'-'

verifying (1). (7)

in (23.1 1) for any 5 < 7 ; here and below we shall freely use the concepts introduced in Definition 23.1.

PROOFO F (2).We shall define a partition J = (J,: 5 < 5 ) of ["2]' verifying (2) and depending on whether a), b), c) or d) hold; e) requires a different approach.

THE NEGATIVE STEPPING-UP LEMMA

We shall fix a

t < r , and

133

X c x 2 will denote a set such that [X]'C J:.

We shall have to prove that (XI
(9)

We may assume to this end that X #O. Observe that if [XI'S IF

(10)

holds instead of (8), then (9)is satisfied. In fact, Lemma 23.12 implies (hat there is a D c ~ w i t h I D I + l = I X l a n d[D]'-'cI:;asthepartition Iverifies therelation in (l), we obtain that ID[< I c , and so (9) follows. As we shall invariably put J, = I F

(11)

if 2 1 t < r , we shall have to establish (9) only in case ( = O or 1. We shall have

(12)

J,nP,=I:

also for 5 =0, 1. We shall assume that (9) fails in the remaining cases, i.e., that

(5=0 or 1).

IXI=1,+1

Ad a). Set

if

J:=IF

(13)

21<
J , = K(0, l)ul:,

and

J0=CK2]'\

u

J,.

lS<
It is easy t o verify that (12) holds. To prove (9), suppose first that 5=0, i.e., that [XI'S J,. In this case [X]'nK(O, 1)=0; noting that l 0 2 w , and so X is infinite by (13), we can conclude from Lemma 23.5(i) that there exists an X'EX with IX'l=(Xl and CX'I'G KO or [X'I'C; K,. As ( X ' (= 1, 1 21, is regular, Lemma 23.6 now implies that there is an X"E X' with IX"( = IX'I (= = I o + 1) and [X"]'cP,; hence (12) implies that [X"]'E 1;. So, with X" replacing X we have (lo), and so (9) as well; i.e., 1, 1 = (X"I< I , 1, which is a contradiction. Suppose now <=1. We have [X]'nK(1,0)=0, and so, noting that (XI= = I 1 + 1 2 w , Lemma23.5(ii)implies that t h e r e i s a n X ' r X w i t h IX'l=lXl and [X'IrcKoor K,.Then [X'~nK(O,l)=O,andso[X']'~I~;therefore(lO),and (9) hold with X' replacing X. But then I, 1= IX'J < I , + 1, which is again a contradiction.

+

+

1x1

+

+

134

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

Ad b). Set J:=Iz

if

215
J , =K(O, 1,o)uI:,

and

J,=["2]\

u

J:.

15{<7

It is easy to see that (12) is satisfied. Suppose 5 = 0. We have [XI' nK (0,1,0)= 0, so Lemma 23.5(iii) and Lemma 23.6implyin view ofthe regularity of I X ( = l , + 1 =A, that thereexistsan X'EX with J X ' J = I X Jand [X'I'GP,. Then [X']'CI& and so we have I , + 1 =\A"[<
+

and

J , =K(O, l)uP(O, l ) U l T ,

Jo=[K2]'\

(J J:.

I
It is easy to prove that (12) is satisfied. Suppose first that 5=0. Noting that JXI=A,+ 1 2 0 and [Xl'n K ( 0 , 1)=0, Lemma 23.5(i) entails that there is an X ' c X with ( X ' I = J X \ = I , + l and [X']'CK, or K , . Observing that [X]'nP(O, l)=O,i.e., [X']'nP(O, 1)=0, we obtain by Lemma 23.9(i) that there exists an X"CX' with JX"I=JX'J=L,+l and [X"]'cP,.Then [X"]'~I,*,andso we have A,+ l=(X"I
J , = K ( O , l,O)uP(O, l , o ) u l y ,

THE NEGATIVE STEPPING-UP LEMMA

and

J,=["2]\

u

I35

J:.

155<7

It is easy to see that (12) is again satisfied. Supposefirstthat 5 = O . T h e n ( X [ = A 0 + 1 i o a n d [X]'nK(O, 1,0)=0;so,by Lemma23.5(iii),thereisan X ' r X with IX'I=IXI=i,+ 1 and [X']'sK,orK,. As J X ' l n P ( 0 , 1,0)=0by [X']'~[X]'EJ,, Lemma23.9(iii)entails theexistence o f a n X " s X with IX"I=IX'I=A,+l and [X"]'~P,.Hence [X"]'~I,*by(12), and so it followsfrom theimplication (10)*(9) that A,+ 1 =IX"I w implies that there is a rearrangement (A;: t < t ) of the sequence ( i f <: < r ) such that & + 5 2 A : for all r < r and, of course, & 2 r for t m (cf. Monotonicity Property b ) in Subsection 9.6). In case r = 3 ( I ) also implies 2 ' 2 K in view of Corollary 17.5 with A= 2 and p = t, and so we have ~ + ( 3 ) : by (19.17). Replacing ( I ) with this relation, the relation corresponding to ( 5 ) becomes 2"+((4),, (4),,4, 4)3, i.e., 2"+(4):; this is again stronger than (2), as r = 3 now. This completes the proof of (2).

<

c,

PROOF OF (3). Let k;, i < 2'- 2, and ,j < 2'-2 - 2, be 1-1 enumerations of all nonconstant 0-1 sequences of length r-1 and r-2, respectively. Put

Clearly, (.It: 5 < t 4 ( 2 ' - ' +2'-2-4),is a partition of ["2]'. Let X s " 2 be a nonempty set such that [X]'EJ: for some < < ~ + ( 2 ' - ' + 2 ' - ~ - 4 ) . Assume first that C
136

NEGATIVE ORDINARY PARTITION RELATIONS CH.

v

to that of 1; in (7),though here we may haves = 1 as well; this will not make much difference.) Lemma 23.12 implies that there is a D G K with ID1 1 =I X I and [D]'- E I,; as the partition I was assumed to verify (l), we have ID I
+

PROOF OF (4). Write

J,=K(O, I ) , 155
for

Jr=I:

and

IJ

J,=["2]'\

J:.

li-<
Assume [XI'S J : for some t 5 T. If 5 = T, then I X I < r + 1 by Lemma 23.2. If 1s5
+

PROOF OF ( 5 ) . Note that r = 3 in the present case, and so we have K = Po u P , ; hence ["2]'= K ( 0 , l ) K(1,O)UPoUPi. ~

(14)

Write Jr+7+,

= K(1,O) 7

J , i , = K ( O , 11, J,+,=

and

(24 E

PI : d(u) E IF),

J g = { u E Po: a@)€I , ) ,

where ( < T . It follows from (14) that ( J ! : q < r i r $ 2 ) is a partition of ["213. Assume [Xl'CJ, for some q < s / r + 2 . If ~ < 7 ,then I X I < I , + l by the implication (10)=49). If q = 7 5 for some 5 < 7 , then we have I XI < I t + 1 by an analogous argument. In fact, assuming IX I = I z + 1, there is a d E IC with [D]'-' GI, and ID1 1 = 1x1 by Lemma 23.12; as the partition I verifies the relationin-(l),wehavelDI
+

THE NEGATIVE STEPPING-UP LEMMA

I37

LEMMA 24.2. Let r 2 3, n, s >0, and mi 2 r ( i < s ) be integers, and assume that

in case r 2 4 and s 2 2 .

PROOF. Write K = n , and use the notations introduced in the preceding section.

< of "2 is a wellordering ;ow,

and so we may assume that the wellordering < * of "2 is the same as < (in fact, it is unlikely that we could gain anything by choosing < * different from <); we have As K is finite, the lexicographical ordering

["2] = K O then. Assume we are given a partition I = ( I i : i <s) of [ K ] ' - ' = [n]'-' verifying (1 5 ) . To prove (16), suppose r = 3 and choose J i and J s + i (i < s) analogously as in the proof of (5), with i and s replacing 5 and t, respectively; i.e., p;t and

Ji = {U E P o : 6(u) E Iil, { u E P , : 6 ( u )E l i )

for each i <s. In contrast to the situation in the proof of ( 5 ) , it follows now from (14)thatJ=(Ji:i<2s)isapartitionofC"2]=["2],asthesetsK(0, 1)and K(1,O) are now empty in view of (18). The same argument as in the proof of (5) with mi replacing Li gives that there is no homogeneous set of class i or s + i that has cardinality mi+ 1 for any i < s . Thus (16) is established. To prove (17), assume r 2 4 and s 2 2. Define I:, i < s, with a slight modification of (7) above as I ; = { u E P : 6 ( u )E I ; ) . . Using the notations introduced in (23.22) and (23.23), put J o = Polu I ; ,

and

J1= P l O u l ;

J,=I{

if 2 1 i < s

(note that we assumed s 2 2 ) . Then J = (Ji: i < s ) is a partition of C"27=c"2lr in view of (18) and (23.24). Let now X s " 2 be a set such that [ X I ' s J , holds for some i <s. Assume i 2 2 first. Then X E P, and so X s Piforj = 0 or 1 by Lemma

138

NEGATIVE ORUINARY PARTITION RELATIONS CH.

v

23.4, since we assumed r 1 4 . Lemma 23.12 now implies that there is a D G n with IDI+1=1XJ and [D]'-'cIi. As the partition I verifies (15), we have IDl
Assume now e.g. i = O , and suppose that IXI>_2rn0.[X]*cJ, implies that [X]'nP,,=O, and so, noting that we assumed r 2 4 , Lemma 23.13 with assumption (i) ensures the existence of a set X ' c X with I X ' ( ~ r n , + l and [X']'~P,.forj=Oor 1.Then [ X ' ~ c P j n J , , a n dso thereisaDwith [D]'-'GI, such that lX'I=lDI+ 1, i.e., such that J D J l r n , ,according to Lemma 23.12. This contradicts our assumption that I verifies (15). Hence we must have I X I < 2m,. In case i = l we obtain analogously that / X / < 2 r n l .Thus (17) is established; the proof is complete.

25. SOME SPECIAL NEGATIVE PARTITION RELATIONS FOR r > _3 We are going to prove two more theorems not covered by the results in the preceding section. The first result is a kind of negative stepping up:

THEOREM 25.1. Let Assume that

K,

I. 2 (I) and T 2 2 be cardinals, and let r 2 2 be an integer. K%(n,:.

Then ti+(;.,

and, moreover

+

( r 2)r- )'

+

ti+(i,T + r ) ' + '

provided

T < (M,

provided

T

and K+(L

r+3)'+2

(4)


PROOF. Let f : ti]'+^ be a coloring verifying relation (1).

PROOF OF (2). We are going to define a partition ( I t : ( < T )verifying (2) as follows: given ordinals xo< x1 < . . . < x, < ti, we put

SOME SPECIAL NEGATIVE PARTITION RELATIONS FOR

r23

I39

where 1; 5 < T (i.e., 5 < T - 1, as T is a cardinal). Assume that this partition does not verify (2). Suppose first that [ X l r + l ~ land o JXI=E.; we may assume tp(X, <)=A here. Chooseelementsx,<x,< . . . < x , - , o f X such that , f ( { x i : i < r j ) = p i s least possible. We claim that

.f b)'P

(5)

holds for any u E [{ x E X : x, - < x;],. In fact, assume, on the contrary, that we have f ( u ) > p f o r some u in this set, and write u = { x i : r s i < 2 r ) , where x , < . . . < x * , - ~ .Then f ( { x i : , j s i< . j + r f ) <,f('xi:,j
1x1

5 = , f ( ( x i : i < r ) ) < , f ( ( x i :I s i < r ) ) and so and {xi:l s i < r + 2 ) EI,+~, {=f({xi: I < i < r j ) < . . ., which is a contradiction, proving (2).

PROOFOF (3). Set 1; =

u

:
1

It+,,

where I = (16 t c t) is the partition defined just before in the proof of (2), i.e., if x o < x l < . . . < x r < u , then {xi:i
iff

f ( { x i : i < r ) ) < f ( { x i :I < i < r l )

We claim that the partition ( l o ,I ; ) verifies the relation in (3). We saw in the proof of (2) that this partition verifies the relation

Assume, therefore, on the contrary, that I X 1 = T + r and [XIr' E 1;. Noting that T is assumed to be finite here, let xi, i < T + r, be an enumeration of the elements of X in increasing order. We have ( x i : j < i s j + r ] E I ; , and so

f ({ x :.j Ii < j

+r

) < f ({xi:.j

-=i I j + r ] )

NEGATIVE ORDINARY PARTITION RELATIONS CH.

I40

v

for any ,j<.r. Hence , f ( ( x i :t < i < r + r ) ) > . r , which is a contradiction, since ra ( f )5. ~(3) is established.

PROOF OF (4). We define a partition J = ( J o , J , ) verifying (4). For any ordinals x o < x l < . . . < x r + , < K put { x i : i s r + l ) E J , iff f ( { x i :i < r ) ) < f ( { x i :1 < i < r + I ) , ) 2 f ( { x i2: < i < r + 2 ] ) ,

and write J 0 = [ ~ ] ‘ + ’ \ J Assume 1. that J does not verify (4). Suppose first that there is an X E K with [ X I r + ’ ~ J and 0 tp (X, <)=A. Let ( x , : a < A) be an enumeration of the elements of X in increasing order, and write g(a)=f({x,ii:i
If g ( a )2 g ( / ? )whenever a < /?
and write y j = a. 4.j and y2r + j . = y Z r - i,f i1 for j < r, j ‘ < r + 1 . Writing h ( j ) = f ( { x , , . . . , x ~ , + ~ - , ;we . ) , have h ( O ) = h ( 2 r ) = h ( 2 r + l ) = p and h ( r ) = p ‘ # p . So h ( j ) < h ( j + l ) > h ( j + 2 ) for some , j 5 2 r - l . Then { x ? , , . . . , X ~ , + ~ + , ) E J ~ , contradicting the assumption that [X]‘+’EJ,. Hence { x a :a , / r < a < A ) is indeed a homogeneous set of color p with respect to f, as claimed, which contradicts our assumption that the coloring f verifies the relation in ( 1 ) . So we must have g ( a )< g ( b ) for some a and p with a