Order, lattices, ordered algebraic structures Definition

Well-quasi-ordering

Definition

Let $X$ be a set and let $\le$ be a preorder on $X$ . The preorder is a well-quasi-ordering when for every infinite sequence $x_1, x_2, x_3, \ldots$ of elements of $X$ there are indices $i < j$ with $x_i \le x_j$ .

Remarks

Example: every finite set with any preorder is well-quasi-ordered. Check: an infinite sequence in a finite set has $x_i = x_j$ for some $i < j$ , and then $x_i \le x_j$ by reflexivity.

Non-example: the positive integers ordered by divisibility are well-founded but not well-quasi-ordered. The sequence of primes $2, 3, 5, 7, \ldots$ has no $i < j$ with $p_i \mid p_j$ .

Equivalent form: every infinite sequence has an infinite subsequence $x_{i_1} \le x_{i_2} \le \cdots$ with $i_1 < i_2 < \cdots$ . Another equivalent form: the strict part of $\le$ is well-founded and every antichain is finite. A sequence with no $i < j$ such that $x_i \le x_j$ is called bad, so a well-quasi-ordering is a preorder with no bad sequences. The abbreviation wqo is common.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Antichain concept
Preorder concept
Sequence concept
Well-quasi-ordering definition

Tag	`PBZK2A09X4`
URI	`m2://PBZK2A09X4`
Kind	definition
Writing	W0 stub
MSC	06A06, 06A07
Defines	Well-quasi-ordering
Uses	Preorder, Sequence, Antichain

Well-quasi-ordering

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here