0. The concept

Definition. A partially ordered set $P$ is well partially ordered (wpo) if

(i) $P$ has the descending chain condition (d.c.c.), i.e., there is no infinite strictly descending chain in $P$, and

(ii) every antichain in $P$ is finite.

Examples

(a) Any well ordered chain.

(b) $\omega^n$.

(c) The set $\Omega ^ *$ of all finite words (finite sequences) from a finite alphabet $\Omega$, where ${\bf s} \leq {\bf t}$ means that ${\bf s}$ is embedded as a subsequence in ${\bf t}$; for example, $aba$ is embedded in $cacbac$. (This is a consequence of the Theorem below.)