Contables de la elección y la extracción de términos

Question

El constructivo Axioma de Contables Elección (ACC) es ampliamente aceptado debido a su computacional de contenido. Éste establece que:

$$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \forall n \in \mathbb{N} . \varphi [n, f(n)]$$

significa: si podemos (de manera constructiva) demostrar el antecedente que existe una función que produce $x$'s de satisfacer el "certificado" $\varphi [n, x]$.

El famoso realizabilidad interpretación afirma que en el fin de demostrar el antecedente, ya tenemos a la construcción de un plazo (de una función) testimonio $\varphi [n, x]$. Por lo tanto, ACC cantidades a la simple necesidad de formatear. Sin embargo, la realizabilidad es un metamathematical concepto en que sentido es justo preguntar cómo las funciones que se le atribuían entran en juego.

Claramente, cada una de las funciones en (la mayoría de) constructivo de la matemática es computable:

Si nos atenemos a intuitionistic lógica, entonces, desde el contable axioma de elección tiene una computable realización, todo lo que resultó de ella será computable en un buen sentido. Y computable cosas son por lo general "intuitiva" y no demasiado sorprendente

Sin embargo, algunos constructivistas como Schwichtenberg, Schuster, Richman, Ruitenburg reclamación de que el uso de la ACC puede evitarse en muchos casos. Algunos de ellos llaman a las funciones producido por ACC "cajas negras" en el sentido de que no están especificados en concreto, excepto que su producción satisface el certificado dado la $\varphi [n, x]$. La única constructivo contenido parece ser más que el hecho de que dichas funciones son computables, sin más detalles.

---

Pregunta: ¿Qué hace un computable realización de ACC precisamente significan y cómo convertir una prueba que implican ACC en un equipo de trabajo del programa? Existe un procedimiento para encontrar un derecho número de Gödel de una función implícita por la ACC? O es ACC de la mera existencia de la reclamación y la razón de la aceptación es sólo debido a las funciones por él producidos son computables?

---

ACTUALIZACIÓN

Estoy dispuesto a conceder a la recompensa. Las tres respuestas son grandes y explicar el significado de BHK muy bien. Sin embargo, sólo Colm la respuesta parece enfrentar el problema real del programa de extracción de, al menos parcialmente.

Answer 1

Como digo en el comentario a la otra pregunta, la realizabilidad se describe en el capítulo 4, sección 4 de Troelstra y van Dalen Constructivismo en Matemáticas, Volumen I y $\mathbf{q}$-realizabilidad aparece en el capítulo 9, sección 7 de Troelstra y van Dalen Constructivismo en Matemáticas, Volumen II. Otra referencia es Beeson, Fundaciones Constructivo de las Matemáticas , que aunque no sé los números de la sección de la mano. Existe una variante de $\mathbf{q}$-realizabilidad llamado realizabilidad con la verdad en Rathjen, La Disyunción y Propiedades Relacionadas para Constructivo Zermelo-Fraenkel de la Teoría de conjuntos que se utiliza para demostrar "la existencia de la propiedad" de los resultados sobre el constructivo conjunto de teorías $\mathsf{CZF}$$\mathsf{IZF}$.

Por el camino hay varias maneras diferentes para extraer computacional de la información de las pruebas y algunos son compatibles con los contables de elección, pero voy a centrarme sólo en la realizabilidad y $\mathbf{q}$-realizabilidad.

La idea de la realizabilidad es tomar la Brouwer-Heyting-Kolmogorov interpretación muy literal. Para cada fórmula $\phi$ que definir lo que significa para un número $e \in \mathbb{N}$ a darse cuenta de $\phi$. Por ejemplo, si $\phi$ es de la forma $\phi := \phi_1 \rightarrow \phi_2$ $e$ cuenta $\phi$ significa que $e$ códigos de una computable de la función parcial, $\varphi_e$ que si $f$ es un realizer para $\phi_1$ $\varphi_e(f)$ está definido y un realizer para $\phi_2$. A continuación mostramos que una teoría de la $T$ satisface una solidez teorema - que es si $T$ demuestra $\phi$, $T$ también demuestra que existe una realizer para $\phi$. Si utilizamos $\mathbf{q}$-realizabilidad a continuación, también habrá un converso a la solidez teorema: si una fórmula se dio cuenta entonces es demostrable.

Para responder a la pregunta es que sucede que siempre es muy fácil encontrar un realizer para contables elección. Un realizer para $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})\phi(n, m)$ es ya una computable función que toma un número como entrada y devuelve un (número de codificación) un par de $m, e$ tal que $e$ es un realizer para $\phi(n, m)$. Encontrar una función de elección es una simple cuestión de volver a formatear. No tiene nada de extraño que involucran números aleatorios ni nada de eso.

Un punto final es que en la teoría de conjuntos algo sutil que sucede. A veces podemos tener un realizer para $(\exists y) \phi(y)$ sin saber en realidad lo $y$ parece. Sin embargo, para tener un realizer para $y \in \mathbb{N}$ necesitamos saber que número natural es igual. Así que si $\phi(x, y)$ pasa a ser de la forma $y \in \mathbb{N} \wedge \phi'(y)$ estamos bien. Resulta que esto no importa y la prueba de que la Iglesia regla vale para la teoría de conjuntos aún se mantiene. Encontrar un realizer para contables de elección es una simple cuestión de volver a formatear como de costumbre. Ver Rathjen del papel para los detalles.

Edit: Realizabilidad y técnicas similares se basan en tener completa y formal de las pruebas disponibles. Esto hace que sea muy difícil dar un ejemplo claro de la extracción de testigos porque formales pruebas se suele ser bastante largo y complicado, incluso para los informes relativamente sencillos (independiente de si asumimos contables elección o no). En la práctica nos encargamos de pruebas utilizando la prueba de los asistentes. No sé si hay prueba de asistentes que permiten que los contables de la elección y el testimonio de la extracción, pero sin duda esto es algo que se puede hacer.

Answer 2

Hay un par de cuestiones planteadas en la pregunta, acerca de algunos de los conceptos de la computabilidad y número de Gödel. Me voy a centrar mi respuesta en la primera parte de la pregunta, y voy a dar una respuesta específica. Así que aquí es lo que voy a intentar responder:

¿Qué hace un computable realización de ACC precisamente significan y cómo convertir una prueba que implican ACC en un equipo de trabajo del programa?

Respuesta Corta

Dos partes:

• Una computable realización de ACC significaría que es posible "mira dentro" existencial prueba y extraer el testigo y, a continuación, utilizar este testigo en posteriores construcciones por ejemplo la construcción de una función. Esto podría romper el paradigma de la prueba de la irrelevancia.

• Sólo es posible convertir una prueba que implican ACC a un equipo de trabajo del programa si la ACC tiene algunos computable realización. Es decir, para dicha conversión no debe ser algo concreto (no de caja negra) programa cuyo tipo corresponde (por el Curry-Howard correspondencia) a ACC. En este caso, cualquier prueba que implican ACC convierte automáticamente a un programa de ordenador, mientras que el resto de sus elementos no son cuadros negros. Basta con sustituir cada aplicación de la ACC con una aplicación de su realización.

Respuesta Larga

Voy a responder a la pregunta como moderadamente experimentado Coq usuario. Coq es una prueba auxiliar que se basa en el Cálculo de (Co)Inductivo Construcciones. La clave característica subyacente de Coq es el Curry Howard Isomorfismo: una correspondencia entre los mundos de pruebas y programas. En particular, tenemos las siguientes:

• Cada Proposición es un tipo.
• Cada prueba es un programa. Esto podría ser llamado también la realización de un tipo.

Ahora, la ACC, como se indica en la pregunta, es la siguiente:

$$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \forall n \in \mathbb{N} . \varphi [n, f(n)]$$

Por el Curry-Howard correspondencia, Coq no distingue entre el tipo de función y la implicación lógica. También no hay ninguna diferencia entre el $\forall$ y el dependiente de la función del producto tipo de $\Pi x \in X. T(x)$ donde $T$ es algún tipo dependiente. Esta es una generalización de la función común de tipo $A \rightarrow B$, donde el tipo de retorno $B$ es constante con respecto al argumento de tipo $A$. No voy a ampliar los cuantificadores existencial, ya que sería demasiado complicado, pero estos dos son en realidad los tipos demasiado. Así que la instrucción anterior en Coq sería:

$$ (\Pi n\in \mathbb{N} . \exists x \in X . \varphi [n, x]) \longrightarrow (\exists f: \mathbb{N} \longrightarrow X . \Pi n \in \mathbb{N} . \varphi [n, f(n)])$$

Es decir, el axioma es un tipo de función. OK, pero ¿qué es exactamente el rango y el dominio de esta función? El dominio es un tipo de función y el rango es un tipo existencial.

• El rango es el tipo de función $(\Pi n\in \mathbb{N} . \exists x \in X . \varphi [n, x])$. Deje $g$ ser un elemento de este tipo. Dado un número natural, $g$ devuelve un testimonio para la existencial. Este testimonio contiene un $x$ y una realización (o elemento, o prueba) de $\varphi [n, x]$. Recuerden $\varphi [n, x]$ es una Proposición, que es tratada como un tipo.

• El dominio de los axiomas de la función es el tipo existencial $(\exists f: \mathbb{N} \longrightarrow X . \Pi n \in \mathbb{N} . \varphi [n, f(n)])$. Un elemento de este tipo es un testigo. El testimonio contiene una función de $f: \mathbb{N} \longrightarrow X$ y una realización (prueba, elemento) del tipo $\Pi n \in \mathbb{N} . \varphi [n, f(n)])$. El último es en sí mismo un tipo de función (estoy empezando a marearse), teniendo un número natural $n$ y dando de nuevo un elemento de $\varphi [n, f(n)])$. En este punto, usted podría tomar una amplitud y maravillarse con la potencia expresiva de los tipos de dependientes.

OK, volviendo a la pregunta anterior.

¿Qué hace un computable realización de ACC precisamente significan y cómo convertir una prueba que implican ACC en un equipo de trabajo del programa?

En realidad tiene dos partes:

1. ¿Qué hace un computable realización de ACC precisamente significa?
2. ¿Cómo se puede convertir en una prueba que implican ACC en un equipo de trabajo del programa?

Para responder a $(1)$ se desenrolla las nociones de "computable" y "realización" (sí, he deliberadamente cambiado a reino unido, la ortografía, que gobernó con nosotros para ~700 años). En primer lugar, la realización de un tipo que es un elemento de ese tipo. En segundo lugar, esta realización es computable si puede ser construido, frente a sólo el que se muestra a existir. Así, un "computable realización" es una construcción de un elemento del tipo especificado por el ACC. En otras palabras, es la construcción de una función que toma la función en el dominio y devuelve un existencial en el rango. Puede una realización de la ACC ser construido? La respuesta es: yo he mentido anteriormente. O, al menos, he ocultado la verdad. Coq hace distinguir entre los tipos y las proposiciones; estos últimos son tratados como los tipos, pero son cajas negras no pueden ser utilizados para la construcción de tipos. En particular, las proposiciones "vivir" en un "universo" llamado Prop y tipos viven en una que se llama... bueno... Tipo. Estrictamente, el ACC no puede ser construido en Coq. Sin embargo, si se relaja la restricción y aplastar todo a un tipo de mundo, la construcción es posible. De hecho, he definido en Coq mí mismo:

Definición ACC (X : Tipo de) (P : nat -> X -> Tipo) (f : (forall n : nat, {x:X & (P n x)})) (n : nat) : X := partido de f n (existT x P) => x final.

Teorema de ACC_full (X : Tipo de) (P : nat -> X -> Tipo) (f : (forall n : nat, {x:X & (P n x)})) : {f : nat -> X & (forall n : nat, P n (f n))}. existe (ACC X P f). intros. desarrollan ACC. recuerde (f n). destruct s. de la asunción. Qed.

Por favor, copia y pasado a la Coq IDE, ya que representa terriblemente aquí. Así que lo que una computable realización de ACC significa es que podemos mirar en el interior de la original existencial producido por la función en el lado izquierdo para la construcción de la RHS plazo. Normalmente, esto no está permitido, porque el existencial es una Proposición , mientras que el lado derecho es un Tipo de. Sin embargo, si se relaja la declaración un poco y definir las cosas en términos de la Sig tipo, como lo he hecho, funciona. El Sig tipo es el tipo existencial, sino en el Tipo de mundo en lugar de en la Proposición mundo.

Ahora es fácil responder a la segunda pregunta, a saber: ¿Cómo se puede convertir en una prueba que implican ACC en un equipo de trabajo del programa? Si el ACC que uso es la versión estricta, con el existencial de la Proposición en el lado izquierdo, entonces usted no puede convertir este tipo de prueba en un programa, porque su ACC sólo será una "caja negra". Pero si usted relajarse esta al Tipo de versión de la ACC, obtendrá automáticamente un programa: basta con aplicar mi Coq programa anterior para que cualquier programa de la LHS tipo y va a dar a usted un programa de la RHS tipo. Intuitivamente, lo que el programa ACC hace es "grietas" el existencial, "mira dentro" y usa lo que encuentra para definir una función - esta es la función de $f$ mencionado en el axioma. El teorema de ACC_full luego aumenta a esta función con la prueba de que la función es correcta, es decir, que la proposición $\varphi$ es respetado. Esto se logra abriendo la primera función y la aplicación de la hipótesis, utilizando el hecho de que la primera función utiliza la función de la LHS, que automáticamente se respeta $\varphi$. En otras palabras, ACC_full corresponde a la plena axioma de la computables elección, aunque restringido al Tipo de mundo solo, mientras ACC simplemente define la función $f$ a ser utilizado en el axioma. Tenga en cuenta que estoy usando P en el lugar de $\varphi$ en mi Coq código.

Me doy cuenta de que al final de mi respuesta que es un poco desordenado porque he cambiado mi opinión sobre algunas cosas en el camino, pero creo que está en buena forma. Por favor, comentar con cualquier pregunta que usted tenga aunque, como estoy seguro de que algo de esto puede no ser del todo claro.

Answer 3

Estamos buscando en el esquema de $$(\forall n\in \mathbb{N})(\exists x \in X)\psi(n,x) \to (\exists f \in X^{\mathbb{N}})(\forall n) \psi(n,f(n)).$$

Hay dos puntos de vista: desde la pura (clásica) la teoría de la computabilidad, y desde un punto de vista constructivo.

En la teoría de la computabilidad

El clásico de la computabilidad de la elección del esquema depende en gran medida del conjunto de $X$ y la clase de fórmulas que $\psi$ proviene. En general, $f$ no necesita ser computable, incluso cuando $X$ es sólo $\mathbb{N}$.

• Al$X = \mathbb{N}$$\psi$$\Sigma^0_1$, la función de $f$ obtenido siempre es computable. Podemos definir a la $f(n) = (\mu m)\psi(n,m)$, y este será computable porque $\phi$$\Sigma^0_1$.

• Si $X = \mathbb{N}$$\psi$$\Pi^0_2$, entonces la función de $f$ no es computable en general. Por ejemplo, si dejamos $\phi_n$ ser un estándar de la enumeración de las funciones computables, se podría poner $$\psi_0(m,k) \equiv [(\phi_{n}(n) \text{ halts in $k$ steps}) \Leftrightarrow (\exists s) (\phi_{n}(n) \text{ halts in $s$ steps})].$$ Certainly we have $(\forall n)(\existe k)\psi_0(n,k)$, but there is no computable selector $f$.

Un poco es conocido acerca de la fuerza del régimen de los casos $X = \mathbb{N}$, $X = \mathbb{N}^\mathbb{N}$, y $X = P(\mathbb{N})$, cuando se $\psi$ proviene de diversas clases en el aritméticos o de jerarquía analítica. Dependiendo de estas opciones, la fuerza puede variar enormemente. En estos casos, la función de elección puede requerir fuertes axiomas en segundo orden de la aritmética. En otros casos, como hemos visto, $f$ puede ser computables.

En la construcción de las matemáticas

En la construcción de las matemáticas, la situación puede ser muy diferente. La razón de esta diferencia es que una prueba de $(\forall m)(\exists k)\psi(m,k)$ debe ser más uniforme en la construcción de las matemáticas, de diversas maneras, que en la clásica de las matemáticas. La clásica prueba de $(\forall m)(\exists k)\psi_0(m,k)$ desde arriba requiere un no constructiva elección entre dos de los casos (si $\phi_n(n)$, se detiene o no). Tal elección es imposible en sistemas constructivos.

El obispo parece haber pensado, esencialmente, que el lado derecho de la opción de esquema es un sinónimo para el lado izquierdo, en su perspectiva sobre el constructivismo. Esto es evidente en su comentario acerca de la elección del esquema siguiente de "el sentido mismo de la existencia". Del mismo modo, el BHK interpretación valida la elección del esquema, como hacer varios tipos de realizabilidad.

En estos entornos, no me gustaría ver el esquema de elección como una "mera existencia de la reclamación". En lugar de eso, me gustaría ver como indica la equivalencia que se desprende directamente de los significados que sus componentes se han dado, tanto como el clásico de equivalencia $$\lnot (\exists x)\phi(x) \Leftrightarrow (\forall x)\lnot \phi(x)$$ se desprende directamente de los significados de sus componentes.

Answer 4

Entiendo que mi experiencia en este campo es bastante baja, pero trato de responder a mi propia pregunta (en términos simples).

Primero de todo, estoy totalmente de acuerdo con @aws profundos de respuesta y comentarios. La única sutileza, en mi opinión, es que estamos hablando de metamathematical conceptos aquí que conduce a un poco de confusión. Sin embargo, la pregunta que les hago es, creo, legítima.

Primero de todo, como se observa por @aws, mi ejemplo con el teorema de la función inversa no es realmente un representante de uno. Un representante común ejemplo es el tratamiento de los números reales.

Suponiendo que definimos reales como secuencias de Cauchy, como se suele hacer en la construcción de las matemáticas, nos encontramos con dos alternativas:

1. Tampoco consideramos sólo los así llamados modulada de Cauchy reales que son esencialmente pares de mapas uno de los cuales se calcula el $n$-ésima aproximación racional y otro de control de la velocidad de convergencia como este:

$$ \left( x \in \mathbb{R} \right) \triangleq \left( \forall k \forall n,m \geq M_x(k) . \big| x(n) - x(m) \big| \leq 2^{-k} \right), $$

donde (con un poco de abuso de notación) $x: \mathbb{N} \longrightarrow \mathbb{Q} $ $ M_x: \mathbb{Z} \longrightarrow \mathbb{N} - $ Cauchy módulo.

2. O nos quite $k$ $M_x(k)$ a partir de la definición y considerar genérico de Cauchy secuencias, ya sea modulada o no modulada.

Como se ha señalado por Lubarsky, reales definidas en el paso 1. no son ni siquiera de Cauchy completa. Ellos son, sin embargo, en el siguiente sentido:

Teorema. Cada modulada secuencia de Cauchy modulada reales converge a un modulada real.

Algunos, como Schwichtenberg, no tienen miedo con esta limitación y seguir adelante con la construcción de cálculo en una instalación de estas (?). Sin embargo, para proporcionar la plena integridad de Cauchy, Axioma de Contables Elección (ACC) es necesario saltar de

$$ \left( \forall k \exists M_x \forall n,m \geq M_x . \big| x(n) - x(m) \big| \leq 2^{-k} \right) $$

a

$$ \left( \exists M_x:\mathbb{Z} \longrightarrow \mathbb{N}. \forall k \forall n,m \geq M_x(k) . \big| x(n) - x(m) \big| \leq 2^{-k} \right) $$

¿Cuál es el truco? El truco es, como @aws correctamente mencionado, para el tratamiento de la realizabilidad de la interpretación literal. Hay, literalmente, tiene que ser un (computable) la función $M_x(k)$ detrás de cualquier prueba que implican un genérico de Cauchy real y ACC. La pregunta es, ¿cuál es esa función? ¿Qué puede decirse acerca de él? Resulta que la poca o nada se puede decir. Siguiente Richman y A. Bauer en Una Computable Universo: la Comprensión y el estudio, es simplemente una caja negra obligado a escupir algunos números de satisfacer el certificado de $\varphi(x, f(x))$. No puede garantizarse que un cuadro que emiten la misma salida para la misma entrada de $-$ que bien podría depender de algún estado interno desconocido para nosotros. No es de extrañar que constructiva contenido de ACC a veces se pone en duda y por lo que mi curiosidad acerca de cualquier trabajó ejemplos con el programa de extracción no podría ser satisfecho. Sin embargo, de nuevo, todo funciona en teoría (de hecho, no deberíamos dudar de que tan o más computable en función de si nos quedamos con intuitionistic lógica), pero la viabilidad de la ACC es discutible. La viabilidad es, sin embargo, solía ser una de las piedras angulares de constructivo de las matemáticas. ¿Cuál es el punto de eliminar algunos de los cuentos de hadas como Medio Excluido o Axioma de Elección por el contexto, pero dejar otro, es decir, la ACC?

Otro problema con el tratamiento secuencial de reales está relacionado con el cálculo de raíces de polinomios complejos. Resulta que las funciones de la computación de las raíces deben ser continuas en los coeficientes del polinomio como parámetros tan pronto como son realmente las funciones en el espíritu constructivo de las matemáticas. Ya que no es el caso, incluso para cúbicos complejas de polinomios, ACC viene a ayudar. Para obtener más información, consulte Richman.

Por lo que ha llevado a algunos constructivistas para revisar Dedekind la construcción de reales. Ayuda a proporcionar integridad y al mismo tiempo para (supuestamente) evitar las invocaciones de ACC. Sin embargo, este tratamiento se levanta un montón de nuevas preguntas con respecto a las posibilidades de aplicación real en un ordenador. A diferencia de los modulada de Cauchy reales, que son inmediatamente los programas de ordenador, Dedekind constructivas reales proporcionan mucha menos potencia de cálculo como se ha señalado por Bauer.

No pretendo que este post es una respuesta, tampoco me lo marca como aceptado. Pero ha sido demasiado largo para un comentario o una actualización de la pregunta. Me gustaría dejar de apreciar si alguien puede arrojar más luz sobre el tema, así como proporcionar ejemplos de la eficacia de la aplicación constructiva de los teoremas basados en Dedekind reales.