Publications of (and about) Paul Erdös
Autor: Erdös, Paul; Milner, E.C.
Title: A theorem in the partition calculus. (In English)
Source: Can. Math. Bull. 15, 501-505 (1972); corrigendum ibid. 17, 305 (1974).
Review: It is shown that if h < \omega and \nu < \omega1 then \omega 1+\nu h > (2h, \omega 1+\nu)2, as known to the authors since 1959. The literature of this result and related results are discussed. The proof is by induction on h from a more comprehensive theorem. For each ordered set S, tp \, S is the order type of S. Consider any order type \alpha. \alpha is right-AI if and only if \alpha = \beta+\gamma, \gamma \ne 0 implies that \gamma \geq \alpha (AI abbreviates additively indecomposable). \alpha is strongly indecomposable (briefly, SI) if and only if whenever A = B \cup C and \alpha is the type of A, B, or C has type \geq \alpha. For each order type \beta, \beta is strong if and only if whenever tp \, B = \beta and D \subset B there are n < \omega and subsets D1, ... ,Dn of D such that tp \, Di is SI for i = 1, ... ,n and such that for each M \subset D, if tp(M \cap Di) \not \geq tp \, Di for i = 1, ... ,n then tp \, M \approx tp \, D. For example, each ordinal number and its reverse are strong. The theorem proved is that for each SI and right-AI order type \alpha and each strong denumerable order type \beta, if 2 le k < \omega and \alpha > (k, \gamma)2 then \alpha \beta > (2k, \gamma \cup \omega \beta)2. (It is added in proof that F. Galvin has proved the same thing with ``strong'' deleted from the hypothesis on \beta, thus settling a conjecture of the writers.)
Classif.: * 04A10 Ordinal and cardinal numbers; generalizations
05A17 Partitions of integres (combinatorics)
05A99 Classical combinatorial problems
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag