Tipo de orden del conjunto más pequeño que contiene la función identidad y cerrado bajo exponenciación.

Question

Sea $E$ sea el conjunto más pequeño de funciones $\mathbb{N}^+\to\mathbb{N}^+$ que contiene la función de identidad $n \mapsto n$ y cerrado bajo exponenciación $(f,g) \mapsto \left(n \mapsto f(n)^{g(n)}\right)$ es decir $E=\{n \mapsto n, n \mapsto n^n, n \mapsto n^{n^n}, n \mapsto (n^n)^n, n \mapsto (n^n)^{n^n},\ \dots\}$ . Sea $E$ ordenarse por una eventual dominación.

Es $E$ ¿Bien ordenado? ¿Cuál es el mínimo ordinal que no puede estar incluido en $E$ ?

Answer 1

Como Joel mostró, el conjunto $E$ está bien ordenado con un tipo de orden no mayor que el ordinal de Cantor $\epsilon_0$ . De hecho, su tipo de orden es exactamente $\epsilon_0$ . Esto puede demostrarse construyendo el isomorfismo de orden entre $\epsilon_0$ y $E$ .

En primer lugar, tenga en cuenta que si $F,G\in E$ son de la forma $F(n)=n^{n^{f(n)}}$ , $G(n)=n^{n^{g(n)}}$ entonces $F^G$ es también de la forma $n\mapsto n^{n^{h(n)}}$ donde $h(n) = f(n)+n^{g(n)}$ . Así pues, permítanme definir $E^\prime$ sea el subconjunto más pequeño de $\mathbb{N}^{\mathbb{N}}$ que contiene la función cero $n\mapsto0$ y tal que para cualquier par $f,g\in E^\prime$ entonces la función $n\mapsto f(n)+n^{g(n)}$ está en $E^\prime$ . Entonces el mapa que toma $f\in E^\prime$ a $n\mapsto n^{n^{f(n)}}$ es un isomorfismo de orden de $E^\prime$ a $E$ .

Ahora definiré un mapa $\theta\colon\epsilon_0\to E^\prime$ y demostrar que es un isomorfismo de orden. En Forma normal de Cantor cualquier ordinal $\alpha < \epsilon_0$ puede escribirse unívocamente como $\alpha=\omega^{\beta_1}+\cdots+\omega^{\beta_k}$ para ordinales $\beta_1\ge\cdots\ge\beta_k$ menos de $\alpha$ . Escribe, $$ \theta(\alpha)(n)=n^{\theta(\beta_1)(n)}+\cdots+n^{\theta(\beta_k)(n)}. $$ Esto define $\theta(\alpha)$ en términos de sus valores en ordinales menores. Obsérvese que si $k=0$ entonces $\theta(\alpha)=0$ está en $E^\prime$ . Por otra parte, si $k\ge1$ entonces $\alpha = \omega^{\beta_1}+\gamma$ para ordinales $\beta_1,\gamma < \alpha$ y, $$ \theta(\alpha)(n)=n^{\theta(\beta_1)(n)}+\theta(\gamma)(n). $$ Así que $\theta(\alpha)$ está en $E^\prime$ siempre que $\theta(\beta_1)$ y $\theta(\gamma)$ son. La inducción transfinita define entonces $\theta\colon\epsilon_0\to E^\prime$ .

Para demostrar que $\theta$ es onto, basta con demostrar que para dos ordinales cualesquiera $\alpha,\gamma < \epsilon_0$ entonces $n\mapsto\theta(\alpha)(n)+n^{\theta(\gamma)(n)}$ también es imagen de $\theta$ . Escriba a $\alpha$ en la forma normal de Cantor como antes, y sea $\tilde\beta_1\ge\cdots\ge\tilde\beta_{k+1}$ sean los ordinales $\beta_1,\ldots,\beta_k,\gamma$ dispuestos en orden decreciente. Configuración $\tilde\alpha=\omega^{\tilde\beta_1}+\cdots+\omega^{\tilde\beta_{k+1}}$ , $$ \theta(\tilde\alpha)(n)=n^{\theta(\tilde\beta_1)(n)}+\cdots+n^{\theta(\tilde\beta_{k+1})(n)} =\theta(\alpha)(n)+n^{\theta(\gamma)(n)}. $$ Así que.., $\theta$ es un mapa suryectivo de $\epsilon_0$ a $E^\prime$ .

Sólo queda por demostrar que $\theta$ preserva (estrictamente) el orden. Demostraré que si $\alpha > \gamma$ son ordinales, entonces $\theta(\alpha)(n) > \theta(\gamma)(n)$ para grandes $n$ . Por inducción, se puede suponer que esto es cierto siempre que $\alpha,\gamma$ se sustituyen por valores más pequeños. De nuevo, utilizando la forma normal de Cantor, $$ \alpha=\omega^{\beta_1}+\cdots+\omega^{\beta_k}, \gamma=\omega^{\tilde\beta_1}+\cdots+\omega^{\tilde\beta_j} $$ donde $\beta_1\ge\cdots\ge\beta_k$ y $\tilde\beta_1\ge\cdots\ge\tilde\beta_j$ . Dejar $i$ sea el menor número tal que uno de $\beta_i\not=\tilde\beta_j$ , $i > j$ o $i > k$ se mantiene entonces, ya que $\alpha > \gamma$ tenemos $i\le k$ y $\beta_i > \tilde\beta_r$ para todos $r=i,\ldots,j$ . Entonces, $$ \theta(\alpha)(n)-\theta(\gamma)(n)\ge n^{\theta(\beta_i)(n)}-n^{\theta(\tilde\beta_i)(n)}-\cdots-n^{\theta(\tilde\beta_j)(n)}. $$ Si $j < i$ entonces el lado derecho es simplemente $n^{\theta(\beta_i)(n)}$ . Por otra parte, si $j\ge i$ entonces, utilizando la hipótesis de inducción, $n^{\theta(\beta_i)(n)}/n^{\theta(\tilde\beta_r)(n)}\to\infty$ para $r\ge i$ por lo que el lado derecho tiende a infinito. En cualquier caso, $\theta(\alpha)(n) > \theta(\gamma)(n)$ para grandes $n$ .

Answer 2

Esta es una respuesta parcial, y en parte no estoy seguro.

Afirmo que estas funciones están bien ordenadas por eventuales dominación, y el tipo de orden es como máximo el ordinal $\epsilon_0$ .

En primer lugar, su colección de funciones puede identificarse con la etiqueta términos unarios que las originan, los términos unarios del álgebra en el lenguaje que ha presentado, términos con una variable libre libre $n$ en el lenguaje con sólo la exponenciación binaria binaria. Ejemplos de estos términos son las expresiones que aparecen en tu pregunta.

$$(n^n)^n\ \ \ \ \ (n^{n^n})^{n^n}\ \ \ \ \ n^{n^n}\ \ \ \ \ (n^{n^n})^{n^{n^n}}$$

A cualquier expresión de este tipo $f(n)$ podemos asociarle el ordinal $f(\omega)$ que se obtiene sustituyendo la variable $n$ con el ordinal $\omega$ e interpretando la expresión resultante mediante el sitio aritmética natural sobre ordinales, en lugar de la aritmética habitual. Es decir, resolvemos $(a^b)^c$ como $a^{b\mathop{\sharp}c}$ utilizando el producto natural $b\mathop{\sharp} c$ que es una versión conmutativa de la multiplicación ordinal.

$$(\omega^\omega)^\omega\ \ \ \ \ (\omega^{\omega^\omega})^{\omega^\omega}\ \ \ \ \ \omega^{\omega^\omega}\ \ \ \ \ (\omega^{\omega^\omega})^{\omega^{\omega^\omega}}$$

Todos estos ordinales resultantes tienen una exponencial finitaria finitaria mediante $\omega$ y, por tanto, son inferiores a épsilon nada $\epsilon_0$ .

Afirmo que esta correspondencia respeta la dominación eventual; en otras palabras, la función dada por el término $f(n)$ es finalmente dominada por la función dada por el término $g(n)$ sólo si $f(\omega)\lt g(\omega)$ interpretado en aritmética ordinal natural. (Nota: la razón para utilizar la multiplicación simétrica surge del hecho de que $(\omega^{\omega})^{\omega^\omega}=\omega^{\omega^{1+\omega}}=\omega^{\omega^\omega}$ con la aritmética ordinal habitual, aunque $(n^n)^{n^n}$ domina $n^{n^n}$ ; pero la aritmética ordinal natural da aquí la respuesta correcta). Esta afirmación tiene afinidad con el análisis habitual de la representación de los ordinales $\epsilon_0$ en términos de base (hereditaria) $n$ como utilizado en Teorema de Goodstein . Básicamente, el eventual orden de dominación viene determinado por lo que podría llamarse altura de la pila de la expresión del término, y una reduce inductivamente a comparar los términos que surgen como coeficientes de esa pila más alta. El valor de una expresión expresión exponencial de $\omega$ se determina exactamente en el mismo modo, por lo que estos dos órdenes coinciden.

Si esto es correcto, entonces el eventual orden de dominación es en efecto un y el tipo de orden es como máximo $\epsilon_0$ como yo afirmaba.

En cuanto a si el tipo de orden alcanza $\epsilon_0$ o no, estoy no estoy seguro, pero sospecho que es estrictamente menos que $\epsilon_0$ . La razón es que los ordinales $f(\omega)$ se enfrentan a una grave restricción en su representación en base completa $\omega$ . La complicación es que no todos los ordinales surgen como $f(\omega)$ para un término de su álgebra. Por ejemplo, el ordinal $\omega^2\cdot 4+\omega^3\cdot99$ es inferior a $\epsilon_0$ pero no surge como ordinal $f(\omega)$ para cualquier término de su álgebra. Los ordinales $f(\omega)$ parecen estar restringidos en su complejidad, por lo que es concebible que el tipo de orden total sea inferior a $\epsilon_0$ . No obstante, es posible obtener algunos coeficientes de números naturales que aparecen, como con

$$(\omega^\omega)^\omega=\omega^{\omega^2}\ \ \ \text{ and }\ \ (\omega^{\omega^2})^\omega=\omega^{\omega^3},$$

que surgen como ordinales de los términos correspondientes. Quizás si uno puede filtrar este fenómeno hacia arriba para obtener una base hereditaria arbitraria $n$ expresiones eventualmente altas en los exponentes, entonces el tipo de orden será $\epsilon_0$ .

Mientras tanto, permítanme mencionar que si uno tuviera un álgebra un poco más generoso, lo que permite la suma y las constantes de los números naturales (que surgirían de la función cero mediante $1=\omega^0$ ), entonces el tipo de orden sería totalmente $\epsilon_0$ ya que todo ordinal inferior a $\epsilon_0$ surgiría como $f(\omega)$ para un término correspondiente en el álgebra de forma completamente natural.