6 votos

¿Hay una "solución" al juego ordinal?

A pesar de que yo casi no tiene antecedentes en la lógica, me parece la idea de ordinal notación bastante interesante. Parece que la idea es llegar con la notación para definir más y más números, hasta que su notación es agotado, en el que caso de que usted realice un nuevo símbolo a ser el número más pequeño que no se puede definir (supremum). A continuación, se repite este proceso. Así que ir a $1,2,...$ que se agota por lo que acaba de declarar $\omega$. Luego de llegar a la torre de $\omega^\omega, \omega^{\omega^\omega},...$ que se agota y se declara $\epsilon_0$. Entonces por lo que entiendo, usted puede ir a través de la Veblen jerarquía de conseguir nuevos números con el Veblen funciones de $\phi_\beta$ hasta que se agota y se obtiene el Feferman–Schütte ordinal $\Gamma_0$. Y sigue adelante con el pequeño Veblen ordinal, gran Veblen ordinal, Bachmann-Howard ordinal, etc. Creo que va en como esta, que nunca llegan más allá de la Iglesia–Kleene ordinal.

Creo que mi pregunta es, básicamente, si hay una forma sistemática de nombramiento de todos los ordinales hasta la Iglesia–Kleene ordinal. Parece que el camino va esto, estamos al final va a ejecutar de las personas a nombre de los ordinales después. O es el punto de que no importa cuán poderoso de un sistema que se piensa que tiene, siempre se puede definir al menos ordinal que no puede ser nombrado por el sistema, en cuyo caso se puede continuar? Así que no hay manera de saltar a la "final" de este proceso?

8voto

ManuelSchneid3r Puntos 116

La respuesta (como era de esperar) depende de lo que quieres decir por "de manera sistemática." A pesar de $\omega_1^{CK}$ no tiene computable descripción, y así no "computable sistema de notación" va a llegar al camino de $\omega_1^{CK}$ (esto puede ser hecho preciso y probado), hay otras maneras de describir los números ordinales. Por ejemplo, cualquier $\alpha<\omega_1^{CK}$ tiene un número natural $n_\alpha$ asignado a la misma, a saber, el menos Kleene la notación correspondiente. Este es un perfectamente bien definidos descripción de $\alpha$; ¿ que cuentan?

De hecho, el mapa de $n:\omega_1^{CK}\rightarrow\omega:\alpha\mapsto n_\alpha$ resulta ser "tan simple como sea posible" en un sentido preciso, y a través de esta simplicidad juega un papel importante en metarecursion teoría (= $\omega_1^{CK}$-la teoría de la recursividad). Así que no es frívola al señalar que es "demasiado complicado" definibles por - que en realidad es algo que importa!

Por otro lado, $\omega_1^{CK}$ no es la verdadera barrera: el problema es que, dada cualquier razonable descriptivo marco, habrá contables ordinales no se puede describir de esa manera, simplemente porque hay una cantidad no numerable de contables de los números ordinales y sólo countably muchas descripciones. "El menor ordinal no se describe por el sistema de $S$" va a ser una perfecta definición razonable de un ordinal, siempre que $S$ es perfectamente razonable descriptivo marco, pero claramente no puede ser parte de $S$ sí.

Por otro otro lado, la palabra "razonable" está haciendo un trabajo serio allí. Hay un sentido preciso en el que es posible que cada contables ordinal (de hecho, cadacosa en absoluto) es de primer orden definible en el universo. La razón de esto no conducirá inmediatamente a una explosión es que "(sin restricciones) definability (dentro de todo el universo) no es definible", y un análisis de esta extraña situación se puede encontrar aquí.

2voto

SSequence Puntos 86

"¿Hay algún sentido en el que incluso a pesar de que cualquier sistema de notación no puede llegar a $ω_{CK}$, existe una jerarquía de los sistemas de notación, de modo que cuando usted toma de la "unión", de hacer llegar?"

En un cierto sentido preciso, la respuesta a esto está en negativo (en un sentido trivial. Pero es un estándar de hecho, sin embargo.

Por ejemplo, supongamos que tenemos una función computable cuya salida se interpreta como el índice de los programas de codificación bien las órdenes de $\mathbb{N}$. Así, por ejemplo, supongamos que un número $x\in \mathbb{N}$ representa el índice de un programa (de $\mathbb{N}^2$ a $\{0,1\}$) que describe un orden (de $\mathbb{N}$) con el fin de tipo $\alpha \in \omega_{CK}$. Luego dicen que escribimos $[x]=\alpha$ para indicar este hecho. Si $x$ no describe bien el fin de, a continuación, supongamos que escribes $[x]=\omega_{CK}$. (Yo sólo arbitrariamente dug-esta $[x]$ terminología, no es estándar, o cualquier cosa)

Ahora tenemos una versión más precisa de la declaración anterior. Decimos que para cada función computable $f:\mathbb{N} \rightarrow \mathbb{N}$ si se cumple la condición siguiente:

para todos los $x\in \mathbb{N}$, tenemos $[f(x)]<\omega_{CK}$

A continuación, debemos tener:

$\mathrm{sup}\,\{\,[f(x)]\,:\,x \in \mathbb{N}\}<\omega_{CK}$

La prueba de esto es bastante fácil de curso.


Una versión determinada de esto también se debe mantener para $\mathcal{O}$ creo (no estoy muy familiarizado con esto de una buena manera, aunque). En el sentido de que para cada función computable $f:\mathbb{N} \rightarrow \mathbb{N}$ si se satisface la condición:

para todos los $x\in \mathbb{N}$, tenemos $f(x) \in \mathcal{O}$ e $|f(x+1)|_{\mathcal{O}}>|f(x)|_{\mathcal{O}}$

A continuación, debemos tener: $\mathrm{sup}\,\{\,|f(x)|_{\mathcal{O}}\,:\,x \in \mathbb{N}\}<\omega_{CK}$

Esto realmente sigue directamente de la definición misma de $\mathcal{O}$, junto con el resultado(s) (realmente necesito para el estudio de estos en algún momento) en que se describe el hecho de que el conjunto de los números ordinales descrito por $\mathcal{O}$ son precisamente los que están por debajo de $\omega_{CK}$.

No sé si la condición de $|f(x+1)|_{\mathcal{O}}>|f(x)|_{\mathcal{O}}$ se puede quitar o no (supongo que yo soy muy tonto para no saber esto).


Hay un poco forma alternativa de mirar a su pregunta. Cada función normal $f:\omega_1 \rightarrow \omega_1$ ha $\omega_1$ muchos puntos fijos. En el estándar de la teoría de conjuntos, sin duda cierto en virtud de la elección (no comentar sobre el caso no estoy completamente seguro acerca de). En particular, podemos suponer que tenemos una (total) de la función de $F:\omega_1 \rightarrow \omega_1$ enumeración de puntos fijos de $f$.

Ahora, como de costumbre, creo que podemos cambiar a una versión explícitos de $F$ en el sentido de que: $(1)$ Definir $F(0)$ $(2)$ Definir $F(x+1)$ en términos de $F(x)$ $(3)$ Definir $F(x)$ para algún valor límite de $x$. Por ejemplo, siguiendo este esquema, las siguientes fórmulas, creo, debe ser una descripción precisa de $F$:

$(1)$ $F(0)=\mathrm{sup}\{\,f^n(0):n \in \mathbb{N}^+\}$

$(2)$ $F(x+1)=\mathrm{sup}\{\,f^n(F(x)+1):n \in \mathbb{N}^+\}$

$(3)$ Cuando $x$ es un límite que hemos: $F(x)=\mathrm{sup}\{\,F(\alpha): \alpha<x\}$

Hay un punto interesante en todo esto. Si hay un fijo computable descripción (debe hacerse un poco más preciso) de la orden de $f(x+1)$ en términos de bien-orden de $f(x)$, e $\alpha<\omega_{CK}$, $f(0)<\omega_{CK}$, entonces podemos mostrar de manera explícita que $F(\alpha)<\omega_{CK}$.

Esto es muy relevante desde el punto de vista de esta pregunta. En el muy menos, esto ya se asegura de que siempre que una función normal $f$ es de cierta forma (creo que las condiciones en las $f$ puede ser más relajado) esto garantiza que $F(0)<\omega_{CK}$ \begin{array}{ccc} \ N&A&B \\ 0&0&0 \\ &2&4 \\ \\ 1&0&1 \\ &3&4 \\ \\ 2&0&2 \\ 3&0&3 \\ &1&2 \\ &4&5 \\ \\ 4&0&4 \\ 5&0&5 \\ &2&3 \\ \end$F(0)$ ser el primero de punto fijo de $f$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X