Well-quasiordering finite tees with gap-condition. Proof of Harvey Friedman’s conjecture

Abstract

Let $s,t$ be trees with edges labelled by ordinals. We say that $s$ is less-or-equal t $t$ with respect to the gap-condition if $s$ can be embdded into $t$ so that each edge is mapped onto a path consisting of edges with greater-or-equal labels. We show that finite trees are well-quasiordered with respect to the gap-condition. This solves a problem posed by Harvey Friedman.

Authors

Igor Křiž