Well-quasiordering finite trees with gap-condition. Proof of Harvey Friedman's conjecture
type: Item
instance of: scholarly article
title: Well-quasiordering finite trees with gap-condition. Proof of Harvey Friedman's conjecture
zbMATH Open document ID: 0684.05016
DOI: 10.2307/1971481
published in: Annals of Mathematics. Second Series
publication date: 1989-01-01T00:00:00Z
review text: 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.
reviewed by: Martin Weese
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 4120187
zbMATH Keywords: well-quasiordering
zbMATH Keywords: labelled tree
zbMATH Keywords: finite trees with edges labelled by ordinals
zbMATH Keywords: gap-condition
author: Igor Kriz
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.2307/1971481
OpenAlex ID: W2331677784
Wikidata QID: Q123010475
description: scientific article; zbMATH DE number 4120187