Partition Relations and Transitivity Domains of Binary Relations
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) \to (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}[2^{m-1}(n-1)^m+n-2]; \] if \(m > 1\), then \(l_0(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 0071.05105), Theorem 25]; Theorem 1 includes also a characterization of \(l_0(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 2^{n-1}\). \{Reviewer's remarks: (1) It is easily seen that \(l_0(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,\omega_0n)^2\) should be changed by replacing \(\gamma\) by \(\omega_0(l_0(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 \(|U_0(x)A_\gamma| = \aleph_\alpha\) for some \(x \in A_\beta\), and (ii) is not quite adequate but becomes so on inserting ``and \(|U_0(x)A_\gamma| < \aleph_\alpha\) for some \(x \in A_\beta\) after ``\(|U_0(\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 \(l_0(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\)\}.
- Partitioned binary relations
- On transitive subrelations of binary relations
- Partition relations for partially ordered sets
- Partition semantics for relations
- scientific article; zbMATH DE number 3853081
- The dual composition of binary relations and its applications to transitivity properties
- Partition of a set and transitive closure
- A partition relation for partially ordered sets
- Relations among partitions
- scientific article; zbMATH DE number 5584252
- Structure of transitive valued binary relations
- On a problem of Erdős and Rado
- Improvement of a partition theorem of Erdős and Rado
- New bounds on the Ramsey number r ( I_m , L_n )
- Ordinary partition relations for ordinal numbers
- Some counterexamples in the partition calculus
- Partitioned binary relations
- On a theorem in the theory of relations and a solution of a problem of Knaster
- ON THE TRANSITIVE HULL OF A κ‐NARROW RELATION
- Topological Ramsey numbers and countable ordinals
This page was built for publication: Partition Relations and Transitivity Domains of Binary Relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5602094)