FANDOM


The finite ordered tree problem was researched by Harvey Friedman.

Friedman defines an ordered tree as a triple (V,≤,<') where (V,≤) is a finite poset with a least element (root) in which the set of predecessors under ≤ of each vertex is linearly ordered by ≤, and where for each vertex, <' is a strict linear ordering on its immediate successors. He also defines the following:

  • Vertex x ≤* y if and only if x is to the left of y, or if x ≤ y.
  • d(v) is the position of v in counting from 1.

He then defines T[k] to be the tree of height k such that every vertex v of height ≤k - 1 has exactly d(v) children, and |T[k]| to be number of children.

Friedman has proven that |T[k]| has a similar growth rate to that of the Ackermann function. The first few values are as follows:

  • |T[0]| = 1
  • |T[1]| = 2
  • |T[2]| = 4
  • |T[3]| = 14
  • |T[4]| > 243
  • |T[5]| > 2↑↑2295

References Edit

See also Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.