Which posets have a scattered MacNeille completion? (Q2577732): Difference between revisions

Let \(\mathbb N\) resp. \(\mathbb Q\) denote the set of natural resp. rational numbers and \(\eta\) the order-type of the set \(\mathbb Q\) in its natural order. Let further \(D(\aleph_0)\) denote the cartesian product \(\mathbb N\times \{0,1\}\), ordered so that \((x,i) < (y,j)\) if \(x\neq y\) and \(i < j\). (This set is isomorphic to the set of atoms and coatoms of the Boolean algebra of all subsets of a denumerable set, ordered by inclusion.) Also \(B(\eta)\) denotes the set \(\mathbb Q\times \{0,1\}\) ordered so that \((x,i) < (y,j)\) if \(x < y\) and \(i < j\), whereas \(E(B(\eta))\) denotes the collection of posets made of \(\mathbb Q\times \{0,1\}\) and any order \(\varepsilon\) extending the order of \(B(\eta)\) with no additional comparabilities between \(\mathbb Q\times \{0\}\) and \(\mathbb Q\times \{1\}\). A poset is scattered if it does not embed the type \(\eta\). In an earlier paper [Discrete Math. 35, 39--52 (1981; Zbl 0466.06002)], \textit{D. Duffus, M. Pouzet}, and \textit{I. Rival} proved: The MacNeille completion \(N(P)\) of a poset \(P\) contains a subset isomorphic to \(\eta\) iff \(P \) contains a subset isomorphic to \(\eta\), \(D(\aleph_0)\) or some member of \(\varepsilon(B(\eta))\). Here the authors define nine sets \(U(a,\beta)\) for binary relations \(a,\beta\) on \(\mathbb Q\) with which they establish a significant completion of the above theorem, namely: \(N(P)\) is scattered iff \(P \) embeds none of \(\eta\), \(D(\aleph_0)\) and the nine sets \(U(\alpha,\beta)\). In addition these eleven sets are pairwise not embeddable in each other. The long proof makes use of several graph-theoretical concepts and formulas of the partitions calculus, e.g., \(\eta\to(\eta,\aleph_0)^2_2\) of Erdős/Rado and \(\eta\to[\eta]^2_3\) of Galvin.