¿Hay algún modelo en el que los Reales de Dedekind y los Reales de Cauchy sean diferentes? Agradecería que alguien me remitiera a cualquier trabajo relacionado en caso de que exista tal modelo.
Respuestas
¿Demasiados anuncios?
MarlonRibunal
Puntos
271
Con la lógica clásica o La elección contable de Cauchy y Dedekind coincide. Por lo tanto, debemos mirar un modelo de matemáticas intuitivas sin elección contable, como un topo de poleas sobre un espacio.
Por ejemplo, consideremos los topos $ \mathsf {Sh}( \mathbb {R})$ de las poleas sobre $ \mathbb {R}$ (equipado con la topología estándar). Los Reales de Dedekind son la gavilla de mapas continuos de valor real, es decir, $$ \mathbb {R}_D(U) = \lbrace f : U \to \mathbb {R} \mid f \text { continuous} \rbrace. $$ Los Reales del Cáucaso son la gavilla de mapas de valor real localmente constantes, si recuerdo bien.
Estas dos poleas no son isomórficas. Una forma de ver esto: en $ \mathbb {R}_C$ el mapa de restricciones $ \mathbb {R}_C(-1,1) \to \mathbb {R}_C(0,1)$ es una bendición, porque cada mapa continuo localmente constante $(0,1) \to \mathbb {R}$ es de hecho constante, y también lo es la restricción de un mapa constante $(-1,1) \to \mathbb {R}$ . Pero en $ \mathbb {R}_D$ este no es el caso, porque $x \mapsto 1/x$ es un mapa continuo $(0,1) \to \mathbb {R}$ que no es la restricción de un mapa continuo $(-1,1) \to \mathbb {R}$ .
En Lubarsky y Rathjen, Sobre los Reales Constructivos de Dedekind construyen un modelo en el que los Reales de Cauchy forman un conjunto, pero los Reales de Dedekind son una clase adecuada. ¡Ciertamente son diferentes en este caso! El modelo satisface una versión modificada de CZF en la que el esquema del axioma de la colección de subconjuntos se sustituye por el axioma de la exponenciación.
Venkata Koppaka
Puntos
21
En la respuesta de Andrej, se asume una "teoría de fondo" de algo como ZF formulada en lógica intuicionista. Permítanme dar un enfoque ligeramente diferente.
(EDITORIAL: Lo hice no significa que la respuesta de Andrej utilizó todo el poder de ZF; sólo quise decir que parecía tener lugar en un ambiente informal con el sabor de ZF. Para mí, la versión intuicionista de la teoría de conjuntos/topos "se siente diferente" a la versión matemática inversa (tengo una imagen muy tosca de las cosas, aquí: para mí, por ejemplo, ZFC+cardenales grandes y ETCS dan la misma, hablando en términos muy generales, "imagen del mundo", que $RCA_0$ hace no ). Definitivamente no quise decir que Andrej usara tal o cual axioma.)
En lugar de mirar a una teoría de conjuntos, podemos abordar la cuestión desde la perspectiva de la teoría de la computación y las matemáticas inversas. La teoría $RCA_0$ consiste básicamente en un razonamiento "computable" sobre los números naturales y los conjuntos de números naturales; para más detalles, véase el libro de Simpson, cuyo primer capítulo es una excelente introducción y motivación para el tema, y está disponible en su sitio web: http://www.math.psu.edu/simpson/sosoa/chapter1.pdf . $RCA_0$ es la teoría de base natural a la que hay que mirar si estamos interesados en el lado de la computabilidad de las cosas, pero también queremos usar la lógica clásica (se podría argumentar que si nos preocupa la computabilidad, no deberíamos usar la lógica clásica; no sostengo esta opinión, pero simpatizo con ella).
Ahora bien, la computabilidad teórica, hay dos nociones razonables de "secuencia caucásica computable de números racionales": una secuencia computable de números racionales que resulta ser una secuencia caucásica clásica, o una secuencia computable de números racionales junto con una función computable $f$ (un módulo) tal que para todos los racionales $ \epsilon $ cualquier término en la secuencia después de la $f( \epsilon )$ Los términos son $< \epsilon $ aparte. Estas últimas secuencias pueden denominarse "efectivamente Cauchy", y la afirmación de que cada secuencia Cauchy tiene un módulo es equivalente a más de $RCA_0$ al sistema mucho más fuerte $ACA_0$ .
Al otro lado de las cosas, hay tres nociones razonables de "corte de racionalidad computable": un conjunto computable no vacío de números racionales que se cierra hacia arriba, junto con un conjunto computable no vacío de números racionales que se cierra hacia abajo, los dos de los cuales están desarticulados y omiten a lo sumo un número racional; un conjunto c.e. no vacío de números racionales que se cierra hacia arriba; o un conjunto c.e. no vacío de números racionales que se cierra hacia abajo. Estos últimos corresponden a los reales que son "semicomputables de arriba abajo"; véase por ejemplo http://arxiv.org/pdf/1110.5028.pdf . Una vez más, creo que la equivalencia de todas estas nociones es equivalente sobre $RCA_0$ a $ACA_0$ .
Ahora se pueden hacer versiones de todas estas definiciones dentro de $RCA_0$ y se pueden hacer preguntas adecuadas sobre la igualdad (aunque hay que tener cuidado al formalizar este tipo de cosas). Mi recuerdo es que al menos una posible versión resulta en $RCA_0$ no demostrando su equivalencia; añadiré los detalles cuando esté más despierto.
Eduard Wirch
Puntos
199
Coincidentemente, me estoy preparando para hablar de algo de esto mañana. Aquí está algo de lo que diré sobre esto. Una buena manera de pensar en los Reales de Dedekind vs. Cauchy es pensar en el tipo de información que da cada representación.
Para los reales de Dedekind, esto está bastante claro: un corte de Dedekind para $r$ le da exactamente la información suficiente para determinar si $r \leq q$ o $r \geq q$ por cada número racional $q$ . Usando esta información, es fácil obtener una secuencia Cauchy para $r$ . Primero encuentre un número entero $n$ de tal manera que $n \leq r \leq n+1$ . Entonces repetidamente bisecciona el intervalo $[n,n+1]$ comparando con el punto medio (que siempre es racional) para determinar qué intervalo medio usar para el siguiente paso. La secuencia de los puntos medios $a_0 = n+1/2, a_1,a_2, \dots $ es una secuencia caucásica para $r$ .
Para los reales caucásicos, en realidad no obtenemos ninguna información a menos que sepamos algo sobre la tasa de convergencia de la secuencia caucásica para el verdadero $r$ . Ya que podemos acelerar fácilmente hasta una tasa de convergencia, asumamos que $|a_n - a_{n+1}| \leq 2^{-n}$ para todos $n$ . Lo que se nos da entonces es una forma de conseguir, en la entrada $ \varepsilon\gt0 $ un intervalo (racional) de duración como máximo $ \varepsilon $ que contiene nuestro número real $r$ . ¿Podemos usar este tipo de información para obtener un corte Dedekind para $r$ ? No es tan fácil...
Para ver que $r \leq q$ debemos asegurarnos de que $a_n \leq q+2^{1-n}$ para todos $n$ de la misma manera, $r \geq q$ sucede si y sólo si $a_n \geq q-2^{1-n}$ para todos $n$ . Para obtener un corte Dedekind para $r$ debemos decidir simultáneamente cuál es el caso de todas las razones $q$ . Tenga en cuenta que si $r = q$ entonces ambos casos se mantienen y debemos elegir uno. Dado que estas decisiones podrían requerir la inspección de toda la secuencia del Caucus, no podemos esperar hacer esto de una manera fácil de calcular como lo hicimos para el otro lado. De hecho, no hay ningún proceso computable que produzca un corte de Dedekind de tal secuencia Cauchy.
En los sistemas intuicionistas, el axioma de la dicotomía $r \leq 0 \lor r \geq 0$ para los reales caucásicos es equivalente al Principio Limitado de Omnisciencia Menor (LLPO):
Dado $f: \mathbb {N} \to\lbrace0 ,1 \rbrace $ que toma el valor $1$ a lo sumo una vez, o bien $f(2n) = 0$ para todos $n$ o $f(2n+1) = 0$ para todos $n$ .
La LLPO no es trivial y no se puede probar en algunos sistemas intuicionistas. Incluso en presencia de la LLPO, no es suficiente simplemente comparar $r$ con $0$ comparamos el verdadero $r$ con todas las razones $q$ y comprender todas estas comparaciones para formar un corte Dedekind para $r$ . Así que se necesita una cierta cantidad de comprensión no trivial además de la LLPO. Dado que estas comparaciones no son independientes entre sí, no es un requisito tan difícil como puede parecer.
Andrej dio un buen ejemplo de un topo de gavilla donde la LLPO falla. En los sistemas clásicos, la LLPO es siempre verdadera y se necesita una muy pequeña cantidad de comprensión, por ejemplo el subsistema espartano de aritmética de segundo orden $ \mathsf {RCA}_0$ ya prueba que cada real caucásico (con una tasa de convergencia conocida) es equivalente a un real de Dedekind. Sin embargo, las dificultades para convertir una representación en otra siguen siendo visibles si el proceso se repite infinitamente a menudo. Véase la discusión en Hirst, Representaciones de los reales en la matemática inversa Boletín de la Academia Polaca de Ciencias, Matemáticas 55 (2007), 303-316 PDF .
davidsmalley
Puntos
374
Déjeme intentar rellenar algunos detalles relacionados con la respuesta de Noah. Como mencionó Noé, uno puede usar subsistemas de aritmética de segundo orden, como la teoría $ \mathsf {RCA}_0$ para hablar de los reales. El mínimo "modelo agradable" de $ \mathsf {RCA}_0$ se llama $ \mathsf {REC}$ y sólo incluye los números naturales (estándar) y todos los objetos que pueden ser codificados como secuencias computables de números naturales.
Ahora, para hacer mi respuesta más simple, en lugar de usar cortes de Dedekind, consideremos representaciones binarias de los reales. Se puede mostrar en $ \mathsf {RCA}_0$ que cada corte del Dedekind donde los racionales son tomados para estar por encima y por debajo corresponde a un número real binario, por ejemplo. $10.01110101...$ (Cabe señalar que esta prueba no es constructiva ya que utiliza la ley del medio excluido).
Desde $ \mathsf {REC}$ sólo sabe de objetos computables, cree que todos los reales binarios son computables.
Ahora considera que el binario real $h = 0.xxx...$ donde $xxx...$ es el problema de la detención (es decir, el $e$ La parte es $1$ Si el $e$ La máquina de torneado (programa de computadora) se detiene en la entrada $0$ ). Tenga en cuenta que $h = \sum 2^{-e}$ donde la suma se toma sobre las máquinas giratorias $e$ que se detenga. Deje que $h_n = \sum 2^{-e}$ donde la suma está sobre las máquinas de Turing que se detienen en $n$ pasos. Ahora $h_n$ es una secuencia monótona, delimitada y computable de racionales que converge en un real binario no computable. (Este ejemplo se denomina Secuencia de espectros .)
Sin embargo, $ \mathsf {RCA}_0$ puede mostrar que cada secuencia monótona delimitada de raciones es una secuencia caucásica (esa es la definición habitual: $ \forall \epsilon > 0\ \exists n\ \forall m>n\ |h_m - h_n| \leq \varepsilon $ donde $ \varepsilon $ se supone que es racional). La prueba es básicamente una aplicación del principio de encasillamiento lo suficientemente débil como para atravesar en $ \mathsf {RCA}_0$ .
De ahí que tengamos un ejemplo de una secuencia computable de Cauchy (que es probadamente Cauchy en $ \mathsf {RCA}_0$ ) pero para el cual el modelo $ \mathsf {REC}$ piensa que no tiene límite.
(Por supuesto que el diablo está en los detalles, y estoy seguro de que me falta un número, pero esa es la idea principal de cómo lo mostrarías.)
