If is a well-quasi-ordering, its finite words form a well-quasi-ordering under subsequence embedding with coordinatewise increase of letters. A minimal bad sequence proof removes the last letter of selected words whose last letters form a nondecreasing subsequence, then contradicts minimality. The result implies finite-subset lifting of a well-quasi-order under Hoare domination preorder.
Higman's lemma is a result in combinatorial mathematics, specifically in the area of order and partially ordered sets (posets). It states that if \( A \) is a finite set of words over a finite alphabet, then there exists a finite set of lists (i.e.
New to topics? Read the docs here!