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

DOI10.1016/S0012-365X(02)00580-0MaRDI QIDQ1874362zbMATH OpenFDO

Authors Maurice Pouzet, Mohamed Sobrani

Publication date 25 May 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00580-0

zbMATH Keywords

ageFeferman's ordinalforestheightorder typeordinal lengthordinal numberprofilerelational structureseries-parallel posetswell-quasi-order

Mathematics Subject Classification ID

Other classical set theory (including functions, relations, and set algebra) (03E20) Partial orders, general (06A06)

Review text

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.

Recommendations

• On Better-Quasi-Ordering Countable Series-Parallel Orders
• Height of a superposition
• On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders
• Generalizing Kruskal's theorem to pairs of cohabitating trees
• Well-quasiordering finite trees with gap-condition. Proof of Harvey Friedman's conjecture
• Subrecursive Complexity of Identifying the Ramsey Structure of Posets
• The length of an intersection
• On trees and tree dimension of ordered sets
• On operations and linear extensions of well partially ordered sets
• scientific article; zbMATH DE number 3914378

Cited in

(12)

• N-free posets as generalizations of series-parallel posets
• Order varieties generated by finite posets
• Posets of finite prinjective type and a class of orders
• Series-parallel posets and relative Ockham lattices
• The setup polyhedron of series-parallel posets
• Enumeration of series-parallel posets according to heights
• On operations and linear extensions of well partially ordered sets
• On Better-Quasi-Ordering Countable Series-Parallel Orders
• The length of an intersection
• Well-quasi-ordering and Embeddability of Relational Structures
• Hereditary classes of ordered sets of width at most two
• Minimal prime ages, words and permutation graphs

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)