The order type of the collection of finite series-parallel posets

From MaRDI portal





If \(R,R'\) are relational structures, \(R\) is embeddable into \(R'\), in symbols \(R\leq R'\), if \(R\) is isomorphic to some substructure of \(R'\). This relation \(\leq\) is a quasi-order and induces an order on the collection of finite substructures considered up to isomorphism. The ordinal length \(o(P)\) of a wqo-set \(P\) (wqo = well-quasi-ordered) is the greatest ordinal which is the type of a linear extension of \(P\) -- it exists due to a theorem of \textit{D. De Jongh} and \textit{R. Parikh} [Nederl. Akad. Wet., Proc. Ser. A 80, 195-207 (1977; Zbl 0435.06004)]. The height \(H(P)\) of a wqo-set \(P\) is the least ordinal which is greater than all types of subchains of \(P\). A forest is a poset \(F\) such that for each \(x\in F\) the set \(\{y\in F\mid y\leq x\}\) is a chain. Theorem 1. The collection \({\mathcal F}\) of finite forests, considered up to isomorphism, is \(wqo\) under embeddability and has ordinal length \(\varepsilon_0 \). (This is the least ordinal \(\alpha\) such that \(\beta<\alpha \to\omega^\beta< \alpha)\). A poset is said to be series-parallel iff it does not embed \(N(=\) the 4-element poset of which this is the Hasse diagram). Theorem 2. The collection \({\mathcal N}\) of finite series-parallel posets, considered up to isomorphism, is wqo under embeddability and has ordinal length the Feferman ordinal \(\Gamma_0\) [\textit{S. Feferman}, J. Symb. Log. 33, 193-220 (1968; Zbl 0162.02201)]. Finite series-parallel posets form an age in Fraïssé's sense [\textit{R. Fraïssé}, Theory of relations. North-Holland, Amsterdam (2000; Zbl 0965.03059)]. Then it is proved that the height of \({\mathcal N}\) in the collection of its subages is also equal to \(\Gamma_0\). Further, for the height, \(H({\mathcal F})= \varepsilon_0\) follows.











This page was built for publication: The order type of the collection of finite series-parallel posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1874362)