Well-quasiordering finite trees with gap-condition. Proof of Harvey Friedman's conjecture (Q1825201): Difference between revisions

Let E denote the class of all triples \((V_ t,\leq,e_ t)\), where \((V_ t,\leq)\) is a finite tree and \(e_ t\) is a function from the edges into the ordinals, i.e., E is the class of all finite trees with edges labelled by ordinals. For \(s,t\in E\), s is less-or-equal to t with respect to the gap-condition if s can be embedded into t so that each edge is mapped onto a path consisting of edges with greater-or-equal labels. The author shows that the class E with respect to this ordering is well- quasiordered. This solves a conjecture of H. Friedman and generalizes a result of Simpson that finite trees with labels bounded by a natural number are well-quasiordered.