Editing Well-quasi-ordering (section)

==Ordinal type==

Let <math>X</math> be well partially ordered. A (necessarily finite) sequence <math>(x_1, x_2, \ldots, x_n)</math> of elements of <math>X</math> that contains no pair <math>x_i \le x_j</math> with <math>i< j</math> is usually called a ''bad sequence''. The ''tree of bad sequences'' <math>T_X</math> is the tree that contains a vertex for each bad sequence, and an edge joining each nonempty bad sequence <math>(x_1, \ldots, x_{n-1}, x_n)</math> to its parent <math>(x_1, \ldots, x_{n-1})</math>. The root of <math>T_X</math> corresponds to the empty sequence. Since <math>X</math> contains no infinite bad sequence, the tree <math>T_X</math> contains no infinite path starting at the root.{{cn|reason=This is far from being obvious, and requires a (reference to a) proof.|date=February 2024}} Therefore, each vertex <math>v</math> of <math>T_X</math> has an ordinal height <math>o(v)</math>, which is defined by transfinite induction as <math>o(v) = \lim_{w \mathrm{\ child\ of\ } v} (o(w)+1)</math>. The ''ordinal type'' of <math>X</math>, denoted <math>o(X)</math>, is the ordinal height of the root of <math>T_X</math>.

A ''linearization'' of <math>X</math> is an extension of the partial order into a total order. It is easy to verify that <math>o(X)</math> is an upper bound on the ordinal type of every linearization of <math>X</math>. De Jongh and Parikh<ref name="dejongh_parikh">{{cite journal |last1=de Jongh |first1=Dick H. G. |last2=Parikh |first2=Rohit |title=Well-partial orderings and hierarchies |journal=Indagationes Mathematicae (Proceedings) |date=1977 |volume=80 |issue=3 |pages=195–207 |doi=10.1016/1385-7258(77)90067-1|doi-access=free }}</ref> proved that in fact there always exists a linearization of <math>X</math> that achieves the maximal ordinal type <math>o(X)</math>.