The order type of the collection of finite series-parallel posets (Q1874362)

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.