Well-Quasiordering Finite Trees with Gap-Condition. Proof of Harvey Friedman's Conjecture

Igor Kříž

Annals of Mathematics · 1989 · 20 citations · 3 references

Concepts

Abstract

Let s, t be trees with edges labelled by ordinals. We say that s is less-or-equal to t with respect to the gap-conditon if s can be embedded 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.

References

3