Ejemplos de declaraciones con una alta complejidad cuantificadora

Question

¿Cuáles son algunas de las propiedades naturales, definiciones y declaraciones que requieren muchos alternando los cuantificadores?

La complejidad puede ser $Π^0_k$, $Π^1_k$, $Π^V_k$, o algo completamente distinto, siempre $k$ no es demasiado pequeño, y la declaración es naturalmente visto por un determinado $k$, frente a una parte de un esquema que funciona independiente de $k$. Más oscuro/complicado ejemplos requieren un mayor $k$ a calificar.

He aquí cinco ejemplos:

• Definición/existencia de un límite (y muchos conceptos relacionados) es $Π^0_3$-completa. (Además, no debe ser natural $Σ^0_4$/$Π^0_4$-completa las propiedades relacionadas con los límites, pero realmente no los he encontrado en ellos-excepto para el siguiente elemento).

• Suponemos que la existencia de una $n^{1+o(1)}$ algoritmo para una decisión determinada problema es $Σ^0_4$completo (incluso si el problema está en P y codificados como tales).

• "Cada conjunto cerrado es la unión de un contable y un conjunto perfecto" es $Π^1_3$ (equivalente a $Π^1_1-\mathrm{CA}_0$ sobre $\mathrm{RCA}_0$).

• El axioma de elección es $Π^1_4$ conservador más de ZF (pero sin grandes cardenal axiomas, no es $Σ^1_4$ conservador).

• La existencia de una clase adecuada de estirable cardenales es $Π^V_5$.

De primer orden de la lógica permite a un número arbitrario de cuantificadores, pero que no sea a través de esquemas (que a menudo puede ser visto como una aproximación a una sola orden superior cuantificador), la práctica de matemáticas rara vez se utiliza muchas alternando los cuantificadores. Tan raramente que los cuantificadores no se formalizaron en una forma general hasta la segunda mitad del siglo 19. La alta cuantificador de la complejidad de los límites de lo que es esencialmente la razón por la que los límites no se define formalmente hasta después de mucho de análisis matemático fue desarrollado. Sin embargo, 'rara vez' no quiere decir 'nunca', y la pregunta es identificar algunas de las excepciones.

Actualización: Aquí hay tres ejemplos más:

• Si $f(x)$ es continuamente diferenciable en $x_0$ es $Σ^0_4$-completa. Por el contrario, la diferenciabilidad en $x_0$ o continuo de la diferenciabilidad en $(a,b)$ es $Π^0_3$.

• Dada una contables espacio métrico (codificado por una enumeración de todos los puntos y las distancias) que se nos promete es localmente completo (o), si el espacio es localmente compacto es $Π^0_5$-completa. Tenga en cuenta que un espacio métrico es localmente compacto si es localmente completo (que para los contables de los espacios es $Π^1_1$completo) y cada punto tiene un totalmente delimitada barrio (que para los contables de los espacios es $Π^0_5$-complete).

• En la teoría de conjuntos, "$κ$ es inefable" es $Π^1_3$ en el segundo orden de la lógica de $V_κ$.

Answer 1

Mi ejemplo favorito es el 5-cuantificador definición de un casi-periódicas de la función: $f$ es casi-periódicas de la fib $$\forall \epsilon>0\, \exists t>0\ \forall a\ \exists s \in [a,a+t]\ \forall x\, |f(x+s)-f(x)| \leqslant \epsilon.$$

Utilizando el hecho de que casi el periódico de funciones uniformemente continuas, se puede demostrar que esto es equivalente a un 3-cuantificador de la propiedad. El 5-cuantificador definición sigue siendo el más natural, especialmente para el propósito de afirmar lo anteriormente hecho.

Para Bohr el teorema de que todos los casi-periódicas de la función arbitrariamente buena appropximations por trigonométricas polinomios es, naturalmente, escrito como una 6-cuantificador declaración.

PS Gracias a @FrancoisZiegler y @DmytroTaranovsky para la clasificación de mí en esto.

Answer 2

Considere la declaración:

• "Ninguno de los dos jugadores tiene una estrategia ganadora en el juego de Tic-tac-dedo del pie."

Esta es una forma natural de declaración, afirma a menudo, y creyó, y la mayoría de formulación naturales de los que se ha complejidad $\Sigma_9\wedge\Pi_9$.

Para estar seguro, las declaraciones acerca de estrategias de juego a menudo, generalmente implican una muy alta cuantificador complejidad. La afirmación de que el jugador I tiene una estrategia ganadora en el juego de la longitud de la $k$, después de todo, es más, naturalmente, de un $\Sigma_k$ afirmación, de la forma:

"Hay un movimiento para el jugador I, tal que para cualquier respuesta, hay un paso más para el jugador I, tal que para cualquier respuesta, hay un paso más,... después de que jugador que ha ganado el juego."

En el caso de tic-tac-dedo del pie, el juego tiene más de nueve movimientos, y así tenemos nueve cuantificadores en la declaración. La afirmación de que ninguno de los dos jugadores tiene una estrategia ganadora es equivalente, por el teorema fundamental de finito de juegos, a la afirmación de que ambos jugadores tienen el dibujo de las estrategias.

Más juegos de forma natural dar lugar a afirmaciones con aún más cuantificadores. Por ejemplo, la declaración correspondiente sobre el ajedrez tendría enormes cuantificador complejidad, limitada fundamentalmente por la longitud de la más larga partida de ajedrez.

Mientras tanto, por supuesto, uno puede subsumir el primer orden de los cuantificadores en un orden superior cuantificadores hablando de estrategias. Esto equivale a comercial de alta de primer orden cuantificador complejidad de bajo orden superior cuantificador complejidad.

Answer 3

Un ejemplo de los sistemas dinámicos es la especificación de los bienes, el cual necesita de 5 cuantificadores. Fue introducido por Rufus Bowen en la década de 1970 para estudiar el equilibrio de las medidas de los sistemas dinámicos; por ejemplo, implica que la limitación de la distribución de órbitas periódicas es la única medida que maximiza la entropía siempre y cuando el sistema se expande. Viene en varias versiones, que no son todos equivalentes, pero permítanme ignorar estas sutilezas y sólo citar uno.

Dado un espacio métrico compacto $X$, un mapa continuo $f\colon X\to X$ tiene la propiedad especificación de si $\forall\epsilon>0$, $\exists T>0$ tal que $\forall (x_1,n_1),\dots,(x_\ell,n_\ell)\in X\times \mathbb{N}$, $\exists y\in X$ tal que $\forall 1\leq k\leq \ell$ e $0\leq j < n_k$, tenemos $d(f^{N_k + j}(y),f^j(x_k)) < \epsilon$ donde $N_k = \sum_{i=1}^{k-1} (n_i + T)$, y también tenemos $f^{N_\ell+n_\ell+T}(y)=y$.

A grandes rasgos dice que cualquier colección finita de segmentos de la órbita puede ser ensombrecida por una órbita periódica que tiene un tiempo delimitado $T$ a la transición de cada una a la siguiente, y que $T$ sólo depende de lo preciso que el seguimiento es necesario para ser.

Answer 4

El lema de bombeo (racional idiomas) los estados que

• para cada racional de lenguaje $L \subseteq \Sigma^*$ (sobre un alfabeto finito $\Sigma$),

• existe un entero $p$ de manera tal que,

• para cada palabra $w\in L$ con $|w|\geq p$,

• existe una factorización de la $w = xyz$ tal que $|y|\geq 1$ e $|xy|\leq p$ y

• para cada $i\geq 0$ tenemos $xy^iz\in L$.

Así ha cuantificador la complejidad de la $5$.

Me gusta este ejemplo porque no es muy sofisticado, pero aún pedagógicamente interesante. Me enseñan un curso elemental en lenguajes formales teoría en la que este lema se discute, y muchos estudiantes tienen dificultades para llegar a un acuerdo con ella (o cómo usarlo), debido a la cuantificador sutileza; así que vale la pena tomarse el tiempo para explicar la lógica. Trato de destacar (en una especie de partida de la teoría del punto de vista) que, cuando se aplica un resultado como este, puedes elegir cada objeto que se introduce con "de todo", pero aquellos cuantificados por "no existe" son impuestas (mientras que, cuando se acredite tal resultado, las cosas son al revés). A pesar de esto, muchos estudiantes siguen creyendo que pueden elegir la factorización quieren.

Answer 5

En la teoría de la computabilidad, un conjunto de números enteros $A$ es infinitamente a menudo computably trazable si hay una función computable $h$ tal que para todas las funciones $g\le_T A$ ($g$ computable de $A$), hay una secuencia computable $T$ finito de conjuntos $T_n$, $n\ge 0$, de tal manera que durante infinitamente muchos $n$, $g(n)\in T_n$, y para todos los $n$ el tamaño de $T_n$ es en la mayoría de las $h(n)$.

Si usted explicar esto es $\Sigma^0_5$: hay un $h$ tal que para todos los $g$ no es un porcentaje ($T$tal que para todos los $m$ hay un $n>m$ con $g(n)\in T_n$.