Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 204.00905
Autor: Erdös, Paul; Rado, R.
Title: Partition relations and transitivity domains of binary relations (In English)
Source: J. Lond. Math. Soc. 42, 624-633 (1967).
Review: The main theorem is Theorem 2: For all positive integers m and n, for some positive integer l(m,n), for each ordinal number \alpha, \omega\alpha l(m,n) ––> (m,\omega\alpha n)2; if l\alpha(m,n) is the least such l(m,n) for a given \alpha, then \gamma \mapsto(m,\omega\alpha n)2 for each \gamma > \omega\alpha l\alpha (m,n), and l\alpha(m,n) \leq (2n-3)-1[2m-1(n-1)m+n-2]; if m > 1, then l0(m,n) \leq l\alpha (m,n).
This generalizes some of Theorem 1, which handles the case \alpha = 0 and was proved by the same authors [Bull. Am. Math. Soc. 62, 427-489 (1956; Zbl 071.05105), Theorem 25]; Theorem 1 includes also a characterization of l0(m,n). Among other results, Theorem 4 is an extension (the statement of which is not the obvious one) to infinite a of a result attributed to R. Stearns: If a is a finite cardinal, if \prec is a relation trichotomous on a set S, then \prec is transitive on some subset of S having cardinal a provided that |S| \geq 2n-1.
{Reviewer's remarks:
(1) It is easily seen that l0(m,2) as characterized by Theorem 1 is the least integer l such that for each set S with cardinal \geq l, for each relation \prec trichotomous on S, \prec is transitive on some subset of S having cardinal a. Specializing the estimate for l\alpha (m,n) in Theorem 2 to n = 2 yields the Stearns result.
(2) Theorem 1 is slightly misstated. If m = 1, ``\gamma \mapsto (m,\omega0n)2'' should be changed by replacing \gamma by \omega0(l0(m,n)-1).
(3) In the footnote on p. 625 ``(n-1)\mu'' should be replaced by ``(2(n-1))\mu''.
(4) On p. 627, (i) is not quite adequate but becomes so on replacing ``for x in A'\beta'', by ``for each x in A'\beta and |U0(x)A\gamma| = \aleph\alpha for some x in A\beta'', and (ii) is not quite adequate but becomes so on inserting ``and |U0(x)A\gamma| < \aleph\alpha for some x in A\beta'' after ``|U0(\bar x)A\gamma| = \aleph\alpha''. [The iteration of the operators O\lambda then becomes adequate for the task at hand.] The last sentence of the third paragraph of (ii) appears to be an inaccurate oversimplication. [It is clear from the rather involved proof of Theorem 2, to which these points attach, that these inaccuracies were not in the original thinking things through. There are only a few others, which are more easily spotted.]
(5) In line with (1) above and the discussion of l0(m,n) on p. 624, the condition under (i) in Theorem 4 is best possible not only for 1 \leq a \leq 3 but also for 1 \leq a \leq 4}.
Reviewer: A.H.Kruse
Classif.: * 05D10 Ramsey theory
03E05 Combinatorial set theory (logic)
04A20 Combinatorial set theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag