4 ms·

What is the canonical ordering on the set of trees? Given how quickly the Goodstein sequence explodes, the "finite" in these cases may be very, very large...

• highergeometer 7y ago
  "An order on the set of finite rooted trees is defined recursively: we first order the subtrees joined to the root in decreasing order, and then use lexicographic order on these ordered sequences of subtrees. In this way the set of all finite rooted trees becomes a well-ordered set which is order-isomorphic to ε0." (https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)#Representation_of_'%22%60UNIQ--postMath-00000028-QINU%60%22'_by_rooted_trees https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)#...) and yes, growth rates of fast-growing functions are an important facet of this analysis. EDIT: you should think of a rooted tree as coding an ordinal written in Cantor normal form (https://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_normal_form https://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_norm...) using only ordinals less than or equal to omega. In fact, here's a nice thesis that sets it out: https://folk.uio.no/alfredb/Masteroppgave%20Alfred%20Bratterud%20v2.pdf https://folk.uio.no/alfredb/Masteroppgave%20Alfred%20Bratter...