He escuchado que algunos axiomas, tales como "todas las funciones son continuas" o "todas las funciones son computables", son compatibles con intuitionistic tipo de teorías, pero no a su clásico equivalentes. Pero si ellos no son compatibles con LEM, ¿no significa que demostrar, no LEM? Pero no LEM significa que no (o no) que, en particular, implica la no - pero eso implica (o no). Lo que ha ido mal aquí?
Respuestas
¿Demasiados anuncios?
Si $A$ es una frase (es decir, no tiene variables libres), entonces el razonamiento es correcto y, de hecho $\neg (A \vee \neg A)$ no es consistente con intuitionistic lógica.
Sin embargo, todas las instancias de medio excluido que están en contradicción con las declaraciones de "todas las funciones son continuas" y "todas las funciones son computables" son para las fórmulas de la forma $A(x)$ donde $x$ es una variable libre. Para dar un ejemplo claro, el trabajo de más de Heyting aritmética (HA), vamos a $A(n)$ ser la afirmación de que el $n$th máquina de Turing se detiene en la entrada de $n$. Entonces, es coherente con el HA que $\forall n\;A(n) \vee \neg A(n)$ es falso. Es decir, $\neg (\forall n \; A(n) \vee \neg A(n))$ es consistente con HA, y es, de hecho, implícita por $\mathsf{CT}_0$ (básicamente, la declaración de que todas las funciones son computables). Tenga en cuenta que incluso en la lógica clásica, esto no implica directamente a $\neg A(n)$, que sería el equivalente a $\forall n \; \neg A(n)$. Lo que podríamos hacer en la lógica clásica es deducir $\exists n \; \neg (A(n) \vee \neg A(n))$ y continuar como antes, pero esto no funciona en intuitionistic lógica.
JoshL
Puntos
290
Esta es una expansión de Henry comentario. Si no podemos añadir axiomas, intuitionistic lógica (por que me refiero a todos los sistemas estándar como HA, IZF, etc.) es compatible con la ley del medio excluido LEM, pero no prueban la LEM. Este es un hecho útil para saber cuándo aprender acerca de estos lógica - que no prueban nada de lo que clásicamente se falsos, aunque hay algunas cosas que son clásicamente comprobable que no pueden probar.
Ahora, si hay una frase que $\lnot \phi$ que es el de la clásica comprobable, pero no es demostrable en algunos intuitionistic sistema de $I$, $\phi$ es el de la clásica disprovable, por lo $\lnot \phi$ no tiene ningún modelo clásico. Pero desde $\lnot \phi$ no es comprobable en $I$, $\phi$ es coherente con $I$ (debido a una prueba de una contradicción de $\phi$ es exactamente una prueba de $\lnot \phi$ en un intuitionistic sistema). Así que por el teorema de completitud para $I$, habrá un modelo de $I$ satisfacción $\phi$, pero que el modelo debe ser necesariamente no clásica.
Ejemplos concretos de $\phi$ que tienen esta propiedad son "cada una de las funciones de $\mathbb{N}$ $\mathbb{N}$es computable" y "cada una de las funciones de $\mathbb{R}$ $\mathbb{R}$es continuo". Estos son disprovable clásico, pero no intuitionistically. Cómo es eso? La manera de entenderlo es a exame de la clásica de la refutación.
Para demostrar que "no todas las funciones de $\mathbb{N}$ $\mathbb{N}$es computable" diríamos, para definir una función de $f$, de modo que, para cada una de las $n$, si el $n$th computable de la función se detiene con la salida de $m$ en la entrada de $n$$f(n) = m+1$, e $f(n) = 0$ lo contrario. Entonces es inmediato que $f$ no es computable. En intuitionistic lógica, si hubo un $f$ con la propiedad, podríamos probar que no es computable. Pero la definición que se acaba de dar, no es una buena definición en intuitionistic lógica. Es posible demostrar que para muchos intuitionistic sistemas que lo hacen no probar "para todos los $n$, $n$th computable de la función, se detiene en la entrada de $n$ o no se detiene en la entrada de $n$". De modo que la definición de $f$ de los casos produce un error, porque no podemos demostrar que los casos en la definición exhaustiva. El problema no es que $f$ no es una relación funcional, es que $f$ puede no ser un total de función de si leemos la definición de un no clásica modelo.
Del mismo modo, la manera más fácil de hacer una función discontinua en los reales es para definir a los casos, por ejemplo,$g(0) = 1$$g(x) = 2$$x \not = 0$. No podemos demostrar intuitionistically que no hay ninguna función $g$ con esa propiedad, porque hay modelos clásicos de intuitionstic sistemas en los que hay una función de este tipo. Pero la definición de los casos tiene éxito solamente en los modelos que satisfacen $(\forall x\in\mathbb{R})[x = 0 \lor x \not = 0]$, y resulta que hay no clásica de los modelos de intuitionistic sistemas que no cumplen con esa frase. En estos modelos, no podemos definir la función de $g$, de hecho.
walcher
Puntos
2569
Creo que estás confundiendo dos cosas aquí: intuitionistic lógica y finitistic (intuitionistic) matemáticas. Intuitionists son impulsados por la filosofía de que la Verdad debe ser equiparada con provability y la Falsedad debe ser equiparada con refutability.
Por lo tanto, intuitionistic lógica se caracteriza por el rechazo de varios clásicos tautologías como LEM (porque puede haber declaraciones que no son ni demostrable ni rebatible), de Eliminación de la Doble Negación (para refutar una proposición es rebatible no demostrar que es comprobable) o $\neg \forall xP(x) \leftrightarrow \exists x \neg P(x)$ (debido a que para el intuitionists una existencia de la prueba debe ser constructiva). Nota, sin embargo, que esto no cometer el intuitionist a decir que no es un contraejemplo a LEM, es decir, sólo porque LEM no siempre puede ser "verdadero" (comprobable) no significa que hay (se puede construir) un contraejemplo.
Finitistic las matemáticas en el otro lado se caracteriza por el rechazo de un 'completado' infinito. Sólo se reconoce (posiblemente infinita) de los objetos que pueden ser calculadas con precisión arbitraria. Entonces, en un sentido finitistic matemáticas rechaza no recursivo y conjuntos de pruebas que implican diagonal argumentos: Por ejemplo, el Cantor de la prueba de que $\Bbb R$ es incontable no es aceptable en finitistic de las matemáticas, porque se lleva a cabo una construcción de un elemento en un infinito 'inspección' (por inspección completa de una lista infinita). En finitistic matemáticas "todas las funciones reales continuas" es cierto porque las $\Bbb R$ sólo consiste en la edificable elementos, que son contables, y para cualquier contables conjunto de pares (x,y) no es un mapa continuo con $f(x)=y$.
Ahora intuitionistic lógica no implica finitistic matemáticas, ni es refutado por la lógica clásica, pero por lo general viene con la filosofía de que los motivos intuitionistic lógica.
