On operations and linear extensions of well partially ordered sets (Q1765955)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On operations and linear extensions of well partially ordered sets |
scientific article |
Statements
On operations and linear extensions of well partially ordered sets (English)
0 references
25 February 2005
0 references
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.
0 references
ordered set
0 references
well-founded order
0 references
partial well-order
0 references
antichain
0 references
width
0 references
rank
0 references
linear extension
0 references
tree
0 references