Lógica Intuitiva

Tabla de contenido:

Lógica Intuitiva
Lógica Intuitiva

Vídeo: Lógica Intuitiva

Vídeo: Lógica Intuitiva
Vídeo: La INTELIGENCIA INTUITIVA 2024, Marzo
Anonim

Navegación de entrada

  • Contenido de entrada
  • Bibliografía
  • Herramientas académicas
  • Vista previa de PDF de amigos
  • Información de autor y cita
  • Volver arriba

Lógica intuitiva

Publicado por primera vez el miércoles 1 de septiembre de 1999; revisión sustantiva mar 4 sep 2018

La lógica intuicionista abarca los principios generales del razonamiento lógico que los lógicos han abstraído de las matemáticas intuitivas, tal como las desarrolló LEJ Brouwer a partir de su [1907] y [1908]. Debido a que estos principios también son válidos para las matemáticas recursivas rusas y el análisis constructivo de E. Bishop y sus seguidores, la lógica intuicionista puede considerarse la base lógica de las matemáticas constructivas. Aunque el análisis intuicionista entra en conflicto con el análisis clásico, la aritmética intuitiva de Heyting es un subsistema de la aritmética clásica de Peano. Se deduce que la lógica proposicional intuicionista es un subsistema propio de la lógica proposicional clásica, y la lógica predicativa intuicionista pura es un subsistema propio de la lógica predicativa clásica pura.

Filosóficamente, el intuicionismo difiere del logicismo al tratar la lógica como una parte de las matemáticas más que como la base de las matemáticas; del finitismoal permitir un razonamiento constructivo sobre innumerables estructuras (por ejemplo, inducción de barras monótonas en el árbol de secuencias potencialmente infinitas de números naturales); y del platonismo al ver los objetos matemáticos como construcciones mentales sin existencia ideal independiente. El programa formalista de Hilbert, para justificar las matemáticas clásicas reduciéndolo a un sistema formal cuya consistencia debería establecerse por medios finitistas (por lo tanto constructivos), fue el rival contemporáneo más poderoso del intuicionismo en desarrollo de Brouwer. En su ensayo de 1912, Intuitionism and Formalism Brouwer predijo correctamente que cualquier intento de probar la consistencia de la inducción completa en los números naturales conduciría a un círculo vicioso.

Brouwer rechazó el formalismo per se pero admitió la utilidad potencial de formular principios lógicos generales que expresen construcciones intuitivamente correctas, como modus ponens. Heyting [1930], Gentzen [1935] y Kleene [1952] desarrollaron completamente los sistemas formales de lógica y aritmética proposicional y predicativa. Gödel [1933] demostró la equiconsistencia de las teorías intuicionistas y clásicas. Beth [1956] y Kripke [1965] proporcionaron semántica con respecto a la cual la lógica intuicionista es correcta y completa, aunque las pruebas de integridad para la lógica de predicados intuicionistas requieren un razonamiento clásico.

  • 1. Rechazo de tertium non datur
  • 2. Lógica de predicados intuitiva de primer orden

    • 2.1 Los sistemas formales (mathbf {H – IPC}) y (mathbf {H – IQC})
    • 2.2 Formalismos alternativos y el teorema de deducción.
  • 3. Teoría intuitiva de números (aritmética de Heyting) (mathbf {HA})
  • 4. Teoría básica de la prueba

    • 4.1 Traducir la lógica clásica a la intuicionista
    • 4.2 Reglas admisibles de lógica intuitiva y aritmética
  • 5. Semántica básica

    • 5.1 Semántica de Kripke para la lógica intuicionista
    • 5.2 Semántica de realizabilidad para la aritmética de Heyting
  • 6. Temas adicionales y lecturas adicionales

    • 6.1 Lógicas subintucionistas e intermedias
    • 6.2 Temas avanzados
    • 6.3 Lectura recomendada
  • Bibliografía
  • Herramientas académicas
  • Otros recursos de internet
  • Entradas relacionadas

1. Rechazo de tertium non datur

La lógica intuicionista puede describirse sucintamente como lógica clásica sin la ley aristotélica del medio excluido:

) tag {LEM} A / vee / neg A)

o la ley clásica de eliminación de doble negación:

) tag {DNE} neg / neg A / rightarrow A)

pero con la ley de contradicción:

[(A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A))

y ex falso sequitur quodlibet:

) neg A / rightarrow (A / rightarrow B).)

Brouwer [1908] observó que LEM se abstraía de situaciones finitas, luego se extendía sin justificación a declaraciones sobre colecciones infinitas. Por ejemplo, deje que (x, y) se extienda sobre los números naturales (0, 1, 2, / ldots) y deje (B (y)) abreviar ((primepred (y) oldand / primepred (y + 2))), donde (primepred (y)) expresa "(y) es un número primo". Entonces (forall y (B (y) vee / neg B (y))) se mantiene tanto intuitiva como clásica, porque para determinar si un número natural es primo o no, solo necesitamos verificar si tiene un divisor estrictamente entre sí y 1.

Pero si (A (x)) abrevia (exist y (y / gt x / oldand B (y))), entonces para afirmar (forall x (A (x) vee / neg A (x))) intuitivamente necesitaríamos un método efectivo (véase la tesis de Church-Turing) para determinar si hay un par de primos gemelos más grandes que un número natural arbitrario (x), y hasta ahora No se conoce tal método. Un método obvio semi-efectivo es enumerar los pares de números primos usando un refinamiento del tamiz de Eratóstenes (generando los números naturales uno por uno y tachando cada número (y) que no satisface (B (y))), y si hay un par de primos gemelos mayores que (x), este método finalmente encontrará el primero. Sin embargo, (forall x A (x)) expresa la Conjetura de los gemelos, que aún no se ha probado o refutado,así que en el estado actual de nuestro conocimiento no podemos afirmar ni (forall x (A (x) vee / neg A (x))) ni (forall x A (x) vee / neg / forall x Hacha)).

Uno puede objetar que estos ejemplos dependen del hecho de que la conjetura de los gemelos no ha sido resuelta. Varios "contraejemplos" originales de Brouwer dependían de problemas (como el último teorema de Fermat) que desde entonces se han resuelto. Pero para Brouwer, el LEM general era equivalente a la suposición a priori de que cada problema matemático tiene una solución, una suposición que rechazó, anticipando el teorema de incompletitud de Gödel en un cuarto de siglo.

El rechazo de LEM tiene consecuencias de largo alcance. Por un lado,

  • Intuitivamente, la reducción ad absurdum solo prueba afirmaciones negativas, ya que (neg / neg A / rightarrow A) no se cumple en general. (Si lo hiciera, LEM seguiría por modus ponens de la intuitivamente demostrable (neg / neg (A / vee / neg A)).)
  • La lógica proposicional intuicionista no tiene una interpretación finita de la tabla de verdad. Hay infinitos sistemas axiomáticos distintos entre la lógica intuicionista y la clásica.
  • No todas las fórmulas proposicionales tienen una forma normal disyuntiva o conjuntiva intuitivamente equivalente, construida a partir de fórmulas primarias y sus negaciones usando solo (vee) y (oldand).
  • No todas las fórmulas de predicados tienen una forma normal de prenex intuitivamente equivalente, con todos los cuantificadores en el frente.
  • Mientras (forall x / neg / neg (A (x) vee / neg A (x))) es un teorema de lógica de predicados intuicionista, (neg / neg / forall x (A (x) vee / neg A (x))) no lo es; entonces (neg / forall x (A (x) vee / neg A (x))) es consistente con la lógica de predicados intuicionista.

Por otra parte,

  • Toda prueba intuicionista de una declaración cerrada de la forma (A / vee B) puede transformarse efectivamente en una prueba intuicionista de (A) o una prueba intuicionista de (B), y de manera similar para declaraciones existenciales cerradas.
  • La lógica proposicional intuicionista es efectivamente decidible, en el sentido de que un proceso constructivo finito se aplica uniformemente a cada fórmula proposicional, ya sea produciendo una prueba intuicionista de la fórmula o demostrando que tal prueba no puede existir.
  • El fragmento negativo de la lógica intuicionista (sin (vee) o (exist)) contiene una traducción fiel de la lógica clásica, y de manera similar para la aritmética intuitiva y clásica.
  • La aritmética intuitiva puede extenderse consistentemente por axiomas que contradicen la aritmética clásica, permitiendo el estudio formal de las matemáticas recursivas.
  • El controvertido análisis intuicionista de Brouwer, que entra en conflicto con LEM, puede formalizarse y mostrarse de forma consistente en relación con una subteoría correcta clásica e intuitivamente.

2. Lógica de predicados intuitiva de primer orden

La lógica intuicionista formalizada está naturalmente motivada por la explicación informal de Brouwer-Heyting-Kolmogorov de la verdad intuicionista, descrita en las entradas sobre intuicionismo en la filosofía de las matemáticas y el desarrollo de la lógica intuicionista. La independencia constructiva de las operaciones lógicas (oldand, / vee, / rightarrow, / neg, / forall, / exist) contrasta con la situación clásica, donde, por ejemplo, (A / vee B) es equivalente a (neg (neg A / oldand / neg B)), y (exist xA (x)) es equivalente a (neg / forall x / neg A (x)). Desde el punto de vista de BHK, una oración de la forma (A / vee B) afirma que se ha construido una prueba de (A) o una prueba de (B);mientras (neg (neg A / oldand / neg B)) afirma que se ha construido un algoritmo que convertiría efectivamente cualquier par de construcciones que demuestren (neg A) y (neg B) respectivamente, en una prueba de una contradicción conocida.

2.1 Los sistemas formales (mathbf {H – IPC}) y (mathbf {H – IQC})

El siguiente es un formalismo de estilo Hilbert (mathbf {H – IQC}) de Kleene [1952] (cf. Troelstra y van Dalen [1988]) para la lógica de predicados intuitiva de primer orden. El lenguaje (L) de (mathbf {H – IQC}) tiene letras predicadas (P, Q (.), / Ldots) de todas las aridades y variables individuales (x, y, z, / ldots) (con o sin subíndices (1, 2, / ldots)), así como símbolos (oldand, / vee, / rightarrow, / neg, / forall, / exist) para las conexiones lógicas y cuantificadores y paréntesis (,). Las fórmulas atómicas (o primas) de (L) son expresiones como (P, Q (x), R (x, y, x)) donde (P, Q ({.}), R ({.} {.} {.})) son (0) - ary, (1) - ary y (3) - ary letras de predicado respectivamente; es decir, el resultado de llenar cada espacio en blanco en una letra predicada con un símbolo de variable individual es una fórmula principal. Las fórmulas (bien formadas) de (L) se definen inductivamente como sigue.

  • Cada fórmula atómica es una fórmula.
  • Si (A) y (B) son fórmulas, también lo son ((A / oldand B), (A / vee B), (A / rightarrow B)) y (neg A).
  • Si (A) es una fórmula y (x) es una variable, entonces (forall xA) y (exist xA) son fórmulas.

En general, usamos (A, B, C) como metavariables para fórmulas bien formadas y (x, y, z) como metavariables para variables individuales. Anticipando aplicaciones (por ejemplo a la aritmética intuicionista) usamos (s, t) como metavariables para los términos; En el caso de la lógica de predicados pura, los términos son simplemente variables individuales. La aparición de una variable (x) en una fórmula (A) está vinculada si está dentro del alcance de un cuantificador (forall x) o (exist x), de lo contrario, está libre. Intuitivamente como clásica, ((A / leftrightarrow B)) abrevia (((A / rightarrow B) oldand (B / rightarrow A))), y los paréntesis se omitirán cuando esto no cause confusión.

Hay tres reglas de inferencia:

Modus Ponens

De (A) y (A / rightarrow B), concluye (B).

(forall) - Introducción

De (C / rightarrow A (x)), donde (x) es una variable que no aparece libre en (C), concluye (C / rightarrow / forall x A (x)).

(exist) - Eliminación de

(A (x) rightarrow C), donde (x) es una variable que no aparece libre en (C), concluye (exist x A (x) rightarrow C).

Los axiomas son todas las fórmulas de las siguientes formas, donde en los dos últimos esquemas la subformula (A (t)) es el resultado de sustituir una aparición del término (t) por cada aparición libre de (x) en (A (x)), y ninguna variable libre en (t) se convierte en (A (t)) como resultado de la sustitución.

) begin {array} {l} A / rightarrow (B / rightarrow A) (A / rightarrow B) rightarrow ((A / rightarrow (B / rightarrow C)) rightarrow (A / rightarrow C)) / A / rightarrow (B / rightarrow (A / oldand B)) (A / oldand B) rightarrow A \(A / oldand B) rightarrow B \\ A / rightarrow (A / vee B) / B / rightarrow (A / vee B) (A / rightarrow C) rightarrow ((B / rightarrow C) rightarrow ((A / vee B) rightarrow C)) (A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A) / \ neg A / rightarrow (A / rightarrow B) / \ forall xA (x) rightarrow A (t) / A (t) flecha derecha / existe xA (x) end {array})

Una prueba es cualquier secuencia finita de fórmulas, cada una de las cuales es un axioma o una consecuencia inmediata, por una regla de inferencia, de (una o dos) fórmulas anteriores de la secuencia. Se dice que cualquier prueba prueba su última fórmula, que se llama teorema o fórmula comprobable de lógica de predicados intuicionistas de primer orden. Una derivación de una fórmula (E) de una colección (F) de supuestos es cualquier secuencia de fórmulas, cada una de las cuales pertenece a (F) o es un axioma o una consecuencia inmediata, por una regla de inferencia, de las fórmulas anteriores de la secuencia, de modo que (E) es la última fórmula de la secuencia. Si existe tal derivación, decimos que (E) es derivable de (F).

La lógica proposicional intuitiva (mathbf {H – IPC}) es el subsistema de (mathbf {H – IQC}) que resulta cuando el lenguaje se restringe a fórmulas construidas a partir de letras de proposiciones (P, Q, R, / ldots) usando los conectivos proposicionales (oldand, / vee, / rightarrow) y (neg), y solo se usan los postulados proposicionales. Así, las dos últimas reglas de inferencia y los dos últimos esquemas de axioma están ausentes del subsistema proposicional.

Si, en la lista dada de esquemas de axiomas para la lógica de predicados proposicional intuitiva o de primer orden, la ley expresa ex falso sequitur quodlibet:

) neg A / rightarrow (A / rightarrow B))

se sustituye por la ley clásica de eliminación de doble negación DNE:

) neg / neg A / rightarrow A)

(o, de manera equivalente, si se introduce la ley intuitiva de la negación:

[(A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A))

se reemplaza por LEM), un sistema formal (mathbf {H – CPC}) para la lógica proposicional clásica o (mathbf {H – CQC}) para los resultados de la lógica de predicados clásica. Dado que ex falso y la ley de contradicción son teoremas clásicos, la lógica intuicionista está contenida en la lógica clásica. En cierto sentido, la lógica clásica también está contenida en la lógica intuicionista; ver la Sección 4.1 a continuación.

Es importante tener en cuenta que si bien LEM y DNE son equivalentes como esquemas sobre (mathbf {H – IPC}), la implicación

[(neg / neg A / rightarrow A) rightarrow (A / vee / neg A))

no es un esquema teorema de (mathbf {H – IPC}). Para las teorías (mathbf {T}) basadas en la lógica intuicionista, si (E) es una fórmula arbitraria de (L (mathbf {T})) entonces, por definición:

(E) es decidible en (mathbf {T}) si y solo si (mathbf {T}) prueba (E / vee / neg E).

(E) es estable en (mathbf {T}) si y solo si (mathbf {T}) prueba (neg / neg E / rightarrow E).

(E) es comprobable en (mathbf {T}) si y solo si (mathbf {T}) prueba (neg E / vee / neg / neg E).

La capacidad de decisión implica estabilidad, pero no a la inversa. La conjunción de estabilidad y capacidad de prueba es equivalente a la capacidad de decisión. Brouwer mismo demostró que "lo absurdo de lo absurdo de lo absurdo es equivalente a lo absurdo" (Brouwer [1923C]), por lo que cada fórmula de la forma (neg A) es estable; pero en (mathbf {H – IPC}) y (mathbf {H – IQC}) las fórmulas principales y sus negaciones son indecidibles, como se muestra en la Sección 5.1 a continuación.

2.2 Formalismos alternativos y el teorema de deducción

El sistema de estilo Hilbert (mathbf {H – IQC}) es útil para las investigaciones metamatemáticas de la lógica intuicionista, pero su linealización forzada de deducciones y su preferencia por los axiomas sobre las reglas lo convierten en un instrumento incómodo para establecer la derivabilidad. Un sistema de deducción natural (mathbf {N – IQC}) para la lógica de predicados intuicionista resulta del sistema deductivo (mathbf {D}), presentado en la Sección 3 de la entrada sobre lógica clásica en esta Enciclopedia, al omitir el símbolo y las reglas de identidad, y reemplazando la regla clásica (DNE) de eliminación de doble negación por la regla de eliminación de negación intuitiva que expresa ex falso:

(INE) Si (F) implica (A) y (F) implica (neg A), entonces (F) implica (B)

Las claves para demostrar que (mathbf {H – IQC}) son equivalentes a (mathbf {N – IQC}) son modus ponens y su inverso, el:

Teorema de deducción

Si (B) es derivable de (A) y posiblemente de otras fórmulas (F), con todas las variables libres en (A) mantenidas constantes en la derivación (es decir, sin usar la segunda o tercera regla de inferencia sobre cualquier variable (x) que ocurra libre en (A), a menos que el supuesto (A) no ocurra en la derivación antes de la inferencia en cuestión), entonces (A / rightarrow B) es derivable de (F).

Este resultado fundamental, que expresa aproximadamente la regla ((rightarrow I)) de (mathbf {I}), puede probarse para (mathbf {H – IQC}) por inducción en la definición de un derivación. Las otras reglas de (mathbf {I}) se mantienen para (mathbf {H – IQC}) esencialmente por modus ponens, que corresponde a ((rightarrow E)) en (mathbf {N –IQC}); y todos los axiomas de (mathbf {H – IQC}) son demostrables en (mathbf {N – IQC}).

Para ilustrar la utilidad del teorema de la deducción, considere el esquema de teorema (aparentemente trivial) ((A / rightarrow A)). Una prueba correcta en (mathbf {H – IPC}) toma cinco líneas:

  • 1. (A / rightarrow (A / rightarrow A))
  • 2. ((A / rightarrow (A / rightarrow A)) rightarrow ((A / rightarrow ((A / rightarrow A) rightarrow A)) rightarrow (A / rightarrow A)))
  • 3. ((A / rightarrow ((A / rightarrow A) rightarrow A)) rightarrow (A / rightarrow A))
  • 4. (A / rightarrow ((A / rightarrow A) rightarrow A))
  • 5. (A / rightarrow A)

donde 1, 2 y 4 son axiomas y 3, 5 provienen de líneas anteriores por modus ponens. Sin embargo, (A) se deriva de (A) (como suposición) en un paso obvio, por lo que el Teorema de la deducción nos permite concluir que existe una prueba de (A / rightarrow A). (De hecho, la prueba formal de (A / rightarrow A) que se acaba de presentar es parte de la prueba constructiva del Teorema de la deducción.)

Es importante tener en cuenta que, en la definición de una derivación de supuestos en (mathbf {H – IQC}), las fórmulas de supuestos se tratan como si todas sus variables libres se cuantificaran universalmente, de modo que (forall x A (x)) es derivable de la hipótesis (A (x)). Sin embargo, la variable (x) variará (no se mantendrá constante) en esa derivación, mediante el uso de la regla de (forall) - introducción; y entonces el Teorema de la deducción no puede usarse para concluir (falsamente) que (A (x) rightarrow / forall x A (x)) (y por lo tanto, por (exist) - eliminación, (exist x A (x) rightarrow / forall x A (x))) son demostrables en (mathbf {H – IQC}). Como ejemplo del uso correcto del teorema de deducción para la lógica de predicados, considere la implicación (exist x A (x) rightarrow / neg / forall x / neg A (x)). Para mostrar esto es demostrable en (mathbf {H – IQC}),Primero derivamos (neg / forall x / neg A (x)) de (A (x)) con todas las variables libres mantenidas constantes:

  • 1. (forall x / neg A (x) rightarrow / neg A (x))
  • 2. (A (x) rightarrow (forall x / neg A (x) rightarrow A (x)))
  • 3. (A (x)) (supuesto)
  • 4. (forall x / neg A (x) rightarrow A (x))
  • 5. ((forall x / neg A (x) rightarrow A (x)) rightarrow ((forall x / neg A (x) rightarrow / neg A (x)) rightarrow / neg / forall x / neg A (x)))
  • 6. ((forall x / neg A (x) rightarrow / neg A (x)) rightarrow / neg / forall x / neg A (x))
  • 7. (neg / forall x / neg A (x))

Aquí 1, 2 y 5 son axiomas; 4 proviene de 2 y 3 por modus ponens; y 6 y 7 provienen de líneas anteriores por modus ponens; entonces no se han variado las variables. El teorema de la deducción nos dice que hay una prueba (P) en (mathbf {H – IQC}) de (A (x) rightarrow / neg / forall) x (neg A (x)), y una aplicación de (exist) - la eliminación convierte (P) en una prueba de (exist x A (x) rightarrow / neg / forall x / neg A (x)). Lo contrario no es demostrable en (mathbf {H – IQC}), como se muestra en la Sección 5.1 a continuación.

Otras alternativas importantes a (mathbf {H – IQC}) y (mathbf {N – IQC}) son los diversos cálculos secuenciales para la lógica proposicional proposicional y predicativa. El primero de estos cálculos fue definido por Gentzen [1934–5], cf. Kleene [1952]. Los sistemas secuenciales, que prueban exactamente las mismas fórmulas que (mathbf {H – IQC}) y (mathbf {N – IQC}), realizan un seguimiento explícito de todos los supuestos y conclusiones en cada paso de una prueba, reemplazando modus ponens (que elimina una fórmula intermedia) mediante una regla de corte (que se puede demostrar que es una regla admisible (véase la Sección 4.2) para el subsistema restante cuando se omite).

Cuando los detalles del formalismo no son importantes, de ahora en adelante seguimos a Troelstra y van Dalen [1988] al permitir que "(mathbf {IQC})" o "(mathbf {IPC})" se refieran a cualquier sistema formal para predicado intuicionista o lógica proposicional respectivamente, y de manera similar "(mathbf {CQC})" y "(mathbf {CPC})" para predicado clásico y lógica proposicional.

Tanto (mathbf {IPC}) como (mathbf {IQC}) satisfacen los teoremas de interpolación, por ejemplo: si (A) y (B) son fórmulas proposicionales que tienen al menos una letra de proposición en común, y si (A / rightarrow B) es demostrable en (mathbf {IPC}), entonces hay una fórmula (C), que contiene solo letras de proposición que ocurren tanto en (A) como en (B), de modo que tanto (A / rightarrow C) como (C / rightarrow B) son demostrables. Estos temas se tratan en Kleene [1952] y Troelstra y Schwichtenberg [2000].

Si bien, por supuesto, la identidad se puede agregar a la lógica intuicionista, para las aplicaciones (por ejemplo, a la aritmética), el símbolo de igualdad generalmente se trata como un predicado distinguido constante que satisface los axiomas para una relación de equivalencia (reflexividad, simetría y transitividad) y axiomas no lógicos adicionales (por ejemplo,, las definiciones recursivas primitivas de suma y multiplicación). La identidad es decidible, tanto intuitiva como clásica, pero la igualdad extensional intuicionista no siempre es decidible; Vea la discusión de los axiomas de continuidad de Brouwer en la Sección 3 de la entrada sobre el intuicionismo en la filosofía de las matemáticas.

3. Teoría intuitiva de números (aritmética de Heyting) (mathbf {HA})

La aritmética intuitiva (Heyting) (mathbf {HA}) y la aritmética clásica (Peano) (mathbf {PA}) comparten el mismo lenguaje de primer orden y los mismos axiomas no lógicos; Solo la lógica es diferente. Además de los conectivos lógicos, cuantificadores y paréntesis y las variables individuales (x, y, z, / ldots) (también utilizadas como metavariables), el lenguaje (L (mathbf {HA})) de la aritmética tiene un símbolo de predicado binario (=), constante individual (0), constante de función unaria (S), y infinita o infinitamente muchas constantes adicionales para funciones recursivas primitivas que incluyen suma y multiplicación; La elección precisa es una cuestión de gusto y conveniencia. Los términos se crean a partir de variables y (0) utilizando las constantes de la función; en particular,cada número natural (n) se expresa en el idioma por el número (mathbf {n}) obtenido al aplicar (S) (n) veces a (0) (por ejemplo, (S (S (0))) es el número para (2)). Las fórmulas principales son de la forma ((s = t)) donde (s, t) son términos, y las fórmulas compuestas se obtienen de estos como de costumbre.

Los axiomas lógicos y las reglas de (mathbf {HA}) son los de la lógica de predicados intuicionistas de primer orden (mathbf {IQC}). Los axiomas no lógicos incluyen las propiedades reflexivas, simétricas y transitivas de (=):) forall x (x = x),)) forall x / forall y (x = y / rightarrow y = x),)) forall x / forall y / forall z ((x = y / oldand y = z) rightarrow x = z);) el axioma que caracteriza a (0) como el menor número natural:

) forall x / neg (S (x) = 0),)

El axioma que caracteriza a (S) como una función uno a uno:

) forall x / forall y (S (x) = S (y) rightarrow x = y),)

El axioma de igualdad extensional para (S):

) forall x / forall y (x = y / rightarrow S (x) = S (y));)

Las ecuaciones de definición recursivas primitivas para cada constante de función, en particular para la suma:) forall x (x + 0 = x),)) forall x / forall y (x + S (y) = S (x + y));) y multiplicación:) forall x (x / cdot 0 = 0),)) forall x / forall y (x / cdot S (y) = (x / cdot y) + x);) y el (cierre universal del) esquema de inducción matemática, para fórmulas arbitrarias (A (x)):

[(A (0) oldand / forall x (A (x) rightarrow A (S (x)))) rightarrow / forall x A (x).)

Los axiomas de igualdad de extensión para todas las constantes de función se pueden derivar por inducción matemática del axioma de igualdad para (S) y los axiomas de funciones recursivas primitivas.

La relación de orden natural (x / lt y) se puede definir en (mathbf {HA}) por (exist z (S (z) + x = y)), o por el libre de cuantificador fórmula (S (x) dot {-} y = 0) si el símbolo y las ecuaciones de definición recursivas primitivas para el predecesor: [Pd (0) = 0,)) forall x (Pd (S (x)) = x)) y resta de corte:) forall x (x / dot {-} 0 = 0),)) forall x (x / dot {-} S (y) = Pd (x / dot {-} y))) están presentes en el formalismo. (mathbf {HA}) prueba la ley comparada

) forall x / forall y (x / lt y / vee x = y / vee y / lt x))

y una forma intuitiva del principio de menor número, para fórmulas arbitrarias (A (x)):

) forall x) forall y (y / lt x / rightarrow (A (y) vee / neg A (y))) rightarrow \(exist y ((y / lt x / oldand A (y)) oldand / forall z (z / lt y / rightarrow / neg A (z))) vee \\ / forall y (y / lt x / rightarrow / neg A (y)))].)

La hipótesis es necesaria porque no todas las fórmulas aritméticas son decidibles en (mathbf {HA}). Sin embargo, (forall x / forall y (x = y / vee / neg (x = y))) puede probarse directamente por inducción matemática, y así

Las fórmulas principales (y, por lo tanto, todas las fórmulas libres de cuantificadores) son decidibles y estables en (mathbf {HA}).

Si (A (x)) es decidible en (mathbf {HA}), entonces por inducción en (x) también lo son (forall y (y / lt x / rightarrow A (y))) y (existe y (y / lt x / oldand A (y))). Por lo tanto

Las fórmulas en las que todos los cuantificadores están limitados son decidibles y estables en (mathbf {HA}).

La colección (Delta_0) de fórmulas aritméticas en las que todos los cuantificadores están limitados es el nivel más bajo de una jerarquía aritmética clásica basada en el patrón de alternancia de cuantificadores en una fórmula de prenex. En (mathbf {HA}) no todas las fórmulas tienen una forma previa, pero Burr [2004] descubrió una jerarquía aritmética intuitiva simple que corresponde nivel por nivel al clásico. Para los propósitos de las siguientes dos definiciones solamente, (forall x) denota un bloque de finitamente muchos cuantificadores de números universales, y de manera similar (exist x) denota un bloque de finitamente muchos cuantificadores de números existenciales. Con estas convenciones, las clases de Burr (Phi_n) y (Psi_n) se definen por:

  • (Phi_0 = / Psi_0 = / Delta_0),
  • (Phi_1) es la clase de todas las fórmulas de la forma (forall x A (x)) donde (A (x)) está en (Psi_0). Para (n / ge 2), (Phi_n) es la clase de todas las fórmulas de la forma (forall x [A (x) rightarrow / exist y B (x, y)]) donde (A (x)) está en (Phi_ {n-1}) y (B (x, y)) está en (Phi_ {n-2}),
  • (Psi_1) es la clase de todas las fórmulas de la forma (exist x A (x)) donde (A (x)) está en (Phi_0). Para (n / ge 2), (Psi_n) es la clase de todas las fórmulas de la forma (A / rightarrow B) donde (A) está en (Phi_n) y (B) está en (Phi_ {n-1}).

Las clases prenexas clásicas correspondientes se definen de manera más simple:

  • (Pi_0 = / Sigma_0 = / Delta_0),
  • (Pi_ {n +1}) es la clase de todas las fórmulas de la forma (forall x A (x)) donde (A (x)) está en (Sigma_n),
  • (Sigma_ {n +1}) es la clase de todas las fórmulas de la forma (exist x A (x)) donde (A (x)) está en (Pi_n).

La aritmética de peano (mathbf {PA}) proviene de la aritmética de Heyting (mathbf {HA}) agregando LEM o (neg / neg A / rightarrow A) a la lista de axiomas lógicos, es decir, por usando la lógica clásica en lugar de la intuicionista. Los siguientes resultados se mantienen incluso en los fragmentos de (mathbf {HA}) y (mathbf {PA}) con el esquema de inducción restringido a las fórmulas (Delta_0).

Teorema de las rebabas:

  • Cada fórmula aritmética es demostrablemente equivalente en (mathbf {HA}) a una fórmula en una de las clases (Phi_n).
  • Cada fórmula en (Phi_n) es demostrablemente equivalente en (mathbf {PA}) a una fórmula en (Pi_n), y viceversa.
  • Cada fórmula en (Psi_n) es demostrablemente equivalente en (mathbf {PA}) a una fórmula en (Sigma_n), y viceversa.

(mathbf {HA}) y (mathbf {PA}) son equivalentes en teoría, como se mostrará en la Sección 4. Cada uno es capaz de (numéricamente) expresar su propio predicado de prueba. Según el famoso teorema de incompletitud de Gödel, si (mathbf {HA}) es consistente, entonces ni (mathbf {HA}) ni (mathbf {PA}) pueden probar su propia consistencia.

4. Teoría básica de la prueba

4.1 Traducir la lógica clásica a la intuicionista

Un hecho fundamental sobre la lógica intuicionista es que tiene la misma fuerza de consistencia que la lógica clásica. Para la lógica proposicional, esto fue probado por primera vez por Glivenko [1929].

Teorema de Glivenko

Una fórmula proposicional arbitraria (A) es demostrable clásicamente, si y solo si (neg / neg A) es demostrable intuitivamente.

El teorema de Glivenko no se extiende a la lógica de predicados, aunque una fórmula de predicado arbitraria (A) es clásicamente demostrable si y solo si (neg / neg A) es demostrable en la lógica de predicados intuicionista más el esquema de "cambio de doble negación".

) tag {DNS} forall x / neg / neg B (x) rightarrow / neg / neg / forall x B (x))

La traducción negativa más sofisticada de las teorías clásicas a las intuitivas, debido independientemente a Gödel y Gentzen, se asocia con cada fórmula (A) del lenguaje (L) otra fórmula (g (A)) (sin (vee) o (exist)), de modo que

  • (I) La lógica de predicados clásica prueba (A / leftrightarrow g (A)).
  • (II) La lógica del predicado intuicionista prueba (g (A) leftrightarrow / neg / neg g (A)).
  • (III) Si la lógica predicativa clásica prueba (A), entonces la lógica predicativa intuicionista prueba (g (A)).

Las pruebas son sencillas a partir de la siguiente definición inductiva de (g (A)) (usando la traducción directa de implicación de Gentzen, en lugar de la de Gödel en términos de (neg) y (oldand)):

) begin {align *} g (P) & / text {is} neg / neg P, / text {if} P / text {is prime}. \\ g (A / oldand B) & / text { es} g (A) oldand g (B). \\ g (A / vee B) & / text {is} neg (neg g (A) oldand / neg g (B)). \\ g (A / rightarrow B) & / text {is} g (A) rightarrow g (B). \\ g (neg A) y / text {is} neg g (A). \\ g (forall xA (x)) & / text {is} forall xg (A (x)). \\ g (exist xA (x)) & / text {is} neg / forall x / neg g (A (x)). / end {align *})

Para cada fórmula (A), (g (A)) es demostrable intuitivamente si y solo si (A) es demostrable clásicamente. En particular, si (B / oldand / neg B) fueran clásicamente demostrables para alguna fórmula (B), entonces (g (B) oldand / neg g (B)) (que es (g (B / oldand / neg B))) a su vez sería demostrable intuitivamente. Por lo tanto

(IV) La lógica de predicados clásica e intuicionista es equiconsistente

La traducción negativa de la teoría clásica al número intuitivo es aún más simple, ya que las fórmulas primarias de la aritmética intuicionista son estables. Por lo tanto, (g (s = t)) puede tomarse como (s = t), y las otras cláusulas no cambian. La traducción negativa de cualquier instancia de inducción matemática es otra instancia de inducción matemática, y los otros axiomas no lógicos de la aritmética son sus propias traducciones negativas, por lo que

(I), (II), (III) y (IV) se mantienen también para la teoría de números

Gödel [1933e] interpretó que estos resultados muestran que la lógica intuitiva y la aritmética son más ricas que la lógica y la aritmética clásicas, porque la teoría intuicionista distingue fórmulas que son clásicamente equivalentes y tiene la misma fuerza de consistencia que la teoría clásica. En particular, los teoremas de incompletitud de Gödel se aplican a (mathbf {HA}) así como a (mathbf {PA}).

Los intentos directos de extender la interpretación negativa al análisis fallan porque la traducción negativa del axioma contable de elección no es un teorema del análisis intuicionista. Sin embargo, es consistente con el análisis intuicionista, incluido el controvertido principio de continuidad de Brouwer, por la versión funcional de la realizabilidad recursiva de Kleene (véase la Sección 6.2 a continuación). De ello se deduce que las matemáticas intuicionistas, que solo se pueden expresar mediante el uso de todos los conectores y cuantificadores lógicos estándar, son consistentes con una traducción fiel de las matemáticas clásicas evitando (vee) y (exist).

Esto es importante porque el análisis intuicionista de Brouwer es inconsistente con LEM. Sin embargo, si (A) es una fórmula negativa (sin (vee) o (exist)), entonces (neg / neg A / rightarrow A) es demostrable utilizando la lógica intuicionista. En Moscovakis [2017] se sugiere una reconciliación del análisis intuicionista y clásico en este sentido, inspirado en la noción de secuencia de elección de Kripke.

4.2 Reglas admisibles de lógica intuitiva y aritmética

Gödel [1932] observó que la lógica proposicional intuicionista tiene la propiedad de disyunción:

(DP) Si (A / vee B) es un teorema, entonces (A) es un teorema o (B) es un teorema

Gentzen [1935] estableció la propiedad de disyunción para fórmulas cerradas de lógica de predicados intuicionistas. De esto se deduce que si la lógica intuicionista es consistente, entonces (P / vee / neg P) no es un teorema si (P) es una fórmula atómica. Kleene [1945, 1952] demostró que la teoría intuitiva de números de primer orden también tiene la propiedad de existencia relacionada (cf. Friedman [1975]):

(EP) Si (exist x A (x)) es un teorema cerrado, entonces para algún término cerrado (t), (A (t)) es un teorema

Las propiedades de disyunción y existencia son casos especiales de un fenómeno general peculiar de las teorías no clásicas. Las reglas admisibles de una teoría son las reglas bajo las cuales se cierra la teoría. Por ejemplo, Harrop [1960] observó que la regla

Si (neg A / rightarrow (B / vee C)) es un teorema, también lo es ((neg A / rightarrow B) vee (neg A / rightarrow C))

es admisible para la lógica proposicional intuitiva (mathbf {IPC}) porque si (A), (B) y (C) son fórmulas tales que (neg A / rightarrow (B / vee C)) es demostrable en (mathbf {IPC}), entonces también ((neg A / rightarrow B) vee (neg A / rightarrow C)) es demostrable en (mathbf {IPC }). La regla de Harrop no se puede derivar en (mathbf {IPC}) porque ((neg A / rightarrow (B / vee C)) rightarrow (neg A / rightarrow B) vee (neg A / rightarrow C)) no es intuitivamente demostrable. Otro ejemplo importante de una regla admisible no derivable de (mathbf {IPC}) es la regla de Mints:

Si ((A / rightarrow B) rightarrow (A / vee C)) es un teorema, también lo es (((A / rightarrow B) rightarrow A) vee ((A / rightarrow B) rightarrow C))).

La interpretación de la tabla de verdad de dos valores de la lógica proposicional clásica (mathbf {CPC}) da lugar a una prueba simple de que toda regla admisible de (mathbf {CPC}) es derivable: de lo contrario, alguna asignación a (A), (B), etc. harían que la hipótesis sea verdadera y la conclusión falsa, y sustituyendo, por ejemplo, (P / rightarrow P) por las letras asignadas "verdadero" y (P / oldand / neg P) para aquellos asignados "falso" uno tendría una hipótesis comprobable y una conclusión no demostrable. El hecho de que la situación intuicionista sea más interesante lleva a muchas preguntas naturales, algunas de las cuales han sido respondidas recientemente.

Al generalizar la Regla de Mints, Visser y de Jongh identificaron una secuencia recursivamente enumerable de reglas admisibles sucesivamente más fuertes ("Reglas de Visser") que, conjeturaron, formaron una base para las reglas admisibles de (mathbf {IPC}) en el sentido que cada regla admisible se deriva de la propiedad de disyunción y una de las reglas de la secuencia. Sobre la base del trabajo de Ghilardi [1999], Iemhoff [2001] logró demostrar su conjetura. Rybakov [1997] demostró que la colección de todas las reglas admisibles de (mathbf {IPC}) es decidible pero no tiene una base finita. Visser [2002] demostró que sus reglas son también las reglas proposicionales admisibles de (mathbf {HA}) y de (mathbf {HA}) extendidas por el Principio MP de Markov (definido en la Sección 5.2 a continuación). Más recientemente,Jerabek [2008] encontró una base independiente para las reglas admisibles de (mathbf {IPC}), con la propiedad de que ninguna regla en la base deriva otra.

Mucho menos se sabe sobre las reglas admisibles de la lógica de predicados intuicionistas. Pure (mathbf {IQC}), sin constantes individuales o predicadas, tiene la siguiente regla admisible notable para (A (x)) sin variables libres pero (x):

Si (exist x x (x)) es un teorema, también lo es (forall x A (x)).

No todas las reglas de predicado admisibles de (mathbf {IQC}) son admisibles para todos los sistemas formales basados en (mathbf {IQC}); por ejemplo, (mathbf {HA}) evidentemente viola la regla que se acaba de indicar. Visser demostró en [1999] que la propiedad de ser una regla predicada admisible de (mathbf {HA}) es (Pi_2) completa, y en [2002] que (mathbf {HA}) (+) MP tiene las mismas reglas admisibles de predicado que (mathbf {HA}). Plisko [1992] demostró que la lógica predicativa de (mathbf {HA}) (+) MP (el conjunto de oraciones en el lenguaje de (mathbf {IQC}) todas cuyas instancias de sustitución uniforme en el lenguaje de la aritmética es demostrable en (mathbf {HA}) (+) MP) es (Pi_2) completo; Visser [2006] extendió este resultado a algunas extensiones consistentes constructivamente interesantes de (mathbf {HA}) que no están contenidas en (mathbf {PA}).

Si bien no se han clasificado por completo, se sabe que las reglas admisibles de la lógica de predicados intuicionistas incluyen la Regla de Markov para predicados decidibles:

Si (forall x (A (x) vee / neg A (x)) oldand / neg / forall x / neg A (x)) es un teorema, también lo es (exist x A (x)).

y la siguiente regla de independencia de premisa (donde se supone que (y) no está libre en (A (x))):

Si (forall x (A (x) vee / neg A (x)) oldand (forall x A (x) rightarrow / exist y B (y))) es un teorema, entonces es (existe y (forall x A (x) rightarrow B (y))).

Ambas reglas también son admisibles para (mathbf {HA}). Las implicaciones correspondientes (MP e IP respectivamente), que no son demostrables intuitivamente, se verifican mediante la interpretación "dialéctica" de Gödel de (mathbf {HA}) (véase la sección 6.3 a continuación). Entonces, ¿la implicación (CT) corresponde a una de las reglas admisibles más interesantes de la aritmética de Heyting, llamémosla la Regla de Church-Kleene:

Si (forall x / existe y A (x, y)) es un teorema cerrado de (mathbf {HA}), entonces hay un número (n) tal que, probablemente en (mathbf {HA}), la función recursiva parcial con el número de Gödel (n) es total y asigna cada (x) a un (y) que satisface (A (x, y)) (y además (A (mathbf {x}, / mathbf {y})) es demostrable, donde (mathbf {x}) es el número para el número natural (x) y (mathbf {y}) es el número para (y)).

La combinación de la regla de Markov con la traducción negativa da el resultado de que la aritmética clásica e intuicionista prueba las mismas fórmulas de la forma (forall x / exist y A (x, y)) donde (A (x, y)) es sin cuantificador. En general, si (A (x, y)) es demostrablemente decidible en (mathbf {HA}) y si (forall x / existe y A (x, y)) es un teorema cerrado de aritmética clásica (mathbf {PA}), la conclusión de la Regla de Church-Kleene se mantiene incluso en la aritmética intuicionista. Porque si (mathbf {HA}) prueba (forall x / forall y (A (x, y) vee / neg A (x, y))) entonces por la Regla de Church-Kleene la función característica de (A (x, y)) tiene un número de Gödel (m), probablemente en (mathbf {HA}); entonces (mathbf {HA}) prueba (forall x / exist y A (x, y) leftrightarrow / forall x / exist y / exist z B (mathbf {m}, x, y, z)) donde (B) no tiene cuantificador,y los cuantificadores existenciales adyacentes se pueden contraer en (mathbf {HA}). De ello se deduce que (mathbf {HA}) y (mathbf {PA}) tienen las mismas funciones probables recursivas.

Aquí hay una prueba de que la regla "Si (forall x (A / vee B (x))) es un teorema, también lo es (A / vee / forall x B (x))" (donde (x) no está libre en (A)) no es admisible para (mathbf {HA}), si (mathbf {HA}) es consistente. La numeración de Gödel proporciona una fórmula libre de cuantificador (G (x)) que (numeralmente) expresa el predicado “(x) es el código de una prueba en (mathbf {HA}) de ((0 = 1)) ". Por lógica intuicionista con la capacidad de decisión de fórmulas aritméticas libres de cuantificadores, (mathbf {HA}) prueba (forall x (exist y G (y) vee / neg G (x))). Sin embargo, si (mathbf {HA}) resultó (exist yG (y) vee / forall x / neg G (x)) entonces por la propiedad de disyunción, (mathbf {HA}) debe probar (exist yG (y)) o (forall x / neg G (x)). El primer caso es imposible.por la propiedad de existencia con el supuesto de coherencia y el hecho de que (mathbf {HA}) prueba todas las oraciones verdaderas sin cuantificador. Pero el segundo caso también es imposible, según el segundo teorema de incompletitud de Gödel, ya que (forall x / neg G (x)) expresa la consistencia de (mathbf {HA}).

5. Semántica básica

Los sistemas intuitivos han inspirado una variedad de interpretaciones, incluidos los cuadros de Beth, los modelos topológicos de Rasiowa y Sikorski, las álgebras de Heyting, las fórmulas como tipos, las realizaciones recursivas de Kleene, las barras de Kleene y Aczel, y los modelos basados en gavillas y topoi. De todas estas interpretaciones, la semántica del mundo posible de Kripke [1965], con respecto a la cual la lógica del predicado intuicionista es completa y consistente, se parece más a la teoría de modelos clásicos. Las interpretaciones recursivas de realizabilidad, por otro lado, intentan implementar efectivamente la explicación BHK de la verdad intuicionista.

5.1 Semántica de Kripke para la lógica intuicionista

Una estructura de Kripke (mathbf {K}) para (L) consiste en un conjunto parcialmente ordenado (K) de nodos y una función de dominio D que se asigna a cada nodo (k) en (K) un conjunto habitado (D (k)), de modo que si (k / le k '), entonces (D (k) subseteq D (k')). Además, (mathbf {K}) tiene una relación forzada determinada de la siguiente manera.

Para cada nodo (k) sea (L (k)) el lenguaje que se extiende (L) por nuevas constantes para todos los elementos de (D (k)). Para cada nodo (k) y cada (0) - letra predicada aria (cada letra de propuesta) (P), asigne (f (P, k) =) verdadero o deje (f (P, k)) indefinido, consistente con el requisito de que si (k / le k ') y (f (P, k) =) verdadero entonces (f (P, k') =) verdadero además. Dilo

(k) (vDash) (P) si y solo si (f (P, k) =) verdadero.

Para cada nodo (k) y cada ((n + 1)) - letra predicada aria (Q (ldots)), asigne un conjunto (posiblemente vacío) (T (Q, k)) of ((n + 1)) - tuplas de elementos de (D (k)) de tal manera que si (k / le k ') entonces (T (Q, k) subseteq T (Q, k ')). Dilo

(k) (vDash) (Q (d_0, / ldots, d_n)) si y solo si ((d_0, / ldots, d_n) in T (Q, k)).

Ahora defina (k) (vDash) (E) (que puede leerse "(k) force (E)") para oraciones compuestas (E) de (L (k)) inductivamente como sigue:

(k) (vDash) ((A / oldand B)) if (k) (vDash) (A) y (k) (vDash) (B).
(k) (vDash) ((A / vee B)) si (k) (vDash) (A) o (k) (vDash) (B).
(k) (vDash) ((A / rightarrow B)) if, para cada (k '\ ge k), if (k') (vDash) (A) luego (k ') (vDash) (B).
(k) (vDash) (neg A) if for no (k '\ ge k) does (k') (vDash) (A).
(k) (vDash) (forall x A (x)) si para cada (k '\ ge k) y cada (d / en D (k')), (k ') (vDash) (A (d)).
(k) (vDash) (exist x A (x)) si para algunos (d / in D (k)), (k) (vDash) (A (d)).

Cualquier relación forzada es consistente:

Para ninguna oración (A) y no (k) es el caso de que tanto (k) (vDash) (A) como (k) (vDash) (neg A).

y monótono:

Si (k / le k ') y (k) (vDash) (A) entonces (k') (vDash) (A).

Los teoremas de solidez e integridad de Kripke establecen que una oración de (L) es demostrable en la lógica del predicado intuicionista si y solo si es forzada por cada nodo de cada estructura de Kripke. Por lo tanto, para mostrar que (neg / forall x / neg P (x) rightarrow / exist x P (x)) es intuitivamente no demostrable, es suficiente considerar una estructura de Kripke con (K = {k, k '},) (k / lt k',) (D (k) = D (k ') = {0 }), (T (P, k)) vacío pero (T (P, k ') = {0 }). Y para mostrar que lo contrario es demostrable intuitivamente (sin exhibir realmente una prueba), uno solo necesita las propiedades de consistencia y monotonicidad de los modelos arbitrarios de Kripke, con la definición de (vDash).

Los modelos de Kripke para idiomas con igualdad pueden interpretar (=) en cada nodo mediante una relación de equivalencia arbitraria, sujeta a monotonicidad. Para las aplicaciones a la aritmética intuicionista, los modelos normales (aquellos en los que la igualdad se interpreta por la identidad en cada nodo) son suficientes porque la igualdad de los números naturales es decidible.

La semántica de Kripke proposicional es particularmente simple, ya que una fórmula proposicional arbitraria es demostrable intuitivamente si y solo si es forzada por la raíz de cada modelo de Kripke cuyo marco (el conjunto (K) de nodos junto con su ordenamiento parcial) es finito árbol con un elemento mínimo (la raíz). Por ejemplo, el modelo de Kripke con (K = {k, k ', k' '}, k / lt k') y (k / lt k ''), y con (P) verdadero solo en (k '), muestra que tanto (P / vee / neg P) como (neg P / vee / neg / neg P) no se pueden probar en (mathbf {IPC}).

Cada nodo terminal u hoja de un modelo de Kripke es un modelo clásico, porque una hoja fuerza cada fórmula o su negación. Solo aquellas letras de proposiciones que aparecen en una fórmula (E), y solo aquellos nodos (k ') tales que (k / le k'), son relevantes para decidir si (k) fuerza o no \(MI). Tales consideraciones nos permiten asociar efectivamente con cada fórmula (E) de (L (mathbf {IPC})) una clase finita de estructuras de Kripke finitas que incluirán un contramodelo a (E) si existe. Dado que la clase de todos los teoremas de (mathbf {IPC}) es recursivamente enumerable, concluimos que

(mathbf {IPC}) es efectivamente decidible. Hay un procedimiento recursivo que determina, para cada fórmula proposicional (E), si (E) es o no un teorema de (mathbf {IPC}), concluyendo con una prueba de (E) o un contramodelo de Kripke (finito).

La capacidad de decisión de (mathbf {IPC}) fue obtenida por primera vez por Gentzen en 1935. La indecidibilidad de (mathbf {IQC}) se deriva de la indecidibilidad de (mathbf {CQC}) por la interpretación negativa.

Los esquemas lógicos no intuicionistas familiares corresponden a propiedades estructurales de los modelos de Kripke, por ejemplo

  • DNS se mantiene en todos los modelos Kripke con marco finito.
  • ((A / rightarrow B) vee (B / rightarrow A)) se mantiene en cada modelo de Kripke con marco ordenado linealmente. Por el contrario, cada fórmula proposicional que no es derivable en (mathbf {IPC} + (A / rightarrow B) vee (B / rightarrow A)) tiene un contramodelo Kripke con marco ordenado linealmente (ver Sección 6.1 a continuación).
  • Si (x) no está libre en (A), entonces (forall x (A / vee B (x)) rightarrow (A / vee / forall x B (x))) se mantiene en cada Kripke modelo (mathbf {K}) con dominio constante (de modo que (D (k) = D (k ')) para todos (k, k') en (K)). Lo mismo es cierto para MP.

Los modelos Kripke y Beth (que difieren de los modelos Kripke en detalle, pero son intuitivamente equivalentes) son una herramienta poderosa para establecer las propiedades de los sistemas formales intuicionistas; cf. Troelstra y van Dalen [1988], Smorynski [1973], de Jongh y Smorynski [1976], Ghilardi [1999] e Iemhoff [2001], [2005]. Sin embargo, no existe una prueba puramente intuitiva de que cada oración que sea válida en todos los modelos de Kripke y Beth sea demostrable en (mathbf {IQC}). Tras una observación de Gödel, Kreisel [1958] verificó que la integridad de la lógica de predicados intuicionistas para la semántica de Beth es equivalente al Principio MP de Markov, que Brouwer rechazó.

Además, Dyson y Kreisel [1961] mostraron que si (mathbf {IQC}) está débilmente completo para la semántica de Beth (es decir, si no se cumple una oración no demostrable en cada modelo de Beth), entonces la siguiente consecuencia de MP se cumple: [tag {GDK} forall / alpha_ {B (alpha)} neg / neg / exist x R (alpha, x) rightarrow / neg / neg / forall / alpha_ {B (alpha)} exist x R (alpha, x),) donde (x) se extiende sobre todos los números naturales, (alpha) se extiende sobre todas las secuencias infinitas de números naturales, (B (alpha)) abrevia (para x (alpha (x) leq 1)), y (R) expresa una relación recursiva primitiva de (alpha) y (x). Por el contrario, GDK implica la completitud débil de (mathbf {IQC}). Este interesante principio, que justificaría la interpretación negativa de una forma del teorema del ventilador de Brouwer,es más débil que MP pero no demostrable en los sistemas actuales de análisis intuicionista. Kreisel [1962] sugirió que GDK podría ser demostrable en base a las propiedades aún no descubiertas de las matemáticas intuicionistas.

Al modificar la definición de un modelo de Kripke para permitir "nodos explosivos" que fuerzan cada oración, Veldman [1976] encontró una prueba de integridad utilizando solo la lógica intuicionista, pero cuestionó si los modelos Kripke con nodos explosivos eran objetos matemáticos intuitivamente significativos.

5.2 Semántica de realizabilidad para la aritmética de Heyting

Una forma de implementar la explicación BHK de la verdad intuicionista para la aritmética es asociar con cada oración (E) de (mathbf {HA}) alguna colección de códigos numéricos para algoritmos que puedan establecer la verdad constructiva de (E). Siguiendo a Kleene [1945], un número (e) realiza una oración (E) del lenguaje de la aritmética por inducción en la forma lógica de (E):

(e) se da cuenta de (r = t) si (r = t) es verdadero.
(e) se da cuenta de (A / oldand B) si (e) codifica un par ((f, g)) de modo que (f) se da cuenta de (A) y (g) se da cuenta de (B).
(e) se da cuenta de (A / vee B) if (e) codifica un par ((f, g)) de modo que if (f = 0) entonces (g) se da cuenta de (A), y if (f / gt 0) entonces (g) realiza (B).
(e) se da cuenta de (A / rightarrow B) si, cada vez que (f) se da cuenta de (A), entonces la función recursiva parcial (e) se define en (f) y su valor se da cuenta de (B).
(e) se da cuenta de (neg A) si no (f) se da cuenta de (A).
(e) se da cuenta de (forall x A (x)) si, para cada (n), la función recursiva parcial (e) th se define en (n) y su valor se da cuenta de (A (mathbf {n})).
(e) se da cuenta de (exist x A (x)) si (e) codifica un par ((n, g)) y (g) realiza (A (mathbf {n})).

Una fórmula arbitraria es realizable si algún número se da cuenta de su cierre universal. Observe que no tanto (A) como (neg A) son realizables, para cualquier fórmula (A). El resultado fundamental es

El teorema de Nelson [1947]

Si (A) es derivable en (mathbf {HA}) a partir de fórmulas realizables (F), entonces (A) es realizable.

Se puede demostrar que algunos principios no intuicionistas son realizables. Por ejemplo, el principio de Markov (para fórmulas decidibles) puede expresarse mediante el esquema

(MP) (forall x (A (x) vee / neg A (x)) oldand / neg / forall x / neg A (x) rightarrow / exist x x (X))

Aunque no se puede demostrar en (mathbf {HA}), MP es realizable mediante un argumento que utiliza el Principio de Markov de manera informal. Pero la realizabilidad es una interpretación fundamentalmente no clásica. En (mathbf {HA}) es posible expresar un axioma de elección recursiva CT (para "Tesis de la Iglesia"), que contradice LEM pero es (constructivamente) realizable. Por lo tanto, según el teorema de Nelson, (mathbf {HA}) (+) MP (+) CT es consistente.

Kleene utilizó una variante de posibilidad de realización de números para demostrar que (mathbf {HA}) satisface la Regla de Church-Kleene; el mismo argumento funciona para (mathbf {HA}) con MP o CT, y para (mathbf {HA}) (+) MP (+) CT. En Kleene y Vesley [1965] y Kleene [1969], las funciones reemplazan a los números como objetos de realización, estableciendo la consistencia del análisis intuicionista formalizado y su cierre bajo una versión de segundo orden de la Regla Iglesia-Kleene.

El teorema de Nelson establece la improbabilidad en (mathbf {IQC}) de algunos teoremas de la lógica de predicados clásica. Si, para cada (n) - coloca la letra de predicado (P (ldots)), una fórmula (f (P)) de (L (mathbf {HA})) con (n) se asignan variables libres, y si la fórmula (f (A)) de (L (mathbf {HA})) proviene de la fórmula (A) de (L) al reemplazar cada fórmula principal (P (x_1, / ldots, x_n)) por (f (P) (x_1, / ldots, x_n)), entonces (f (A)) se llama una instancia de sustitución aritmética de (UNA). Como ejemplo, si una fórmula de (L (mathbf {HA})) que expresa “(x) codifica una prueba en (mathbf {HA}) de la fórmula con el código (y) Se asigna a (P (x, y)), la instancia de sustitución aritmética resultante de (forall y (exist x P (x, y) vee / neg / exist x P (x, y))) es irrealizable y, por lo tanto, no demostrable en (mathbf {HA}), y también lo es su doble negación. De ello se deduce que (neg / neg / forall y (exist x P (x, y) vee / neg / exist x P (x, y))) no es demostrable en (mathbf {IQC})

De Jongh [1970] combinó la realizabilidad con el modelado de Kripke para mostrar que la lógica proposicional intuitiva (mathbf {IPC}) y un fragmento de (mathbf {IQC}) están aritméticamente completos para (mathbf {HA}) Una asignación uniforme de fórmulas existenciales simples para predicar letras es suficiente para demostrar

Teorema de De Jongh (para IPC) [1970]

Si una fórmula proposicional (A) del lenguaje (L) no es demostrable en (mathbf {IPC}), entonces alguna instancia de sustitución aritmética de (A) no es demostrable en (mathbf {HA}).

La prueba de esta versión del Teorema de de Jongh no necesita realizabilidad; cf. Smorynski [1973]. Como ejemplo, la forma de Rosser del Teorema de incompletitud de Gödel proporciona una oración (C) de (L (mathbf {HA})) tal que (mathbf {PA}) no prueba ni (C) ni (neg C), por lo que por la propiedad de disyunción (mathbf {HA}) no se puede probar ((C / vee / neg C)). Pero la prueba semántica de De Jongh también estableció que toda fórmula de predicado intuitivamente no demostrable de un tipo restringido tiene una instancia de sustitución aritmética que no se puede probar en (mathbf {HA}). Utilizando un método sintáctico, Daniel Leivant [1979] extendió el Teorema de De Jongh a todas las fórmulas de predicados intuitivamente no demostrables, demostrando que (mathbf {IQC}) está aritméticamente completo para (bf {HA}). Ver van Oosten [1991] para una exposición histórica y una prueba más simple del teorema completo, utilizando la realizabilidad abstracta con los modelos Beth en lugar de los modelos Kripke.

Sin afirmar que la realizabilidad numérica coincide con la verdad aritmética intuicionista, Nelson observó que para cada fórmula (A) de (L (mathbf {HA})) el predicado "(y) realiza (A) "Puede expresarse en (mathbf {HA}) mediante otra fórmula (abreviada" (y / realizesrel A) "), y el esquema (A / leftrightarrow / existe y (y / realizesrel A)) es consistente con (mathbf {HA}). Troelstra [1973] demostró que (mathbf {HA}) (+) ((A / leftrightarrow / exist y (y / realizesrel A))) es equivalente a (mathbf {HA}) (+) ECT, donde ECT es una forma fortalecida de CT. En (mathbf {HA}) (+) MP (+) ECT, que Troelstra considera una formalización de las matemáticas recursivas rusas (véase la sección 3.2 de la entrada sobre matemáticas constructivas), cada fórmula de la forma ((y / realizesrel A)) tiene una forma prenexa "clásica" equivalente (A '(y)) que consiste en una subformula libre de cuantificadores precedida por cuantificadores “clásicos” alternos de las formas (neg / neg / exist x) y (forall z / neg / neg), y entonces (exist y A '(y)) es una especie de forma de anexo de (A).

6. Temas adicionales y lecturas adicionales

6.1 Lógicas subintucionistas e intermedias

En la actualidad, hay varias otras entradas en esta enciclopedia que tratan la lógica intuicionista en diversos contextos, pero parece que falta un tratamiento general de lógicas proposicionales y predicadas cada vez más fuertes. Muchas de estas lógicas han sido identificadas y estudiadas. Aquí están algunos ejemplos.

Se puede obtener una lógica proposicional subintucionista a partir de (mathbf {IPC}) restringiendo el lenguaje o debilitando la lógica, o ambas. Un ejemplo extremo de lo primero es (mathbf {RN}), lógica intuicionista con una sola variable proposicional (P), que lleva el nombre de sus descubridores Rieger y Nishimura [1960]. (mathbf {RN}) se caracteriza por la red de Rieger-Nishimura de infinitas fórmulas no equivalentes (F_n) de modo que cada fórmula cuya única variable proposicional es (P) es equivalente por lógica intuitiva a alguna (F_n). La versión de Nishimura es

) begin {align *} F _ { infty} & = P / rightarrow P. \\ F_0 & = P / oldand / neg P. \\ F_1 & = P. \\ F_2 & = / neg P. \\ F_ {2 n + 3} & = F_ {2 n + 1} vee F_ {2n + 2}. \\ F_ {2 n + 4} & = F_ {2 n + 3} rightarrow F_ {2 n + 1}. / end {align *})

En (mathbf {RN}) ni (F_ {2 n + 1}) ni (F_ {2 n + 2}) implica el otro; pero (F_ {2 n}) implica (F_ {2 n + 1}), y (F_ {2 n + 1}) implica cada uno de (F_ {2 n + 3}) y (F_ {2 n + 4}).

Los fragmentos de (mathbf {IPC}) que faltan uno o más conectivos lógicos restringen el lenguaje e incidentalmente la lógica, ya que los conectivos intuicionistas (oldand), (vee), (rightarrow), (neg) son lógicamente independientes sobre (mathbf {IPC}). Rose [1953] demostró que el fragmento sin implicación (sin (rightarrow)) está completo con respecto a la realizabilidad, en el sentido de que si cada instancia de sustitución aritmética de una fórmula proposicional (E) sin (rightarrow) es (número) -realizable entonces (E) es un teorema de (mathbf {IPC}). Este resultado contrasta con

El teorema de Rose [1953]

(mathbf {IPC}) está incompleto con respecto a la realizabilidad.

Sea (F) la fórmula proposicional [((neg / neg D / rightarrow D) rightarrow (neg / neg D / vee / neg D)) rightarrow (neg / neg D / vee / neg D)) donde (D) es ((neg P / vee / neg Q)) y (P), (Q) son primos. Cada instancia de sustitución aritmética de (F) es realizable (usando lógica clásica), pero (F) no es demostrable en (mathbf {IPC}).

De ello se deduce que (mathbf {IPC}) está aritméticamente incompleto para (mathbf {HA}) (+) ECT (véase la Sección 5.2).

La lógica mínima (mathbf {ML}) proviene de la lógica intuicionista al eliminar ex falso. Kolmogorov [1925] mostró que este fragmento ya contiene una interpretación negativa de la lógica clásica que conserva ambos cuantificadores, cf. Leivant [1985]. La lógica mínima prueba el caso especial (neg A / rightarrow (A / rightarrow / neg B)) de ex falso para las negaciones. Colacito, de Jongh y Vardas [2017] estudian varias lógicas submínimas, cada una más débil que (mathbf {ML}).

Griss cuestionó el uso de la negación por parte de Brouwer, objetando tanto la ley de contradicción como la ex falso. Vale la pena señalar que la negación no es realmente necesaria para las matemáticas intuicionistas ya que (0 = 1) es una contradicción conocida, por lo que (neg A) puede definirse por (A / rightarrow 0 = 1). Entonces ex falso puede expresarse como (0 = 1 / rightarrow A), y la ley de contradicción puede demostrarse a partir de los axiomas restantes de (mathbf {H}).

Una lógica proposicional intermedia es cualquier colección consistente de fórmulas proposicionales que contiene todos los axiomas de (mathbf {IPC}) y se cierra bajo modus ponens y la sustitución de fórmulas arbitrarias por letras de propuesta. Cada lógica proposicional intermedia está contenida en (mathbf {CPC}). Algunas lógicas proposicionales intermedias particulares, caracterizadas por agregar uno o más esquemas de axiomas clásicamente correctos pero intuitivamente no demostrables a (mathbf {IPC}), se han estudiado ampliamente.

Una de las lógicas proposicionales intermedias más simples es la lógica de Gödel-Dummett (mathbf {LC}), obtenida agregando a (mathbf {IPC}) el esquema ((A / rightarrow B) vee (B / rightarrow A)) que es válido en todos y solo aquellos marcos de Kripke en los que el orden parcial de los nodos es lineal. Gödel [1932] usó una secuencia infinita de lógicas intermedias sucesivamente más fuertes para mostrar que (mathbf {IPC}) no tiene una interpretación finita de la tabla de verdad. Para cada entero positivo (n), deje que (mathbf {G_n}) sea (mathbf {LC}) más el esquema ((A_1 / rightarrow A_2) vee / ldots / vee (A_1 / oldand / ldots / oldand A_n / rightarrow A_ {n + 1})). Entonces (mathbf {G_n}) es válido en todos y solo aquellos marcos de Kripke ordenados linealmente con no más de (n) nodos.

La lógica de Jankov (mathbf {KC}), que agrega a (mathbf {IPC}) el principio de comprobabilidad (neg A / vee / neg / neg A), obviamente no tiene la disyunción propiedad. La lógica de Kreisel-Putnam (mathbf {KP}), obtenida agregando a (mathbf {IPC}) el esquema ((neg A / rightarrow B / vee C) rightarrow ((neg A / rightarrow B) vee (neg A / rightarrow C))), tiene la propiedad de disyunción pero no cumple con todas las reglas de Visser. La lógica intermedia obtenida al agregar el esquema (((neg / neg D / rightarrow D) rightarrow (D / vee / neg D)) rightarrow (neg / neg D / vee / neg D)), correspondiente al contraejemplo de Rose, a (mathbf {IPC}) también tiene la propiedad de disyunción. Iemhoff [2005] demostró que (mathbf {IPC}) es la única lógica proposicional intermedia con la propiedad de disyunción que está cerrada bajo todas las reglas de Visser. Iemhoff y Metcalfe [2009] desarrollaron un cálculo formal para la admisibilidad generalizada de (mathbf {IPC}) y algunas lógicas intermedias. Goudsmit [2015] es un estudio exhaustivo de las reglas admisibles de las lógicas intermedias, con una bibliografía exhaustiva.

Se dice que una lógica proposicional intermedia (mathbf {L}) tiene la propiedad de marco finito si hay una clase de marcos finitos en la que las fórmulas válidas de Kripke son exactamente los teoremas de (mathbf {L}). Muchas lógicas intermedias, incluidas (mathbf {LC}) y (mathbf {KP}), tienen esta propiedad. Jankov [1968] usó una secuencia infinita de marcos Kripke enraizados finitos para demostrar que hay continuas muchas lógicas intermedias. De Jongh, Verbrugge y Visser [2009] demostraron que cada lógica intermedia (mathbf {L}) con la propiedad de marco finito es la lógica proposicional de (mathbf {HA (L)}), es decir, el clase de todas las fórmulas en el lenguaje de (mathbf {IPC}) todas cuyas instancias de sustitución aritmética son demostrables en la extensión lógica de (mathbf {HA}) por (mathbf {L}).

Una lógica proposicional intermedia (mathbf {L}) está estructuralmente completa si cada regla que es admisible para (mathbf {L}) se puede derivar en (mathbf {L}), y hereditariamente estructuralmente completa si cada lógica intermedia que se extiende (mathbf {L}) también está estructuralmente completa. Cada lógica intermedia (mathbf {L}) tiene una terminación estructural (mathbf { overline {L}}), obtenida al unir todas sus reglas admisibles. (mathbf {LC}) y (mathbf {G_n}) están estructuralmente completas de forma hereditaria. Mientras que (mathbf {IPC}), (mathbf {RN}) y (mathbf {KC}) no están estructuralmente completas, sus terminaciones estructurales son hereditariamente estructuralmente completas. Para estos resultados y más, vea Citkin [2016, Otros recursos de Internet].

Algunas lógicas de predicados intermedios, que se extienden (mathbf {IQC}) y se cierran bajo sustitución, son (mathbf {IQC}) (+) DNS (Sección 4.1), (mathbf {IQC}) (+) MP (véase la Sección 5.2), (mathbf {IQC}) (+) MP (+) IP (véase la Sección 4.2), y la lógica intuicionista de dominios constantes (mathbf {CD}) obtenido al agregar a (mathbf {IQC}) el esquema (forall x (A / vee B (x)) rightarrow (A / vee / forall x B (x))) para todas las fórmulas (A), (B (x)) con (x) que no aparece libre en (A). Mints, Olkhovikov y Urquhart [2012, Otros recursos de Internet] mostraron que (mathbf {CD}) no tiene la propiedad de interpolación, refutando las pruebas publicadas anteriormente por otros autores.

6.2 Temas avanzados

La influencia de Brouwer en Gödel fue significativa, aunque Gödel nunca se convirtió en un intuicionista. La traducción de Gödel [1933f] de la lógica proposicional intuicionista a la lógica modal (mathbf {S4}) se describe en la Sección 2.5 de la entrada sobre Gödel y en la nota introductoria de Troelstra a la traducción de [1933f] en el Volumen I de Gödel's Collected Trabajos. Ver también Mentas [2012]. Los modelos de Kripke para la lógica modal son anteriores a los de la lógica intuicionista.

Las alternativas a la semántica de Kripke y Beth para la lógica proposicional proposicional y predicativa incluyen la interpretación topológica de Stone [1937], Tarski [1938] y Mostowski [1948] (cf. Rasiowa y Sikorski [1963], Rasiowa [1974]), que se amplió al análisis intuicionista de Scott [1968] y Krol [1978]. M. Hyland [1982] definió el efectivo topos Eff y demostró que su lógica es intuicionista. Para una discusión muy informativa de la semántica para la lógica intuitiva y las matemáticas por W. Ruitenberg, y una nueva perspectiva interesante por G. Bezhanishvili y W. Holliday, ver Otros recursos de Internet (a continuación).

Una alternativa a la semántica de realizabilidad para la aritmética intuicionista es la interpretación "dialéctica" de Gödel [1958], que se asocia con cada fórmula (B) de (L (mathbf {HA})) una fórmula libre de cuantificadores (B_D) en el lenguaje de la aritmética intuicionista de todos los tipos finitos. La interpretación "dialéctica" de (B), llámela (B ^ D), es (exist Y / forall x B_D (Y, x)). Si (B) es un teorema cerrado de (mathbf {HA}), entonces (B_D (F, x)) es demostrable para algún término (F) en la teoría de Gödel (mathbf { T}) de funciones "primitivas recursivas" de tipo superior. La traducción de (B) a (B ^ D) requiere el axioma de elección (en todos los tipos finitos), MP e IP, por lo que no es estrictamente constructivo; sin embargo,Las funciones teóricas numéricas que se expresan mediante los términos (F) de (mathbf {T}) son precisamente las funciones probables y recursivas de (mathbf {HA}) (y de (mathbf {PA})). La interpretación fue extendida al análisis por Spector [1962]; cf. Howard [1973]. Se pueden encontrar exposiciones claras y referencias adicionales en la introducción de Troelstra a la traducción al inglés en Gödel [1990] del artículo original de Dialectica, en Avigad y Feferman [1998], y en Ferreira [2008].

Si bien (mathbf {HA}) es una parte adecuada de la aritmética clásica, la actitud intuicionista hacia los objetos matemáticos da como resultado una teoría de los números reales (cf. secciones 3.4 a 3.7 de la entrada sobre el intuicionismo en la filosofía de las matemáticas) divergente De lo clásico. La interpretación de la función de realizabilidad de Kleene, desarrollada para demostrar la consistencia de su formalización (mathbf {FIM}) de la teoría intuicionista de secuencias ("análisis intuicionista"), cambia la interpretación de las fórmulas aritméticas; por ejemplo, (neg / neg / forall x (A (x) vee / neg A (x))) es realizable por función para cada fórmula aritmética (A (x)). En el lenguaje de análisis,El Principio de Markov y la traducción negativa del axioma contable de elección se encuentran entre los muchos principios no intuicionistas que son realizables en función (por argumentos clásicos) y, por lo tanto, consistentes con (mathbf {FIM}); cf. Kleene [1965], Vesley [1972] y Moschovakis [2003].

La lógica de realización concreta y abstracta para una amplia variedad de sistemas formales ha sido desarrollada y estudiada por lógicos e informáticos; cf. Troelstra [1998] y van Oosten [2002] y [2008]. Las variaciones de las nociones básicas son especialmente útiles para establecer la consistencia relativa y la independencia relativa de los axiomas no lógicos en las teorías basadas en la lógica intuicionista; algunos ejemplos son Moschovakis [1971], Lifschitz [1979], y las nociones de realizabilidad para teorías de conjuntos constructivos e intuicionistas desarrolladas por Rathjen [2006, 2012] y Chen [2012]. Las primeras nociones abstractas de realizabilidad incluyen los cortes de Kleene [1962, 1963] y Aczel [1968], y Läuchli [1970]. Kohlenbach, Avigad y otros han desarrollado interpretaciones de realización para partes de las matemáticas clásicas.

La lógica de justificación de Artemov es una interpretación alternativa de la explicación BHK de los conectivos y cuantificadores intuicionistas, con pruebas (idealizadas) que desempeñan el papel de objetos de realización. Ver también Artemov e Iemhoff [2007].

Otra línea de investigación en lógica intuicionista se refiere a la muy controvertida "creación de contraejemplos de sujetos" de Brouwer a los principios del análisis clásico (como el Principio de Markov) que no se puede refutar sobre la base de la teoría (mathbf {FIM}) de Kleene y Vesley [1965]. Al debilitar la forma de Kleene del principio de elección continua de Brouwer, y al agregar un axioma que llamó el Esquema de Kripke (KP), Myhill logró formalizar los argumentos de los temas de creación. KP es inconsistente con (mathbf {FIM}), pero Vesley [1970] encontró un principio alternativo (Vesley's Schema VS) que se puede agregar consistentemente a (mathbf {FIM}) e implica todos los contraejemplos para los cuales Brouwer requirió un tema de creación. Krol [1978] y Scowcroft dieron pruebas de consistencia topológica para el análisis intuicionista con el esquema de Kripke y la continuidad débil.

6.3 Lectura recomendada

La entrada sobre LEJ Brouwer discute la filosofía y las matemáticas de Brouwer, con una cronología de su vida y una lista seleccionada de publicaciones que incluyen traducciones y fuentes secundarias. La mejor manera de aprender más es leer algunos de los documentos originales. Las traducciones al inglés de la tesis doctoral de Brouwer y otros documentos que aparecieron originalmente en holandés, junto con varios artículos en alemán, se pueden encontrar en LEJ Brouwer: Collected Works [1975], editado por Heyting. El libro fuente esencial de Benacerraf y Putnam contiene Brouwer [1912] (en traducción al inglés), Brouwer [1949] y Dummett [1975]. Mancosu [1998] proporciona traducciones al inglés de muchos artículos fundamentales de Brouwer, Heyting, Glivenko y Kolmogorov, con material introductorio esclarecedor de W. van Stigt cuyo [1990] es otro recurso valioso.

La tercera edición [1971] del clásico de Heyting [1956] es una introducción atractiva a la filosofía intuitiva, la lógica y la práctica matemática. Como parte del formidable proyecto de edición y publicación de Nachlass de Brouwer, van Dalen [1981] ofrece una visión integral de la filosofía intuicionista de Brouwer. La traducción al inglés, en van Heijenoort [1969], de Brouwer [1927] (con una buena introducción de Parsons) sigue siendo una referencia indispensable para la teoría del continuo de Brouwer. Veldman [1990] y [2005] son auténticos ejemplos modernos de práctica matemática intuicionista tradicional. Troelstra [1991] coloca la lógica intuicionista en su contexto histórico como la base común de las matemáticas constructivas en el siglo XX. Bezhanishvili y de Jongh [2005,Otros recursos de Internet] incluye desarrollos recientes en lógica intuicionista.

Kleene y Vesley [1965] ofrece un tratamiento axiomático cuidadoso del análisis intuicionista, una prueba de su consistencia en relación con una subteoría clásica y correcta, y una aplicación extendida a la teoría de Brouwer de generadores de números reales. Kleene [1969] formaliza la teoría de los funcionales recursivos parciales, permitiendo formalizaciones precisas de la interpretación de la realización de funciones utilizada en [1965] y de una interpretación relacionada de la realizabilidad q que da la Regla de Church-Kleene para el análisis intuicionista.

Troelstra [1973], Beeson [1985] y Troelstra y van Dalen [1988] (con correcciones) se destacan como los estudios más completos de teorías formales intuicionistas y semi-intuicionistas, utilizando métodos constructivos y clásicos, con bibliografías útiles. Troelstra y Schwichtenberg [2000] presentan la teoría de prueba de la lógica clásica, intuitiva y mínima en paralelo, centrándose en los sistemas secuenciales. Troelstra [1998] presenta interpretaciones de fórmulas como tipos y (Kleene y Aczel) para la lógica proposicional y de predicados, así como las realizaciones abstractas y concretas para una multitud de aplicaciones. La teoría constructiva de los tipos de Martin-Löf [1984] (véase la Sección 3.4 de la entrada sobre matemáticas constructivas) proporciona otro marco general dentro del cual el razonamiento intuicionista continúa desarrollándose.

Bibliografía

  • Aczel, P., 1968, "Teorías intuicionistas saturadas", en HA Schmidt, K. Schütte y H.-J. Thiele (eds.), Contribuciones a la lógica matemática, Amsterdam: Holanda del Norte: 1–11.
  • Artemov, S. e Iemhoff, R., 2007, "La lógica intuitiva básica de las pruebas", Journal of Symbol Logic, 72: 439-451.
  • Avigad, J. y Feferman, S., 1998, "Interpretación funcional de Gödel (" Dialéctica ")", Capítulo V de Buss (ed.) 1998: 337–405.
  • Bar-Hillel, Y. (ed.), 1965, Lógica, Metodología y Filosofía de la Ciencia, Amsterdam: Holanda del Norte.
  • Beeson, MJ, 1985, Fundamentos de Matemática Constructiva, Berlín: Springer.
  • Benacerraf, P. e Hilary Putnam (eds.), 1983, Filosofía de la matemática: lecturas seleccionadas, 2ª edición, Cambridge: Cambridge University Press.
  • Beth, EW, 1956, "Construcción semántica de la lógica intuicionista", Koninklijke Nederlandse Akad. von Wettenscappen, 19 (11): 357–388.
  • Brouwer, LEJ, 1907, "Sobre los fundamentos de las matemáticas", Tesis, Amsterdam; Traducción al inglés en Heyting (ed.) 1975: 11-101.
  • –––, 1908, “La falta de fiabilidad de los principios lógicos”, traducción al inglés en Heyting (ed.) 1975: 107–111.
  • –––, 1912, “Intuitionism and Formalism”, traducción al inglés de A. Dresden, Boletín de la American Mathematical Society, 20 (1913): 81–96, reimpreso en Benacerraf y Putnam (eds.) 1983: 77–89; también reimpreso en Heyting (ed.) 1975: 123–138.
  • –––, 1923 [1954], “Sobre la importancia del principio de la exclusión del medio en las matemáticas, especialmente en la teoría de funciones”, “Addenda y corrigenda” y “Addenda y corrigenda adicionales”, traducción al inglés en van Heijenoort (ed.) 1967: 334–345.
  • –––, 1923C, “Intuitionistische Zerlegung Mathischer Grundbegriffe”, Jahresbericht der Deutschen Mathematiker-Vereinigung, 33 (1925): 251-256; reimpreso en Heyting (ed.) 1975, 275–280.
  • –––, 1927, “Reflexiones intuicionistas sobre el formalismo”, publicado originalmente en 1927, traducción al inglés en van Heijenoort (ed.) 1967: 490–492.
  • –––, 1948, “Conciencia, filosofía y matemáticas”, publicado originalmente (1948), reimpreso en Benacerraf y Putnam (eds.) 1983: 90–96.
  • Burr, W., 2004, "La jerarquía aritmética intuitiva", en J. van Eijck, V. van Oostrom y A. Visser (eds.), Logic Colloquium '99 (Lecture Notes in Logic 17), Wellesley, MA: ASL y AK Peters, 51–59.
  • Buss, S. (ed.), 1998, Handbook of Proof Theory, Amsterdam y Nueva York: Elsevier.
  • Chen, RM. y Rathjen, M., 2012, "Realización de Lifschitz para la teoría de conjuntos intuitiva de Zermelo-Fraenkel", Archive for Mathematical Logic, 51: 789–818.
  • Colacito, A., de Jongh, D. y Vargas, A., 2017, "Negación subminimal", Soft Computing, 21: 165–164.
  • Crossley, J. y MAE Dummett (eds.), 1965, Sistemas formales y funciones recursivas, Amsterdam: North-Holland Publishing.
  • van Dalen, D. (ed.), 1981, Brouwer's Cambridge Lectures on Intuitionism, Cambridge: Cambridge University Press.
  • Dummett, M., 1975, "La base filosófica de la lógica intuicionista", publicado originalmente (1975), reimpreso en Benacerraf y Putnam (eds.) 1983: 97-129.
  • Dyson, V. y Kreisel, G., 1961, Análisis de la construcción semántica de Beth de la lógica intuicionista, Informe técnico n. ° 3, Stanford: Laboratorio de matemática aplicada y estadística, Universidad de Stanford.
  • Ferreira, F., 2008, "El paquete más artístico de un revoltijo de ideas", Dialectica, 62: 205–222.
  • Friedman, H., 1975, "La propiedad de disyunción implica la propiedad de existencia numérica", Proceedings of the National Academy of Science, 72: 2877–2878.
  • Gentzen, G., 1934–5, "Untersuchungen Über das logische Schliessen", Mathematische Zeitschrift, 39: 176–210, 405–431.
  • Ghilardi, S., 1999, "Unificación en lógica intuicionista", Journal of Symbolic Logic, 64: 859–880.
  • Glivenko, V., 1929, "Sur quelques points of the logique of M. Brouwer", Académie Royale de Belgique, Boletines de la clase de ciencias, 5 (15): 183-188.
  • Gödel, K., 1932, “Zum intuitionistischen Aussagenkalkül”, Anzeiger der Akademie der Wissenschaften en Viena, 69: 65–66. Reproducido y traducido con una nota introductoria de AS Troelstra en Gödel 1986: 222–225.
  • –––, 1933e, "Zur intuitionistischen Arithmetik und Zahlentheorie", Ergebnisse eines Mathischen Kolloquiums, 4: 34–38.
  • –––, 1933f, “Eine Interpretation des intuitionistischen Aussagenkalküls”, reproducido y traducido con una nota introductoria de AS Troelstra en Gödel 1986: 296–304.
  • –––, 1958, “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”, Dialectica, 12: 280–287. Reproducido con una traducción al inglés en Gödel 1990: 241–251.
  • –––, 1986, Obras completas, vol. I, S. Feferman y col. (eds.), Oxford: Oxford University Press.
  • –––, 1990, Obras completas, vol. II, S. Feferman y col. (eds.), Oxford: Oxford University Press.
  • Goudsmit, JP, 2015, Reglas intuitivas: reglas admisibles de lógica intermedia, Ph. D. disertación, Universidad de Utrecht.
  • Harrop R., 1960, "Con respecto a las fórmulas de los tipos (A / rightarrow B / vee C, A / rightarrow (Ex) B (x)) en sistemas formales intuicionistas", Journal of Symbolic Logic, 25: 27–32.
  • van Heijenoort, J. (ed.), 1967, From Frege to Gödel: A Source Book In Mathematical Logic 1879–1931, Cambridge, MA: Harvard University Press.
  • Heyting, A., 1930, "Die formalen Regeln der intuitionistischen Logik", en tres partes, Sitzungsberichte der preussischen Akademie der Wissenschaften: 42–71, 158–169. Traducción al inglés de la Parte I en Mancosu 1998: 311–327.
  • –––, 1956, Intuitionism: An Introduction, Amsterdam: North-Holland Publishing, 3a edición revisada, 1971.
  • Heyting, A. (ed.), 1975, LEJ Brouwer: Obras completas (Volumen 1: Filosofía y fundamentos de las matemáticas), Amsterdam y Nueva York: Elsevier.
  • Howard, WA, 1973, "Funcionalidades hereditariamente mayorizables de tipo finito", en Troelstra (ed.) 1973: 454-461.
  • Hyland, JME, 1982, "The topos efectivo", en Troelstra y van Dalen (ed.) 1982: 165-216.
  • Iemhoff, R., 2001, "Sobre las reglas admisibles de la lógica proposicional intuicionista", Journal of Symbolic Logic, 66: 281–294.
  • –––, 2005, “Lógicas intermedias y reglas de Visser”, Notre Dame Journal of Formal Logic, 46: 65–81.
  • Iemhoff, R. y Metcalfe, G., 2009, "Prueba de la teoría de las reglas admisibles", Annals of Pure and Applic Logic, 159: 171-186.
  • Jankov, VA, 1968, "La construcción de una secuencia de cálculos proposicionales superintuitivos fuertemente independientes", Matemáticas soviéticas. Doklady, 9: 801–807.
  • Jerabek, E., 2008, "Bases independientes de las normas admisibles", Logic Journal of the IGPL, 16: 249–267.
  • de Jongh, DHJ, 1970, "La maximidad del cálculo proposicional intuicionista con respecto a la aritmética de Heyting", Journal of Symbolic Logic, 6: 606.
  • de Jongh, DHJ, y Smorynski, C., 1976, "Modelos de Kripke y la teoría intuicionista de las especies", Annals of Mathematical Logic, 9: 157-186.
  • de Jongh, D., Verbrugge, R. y Visser, A., 2011, "Lógicas intermedias y la propiedad de Jongh", Archive for Mathematical Logic, 50: 197–213.
  • Kino, A., Myhill, J. y Vesley, RE (eds.), 1970, Intuitionism and Proof Theory: Proceedings of the summer conference at Buffalo, NY, 1968, Amsterdam: North-Holland.
  • Kleene, SC, 1945, "Sobre la interpretación de la teoría intuitiva de los números", Journal of Symbolic Logic, 10: 109-124.
  • –––, 1952, Introducción a la metamatemática, Princeton: Van Nostrand.
  • –––, 1962, “Disyunción y existencia bajo implicación en formalismos intuicionistas elementales”, Journal of Symbolic Logic, 27: 11–18.
  • –––, 1963, “Un apéndice”, Journal of Symbolic Logic, 28: 154–156.
  • –––, 1965, “Extensiones clásicas de las matemáticas intuicionistas”, en Bar-Hillel (ed.) 1965: 31–44.
  • –––, 1969, Formalized Recursive Functionals and Formalized Realizability, Memoirs of the American Mathematical Society 89.
  • Kleene, SC y Vesley, RE, 1965, The Foundations of Intuitionistic Mathematics, Especialmente en relación con las funciones recursivas, Amsterdam: Holanda del Norte.
  • Kreisel, G., 1958, "Propiedades de integridad elemental de la lógica intuicionista con una nota sobre negaciones de fórmulas prenex," Journal of Symbolic Logic, 23: 317–330.
  • –––, 1962, “Sobre la integridad débil de la lógica predicativa intuicionista”, Journal of Symbolic Logic, 27: 139–158.
  • Kripke, SA, 1965, "Análisis semántico de la lógica intuicionista", en J. Crossley y MAE Dummett (eds.) 1965: 92-130.
  • Krol, M., 1978, "Un modelo topológico de análisis intuicionista con el esquema de Kripke", Zeitschrift für Math. Logik und Grundlagen der Math., 24: 427-436.
  • Leivant, D., 1979, "Maximality of Intuitionistic Logic", Mathematical Center Tracts 73, Mathematisch Centrum, Amsterdam.
  • –––, 1985, “Traducciones sintácticas y funciones probables recursivas”, Journal of Symbolic Logic, 50: 682–688.
  • Läuchli, H., 1970, "Una noción abstracta de realizabilidad para la cual el cálculo del predicado intuicionista es completo", en A. Kino et al. (eds.) 1965: 227–234.
  • Lifschitz, V., 1979, “CT (_ 0) es más fuerte que CT (_ 0) !,” Proceedings of the American Mathematical Society, 73 (1): 101–106.
  • Mancosu, P., 1998, De Brouwer a Hilbert: El debate sobre los fundamentos de las matemáticas en la década de 1920, Nueva York y Oxford: Oxford University Press.
  • Martin-Löf, P., 1984, Intuitionistic Type Theory, Notas de Giovanni Sambin de una serie de conferencias impartidas en Padua, junio de 1980, Napoli: Bibliopolis.
  • Mints, G., 2012, "Las traducciones de Gödel-Tarski de fórmulas proposicionales intuitivas", en Correct Reasoning (Lecture Notes in Computer Science 7265), E. Erdem et al. (eds.), Dordrecht: Springer-Verlag: 487–491.
  • Moschovakis, JR, 1971, "¿Puede haber funciones no recursivas?", Journal of Symbolic Logic, 36: 309–315.
  • –––, 2003, “Jerarquías clásicas y constructivas en el análisis intuicionista extendido”, Journal of Symbolic Logic, 68: 1015–1043.
  • –––, 2009, “La lógica de Brouwer y Heyting”, en Logic from Russell to Church (Handbook of the History of Logic, Volumen 5), J. Woods y D. Gabbay (eds.), Amsterdam: Elsevier: 77 –125.
  • –––, 2017, “Análisis intuicionista y el fin de los tiempos”, Boletín de lógica simbólica, 23: 279–295.
  • Nelson, D., 1947, "Funciones recursivas y teoría intuitiva de números", Transactions of the American Mathematical Society, 61: 307–368.
  • Nishimura, I., 1960, "Sobre fórmulas de una variable en cálculo proposicional intuicionista", Journal of Symbolic Logic, 25: 327–331.
  • van Oosten, J., 1991, "Una prueba semántica del teorema de De Jongh", Archives for Mathematical Logic, 31: 105-114.
  • –––, 2002, “Realizabilidad: un ensayo histórico,” Mathematical Structures in Computer Science, 12: 239–263.
  • –––, 2008, Realizabilidad: una introducción a su lado categórico, Amsterdam: Elsevier.
  • Plisko, VE, 1992, "Sobre la complejidad aritmética de ciertas lógicas constructivas", Mathematical Notes, (1993): 701-709. Traducido de Matematicheskie Zametki, 52 (1992): 94-104.
  • Rasiowa, H., 1974, Algebraic Appriach to Non-Classical Logics, Amsterdam: Holanda del Norte.
  • Rasiowa, H. y Sikorski, R., 1963, The Mathematics of Metamathematics, Varsovia: Panstwowe Wydawnictwo Naukowe.
  • Rathjen, M., 2006, "Realizabilidad para la teoría de conjuntos constructiva de Zermelo-Fraenkel", en Logic Colloquium 2003 (Lecture Notes in Logic 24), J. Väänänen et al. (eds.), AK Peters 2006: 282–314.
  • –––, 2012, “De la existencia de la existencia débil a la fuerte”, Annals of Pure and Applied Logic, 163: 1400–1418.
  • Rose, GF, 1953, "Cálculo proposicional y realizabilidad", Transactions of the American Mathematical Society, 75: 1–19.
  • Rybakov, V., 1997, Admisibilidad de las reglas de inferencia lógica, Amsterdam: Elsevier.
  • Scott, D., 1968, "Extendiendo la interpretación topológica al análisis intuicionista", Compositio Mathematica, 20: 194-210.
  • Smorynski, CA, 1973, "Aplicaciones de los modelos Kripke", en Troelstra (ed.) 1973: 324-391.
  • Spector, C., 1962, "Funcionalidades de análisis probadamente recursivas: una prueba de análisis de consistencia mediante una extensión de principios formulados en las matemáticas intuitivas actuales", Teoría de la función recursiva: Procedimientos de simposios en matemática pura, Volumen 5, JCE Dekker (ed.), Providence, RI: American Mathematical Society, 1–27.
  • van Stigt, WP, 1990, Brouwer's Intuitionism, Amsterdam: North-Holland.
  • Stone, MH, 1937, "Representación topológica de celosías distributivas y lógicas brouwerianas", Casopis Pest. Estera. Fys 67: 1–25.
  • Tarski, A., 1938, "Der Aussagenkalkül und die Topologie", Fundamenta Mathematicae, 31: 103-104.
  • Troelstra, AS, 1991, "Historia del constructivismo en el siglo XX", ITLI Prepublication Series ML – 1991–05, Amsterdam. Versión final en Set Theory, Arithmetic and Foundations of Mathematics (Lecture Notes in Logic 36), J. Kenney y R. Kossak (eds.), Association for Symbolic Logic, Ithaca, NY, 2011: 150-179.
  • –––, 1998, “Realizability”, Capítulo VI de Buss (ed.), 1998: 407–473.
  • –––, Nota introductoria a 1958 y 1972, en Gödel, 1990: 217–241.
  • Troelstra, AS (ed.), 1973, Metamathematical Investigation of Intuitionistic Aritmetic and Analysis (Lecture Notes in Mathematics 344), Berlín: Springer-Verlag. Correcciones y adiciones disponibles del editor.
  • Troelstra, AS y Schwichtenberg, H., 2000, Basic Proof Theory (Cambridge Tracts in Theoretical Computer Science: Volume 43), 2nd edition, Cambridge: Cambridge University Press.
  • Troelstra, AS y van Dalen, D., 1988, Constructivism in Mathematics: An Introduction, 2 tomos, Amsterdam: North-Holland Publishing. [Ver también las correcciones, en otros recursos de Internet.]
  • Troelstra, AS y van Dalen, D. (eds.), 1982, Simposio del Centenario LEJ Brouwer, Amsterdam: North-Holland Publishing.
  • Veldman, W., 1976, "Un teorema de completitud intuicionista para la lógica de predicados intuicionista", Journal of Symbolic Logic, 41: 159–166.
  • –––, 1990, “Una encuesta de la teoría intuitiva de conjuntos descriptivos”, en PP Petkov (ed.), Lógica matemática, Actas de la Conferencia de Heyting, Nueva York y Londres: Plenum Press, 155–174.
  • –––, 2005, “Dos conjuntos simples que no son positivamente Borel”, Annals of Pure and Applied Logic, 135: 151–209.
  • Vesley, RE, 1972, "Secuencias de elección y el principio de Markov", Compositio Mathematica, 24: 33–53.
  • –––, 1970, “Una alternativa agradable al esquema de Kripke”, en A. Kino et al. (eds.) 1970: 197 ss.
  • Visser, A., 1999, "Reglas y aritmética", Notre Dame Journal of Formal Logic, 40: 116–140.
  • –––, 2002, “Sustituciones de oraciones (Sigma ^ {0} _1): exploraciones entre la lógica proposicional intuitiva y la aritmética intuicionista”, Annals of Pure and Applied Logic, 114: 227–271.
  • –––, 2006, “Predicate lógicas de teorías aritméticas constructivas”, Journal of Symbolic Logic, 72: 1311–1326.

Herramientas académicas

icono de hombre sep
icono de hombre sep
Cómo citar esta entrada.
icono de hombre sep
icono de hombre sep
Obtenga una vista previa de la versión PDF de esta entrada en Friends of the SEP Society.
icono inpho
icono inpho
Busque este tema de entrada en el Proyecto de ontología de filosofía de Internet (InPhO).
icono de papeles de phil
icono de papeles de phil
Bibliografía mejorada para esta entrada en PhilPapers, con enlaces a su base de datos.

Otros recursos de internet

  • Bezhanishvili, G. y Holliday, W., 2018, "Una jerarquía semántica para la lógica intuicionista", manuscrito, UC Berkeley Faculty Publications.
  • Bezhanishvili, N. y de Jongh, DHJ, 2005, Intuitionistic Logic, Notas de la conferencia presentadas en ESSLLI, Edimburgo.
  • Brouwer, extractos de las conferencias de Brouwer en Cambridge.
  • Citkin, A., 2016, "Sistemas deductivos superintucionistas hereditariamente estructuralmente completos", manuscrito en arXiv.org.
  • Mentas, G., Olkhovikov, G. y Urquhart, A., 2012, "Fracaso de la interpolación en la lógica intuicionista de dominios constantes", manuscrito, arXiv.org.
  • Troelstra, AS y JR Moschovakis, 2018, Correcciones a AS Troelstra y D. van Dalen, 1988, Constructivismo en Matemáticas.
  • Problemas en la lógica de demostrabilidad, mantenida por Lev Beklemishev.
  • Bibliografía de realización, mantenida por Lars Birkedal.
  • van Oosten 2000, y otras preimpresiones relacionadas con la realizabilidad, mantenidas por Jaap van Oosten.

Recomendado: