Return to Answer

Comment on the answer by "Deedlit":

Comment on the answer by "Feldman Denis":

Comment on the answer by "Deedlit":

Comment on the answer by "Feldman Denis":

Actually, we can do even better (although these may be relatively "small" adjustments) ... Specifically, by playing with various ways to start a long embedding-free sequence, one can do better than the one shown below constructed by Friedman, but still using his method of coding $n()$- or $F()$-type longest word-sequences via certain subtrees. For example, one can find sequences that demonstrate (in Deedlit's notation)

$N \ = \ F_{\omega}^3 \\ F_{\omega+1} \ F_{\omega}^2 \ F(4)$

with $F_\alpha$ being a fast-growing hierarchy that begins with $F_0 = F$ (rather than beginning with $F_0(x) = x+1$). I've posted a very terse derivation-sketch of this result.

Rather than "is not a subtree of", that should be "is not homeomorphically embedded in", which is a very much more stringent requirement. (There might not even exist a longest such sequence in the less-stringent case. A similar situation occurs for Friedman's $n()$ function -- in that case, the relation "is not a subsequence of" is more stringent than "is not a substring of" -- there being no longest sequence in the latter case.) With this correction, and by starting with $T_2$, the length of the resulting sequence will of course be TREE(3) - 1.

BTW, a convenient representation of TREE(3) uses nested bracket expressions (well-formed in the usual way with pairs of matching brackets) involving only three bracket-types -- say (),[],{} -- each rooted tree being uniquely represented by a nest of such brackets (up to isomorphism with respect to sibling order). TREE(3) is then the length of a longest sequence $(T_1,T_2,T_3,T_4,…,T_n)$ of nests such that each $T_k$ has at most $k$ bracket pairs and for no $i \lt j$ is $T_i$ embedded in $T_j$. Here $X$ is embedded in $Y$ means that $X$ can be obtained from $Y$ by erasing zero or more matching bracket-pairs.

(Note that, because $T_1$ must be some single bracket pair which cannot then appear in any later nest in an embedding-free sequence, an equivalent definition is obtained by assuming $T_1=\ ${}, so TREE(3) is one greater than the length of a longest embedding-free sequence $(T_2,T_3,T_4,…,T_n)$ (starting with index 2) of nests formed as before but using only two bracket types (),[].)

Another thing to note is that TREE(3) assumes rooted trees with unordered siblings, so, for example, the nests ([]()) and (()[]) are not regarded as distinct. Some authors have treated wqo's for rooted trees with ordered siblings, with corresponding "longest sequence" results.

Actually, we can do even better, although these may be relatively "small" adjustments: by playing with various ways to start a long embedding-free sequence, one can improve upon the sequence constructed by Friedman (displayed below), but still using his method of coding $n()$- or $F()$-type longest word-sequences via certain subtrees. For example, one can find sequences that demonstrate (in Deedlit's notation)

$N \ = \ F_\omega F_\omega F_\omega F_{\omega+1} F_\omega F_\omega \ F(4)$

with $F_\alpha$ being a fast-growing hierarchy that begins with $F_0 = F$, rather than beginning as usual with $F_0(x) = x+1$. (Friedman showed that $F$ eventually dominates every $f_{\lt \omega^\omega}$ in the usual fast-growing hierarchy.)

I've posted a very terse derivation-sketch of this result.

Rather than "is not a subtree of", that should be "is not homeomorphically embeddable into", which is a very much more stringent requirement. (There might not even exist a longest such sequence in the less-stringent case. A similar situation occurs for Friedman's $n()$ and $F()$ functions concerning word-sequences: these use "is not a subsequence of" rather than the less-stringent "is not a substring of", there being no longest word-sequence in the latter case.) With this correction, and by starting with $T_2$, the length of the resulting sequence will of course be TREE(3) - 1.

A convenient way of representing these trees is to use nested bracket expressions (well-formed in the usual way with pairs of matching brackets) involving only three bracket-types -- say (),[],{} -- each tree being uniquely represented by a nest of such brackets (up to isomorphism with respect to sibling order). A lower bound on TREE(3) is then the length of a longest sequence $(X_1,X_2,…,X_n)$ of nests such that each $X_k$ has at most $k$ bracket pairs and no $X_i$ is embedded in a later $X_j$, where $X$ is embedded in $Y$ means that $X$ can be obtained from $Y$ by erasing zero or more pairs of matching brackets. (Thus, if $X$ is not embedded in $Y$, then the tree represented by $X$ is not inf-and-label-preserving embeddable into the tree represented by $Y$; the converse, however, does not hold.)

Because $X_1$ must be some single bracket-pair which cannot then appear in any later nest in an embedding-free sequence, it may be assumed that $X_1=\ ${}, with all later nests using only the two bracket-types (),[]. Also, note that TREE(3) concerns trees with unordered siblings, so, for example, the nests ([]()) and (()[]) are not regarded as distinct. (Some authors have treated wqo's for rooted trees with ordered siblings, with corresponding "longest sequence" results.)

$N \ = \ F_{\omega}^3 \\ F_{\omega+1} \ {F_\omega}^2 \ F(4)$

with $F_\alpha$ being a fast-growing hierarchy that begins with $F_0() = F()$ (rather than beginning with $F_0(x) = x+1$).

$N \ = \ F_{\omega}^3 \\ F_{\omega+1} \ F_{\omega}^2 \ F(4)$

with $F_\alpha$ being a fast-growing hierarchy that begins with $F_0 = F$ (rather than beginning with $F_0(x) = x+1$). I've posted a very terse derivation-sketch of this result.