The order type of the collection of finite series-parallel posets
type: Item
instance of: scholarly article
title: The order type of the collection of finite series-parallel posets
zbMATH Open document ID: 1023.06001
DOI: 10.1016/S0012-365X(02)00580-0
author: Maurice Pouzet
author: Mohamed Sobrani
published in: Discrete Mathematics
publication date: 2003-05-25T00:00:00Z
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.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 03E20
zbMATH DE Number: 1915543
zbMATH Keywords: Feferman's ordinal
zbMATH Keywords: height
zbMATH Keywords: ordinal number
zbMATH Keywords: ordinal length
zbMATH Keywords: relational structure
zbMATH Keywords: well-quasi-order
zbMATH Keywords: order type
zbMATH Keywords: profile
zbMATH Keywords: forest
zbMATH Keywords: series-parallel posets
zbMATH Keywords: age
reviewed by: Egbert Harzheim
MaRDI profile type: Publication
Recommended article: On Better-Quasi-Ordering Countable Series-Parallel Orders
Recommended article: Height of a superposition
Recommended article: On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders
Recommended article: Generalizing Kruskal's theorem to pairs of cohabitating trees
Recommended article: Well-quasiordering finite trees with gap-condition. Proof of Harvey Friedman's conjecture
Recommended article: Subrecursive Complexity of Identifying the Ramsey Structure of Posets
Recommended article: The length of an intersection
Recommended article: On trees and tree dimension of ordered sets
Recommended article: On operations and linear extensions of well partially ordered sets
Recommended article: Q3691785
description: scientific article; zbMATH DE number 1915543