On operations and linear extensions of well partially ordered sets
The aim of the present paper is to investigate some operations and linear extensions of well partially ordered sets. In Section 1 the authors introduce some basic concepts. If \((P,\leq _{P})\) is a poset, then they denote by \(P^{*}\) the set of all finite sequences with terms in \(P\) (for an element \(t=(x_{0},x_{1},\dots,x_{n-1})\in \) \(P^{*}\), its length lh\((t)\) is \(n\) and, for all \(i\prec \text{lh}(t)\), \((t)_{i}=x_{i})\). \( P^{*}\) becomes a poset under the following two orders: \(t\subseteq s\) iff \(\text{lh}(t)\prec \text{lh}(s)\) and for all \(i\prec \text{lh}(t)\), \( (t)_{i}\leq _{P} (s)_{i}\), and \(t\subseteq ^{\prime}s\) iff there is a subsequence \(s^{\prime}\) of \(s \) with \(t\subseteq s^{\prime}\). They also construct the poset \(P^{\bigcirc }\) consisting of all weakly decreasing sequences from \(P^{*}\) with the order \(\subseteq \) inherited from \(P^{*}\). Moreover, they introduce the concepts of well-founded poset and partially well-ordered poset (in short p.w.o. set), and they establish some general results concerning these ones. In Section 2 it is shown that if \(P\) is a p.w.o. set, then \(P^{\bigcirc }\) is also a p.w.o. set. If \(P\) is a p.w.o. set, then each linear extension of \(\leq _{P}\) is a well-ordering of \(P\). Let WO\((P)\) be the family of all these extensions. Section 3 is dedicated to presenting some information on ordinals that can be achieved by elements of WO\((P)\). The main goal of Section 4 is to prove that a tree \(T\) with no antichains of size \(\mid T\mid \) has reach not much greater than its rank.
- Complexity bounds for some finite forms of Kruskal's theorem
- scientific article; zbMATH DE number 1154166 (Why is no real title available?)
- On Chains and Antichains in well Founded Partially Ordered Sets
- On Ordered Division Rings
- On well-quasi-ordering finite sequences
- Ordering by Divisibility in Abstract Algebras
- Partially well ordered sets and partial ordinals
- The theory of well-quasi-ordering: a frequently discovered concept
- Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
- Toggles of openings, and a new family of idempotent operators on partially ordered sets
- Relating subsets of a poset, and a partition theorem for WQOs
- The order type of the collection of finite series-parallel posets
- Expressivity of imperfect information logics without identity
- The automorphism conjecture for ordered sets of dimension 2 and interval orders
- Computable linearizations of well-partial-orderings
- On extensions, linear extensions, upsets and downsets of ordered sets (extended abstract)
- scientific article; zbMATH DE number 1295194 (Why is no real title available?)
- ω‐operations over partial enumerated sets
- Constrained abstract representation problems in semigroups and partial groupoids
- The length of an intersection
- Operators of equivalent sorting power and related Wilf-equivalences
- scientific article; zbMATH DE number 6257549 (Why is no real title available?)
- Topology on semi-well ordered sets
This page was built for publication: On operations and linear extensions of well partially ordered sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1765955)
