Creo que puedo afirmar con confianza que el ÁRBOL de(3) es mayor que $f_{\vartheta (\Omega^{\omega}, 0)} (n(4))$, dada una definición natural de $f$ a a $\vartheta (\Omega^{\omega}, 0)$. Puedo afirmar con certeza que el ÁRBOL de(3) es mayor que $H_{\vartheta (\Omega^{\omega}, 0)} (n(4))$, donde H es cierta la versión de los Hardy jerarquía.
Para obtener este resultado, en primer lugar definir una versión de ÁRBOL(n) para no marcado de los árboles:
Vamos árbol(n) ser la longitud de la secuencia más larga de etiqueta árboles arraigados $T_1, T_2, \ldots, T_m$ tal que $T_i$ tiene menos de o igual a $n+i$ vértices y para el no $i, j$ con $i < j$ do tenemos $T_i$ homeomorphically integrable en $T_j$. (Nota: el término "incrustada" en lugar de "subtree"; los términos son diferentes, y creo que con "subtree" daría lugar a secuencias infinitas.)
Con el fin de obtener una larga secuencia de árboles, vamos a definir un orden en la etiqueta árboles de raíces. Esta definición será por inducción sobre la suma de las alturas de los dos árboles que se compara.
Definir una inmediata subárbol de un árbol de raíces $T$ a de ser un subárbol a partir de uno de sus hijos.
Dados dos árboles arraigados $S, T$, definimos $S = T$ si los dos árboles son idénticos. Definimos $S \leq T$ si $S = T$ o $S < T$.
Dados dos árboles arraigados $S, T$, definimos $ < $ como sigue. Decir $S < T$ si $S \leq T_i$ donde $T_i$ es inmediata subárbol de $T$. Del mismo modo, decir $T < S$ si $T \leq S_i$ donde $S_i$ es inmediata subárbol de $S$.
De lo contrario, comparar el número de niños de $S$ e $T$. Si $S$ tiene más hijos que los $T$,, a continuación,$S > T$, y viceversa.
De lo contrario, supongamos $S$ e $T$ ambos tienen $n$ niños. Deje $S_1, S_2, \ldots, S_n$ e $T_1, T_2, \ldots T_n$ ser la inmediata subárboles de $S$ e $T$ respectivamente, ordenadas de menor a mayor. Compare $S_1$ a$T_1$,, a continuación, $S_2$ a $T_2$, etc., hasta que llegamos a un par de desigual árboles $S_i$ e $T_i$. Si $S_i > T_i$ entonces $S > T$, y viceversa. Por supuesto, de todos los pares de inmediato subárboles son iguales, $S$ e $T$ va a ser igual.
Esto le da un orden lineal en la etiqueta árboles de raíces, y se puede demostrar que este es un bien de orden. Además, este ordenamiento es de orden tipo de $\vartheta(\Omega^\omega,0)$. Esta definición es una modificación de un pedido de ordenada árboles de raíces debido a Levitz, y se expuso en papeles con el síndrome de Jervell.
A partir de este pedido podemos definir fundamentales de las secuencias de los números ordinales hasta el $\vartheta (\Omega^{\omega}, 0)$. Simplemente, dado un ordinal $\alpha$, vamos a $\alpha[n]$ ser el más grande ordinal menos de $\alpha$ correspondiente a un árbol de la $n$ vértices o menos.
A partir de esto, podemos definir nuestra versión de los Hardy jerarquía:
$H_0(n) = n$
$H_{\alpha + 1}( n) = H_{\alpha}( n+1)$
Para $\alpha$ un ordinal límite, $H_{\alpha}( n) = H_{\alpha[n+1]}( n+1)$
Tenga en cuenta el $n+1$'s en la última línea - esto difiere de la habitual de los valores de $n$. Por supuesto, esto sólo hará las funciones de mayor tamaño.
$H_{\alpha}( n)$ para $\alpha < \vartheta (\Omega^{\omega}, 0)$ es el índice final $m$ en la secuencia de los árboles $T_n, T_{n+1}, \ldots, T_m$ donde $T_n$ corresponde a $\alpha$ e $T_i$ es el árbol más grande con en la mayoría de las $i$ vértices que es menor que $T_{i-1}$, e $T_m$ es el árbol con un vértice. Por lo tanto $H_{\vartheta (\Omega^{\omega}, 0)}( n)$ será el último índice de $m$ en la secuencia de los árboles $T_{n+1}, T_{n+2}, \ldots, T_m$ donde $T_{n+1}$ es arbitrario.
Así árbol(n) $\geq H_{\vartheta (\Omega^{\omega}, 0)}( n) - n$.
Entonces, ¿dónde ÁRBOL(3) vendrá? Harvey Friedman mismo explica en un post a los Fundamentos de la Matemática tableros de mensajes:
http://www.cs.nyu.edu/pipermail/fom/2006-March/010260.html
En el post se explica por qué una prueba del teorema "de ÁRBOL(3) existe" en la teoría de la $ACA_0 + Pi^1_2 - BI$ debe tener más de 2^^1000 símbolos. Lo hace mostrando que el ÁRBOL(3) debe de ser muy grande - en concreto, se construye una secuencia de más de $n(4)$ árboles de raíces etiqueta de {1,2,3} tal que $T_i$ tiene más de $i$ vértices, para no $i, j$ con $i < j$ do tenemos $T_i$ homeomorphically integrable en $T_j$, y cada árbol contiene un 2 o una etiqueta 3 de la etiqueta. Podemos, por supuesto, continuar con este árbol($n(4)$) árboles con todas las etiquetas 1. Así tenemos
ÁRBOL(3) $\geq$ árbol de$(n(4)) + n(4) \geq H_{\vartheta (\Omega^{\omega}, 0)}(n(4))$
De hecho, podemos hacer algo mejor que esto, podemos reemplazar la $n(4)$ por encima de por $F(4)$ donde $F(4)$ se define como la longitud de la secuencia más larga de secuencias de $x_1, x_2, \ldots x_n$ a partir de {1,2,3,4} tal que $x_i$ tiene una longitud de $i+1$ y para el no $i,j$ con $i < j$ do tenemos $x_i$ una larga de $x_j$. Puedo ser mucho mejor de los límites para la $F(4)$ de Friedman límite inferior de $n(4)$; en concreto,
$F(4) > f_{\omega^2 + \omega + 1}f_{\omega^2 + \omega + 1}f_{\omega^2 + \omega}f_{\omega^2 + 1}f_{\omega^2 + 1}f_{\omega^2}f_{ \omega + 1}f_{ \omega + 1}f_{\omega}(30)$
Pero tal especificidad es tal vez injustificado dado lo lejos de ÁRBOL(3) puede ser.
