No edit summary |
Loller of lols (talk | contribs) mNo edit summary Tags: Visual edit apiedit |
||
Line 3: | Line 3: | ||
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: |
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 |
+ | * Vertex x ≤* y if ''x'' is to the left of ''y'', or if x ≤ y. |
* d(v) is the position of ''v'' in counting from 1. |
* d(v) is the position of ''v'' in counting from 1. |
||
Revision as of 03:43, 22 June 2017
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 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
- Friedman, Harvey. Enormous Integers in Real Life
See also
Main article: Harvey Friedman
Mythical tree problem · Friedman's vector reduction problem · Friedman's finite ordered tree problem · block subsequence theorem n(4) · Friedman's circle theorem · TREE sequence TREE(3) · subcubic graph number SCG(13) · transcendental integer · finite promise games · Friedman's finite trees · Greedy clique sequence · Bop-counting function