Oculto uso de contables elección

Question

Axioma de Contables de Elección es una forma más débil de el famoso Axioma de Elección, que es generalmente aceptada incluso por los constructivistas. Tras el famoso libro de Obispo Y Puentes, Contables Elección en la construcción de las matemáticas parece tener un significado claro. Si algo con una determinada propiedad existe, entonces existe un número finito de procedimiento (leer: el algoritmo que calcula que algo. El truco es que en la construcción de las matemáticas, cuando decimos "así o así que existe con tan o más de la propiedad", que efectivamente significa que tenemos un algoritmo que construye un objeto deseado, junto con un "certificado" (testigo) que la dicha propiedad se mantiene.

En algunas variaciones de constructivo de las matemáticas, Contables Elección puede ser incluso probado (ejemplo $-$ esta relativamente fresca del libro). En términos formales, la instrucción es la siguiente:

$$ \forall x \exists y . \varphi[x, y] \implies \exists f \forall x . \varphi[x, f(x)].$$

En los Contables de Elección, $x$ es un número natural a diferencia de la habitual en el Axioma de Elección donde $x$ puede ser cualquier cosa. En la construcción de las matemáticas, se necesita un algoritmo de producción de $y$ de las $x$ con la propiedad $\varphi[x, y]$. Más detalles aquí.

Ahora vamos a recordar en qué casos realmente necesitamos la Elección. La respuesta es, cuando se trata con conjuntos infinitos y el objeto que buscamos, no está definida de forma única (el famoso ejemplo con calcetines).

Estoy más preocupado por el caso en que no podemos única elegir el elemento con la propiedad deseada. Por ejemplo (sin entrar en detalles técnicos de la representación de números reales en la construcción de las matemáticas), digamos que tenemos una función continua $f:[0,1] \longrightarrow \mathbb{R}$. En la construcción de matemáticas, declaraciones como las siguientes se utilizan a menudo:

Partición de la unidad de intervalo en $N$ subintervalos $[p_i, p_{i+1}]$ de tan o más de longitud, evaluar la función en los extremos, considerar todo un número finito de $\{ f(p_i) \}_{i=1}^{N}$ y recoger el máximo (o mínimo) $f(p_j)$

Un ejemplo de este tipo de construcción se puede encontrar en este blog, Teorema en la parte inferior por Bauer o en este muy bonito y primaria libro por Schwichtenberg, Lema en la página 35. En el primero, Bauer utiliza explícitamente el Contable de la Elección, mientras que en el segundo Schwichtenberg no recordar la Elección en cualquier lugar.

Examinemos la parte pertinente de este lema:

Sin entrar en los detalles de una función de orden, situado encima, que nos acaba de decir que buscamos un algoritmo que, dados dos números racionales $a$ $b$ natural y un $k$, devuelve un indicador de que $\forall x. f(x) \leq b$ o un número racional, digamos, $x=a_j$ tal que $a \leq f(x)$. ¿Qué se entiende por "datos para la función de" es sólo un mapa de $h$ que es una aproximación racional a $f$ hasta una precisión especificada $\alpha_f$ mientras $\omega_f$ desempeña el papel de $\delta$ en la definición de continuidad. Pero estos detalles no son importantes en el momento. Me pregunto si el hecho de que puede haber más de una maxima $h(a_j, n_k)$, podría requerir Contables Elección.

Mis preguntas son por lo tanto:

1. ¿Por qué el Axioma de Contables Opción "look" tan trivial y por qué qué se necesita para ser declarado como un axioma independiente en todos los constructivo de la matemática? Recuerde, el Obispo escribió: Elección está implícita en el significado mismo de la existencia. Y, a continuación, Puentes aclaró que $\forall x \exists y . \varphi[x, y]$ leer: existe un procedimiento que calcula el $y$ y muestra $\varphi[x, y]$. Así que ¿por qué ¿cuál es el punto?

2. Qué necesitamos la Opción de escoger un máximo entero fuera de un conjunto finito de números enteros si hay varios de esos máxima enteros?

3. Qué dijo el lema implica Contables Elección?

4. A mí me parece que puedo escribir un programa que se divide la unidad de intervalo fijo de subinterval de longitud, las tiendas de los pedidos de los extremos en una matriz, examina los valores de la función en los extremos de dicho pedido y devuelve el último extremo de que se obtiene un máximo valor de la función. Entonces, ¿dónde está el Contable de Elección utilizado?

5. En algunos de sus posts, Bauer dijo que todo lo que utiliza el Contable de Elección en la construcción de las matemáticas tiene una computable realización. ¿Qué significa exactamente? Podemos convertir cualquier prueba de un teorema que utiliza el Contable de Elección en un equipo de trabajo del programa?

Comentario: las respuestas parciales son bienvenidos!

Comentario: me gustaría evitar fundacional de la discusión sobre la necesidad de Contables de Elección en la definición de Cauchy reales, funciones continuas, etc.

Answer 1

(1) Una posible razón para explícitamente llamar la atención a los usos de los contables de la elección es que el Obispo estilo constructivo de las matemáticas debe ser lo más universal posible. No sólo debería pruebas mantenga en el conocido variedades de constructivo de las matemáticas, pero que aún debe ser válido en $\mathsf{ZF}$. También es bueno si los teoremas mantenga en el lenguaje interno de toposes, pero hay muchos ejemplos de toposes donde contables elección falla.

(2)-(4) no creo que Schwichtenberg la prueba de los usos contables opción en absoluto. Con respecto a los máximos, tenemos las siguientes

• Supremums son siempre únicas, cuando existan.
• Supremums finito de conjuntos de reales existen.
• Máximos de conjuntos finitos de números enteros o racionales existen. Es decir, dado racionales $a_1,\ldots,a_n$, hay un $i$ tal que $a_i = \sup \{a_1,\ldots,a_n\}$. Sin embargo, esta $i$ podría no ser único, pero eso está bien porque se puede tomar sólo el más grande de $i$.
• Constructivamente no podemos demostrar que supremums finito de conjuntos de reales siempre se alcanzan por lo que la máxima podría no existir.

Así que podemos asumir que el $j$ en Schwichtenberg la prueba es única. Sin embargo, resulta que en este caso no necesitamos ni $j$ a ser único. Esto es debido a que sólo se necesita una $j$ pero contables de la elección sólo se produciría si queríamos una secuencia infinita. El punto clave es que tenemos el módulo de continuidad de funciones incorporadas en la definición de función continua, que se utiliza para asegurarse de escoger un adecuado $j$ primera vez. Si no recuerdo mal esta es una técnica común cuando se trabaja de manera constructiva, sin contable elección.

En Bauer prueba algo diferente sucede. Él está demostrando algo un poco diferente y tal vez él tiene en mente más simple, más natural definiciones de secuencia y función continua. En su prueba, $f(x_1),\ldots,f(x_n)$ es una lista finita de números reales que no son necesariamente racionales. El máximo de un conjunto finito de números reales no podría ser alcanzado de manera constructiva. Esto es, puede no existir una $i$ tal que $f(x_i) = \max(f(x_1),\ldots,f(x_n))$. Para dar la vuelta a este, Bauer se utiliza el siguiente truco. Resulta que sólo necesitamos $i$ tal que $f(x_i) \geq \max(f(x_1),\ldots,f(x_n)) - 1$. Ese número existe, pero no está definida de forma única, por lo que para obtener una secuencia de números tales como Bauer prueba requiere, necesitamos utilizar contables elección.

(5) Bauer es más probable refiriéndose a la realizabilidad de los modelos y, en particular, el eficaz topos. Si podemos probar que una función existe de manera constructiva, a continuación, podemos hacerlo internamente en la eficacia de topos. Pero esto implica que podemos encontrar una computable testigo. Desde contable elección tiene en la eficacia de topos, podemos asumir que en nuestras pruebas y aún así obtener computable a los testigos.