Which posets have a scattered MacNeille completion? (Q2577732): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Hamza Si Kaddour / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Egbert Harzheim / rank | |||
Normal rank |
Revision as of 14:22, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Which posets have a scattered MacNeille completion? |
scientific article |
Statements
Which posets have a scattered MacNeille completion? (English)
0 references
6 January 2006
0 references
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.
0 references
MacNeill completion
0 references
scattered posets
0 references
partition theorems
0 references