---
tag: NH25G6GC07
kind: concept
name: Well-quasi-ordering
msc: [06A06, 06A07]
specializes: [0VABYWJWH9]
sources:
  - url: https://en.wikipedia.org/wiki/Well-quasi-ordering
same_as:
  wikidata: Q2894153
  wikipedia: Well-quasi-ordering
---

## Summary

A well-quasi-ordering is a [[preorder|0VABYWJWH9]] in which every infinite sequence $x_1, x_2, \ldots$ has indices $i < j$ with $x_i \le x_j$.
Equivalently, it is well-founded and has no infinite [[antichain|03HF498P1J]].
Well-quasi-orders give finiteness results: every upward closed set is the upward closure of finitely many of its elements.
Basic examples are $\N^k$ with the product order ([[Dickson's lemma|NQD0Q9S9M7]]), finite words under subword embedding ([[Higman's lemma|GHK66XE1S8]]) and finite trees under embedding ([[Kruskal's tree theorem|XVHKCX4F5Y]]).

## Explanations

### L1 human

In a well-quasi-order, any endless list of elements must contain an element that is below a later element.
You cannot keep writing down new elements that avoid all earlier ones.
For pairs of natural numbers ordered coordinatewise, the list $(5, 0), (4, 1), (3, 2), (2, 3), (1, 4), (0, 5)$ has no pair below a later one, but no such list can go on forever.
The positive integers under divisibility fail this: the primes $2, 3, 5, 7, \ldots$ never divide one another.