Editing Well-quasi-ordering (section)

==Properties of wqos==

* Given a quasiordering <math>(X,\le)</math> the quasiordering <math>(P(X), \le^+)</math> defined by  <math> A \le^+ B \iff \forall a \in A, \exists b \in B, a \le b</math> is well-founded if and only if <math>(X,\le)</math> is a wqo.<ref name="forster"/>
* A quasiordering is a wqo if and only if the corresponding partial order (obtained by quotienting by <math>x \sim y \iff x\le y \land y \le x</math>) has no infinite descending sequences or [[antichain]]s. (This can be proved using a [[Ramsey theory|Ramsey argument]] as above.)
* Given a well-quasi-ordering <math>(X,\le)</math>, any sequence of upward-closed subsets <math>S_0 \subseteq S_1 \subseteq \cdots \subseteq X</math> eventually stabilises (meaning there exists <math>n \in \N</math> such that <math>S_n = S_{n+1} = \cdots</math>; a subset <math>S \subseteq X</math> is called ''upward-[[closure (mathematics)|closed]]'' if <math>\forall x,y \in X, x \le y \wedge x \in S \Rightarrow y \in S</math>): assuming the contrary <math>\forall i \in \N, \exists j \in \N, j > i, \exists x \in S_j \setminus S_i</math>, a contradiction is reached by extracting an infinite non-ascending subsequence.
* Given a well-quasi-ordering <math>(X,\le)</math>, any subset <math>S</math> of <math>X</math> has a finite number of minimal elements with respect to <math>\le</math>, for otherwise the minimal elements of <math>S</math> would constitute an infinite antichain.