Logique De Prouvabilité

Table des matières:

Logique De Prouvabilité
Logique De Prouvabilité

Vidéo: Logique De Prouvabilité

Vidéo: Logique De Prouvabilité
Vidéo: PROBABILITÉS 2024, Mars
Anonim

Navigation d'entrée

  • Contenu de l'entrée
  • Bibliographie
  • Outils académiques
  • Aperçu du PDF des amis
  • Informations sur l'auteur et la citation
  • Retour au sommet

Logique de prouvabilité

Publié pour la première fois le mercredi 2 avril 2003; révision de fond mer.5 avr.2017

La logique de prouvabilité est une logique modale utilisée pour étudier ce que les théories arithmétiques peuvent exprimer dans un langage restreint au sujet de leurs prédicats de prouvabilité. La logique a été inspirée par les développements en méta-mathématiques tels que les théorèmes d'incomplétude de Gödel de 1931 et le théorème de Löb de 1953. En tant que logique modale, la logique de la prouvabilité a été étudiée depuis le début des années soixante-dix et a eu des applications importantes dans les fondements des mathématiques.

D'un point de vue philosophique, la logique de la prouvabilité est intéressante parce que le concept de prouvabilité dans une théorie fixe de l'arithmétique a une signification unique et non problématique, autre que des concepts comme la nécessité et la connaissance étudiés en logique modale et épistémique. De plus, la logique de prouvabilité fournit des outils pour étudier la notion d'auto-référence.

  • 1. L'histoire de la logique de la prouvabilité
  • 2. Le système d'axiomes de la logique de la prouvabilité propositionnelle

    • 2.1 Axiomes et règles
    • 2.2 Le théorème du point fixe
  • 3. Sémantique des mondes possibles et sémantique topologique

    • 3.1 Caractérisation et solidité modale
    • 3.2 Exhaustivité modale
    • 3.3 Échec de l'exhaustivité forte
    • 3.4 Sémantique topologique pour la logique de prouvabilité
  • 4. Logique de prouvabilité et arithmétique Peano

    • 4.1 Solidité arithmétique
    • 4.2 Exhaustivité arithmétique
  • 5. La portée de la logique de la prouvabilité

    • 5.1 Limites
    • 5.2 Logique d'interprétabilité
    • 5.3 Quantificateurs propositionnels
    • 5.4 Logiques de prouvabilité bimodales et polymodales de Japaridze
    • 5.5 Logique de prouvabilité des prédicats
    • 5.6 Autres généralisations
  • 6. Importance philosophique
  • Bibliographie
  • Outils académiques
  • Autres ressources Internet

    • Articles et présentations
    • Autres sites
  • Entrées connexes

1. L'histoire de la logique de la prouvabilité

Deux axes de recherche ont conduit à la naissance de la logique de la prouvabilité. Le premier découle d'un article de K. Gödel (1933), où il introduit les traductions de la logique propositionnelle intuitionniste en logique modale (plus précisément, dans le système aujourd'hui appelé S4), et mentionne brièvement que la prouvabilité peut être considérée comme un opérateur modal. Même plus tôt, CI Lewis a commencé l'étude moderne de la logique modale en introduisant l'implication stricte comme une sorte de déductibilité, où il peut avoir signifié la déductibilité dans un système formel comme Principia Mathematica, mais ce n'est pas clair dans ses écrits.

L'autre volet part de la recherche en méta-mathématiques: que peuvent dire les théories mathématiques sur elles-mêmes en encodant des propriétés intéressantes? En 1952, L. Henkin posa une question trompeusement simple inspirée des théorèmes d'incomplétude de Gödel. Afin de formuler la question de Henkin, un peu plus de contexte est nécessaire. Pour rappel, le premier théorème d'incomplétude de Gödel affirme que, pour une théorie formelle suffisamment forte comme Peano Arithmetic, toute phrase affirmant sa propre non-prouvabilité est en fait indémontrable. D'un autre côté, de «l'extérieur» de la théorie formelle, on peut voir qu'une telle phrase est vraie dans le modèle standard, indiquant une distinction importante entre vérité et prouvabilité.

Plus formellement, soit (ulcorner A / urcorner) le nombre de Gödel de la formule arithmétique (A), qui est le résultat de l'attribution d'un code numérique à (A). Soit (Prov) le prédicat de prouvabilité formalisé pour Peano Arithmetic, qui est de la forme (existe p \, / Proof (p, x)). Ici, (Proof) est le prédicat de preuve formalisé de Peano Arithmetic, et (Proof (p, x)) signifie «Gödel number (p) code une preuve correcte des axiomes de Peano Arithmetic de la formule avec le nombre de Gödel (x)”. (Pour une formulation plus précise, voir Smoryński (1985), Davis (1958).) Maintenant, supposons que Peano Arithmetic prouve (A / leftrightarrow / neg) (Prov (ulcorner A / urcorner)), alors par le résultat de Gödel, (A) n'est pas prouvable dans Peano Arithmetic, et donc c'est vrai, car en fait la phrase autoréférentielle (A) déclare «je ne suis pas prouvable».

Henkin, d'autre part, voulait savoir si quelque chose pouvait être dit sur les phrases affirmant leur propre prouvabilité: en supposant que Peano Arithmetic prouve (B / leftrightarrow / Prov (ulcorner B / urcorner)), qu'est-ce que cela implique à propos de (B)? Trois ans plus tard, M. Löb a relevé le défi et répondu de manière surprenante à la question de Henkin. Même si toutes les phrases prouvables en Peano Arithmetic sont en effet vraies sur les nombres naturels, Löb a montré que la version formalisée de ce fait, (Prov (ulcorner B / urcorner) rightarrow B), ne peut être prouvée qu'en Peano Arithmetic dans le cas trivial où Peano Arithmetic prouve déjà (B) lui-même. Ce résultat, maintenant appelé théorème de Löb, répond immédiatement à la question de Henkin. (Pour une démonstration du théorème de Löb, voir la section 4.) Löb a également montré une version formalisée de son théorème,à savoir que Peano Arithmetic prouve

) Prov (ulcorner / Prov (ulcorner B / urcorner) rightarrow B / urcorner) rightarrow / Prov (ulcorner B / urcorner).)

Dans le même article, Löb a formulé trois conditions sur le prédicat de prouvabilité de Peano Arithmetic, qui forment une modification utile des conditions compliquées que Hilbert et Bernays ont introduites en 1939 pour leur preuve du deuxième théorème d'incomplétude de Gödel. Dans ce qui suit, la dérivabilité de (A) à partir de Peano Arithmetic est désignée par (PA / vdash A):

  1. Si (PA / vdash A), alors (PA / vdash / Prov (ulcorner A / urcorner));
  2. (PA / vdash / Prov (ulcorner A / rightarrow B / urcorner) rightarrow (Prov (ulcorner A / urcorner) rightarrow / Prov (ulcorner B / urcorner));)
  3. (PA / vdash / Prov (ulcorner A / urcorner) rightarrow / Prov (ulcorner / Prov (ulcorner A / urcorner) urcorner).)

Ces conditions de Löb, comme on les appelle de nos jours, semblent réclamer une investigation logique modale, où la modalité (Box) représente la prouvabilité en PA. Ironiquement, la première fois que la version formalisée du théorème de Löb a été énoncée comme le principe modal

) Box (Box A / rightarrow A) rightarrow / Box A)

était dans un article de Smiley en 1963 sur la base logique de l'éthique, qui ne considérait pas du tout l'arithmétique. Des enquêtes plus pertinentes, cependant, n'ont sérieusement commencé que près de vingt ans après la publication de l'article de Löb. Le début des années 1970 a vu le développement rapide de la logique de provabilité propositionnelle, où plusieurs chercheurs de différents pays ont indépendamment prouvé les résultats les plus importants, discutés dans les sections 2, 3 et 4. La logique de provabilité propositionnelle s'est avérée capturer exactement ce que de nombreuses théories formelles de l'arithmétique peuvent dire par des moyens propositionnels sur leur propre prédicat de prouvabilité. Plus récemment, les chercheurs ont étudié les limites de cette approche et ont proposé plusieurs extensions intéressantes plus expressives de la logique de la prouvabilité (voir section 5).

2. Le système d'axiomes de la logique de la prouvabilité propositionnelle

Le langage logique de la logique de prouvabilité propositionnelle contient, en plus des atomes propositionnels et des opérateurs fonctionnels de vérité habituels ainsi que du symbole de contradiction (bot), un opérateur modal (Box) avec une signification voulue est prouvable dans (T) », où (T) est une théorie formelle suffisamment forte, disons Peano Arithmetic (voir section 4). (Diamond A) est une abréviation pour (neg \, / Box / neg \, A). Ainsi, le langage est le même que celui des systèmes modaux tels que K et S4 présentés dans la logique modale d'entrée.

2.1 Axiomes et règles

La logique de provabilité propositionnelle est souvent appelée GL, après Gödel et Löb. (Les noms alternatifs trouvés dans la littérature pour des systèmes équivalents sont L, G, KW, K4W et PrL). La logique GL résulte de l'ajout de l'axiome suivant à la logique modale de base K:

) tag {GL} Box (Box A / rightarrow A) rightarrow / Box A.)

Pour rappel, comme GL étend K, il contient toutes les formules ayant la forme d'une tautologie propositionnelle. Pour la même raison, GL contient le

) tag {Axiome de distribution} Box (A / rightarrow B) rightarrow (Box A / rightarrow / Box B).)

De plus, il est fermé sous la règle Modus Ponens, qui permet de dériver (B) de (A / rightarrow B) et (A), et la règle de généralisation, qui dit que si (A) est un théorème de GL, alors (Box A) l'est aussi.

La notion (GL / vdash A) désigne la prouvabilité d'une formule modale (A) dans la logique de prouvabilité propositionnelle. Il n'est pas difficile de voir que l'axiome modal (Box A / rightarrow / Box / Box A) (connu sous le nom d'axiome 4 de la logique modale) est en effet prouvable dans GL. Pour le prouver, on utilise la substitution (A / wedge / Box A) pour (A) dans l'axiome (GL). Puis, voyant que l'antécédent de l'implication résultante découle de (Case A), on applique l'axiome de distribution et la règle de généralisation ainsi qu'une logique propositionnelle. Sauf indication contraire explicite, dans la suite, la «logique de prouvabilité» représente le système GL de la logique de prouvabilité propositionnelle.

Quant à la théorie de la preuve de la logique de la prouvabilité, Valentini (1983) a prouvé qu'une formulation standard de calcul séquentiel de GL obéit à l'élimination de coupures, ce qui signifie, grossièrement formulée, que chaque formule prouvable à partir de GL dans le calcul séquentiel a également une preuve séquentielle GL «sans détours »(voir l'entrée le développement de la théorie de la preuve pour une explication précise de l'élimination des coupures). Ces dernières années, il y a eu un regain d'intérêt pour la théorie de la preuve de GL, voir par exemple Goré et Ramanayake (2008). L'élimination des coupures conduit à la propriété de sous-formule souhaitable pour GL, car toutes les formules qui apparaissent dans une épreuve sans coupure sont des sous-formules des formules finales.

Pour des recherches récentes sur la théorie de la preuve de la logique de la prouvabilité basée sur différents calculs séquentiels sans coupure, voir (Negri 2005, 2014; Poggiolesi 2009). Negri présente deux calculs séquents étiquetés équivalents pour GL et une preuve syntaxique de l'élimination des coupures. Même si une propriété de sous-formule complète ne tient pas pour ces calculs à cause de l'étiquetage, les conséquences habituelles de la propriété de sous-formule peuvent être établies: Le formalisme étiqueté permet une preuve directe d'exhaustivité, qui peut être utilisée pour établir la décidabilité ainsi que le modèle fini propriété, ce qui signifie que toute formule non prouvable a un contre-modèle fini.

Un nouveau développement intrigant de la théorie de la preuve est l'expansion de Shamkanov des systèmes de preuve de style séquentiel en autorisant les preuves circulaires (Shamkanov 2014). Considérons un système séquentiel pour K4, le système modal résultant de GL en remplaçant l'axiome GL par l'axiome le plus faible (Box A / rightarrow / Box / Box A) (axiome 4). Cependant, supposons que les hypothèses ouvertes soient autorisées, à condition que la même séquence se produise strictement en dessous de cette hypothèse dans l'arbre de preuve. Formulée plus techniquement, on peut trouver une dérivation circulaire à partir d'un arbre de dérivation ordinaire en reliant chacune de ses feuilles non axiomatiques à un nœud intérieur identique. Shamkanov (2014) a prouvé que le système résultant est cohérent et que de plus, en général, chaque séquence a une dérivation GL si et seulement si elle a une dérivation K4 circulaire. Les preuves circulaires fournissent également une méthode pour montrer en théorie que le théorème d'interpolation de Lyndon est valable pour GL. L'interpolation standard pour GL avait déjà été prouvée par différentes méthodes (Boolos 1979; Smoryński 1978; Rautenberg 1983). (Pour plus d'informations sur le théorème d'interpolation de Lyndon pour la logique du premier ordre, voir aussi l'entrée théorie des modèles du premier ordre).

2.2 Le théorème du point fixe

Le principal résultat «modal» de la logique de prouvabilité est le théorème du point fixe, que D. de Jongh et G. Sambin ont indépendamment prouvé en 1975 (Sambin 1976). Même s'il est formulé et prouvé par des méthodes strictement modales, le théorème du point fixe a encore une grande signification arithmétique. Il dit essentiellement que l'autoréférence n'est pas vraiment nécessaire, dans le sens suivant. Supposons que toutes les occurrences de la variable propositionnelle (p) dans une formule donnée (A (p)) soient sous la portée de l'opérateur de prouvabilité, par exemple (A (p) = / neg / Box p), ou (A (p) = / Box (p / rightarrow q)). Ensuite, il y a une formule (B) dans laquelle (p) n'apparaît pas, de sorte que toutes les variables propositionnelles qui apparaissent dans (B) apparaissent déjà dans (A (p)), et telles que

) GL / vdash B / leftrightarrow A (B).)

Cette formule (B) est appelée un point fixe de (A (p)). De plus, le point fixe est unique, ou plus précisément, s'il existe une autre formule (C) telle que (GL / vdash C / leftrightarrow A (C)), alors nous devons avoir (GL / vdash B / leftrightarrow C). La plupart des preuves dans la littérature donnent un algorithme par lequel on peut calculer le point fixe (voir Smoryński 1985, Boolos 1993, Sambin et Valentini 1982, Lindström 2006). Une preuve particulièrement courte et claire, ainsi qu'un algorithme très efficace pour calculer les points fixes, peuvent être trouvés dans Reidhaar-Olson (1990).

Par exemple, supposons que (A (p) = / neg \, / Box p). Alors le point fixe produit par un tel algorithme est (neg \, / Box / bot), et en effet on peut prouver que

) GL / vdash / neg \, / Box / bot / leftrightarrow / neg \, / Box (neg \, / Box / bot).)

Si cela est lu arithmétiquement, la direction de gauche à droite n'est que la version formalisée du deuxième théorème d'incomplétude de Gödel: si une théorie formelle suffisamment forte (T) comme Peano Arithmetic ne prouve pas une contradiction, alors elle n'est pas prouvable dans (T) que (T) ne prouve pas une contradiction. Ainsi, des théories arithmétiques cohérentes suffisamment fortes ne peuvent pas prouver leur propre cohérence. Nous étudierons plus précisément la relation entre la logique de prouvabilité et l'arithmétique dans la section 4, mais à cette fin, un autre aspect «modal» de GL doit d'abord être fourni: la sémantique.

3. Sémantique des mondes possibles et sémantique topologique

La logique de prouvabilité a une sémantique appropriée des mondes possibles, tout comme de nombreuses autres logiques modales. Pour rappel, un modèle de mondes possibles (ou modèle de Kripke) est un triple (M = / langle W, R, V / rangle), où (W) est un ensemble non vide de mondes possibles, (R) est une relation d'accessibilité binaire sur (W), et (V) est une évaluation qui attribue une valeur de vérité à chaque variable propositionnelle pour chaque monde dans (W). Le couple (F = / langle W, R / rangle) est appelé le cadre de ce modèle. La notion de vérité d'une formule (A) dans un modèle (M) à un monde (W), notation (M, w / modèles A), est définie inductivement. Répétons uniquement la clause la plus intéressante, celle de l'opérateur de prouvabilité (Box):

[M, w / models / Box A / text {iff pour chaque} w ', / text {if} wRw', / text {then} M, w '\ models A.)

Voir la logique modale d'entrée pour plus d'informations sur la sémantique des mondes possibles en général.

3.1 Caractérisation et solidité modale

La logique modale K est valable dans tous les modèles Kripke. Cependant, son extension GL ne l'est pas: nous devons restreindre la classe des modèles de mondes possibles à une classe plus appropriée. Disons qu'une formule (A) est valide dans le cadre (F), notation (F / models A), ssi (A) est vraie dans tous les mondes des modèles de Kripke (M) basé sur (F). Il s'avère que le nouvel axiome (GL) de la logique de prouvabilité correspond à une condition sur les cadres, comme suit:

Pour tous les cadres (F = / langle W, R / rangle, F / models / Box (Box p / rightarrow p) rightarrow / Box p) ssi (R) est transitif et inversement bien fondé.

Ici, la transitivité est la propriété bien connue que pour tous les mondes (w_1), (w_2), (w_3) in (W), if (w_1 Rw_2) et (w_2 Rw_3), puis (w_1 Rw_3). Une relation est à l'inverse bien fondée ssil n'y a pas de séquences ascendantes infinies, c'est-à-dire des séquences de la forme (w_1 Rw_2 Rw_3 R / ldots). Notez que les trames inversement bien fondées sont également irréflexives, car si (wRw), cela donne lieu à une séquence ascendante infinie (wRwRwR / ldots).

Le résultat de correspondance ci-dessus montre immédiatement que GL est modalement sain par rapport à la classe des modèles de mondes possibles sur des cadres transitifs inversement bien fondés, car tous les axiomes et règles de GL sont valides sur de tels modèles. La question est de savoir si la complétude tient également: par exemple, la formule (Box A / rightarrow / Box / Box A), qui est valable sur toutes les trames transitives, est effectivement prouvable dans GL, comme cela a été mentionné dans la section 1. Mais Est-ce que chaque formule qui est valide sur tous les cadres transitifs inversement bien fondés est également prouvable dans GL?

3.2 Exhaustivité modale

Ignorant la signification arithmétique de GL, K. Segerberg a prouvé en 1971 que GL est en effet complet par rapport aux cadres transitifs inversement bien fondés; D. de Jongh et S. Kripke ont également prouvé ce résultat de manière indépendante. Segerberg a montré que GL est complet même par rapport à la classe plus restreinte des arbres irréflexifs transitifs finis, un fait qui s'est avéré plus tard très utile pour la démonstration de Solovay du théorème de complétude arithmétique (voir Section 4).

Les théorèmes de solidité modale et d'exhaustivité donnent immédiatement lieu à une procédure de décision pour vérifier toute formule modale (A) si (A) découle de GL ou non, par une recherche en profondeur d'abord à travers des arbres transitifs irréflexifs de profondeur bornée. En regardant la procédure un peu plus précisément, on peut montrer que GL est décidable dans la classe de complexité de calcul PSPACE, comme les logiques modales bien connues K, T et S4. Cela signifie qu'il existe une machine de Turing qui, étant donné une formule (A) en entrée, répond si (A) découle de GL ou non; la taille de la mémoire dont la machine de Turing a besoin pour son calcul n'est que polynomiale de la longueur de (A). On peut montrer que le problème de décision pour GL (encore une fois, comme les problèmes de décision pour K, T et S4) est PSPACE- complet,en ce sens que tous les autres problèmes de PSPACE ne sont pas plus difficiles que de décider si une formule donnée est un théorème de GL. (Voir Goré et Kelly (2007) pour la description d'un prouveur de théorème automatisé pour GL.)

Pour donner un peu plus de perspective sur la complexité, la classe P des fonctions calculables en une quantité de temps polynomiale dans la longueur de l'entrée, est incluse dans PSPACE, qui à son tour est incluse dans la classe EXPTIME des fonctions calculables en temps exponentiel (voir le calculabilité et complexité d'entrée). Reste à savoir si ces deux inclusions sont strictes, bien que de nombreux théoriciens de la complexité pensent qu'elles le sont. Certaines autres logiques modales bien connues, comme la logique épistémique avec des connaissances communes, sont décidables dans EXPTIME, elles peuvent donc être plus complexes que GL, en fonction des problèmes ouverts.

3.3 Échec de l'exhaustivité forte

De nombreuses logiques modales (S) bien connues sont non seulement complètes par rapport à une classe appropriée de trames, mais même fortement complètes. Afin d'expliquer la forte complétude, nous avons besoin de la notion de dérivabilité à partir d'un ensemble d'hypothèses. Une formule (A) est dérivable de l'ensemble des hypothèses (Gamma) dans une logique modale (S), écrite comme (Gamma / vdash A), si (A) est dans (Gamma) ou (A) découle des formules dans (Gamma) et des axiomes de (S) par des applications de Modus Ponens et de la règle de généralisation. Ici, la règle de généralisation ne peut être appliquée qu'aux dérivations sans hypothèses (voir Hakli et Negri 2010).

Or une logique modale (S) est fortement complète si pour tous les ensembles (finis ou infinis) (Gamma) et toutes les formules (A):

Si, sur des cadres (S) - appropriés, (A) est vrai dans tous les mondes dans lesquels toutes les formules de (Gamma) sont vraies, alors (Gamma / vdash A) dans la logique (S).

Cette condition s'applique aux systèmes tels que K, M, K4, S4 et S5. Si elle est restreinte à des ensembles finis (Gamma), la condition ci-dessus correspond à l'exhaustivité.

Cependant, une complétude forte ne vaut pas pour la logique de prouvabilité, car la compacité sémantique échoue. La compacité sémantique est la propriété que pour chaque ensemble infini (Gamma) de formules, Si chaque sous-ensemble fini (Delta) de (Gamma) a un modèle sur une image (S) - appropriée, alors (Gamma) a également un modèle sur un (S) approprié -Cadre.

Comme contre-exemple, prenons l'ensemble infini de formules

) Gamma = { Diamond p_0, / Box (p_0 / rightarrow / Diamond p_1), / Box (p_1 / rightarrow / Diamond p_2), / Box (p_2 / rightarrow / Diamond p_3), / ldots, / Box (p_n / rightarrow / Diamond p_ {n + 1}), / ldots })

Alors pour tout sous-ensemble fini (Delta) de (Gamma), on peut construire un modèle sur un cadre transitif, inversement bien fondé et un monde dans le modèle où toutes les formules de (Delta) sont vrai. Donc par solidité modale, GL ne prouve pas (bot) from (Delta) pour tout fini (Delta / subseteq / Gamma), et a fortiori GL ne prouve pas (bot) de (Gamma), car toute preuve GL est finie. D'un autre côté, il est facile de voir qu'il n'y a pas de modèle sur un cadre transitif, inversement bien fondé, où dans n'importe quel monde, toutes les formules de (Gamma) sont valables. Ainsi (bot) suit sémantiquement de (Gamma), mais n'est pas prouvable à partir de celui-ci dans GL, ce qui contredit la condition de forte complétude.

3.4 Sémantique topologique pour la logique de prouvabilité

Comme alternative à la sémantique possible des mondes, de nombreuses logiques modales peuvent recevoir une sémantique topologique. Clairement, les propositions peuvent être interprétées comme des sous-ensembles d'un espace topologique. Il est également facile de voir que le connectif propositionnel (wedge) correspond à l'opération ensembliste (cap), tandis que (vee) correspond à (cup), (neg) correspond au complément de la théorie des ensembles, et (rightarrow) correspond à (subseteq). Les logiques modales qui contiennent l'axiome de réflexion (Box A / rightarrow A) bénéficient également d'une interprétation particulièrement naturelle des opérateurs modaux. Pour ces logiques, (Diamond) correspond à l'opérateur de fermeture dans un espace topologique, tandis que (Box) correspond à l'intérieur. Pour voir pourquoi ces interprétations sont appropriées,notez que l'axiome de réflexion correspond au fait que chaque ensemble est inclus dans sa fermeture et que chaque ensemble comprend son intérieur.

Cependant, la logique de prouvabilité ne prouve pas la réflexion, car l'instanciation (Box / bot / rightarrow / bot) de la réflexion conduirait à une contradiction avec l'axiome (GL).

La logique de la prouvabilité nécessite donc une approche différente. Sur la base d'une suggestion de J. McKinsey et A. Tarski (1944), L. Esakia (1981, 2003) a étudié l'interprétation de (Diamond) comme opérateur d'ensemble dérivé (d), qui cartographie un ensemble (B) à l'ensemble de ses points limites (d (B)). Pour expliquer les conséquences de cette interprétation de (Diamond), nous avons besoin de deux définitions supplémentaires, à savoir des concepts dense en soi et dispersé. Un sous-ensemble (B) d'un espace topologique est appelé dense-en-soi si (B / subseteq d (B)). Un espace topologique est appelé dispersé s'il n'a pas de sous-ensemble non vide qui est dense en soi. Les ordinaux dans leur topologie d'intervalle forment des exemples d'espaces dispersés. Esakia (1981) a démontré une correspondance importante: il a montré qu'un espace topologique satisfait l'axiome GL si et seulement si l'espace est dispersé. Cette correspondance a rapidement conduit au résultat, trouvé indépendamment par Abashidze (1985) et Blass (1990), que la logique de prouvabilité est complète par rapport à tout ordinal (ge / omega ^ / omega).

Ces dernières années, la sémantique topologique de la logique de prouvabilité a connu un véritable renouveau, notamment dans l'étude de la logique de prouvabilité bimodale de Japaridze GLB, une extension de GL (Japaridze 1986). La logique GLB s'avère modalement incomplète par rapport à sa sémantique de mondes possibles, en ce sens qu'elle ne correspond à aucune classe de cadres. Cette caractéristique place le GLB bimodal en contraste marqué avec le GL unimodal, qui correspond à la classe des arbres irréflexifs transitifs finis, comme mentionné ci-dessus. Beklemishev et coll. (2009) ont montré que GLB est cependant complet en ce qui concerne sa sémantique topologique (voir aussi Beklemishev 2009, Icard 2011). Des réverbérations intrigantes de la correspondance d'Esakia entre GL et les espaces topologiques dispersés peuvent même être trouvées dans des études topologiques récentes des logiques spatiales et épistémiques (voir Aiello et al.2007). (Voir la section 5.4 pour une discussion plus approfondie sur GLB).

4. Logique de prouvabilité et arithmétique Peano

Depuis la formulation de GL, les chercheurs se sont demandé s'il était adéquat pour des théories formelles comme Peano Arithmetic (PA): est-ce que GL prouve tout sur la notion de prouvabilité qui peut être exprimée dans un langage modal propositionnel et peut être prouvée dans Peano Arithmetic, ou faut-il ajouter plus de principes à GL? Pour préciser cette notion d'adéquation, nous définissons une réalisation (parfois appelée traduction ou interprétation) comme une fonction f qui assigne à chaque atome propositionnel de la logique modale une phrase d'arithmétique, où

  • (f (bot) = / bot;)
  • (f) respecte les connecteurs logiques, par exemple, (f (B / rightarrow C) = (f (B) rightarrow f (C));) et
  • (Box) est traduit par le prédicat de prouvabilité (Prov), donc (f (Box B) = / Prov (ulcorner f (B) urcorner).)

4.1 Solidité arithmétique

Il était déjà clair au début des années 1970 que GL est arithmétiquement sain par rapport à PA, formellement:

) text {If} GL / vdash A, / text {alors pour toutes les réalisations} f, / PA / vdash f (A).)

Pour donner un avant-goût des méta-mathématiques, esquissons la preuve de solidité.

Croquis de preuve de la solidité arithmétique. PA prouve en effet des réalisations de tautologies propositionnelles, et la prouvabilité de l'axe de distribution de GL se traduit par

) PA / vdash / Prov (ulcorner A / rightarrow B / urcorner) rightarrow (Prov (ulcorner A / urcorner) rightarrow / Prov (ulcorner B / urcorner)))

pour toutes les formules A et B, qui n'est que la seconde condition de dérivabilité de Löb (voir section 1). De plus, PA obéit à Modus Ponens, ainsi qu'à la traduction de la règle de généralisation:

) text {If} PA / vdash A, / text {then} PA / vdash / Prov (ulcorner A / urcorner),)

qui n'est que la première condition de dérivabilité de Löb. Enfin, la traduction de l'axiome principal (GL) est en effet prouvable en PA:

) PA / vdash / Prov (ulcorner / Prov (ulcorner A / urcorner) rightarrow A / urcorner) rightarrow / Prov (ulcorner A / urcorner).)

C'est exactement la version formalisée du théorème de Löb mentionnée dans la section 1.

Donnons une esquisse de la preuve du théorème de Löb lui-même à partir de ses conditions de dérivabilité (la preuve de la version formalisée est similaire). La preuve est basée sur le lemme de diagonalisation de Gödel, qui dit que pour toute formule arithmétique (C (x)) il existe une formule arithmétique (B) telle que

) PA / vdash B / leftrightarrow C (ulcorner B / urcorner).)

En mots, la formule (B) dit "J'ai la propriété (C)."

Preuve LOB théorème:. Supposons que (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A); nous devons montrer que (PA / vdash A). Par le lemme de diagonalisation, il existe une formule (B) telle que

) PA / vdash B / leftrightarrow (Prov (ulcorner B / urcorner) rightarrow A).)

De cela, il découle des conditions de dérivabilité première et seconde de Löb plus un raisonnement propositionnel que

) PA / vdash / Prov (ulcorner B / urcorner) leftrightarrow / Prov (ulcorner / Prov (ulcorner B / urcorner) rightarrow A / urcorner).)

Ainsi, toujours par la deuxième condition de Löb,) PA / vdash / Prov (ulcorner B / urcorner) rightarrow (Prov (ulcorner / Prov (ulcorner B / urcorner) urcorner) rightarrow / Prov (ulcorner A / urcorner)).)

D'autre part, la troisième condition de Löb donne

) PA / vdash / Prov (ulcorner B / urcorner) rightarrow / Prov (ulcorner / Prov (ulcorner B / urcorner) urcorner),)

Donc

) PA / vdash / Prov (ulcorner B / urcorner) rightarrow / Prov (ulcorner A / urcorner).)

Avec l'hypothèse que (PA / vdash / Prov (ulcorner A / urcorner) rightarrow A), cela donne

) PA / vdash / Prov (ulcorner B / urcorner) rightarrow A.)

Enfin, l'équation produite par le lemme de diagonalisation implique que (PA / vdash B), donc (PA / vdash / Prov (ulcorner B / urcorner)), donc

) PA / vdash A,)

comme voulu.

Notez qu'en remplaçant (bot) pour (A) dans le théorème de Löb, nous dérivons que (PA / vdash / neg \, / Prov (ulcorner / bot / urcorner)) implique (PA / vdash / bot), qui n'est que la contraposition du deuxième théorème d'incomplétude de Gödel.

4.2 Exhaustivité arithmétique

Le résultat marquant de la logique de la prouvabilité est le théorème de complétude arithmétique de R. Solovay de 1976, montrant que GL est en effet adéquat pour Peano Arithmetic:

) GL / vdash A / text {si et seulement si pour toutes les réalisations} f, / PA / vdash f (A).)

Ce théorème dit essentiellement que la logique modale GL capture tout ce que Peano Arithmetic peut dire avec vérité en termes modaux sur son propre prédicat de prouvabilité. La direction de gauche à droite, la solidité arithmétique de GL, est discutée ci-dessus. Solovay a entrepris de prouver l'autre direction, beaucoup plus difficile, par contraposition. Sa preuve est basée sur des techniques autoréférentielles complexes, et seul un petit aperçu peut être donné ici.

Le théorème d'exhaustivité modale de Segerberg a été une première étape importante dans la preuve de Solovay de l'exhaustivité arithmétique de GL par rapport à Peano Arithmetic. Supposons que GL ne prouve pas la formule modale (A). Ensuite, par complétude modale, il existe un arbre irréflexif transitif fini tel que (A) est faux à la racine de cet arbre. Maintenant, Solovay a conçu une manière ingénieuse de simuler un arbre aussi fini dans le langage de Peano Arithmetic. Ainsi, il a trouvé une réalisation (f) des formules modales aux phrases d'arithmétique, telle que Peano Arithmetic ne prouve pas (f (A)).

Le théorème de complétude de Solovay fournit une manière alternative de construire de nombreuses phrases arithmétiques qui ne sont pas prouvables en Peano Arithmetic. Par exemple, il est facile de faire un modèle de mondes possible pour montrer que GL ne prouve pas (Box p / vee / Box / neg \, p), donc par le théorème de Solovay, il y a une phrase arithmétique (f (p)) tel que Peano Arithmetic ne prouve pas (Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)). En particulier, cela implique que ni (f (p)) ni (neg \, f (p)) ne sont prouvables en Peano Arithmetic; car supposons au contraire que (PA / vdash f (p)), alors par la première condition de Löb et la logique propositionnelle, (PA / vdash / Prov (ulcorner f (p) urcorner) vee / Prov (ulcorner / neg \, f (p) urcorner)), conduisant à une contradiction, et de même si l'on suppose que (PA / vdash / neg \, f (p)).

Le théorème de Solovay est si significatif car il montre qu'un fragment intéressant d'une théorie formelle indécidable comme Peano Arithmetic - à savoir ce que l'arithmétique peut exprimer en termes propositionnels sur son propre prédicat de prouvabilité - peut être étudié au moyen d'une logique modale décidable, GL, avec une sémantique perspicace des mondes possibles.

5. La portée de la logique de la prouvabilité

Dans cette section, quelques tendances récentes de la recherche sur la logique de la preuve sont discutées. Un volet important concerne les limites de la portée de GL, où la question principale est, pour quelles théories formelles, autres que Peano Arithmetic, GL est la logique de provabilité propositionnelle appropriée? Ensuite, nous discutons de certaines généralisations de la logique de provabilité propositionnelle dans des langages modaux plus expressifs.

5.1 Limites

Ces dernières années, les logiciens ont étudié de nombreux autres systèmes d'arithmétique qui sont plus faibles que Peano Arithmetic. Souvent, ces logiciens se sont inspirés des problèmes de calculabilité, par exemple l'étude des fonctions calculables en temps polynomial. Ils ont donné une réponse partielle à la question: «Pour quelles théories de l'arithmétique le théorème de complétude arithmétique de Solovay (par rapport au prédicat de prouvabilité approprié) est-il toujours valable?» Pour discuter de cette question, deux concepts sont nécessaires. (Delta_0) - les formules sont des formules arithmétiques dans lesquelles tous les quantificateurs sont délimités par un terme, par exemple

) forall y / le / bs / bs 0 \: / forall z / le y \: / forall x / le y + z \: (x + y / le (y + (y + z))),)

où (bs) est l'opérateur successeur («(+ 1)»). La théorie arithmétique (I / Delta_0) (où I signifie «induction»), est similaire à Peano Arithmetic, sauf qu'elle permet moins d'induction: le schéma d'induction

[A (0) wedge / forall x \, (A (x) rightarrow A (bs x)) rightarrow / forall x \, A (x))

est limité à (Delta_0) - formules (A).

Comme l'ont souligné De Jongh et al. (1991), la complétude arithmétique est certainement valable pour les théories (T) qui satisfont aux deux conditions suivantes:

  1. (T) prouve l'induction pour (Delta_0) - formules, et (T) prouve EXP, la formule exprimant que pour tout (x), sa puissance (2 ^ x) existe. En notation plus standard: (T) étend (I / Delta_0) + EXP;
  2. (T) ne prouve pas de fausses phrases de la forme (existe x \, A (x)), avec (A (x)) a (Delta_0) - formule.

Pour de telles théories, la solidité arithmétique et l'exhaustivité de GL sont valables, à condition que (Box) se traduise par (Prov_T), un prédicat de prouvabilité naturel par rapport à une axiomatisation suffisamment simple de (T). Ainsi pour les phrases modales (A):

) GL / vdash A / text {si et seulement si pour toutes les réalisations} f, T / vdash f (A).)

Il n'est pas encore clair si la condition 1 donne une limite inférieure à la portée de la logique de prouvabilité. Par exemple, la question reste ouverte de savoir si GL est la logique de prouvabilité de (I / Delta_0 + / Omega_1), une théorie qui est un peu plus faible que (I / Delta_0) + EXP dans ce (Omega_1) est l'axiome affirmant que pour tout (x), sa puissance (x ^ { log (x)}) existe. La logique de prouvabilité GL est arithmétiquement valable par rapport à (I / Delta_0 + / Omega_1), mais à l'exception de quelques résultats partiels de Berarducci et Verbrugge (1993), fournissant des réalisations arithmétiques cohérentes avec (I / Delta_0 + / Omega_1) pour un classe de phrases conforme à GL, la question reste ouverte. Sa réponse peut reposer sur des problèmes ouverts en théorie de la complexité computationnelle.

Le résultat ci-dessus de De Jongh et al. montre une caractéristique forte de la logique de prouvabilité: pour de nombreuses théories arithmétiques différentes, GL capture exactement ce que ces théories disent au sujet de leurs propres prédicats de prouvabilité. En même temps, c'est une faiblesse. Par exemple, la logique de prouvabilité propositionnelle ne met en évidence aucune différence entre les théories qui sont finement axiomatisables et celles qui ne le sont pas.

5.2 Logique d'interprétabilité

Afin de pouvoir parler dans un langage modal des distinctions importantes entre les théories, les chercheurs ont étendu la logique de la prouvabilité de différentes manières. Citons-en quelques-uns. Une extension consiste à ajouter une modalité binaire (interprets), où pour une théorie arithmétique donnée (T), la phrase modale (A / interprète B) est censée représenter (T + B) est interprétable dans (T + A) »(Švejdar, 1983). De Jongh et Veltman (1990) ont étudié la sémantique modale pour plusieurs logiques d'interprétabilité, tandis que De Jongh et Visser (1991) ont démontré la propriété de virgule fixe explicite pour les plus importantes. Visser a caractérisé la logique d'interprétabilité des théories finement axiomatisées les plus courantes, et Berarducci et Shavrukov ont indépendamment caractérisé celle de l'AP, qui n'est pas finement axiomatisable. Il semble qu'en effet,la logique d'interprétabilité des théories finement axiomatisables est différente de la logique d'interprétabilité de Peano Arithmetic (voir Montagna 1987; Visser 1990, 1998; Berarducci 1990, Shavrukov 1988; Joosten et Visser 2000).

5.3 Quantificateurs propositionnels

Une autre façon d'étendre le cadre de la logique de prouvabilité propositionnelle est d'ajouter des quantificateurs propositionnels, afin que l'on puisse exprimer des principes comme celui de Goldfarb:

) forall p \, / forall q \, / existe r \: / Box ((Box p / vee / Box q) leftrightarrow / Box r),)

en disant que pour deux phrases quelconques, il y a une troisième phrase qui est prouvable si et seulement si l'une des deux premières phrases est prouvable. Ce principe est prouvable dans Peano Arithmetic (voir par exemple Artemov et Beklemishev 1993). L'ensemble des phrases de GL avec des quantificateurs propositionnels qui est arithmétiquement valide s'avère indécidable (Shavrukov 1997).

5.4 Logiques de prouvabilité bimodales et polymodales de Japaridze

La logique bimodale GLB de Japaridze (1988) a deux opérateurs de prouvabilité de type (Box), désignés par ([0]) et ([1]), avec leurs opérateurs doubles (Diamond) (langle 0 / rangle) et (langle 1 / rangle), respectivement. Dans l'interprétation de Japaridze, on peut penser à ([0]) comme représentant le prédicat de prouvabilité standard dans Peano Arithmetic. En revanche, ([1]) correspond à un prédicat de prouvabilité plus fort, à savoir (omega) - provabilty.

Définissons les concepts nécessaires pour comprendre cette interprétation voulue de GLB. Une théorie arithmétique (T) est définie comme (omega) - cohérente si et seulement si pour toutes les formules A avec variable libre (x), (T / vdash / neg \, A (I_n)) pour tout (n) implique que (T / not / vdash / existe x \, A (x)); ici, (I_n) est le nombre de (n), c'est-à-dire le terme (bs / bs / ldots / bs 0) avec (n) occurrences de l'opérateur successeur (bs). Peano Arithmetic (PA) est l'exemple le plus connu d'une théorie (omega) - cohérente (voir aussi les théorèmes d'incomplétude de Gödel). Soit maintenant PA (^ +) la théorie arithmétique dont les axiomes sont ceux de PA avec toutes les phrases (forall x \, / neg \, A (x)) telles que pour tout (n), PA (vdash / neg \, A (I_n)). Maintenant (omega) - la prouvabilité est simplement la prouvabilité dans PA (^ +),c'est donc le dual de (omega) - cohérence.

La logique de prouvabilité bimodale de Japaridze GLB peut être axiomatisée par les axiomes et les règles de GL (voir section 2), formulées séparément pour [0] et [1]. De plus, GLB a deux axiomes mixtes, à savoir:) tag {Monotonicity} [0] A / rightarrow [1] A)) tag {(Pi ^ 0_1) - complétude} langle 0 / rangle A / rightarrow [1] langle 0 / rangle A) La logique de Japaridze est décidable et a une sémantique de Kripke raisonnable, et elle est arithmétiquement saine et complète par rapport à Peano Arithmetic (Japaridze 1988, Boolos 1993).

Un analogue polymodal du GLB de Japaridze, appelé GLP, a reçu beaucoup d'attention ces dernières années. GLP a une infinité de (Box) - comme les opérateurs de prouvabilité, désignés par des boîtes ([n]) pour chaque nombre naturel (n), avec leur double (Diamond) - comme opérateurs (langle n / rangle). Encore une fois, on peut penser à ([0]) comme représentant le prédicat de prouvabilité standard dans Peano Arithmetic, (langle 1 / rangle) pour (omega) - prouvabilité, etc. GLP a été axiomatisé en partant des axiomes et des règles de GL (voir section 2), formulés séparément pour chaque ([n]). De plus, GLP a trois schémas d'axiomes mixtes, à savoir, comme formulé par Beklemishev (2010): [m] A / rightarrow [n] A, / mbox {for} m / leq n)) langle k / rangle A / rightarrow [n] langle k / rangle A, / mbox {for} k / lt n) [m] A / rightarrow [n] [m] A, / mbox {for} m / leq n)

GLP a récemment été doté d'une sémantique de Kripke par rapport à laquelle il est complet, et s'est également révélé arithmétique complet par rapport à Peano Arithmetic (voir Beklemishev 2010a, 2011a). Tout comme pour GL, le problème de décision pour GLP est PSPACE-complet (Shapirovsky 2008), tandis que son fragment fermé est décidable en temps polynomial (Pakhomov 2014).

Ces dernières années, un certain nombre de résultats ont été prouvés sur la logique polymodale BPL des prédicats de prouvabilité forts. Voici quelques sujets particulièrement fructueux:

  • le fragment fermé de BPL (voir Ignatiev 1993; Beklemishev, Joosten et Vervoort 2005);
  • BPL et ordinaux de la théorie de la preuve (Beklemishev 2004);
  • Théorèmes d'interpolation pour les BPL (voir Beklemishev 2010b, Shamkanov 2011);
  • La relation entre la sémantique topologique et la théorie des ensembles, entre autres grands axiomes cardinaux particuliers et réflexion stationnaire (voir Beklemishev 2011b; Beklemishev et Gabelaia 2013, 2014; Fernández-Duque 2014).

5.5 Logique de prouvabilité des prédicats

Enfin, on peut bien sûr étudier la logique de prouvabilité des prédicats. Le langage est celui de la logique de prédicat sans symboles de fonction, avec l'opérateur (Box). Ici, la situation devient beaucoup plus complexe que dans le cas de la logique de provabilité propositionnelle. Pour commencer, la version quantifiée simple de GL n'a pas la propriété de virgule fixe, n'est pas complète par rapport à aucune classe de cadres de Kripke, et n'est pas arithmétiquement complète par rapport à Peano Arithmetic (Montagna, 1984). La question se pose alors: y a-t-il une logique de prouvabilité de prédicat bien axiomatisée qui soit adéquate, prouvant exactement les principes valides de la prouvabilité? La réponse est malheureusement un non catégorique:Vardanyan (1986) a prouvé sur la base des idées d'Artemov (1985a) que l'ensemble des phrases de la logique de prouvabilité des prédicats dont toutes les réalisations sont prouvables dans PA n'est même pas récursivement énumérable mais (Pi ^ 0_2) - complet, il n'a donc pas d'axiomatisation raisonnable. Visser et De Jonge (2006) ont montré qu'il n'y a pas d'échappatoire au théorème de Vardanyan en prouvant une généralisation: pour un large éventail de théories arithmétiques (T), l'ensemble des phrases de la logique de prouvabilité des prédicats dont toutes les réalisations sont prouvables dans (T) s'avère être (Pi ^ 0_2) - complet également. Pour un large éventail de théories arithmétiques (T), l'ensemble des phrases de la logique de prouvabilité des prédicats dont toutes les réalisations sont prouvables dans (T) se révèle être (Pi ^ 0_2) - complet également. Pour un large éventail de théories arithmétiques (T), l'ensemble des phrases de la logique de prouvabilité des prédicats dont toutes les réalisations sont prouvables dans (T) se révèle être (Pi ^ 0_2) - complet également.

5.6 Autres généralisations

La discussion ci-dessus laisse de côté de nombreux autres axes de recherche importants sur la logique de la prouvabilité et ses extensions. Le lecteur intéressé est dirigé vers les domaines suivants:

  • la logique de prouvabilité de l'arithmétique intuitionniste (voir Troelstra 1973; Visser 1982, 1999; Iemhoff 2000, 2001, 2003; Visser 2002, 2008);
  • classification des logiques de prouvabilité (voir Visser 1980, Artemov 1985b, Beklemishev 1989, Beklemishev et al. 1999);
  • Ordonnances de Rosser et accélération de la preuve (voir Guaspari et Solovay 1979, Švejdar 1983, Montagna 1992);
  • plusieurs types de logiques de prouvabilité bimodales avec des opérateurs de prouvabilité pour différentes théories (voir Carlson 1986; Smoryński 1985; Beklemishev 1994, 1996);
  • logiques de prouvabilité pour la prouvabilité standard combinée à des prédicats de prouvabilité inhabituels énumérant les AP de manière externe, tels que les prédicats de prouvabilité de Feferman et Parikh et les prédicats de prouvabilité lente (voir Montagna 1978; Visser 1989; Shavrukov 1994; Lindström 1994, 2006; Henk et Pakhomov 2016 (Other Internet Resources));
  • la logique des preuves explicites (voir Artemov 1994, 2001; Artemov et Montagna 1994; Artemov et Iemhoff 2007);
  • applications de la logique de la prouvabilité dans la théorie de la preuve (voir Beklemishev 1999, 2004, 2005, 2006);
  • logiques de prouvabilité positive et calcul de réflexion (voir Beklemishev 2012, 2014; Dashkov 2012);
  • les généralisations de la logique de prouvabilité polymodale BPL, à savoir les logiques de prouvabilité avec des modalités transfiniment nombreuses (voir Beklemishev et al.2014; Fernández-Duque et Joosten 2013a, 2013b, 2013 (Other Internet Resources), 2014);
  • les relations entre la logique de prouvabilité et le (mu) - calcul (voir van Benthem 2006, Visser 2005, Alberucci et Facchini 2009); et
  • algèbres de prouvabilité, également appelées algèbres diagonalisables ou algèbres de Magari (voir Magari 1975a, 1975b; Montagna 1979, 1980a, 1980b; Shavrukov 1993a, 1993b, 1997; Zambella 1994; pour des résultats récents sur leurs théories élémentaires, voir Pakhomov 2012, 2014 (Other Internet Resources), 2015 (Autres ressources Internet)).

Pour le lecteur qui souhaite contribuer au domaine de la logique de la prouvabilité et de ses généralisations, Beklemishev et Visser (2006) ont proposé une liste annotée de problèmes ouverts intrigants.

6. Importance philosophique

Même si la logique de provabilité propositionnelle est une logique modale avec une sorte d'opérateur de «nécessité», elle résiste à la critique controversée de Quine (1976) des notions modales comme inintelligibles, déjà en raison de son interprétation arithmétique claire et sans ambiguïté. Par exemple, contrairement à de nombreuses autres logiques modales, les formules avec des modalités imbriquées telles que (Box / Diamond p / rightarrow / Box / bot) ne sont pas problématiques, et il n'y a pas non plus de litige sur celles qui devraient être des tautologies. En fait, la logique de la prouvabilité incarne toutes les desiderata que Quine (1953) a énoncées pour les traitements syntaxiques de la modalité.

Les flèches principales de Quine étaient dirigées vers des logiques de prédicat modal, en particulier la construction de phrases contenant des opérateurs modaux dans le cadre de quantificateurs («quantifying in»). Dans la logique de prouvabilité des prédicats, cependant, où les quantificateurs se situent sur des nombres naturels, les modalités de dicto et de re ont des interprétations simples, contrairement au cas d'autres logiques modales (voir la note sur la distinction de dicto / de re). Par exemple, des formules comme

) forall x \, / Box \, / existe y \, (y = x))

ne sont pas du tout problématiques. Si le nombre (n) est attribué à (x), alors (Box \, / existe y \, (y = x)) est vrai par rapport à cette affectation ssi la phrase (existe y \, (y = I_n)) est prouvable en Peano Arithmetic; ici, (I_n) est le nombre de (n), c'est-à-dire le terme (bs / bs / ldots / bs 0) avec (n) occurrences de l'opérateur successeur (bs). Cette phrase est vraie pour tout (n) dans le modèle standard des nombres naturels, et (forall x \, / Box \, / exists y \, (y = x)) est même prouvable en Peano Arithmetic.

Au fait, la formule Barcan

) forall x \, / Box \, A (x) rightarrow / Box \, / forall x \, A (x))

n'est pas vrai pour les nombres entiers, encore moins prouvable (par exemple, prenez pour (A (x)) la formule «(x) ne code pas une preuve de (bot)»). Son converse

) Box \, / forall x \, A (x) rightarrow / forall x \, / Box \, A (x))

d'autre part, est prouvable dans Peano Arithmetic pour toute formule (A).

La logique de la prouvabilité a des principes très différents des autres logiques modales, même celles ayant un objectif apparemment similaire. Par exemple, alors que la logique de la prouvabilité saisit la prouvabilité dans les théories formelles de l'arithmétique, la logique épistémique s'efforce de décrire la connaissance, qui pourrait être considérée comme une sorte de prouvabilité informelle. Dans de nombreuses versions de la logique épistémique, l'un des principes les plus importants est l'axiome de la vérité (5):

) mbox {S5} vdash / Box A / rightarrow A, (text {si on sait} A, / text {then} A / text {est vrai}).)

Le principe analogue ne vaut clairement pas pour GL: après tout,) text {if} GL / vdash / Box A / rightarrow A, / text {then} GL / vdash A.)

Ainsi, il semble erroné de comparer la force des deux notions ou de les combiner dans un système modal. Peut-être que la prouvabilité formelle est en effet dans un certain sens une notion plus forte que la prouvabilité informelle, mais ce n'est certainement pas une vérité ou une validité arithmétique, ni l'autre direction. Les discussions sur les conséquences des théorèmes d'incomplétude de Gödel impliquent parfois une confusion autour de la notion de prouvabilité, donnant lieu à des affirmations selon lesquelles les humains pourraient battre les systèmes formels dans les théorèmes de «connaissance» (voir Davis (1990, 1993) pour de bonnes discussions sur ces affirmations).

Dans l'ensemble, la prouvabilité formelle est un concept précisément défini, bien plus que la vérité et la connaissance. Ainsi, l'auto-référence dans le cadre de la prouvabilité ne conduit pas à des paradoxes sémantiques comme le menteur. Au lieu de cela, cela a conduit à certains des résultats les plus importants sur les mathématiques, tels que les théorèmes d'incomplétude de Gödel.

Bibliographie

Références générales sur la logique de la prouvabilité

  • Artemov, SN, 2006, «Modal Logic in Mathematics», dans P. Blackburn, et al. (eds.), Handbook of Modal Logic, Amsterdam: Elsevier, pp. 927–970.
  • Artemov, SN et LD Beklemishev, 2004, «Provability Logic», dans Handbook of Philosophical Logic, deuxième édition, D. Gabbay et F. Guenthner, éds., Volume 13, Dordrecht: Kluwer, pp. 229–403.
  • Boolos, G., 1979, L'improvabilité de la cohérence: un essai en logique modale, Cambridge: Cambridge University Press.
  • –––, 1993, The Logic of Provability, New York et Cambridge: Cambridge University Press.
  • de Jongh, DHJ et G. Japaridze, 1998, «The Logic of Provability», dans Handbook of Proof Theory, Buss, SR (éd.), Amsterdam: North-Holland, pp. 475-546.
  • Lindström, P., 1996, «Provability Logic-A Short Introduction», Theoria, 52 (1–2): 19–61.
  • Segerberg, K., 1971, Un essai en logique modale classique, Uppsala: Filosofiska Föreningen och Filosofiska Institutionen vid Uppsala Universitet.
  • Švejdar, V., 2000, «On Provability Logic», Nordic Journal of Philosophy, 4: 95–116.
  • Smoryński, C., 1985, Self-Reference and Modal Logic, New York: Springer-Verlag.
  • Verbrugge, R. 1996, «Provability» dans The Encyclopedia of Philosophy (Supplément), DM Borchert (ed.), New York: Simon et Schuster MacMillan, pp. 476–478.
  • Visser, A., 1998, «Provability Logic», dans Routledge Encyclopedia of Philosophy, W. Craig (éd.), Londres: Routledge, pp. 793–797.

L'histoire

  • van Benthem, JFAK, 1978, «Quatre paradoxes», Journal of Philosophical Logic, 7 (1): 49–72.
  • Boolos, G. et G. Sambin, 1991, «Provability: The Emergence of a Mathematical Modality», Studia Logica, 50 (1): 1–23.
  • Gödel, K., 1933, «Interprétation Eine des intuitionistischen Aussagenkalküls», Ergebnisse eines Mathematischen Kolloquiums, 4: 39–40; traduction «Une interprétation du calcul propositionnel intuitionniste», dans K. Gödel, Œuvres collectées, S. Feferman et al. (eds.), Oxford et New York: Oxford University Press, Volume 1, 1986, pp. 300–302.
  • –––, 1931, «Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme I», Monatshefte für Mathematik und Physik, 38: 173–198.
  • Halbach, V. et A. Visser, 2014, «The Henkin Sentence», dans M. Mazano, I. Sain et E. Alonso (éd.), The Life and Work of Leon Henkin: Essays on His Contributions, Dordrecht: Springer International Publishing, pp. 249-263.
  • Henkin, L., 1952, «Un problème concernant la prouvabilité», Journal of Symbolic Logic, 17: 160.
  • –––., 1954, «Examen de G. Kreisel: Sur un problème de Léon Henkin», Journal of Symbolic Logic, 19 (3): 219–220.
  • Hilbert, D. et P. Bernays, 1939, Grundlagen der Mathematik, volume 2, Berlin / Heidelberg / New York: Springer-Verlag.
  • Kreisel, G., 1953, «Sur un problème de Léon Henkin», Indagationes Mathematicae, 15: 405–406.
  • Lewis, CI, 1912, «Implication et l'algèbre de la logique», Mind, 21: 522-531.
  • Löb, MH, 1955, «Solution d'un problème de Léon Henkin», Journal of Symbolic Logic, 20: 115–118.
  • Macintyre, AJ et H. Simmons, 1973, «Technique de diagonalisation de Gödel et propriétés connexes des théories», Colloquium Mathematicum, 28: 165-180.
  • Magari, R., 1975a, «Les algèbres diagonalisables», Bollettino della Unione Mathematica Italiana, 12: 117–125.
  • –––, 1975b, «Théorie de la représentation et de la dualité pour les algèbres diagonalisables», Studia Logica, 34 (4): 305–313.
  • Smiley, TJ, 1963, «La base logique de l'éthique», Acta Philosophica Fennica, 16: 237–246.
  • Smoryński, C., 1991, «Le développement de l'auto-référence: le théorème de Löb», dans T. Drucker (éd.), Perspectives sur l'histoire de la logique mathématique, Bâle: Birkhäuser, pp. 110–133.

Élimination des coupures pour la logique de prouvabilité

  • Goré, R. et R. Ramanayake, 2008, «Valentini's Cut-Elimination for Provability Logic Resolved», dans Advances in Modal Logic Volume 7, C. Areces et R. Goldblatt (éd.), Londres: College Publications, pp. 67 -86.
  • Negri, S., 2005, «Proof Analysis in Modal Logic», Journal of Philosophical Logic, 50: 507-544.
  • Negri, S., 2014, «Preuves et contre-modèles dans les logiques non classiques», Logica Universalis, 8 (1): 25–60.
  • Poggiolesi, F., 2009, «Un calcul séquentiel purement syntaxique et sans coupure pour la logique modale de la prouvabilité», The Review of Symbolic Logic, 2 (4): 593–611.
  • Rautenberg, W., 1983, «Modal Tableau Calculi and Interpolation», Journal of Philosophical Logic, 12 (4): 403–423.
  • Sambin, G. et S. Valentini, 1982, «La logique modale de la prouvabilité. L'approche séquentielle », Journal of Philosophical Logic, 11 (3): 311–342.
  • Shamkanov, DS, 2011, «Propriétés d'interpolation pour Provability Logics GL et GLP», Actes du Steklov Institute of Mathematics, 274 (1): 303–316.
  • –––, 2014, «Preuves circulaires pour la logique de prouvabilité de Gödel-Löb», Notes mathématiques, 96 (4): 575–585.
  • Smoryński, C., 1978, «Théorème de Beth et phrases autoréférentielles», Studies in Logic and the Foundations of Mathematics, 96: 253-261.
  • Valentini, S., 1983, «La logique modale de la prouvabilité: Cut-Elimination», Journal of Philosophical Logic, 12: 471–476.

Le théorème du point fixe

  • de Jongh, DHJ et F. Montagna, 1988, «Provable Fixed Points», Mathematical Logic Quarterly, 34 (3): 229-250.
  • Lindström, P., 2006, «Note sur certaines constructions en points fixes dans la logique de la provabilité», Journal of Philosophical Logic, 35 (3): 225–230.
  • Reidhaar-Olson, L., 1990, «Une nouvelle preuve du théorème à virgule fixe de la logique de la prouvabilité», Notre Dame Journal of Formal Logic, 31 (1): 37–43.
  • Sambin, G., 1976, «Un théorème de point fixe efficace dans les algèbres diagonalisables intuitionnistes (l'algèbre des théories qui expriment le théorème, IX)», Studia Logica 35: 345–361.
  • Sambin, G. et S. Valentini, 1982, «La logique modale de la prouvabilité. L'approche séquentielle », Journal of Philosophical Logic, 11 (3): 311–342.

Sémantique des mondes possibles et sémantique topologique

  • Abashidze, M., 1985, «Complétude ordinale du système modal de Gödel-Löb», (en russe) dans Intensional Logics and the Logical Structure of Theories, Tbilissi: Metsniereba, pp. 49–73.
  • Aiello, M., I. Pratt-Hartmann et J. van Benthem (éds.), 2007, Handbook of Spatial Logics, Berlin: Springer-Verlag.
  • Beklemishev, LD 2009, «Complétude ordinale de la logique de prouvabilité bimodale GLB», dans le Symposium international de Tbilissi sur la logique, le langage et le calcul, Berlin: Springer-Verlag, pp. 1–15.
  • Beklemishev, LD, G. Bezhanishvili et T. Icard, 2009, «On Topological Models of GLP», dans R. Schindler (ed.), Ways of Proof Theory (Ontos Mathematical Logic: Volume 2), Frankfurt: Ontos Verlag, 133-153.
  • Blass, A., 1990, «Combinatoire infinitaire et logique modale», Journal of Symbolic Logic, 55 (2): 761–778.
  • Esakia, L., 1981, «Diagonal Constructions, Löb's Formula and Cantor Scattered Spaces» (en russe), in Studies in Logic and Semantics, Z. Mikeladze (ed.), Tbilissi: Metsniereba, pp. 128–143.
  • –––, 2003, «Logique intuitionniste et modalité via la topologie», Annals of Pure and Applied Logic, 127: 155-170.
  • Goré, R., 2009, «Machine Checking Proof Theory: An Application of Logic to Logic», dans ICLA '09: Actes de la 3e Conférence indienne sur la logique et ses applications, Berlin: Springer-Verlag, pp. 23–35.
  • Goré, R. et J. Kelly, 2007, «Automated Proof Search in Gödel-Löb Provability Logic», British Logic Colloquium 2007, disponible sur https://www.dcs.bbk.ac.uk/~roman/blc/.
  • Hakli, R. et S. Negri, 2012, «Le théorème de déduction échoue-t-il pour la logique modale?», Synthese 187 (3): 849–867.
  • Icard, TF III, 2011, «Une étude topologique du fragment fermé de GLP», Journal of Logic and Computation, 21 (4): 683–696; première publication en ligne 2009, doi: 10.1093 / logcom / exp043
  • Japaridze, GK, 1986, The Modal Logical Means of Investigation of Provability, Thèse de Philosophie (en russe), Moscou.
  • McKinsey, JCC et A. Tarski, 1944, «L'algèbre de la topologie», Annals of Mathematics, 45: 141–191.

Prouvabilité et arithmétique Peano

  • Davis, M., 1958, Computability and Unsolvability, New York, McGraw-Hill; réimprimé avec une annexe supplémentaire, New York, Dover Publications 1983.
  • Feferman, S., 1960, «Arithmétisation des métamathématiques dans un contexte général», Fundamenta Mathematicae, 49 (1): 35–92.
  • Hájek, P. et P. Pudlák, 1993, Métamathématiques de l'arithmétique du premier ordre, Berlin: Springer-Verlag.
  • Solovay, RM, 1976, «Interprétations de la prouvabilité de la logique modale», Journal d'Israël de mathématiques, 25: 287–304.

La portée de la logique de la prouvabilité: les limites

  • Berarducci, A. et R. Verbrugge, 1993, «Sur la logique de la prouvabilité de l'arithmétique bornée», Annals of Pure and Applied Logic, 61: 75–93.
  • Buss, SR, 1986, Arithmétique bornée, Naples: Bibliopolis.
  • de Jongh, DHJ, M. Jumelet et F. Montagna, 1991, «Sur la preuve du théorème de Solovay», Studia Logica, 50 (1): 51–70.

Logique d'interprétabilité

  • Berarducci, A., 1990, «La logique d'interprétabilité de Peano Arithmetic», Journal of Symbolic Logic, 55: 1059-1089.
  • de Jongh, DHJ et F. Veltman, 1990, «Provability Logics for Relative Interprétabilité», in PP Petkov (ed.), Mathematical Logic: Proceedings of the Heyting 1988 Summer School in Varna, Bulgaria, Boston: Plenum Press, pp. 31–42.
  • de Jongh, DHJ et A. Visser, 1991, «Points fixes explicites dans la logique d'interprétabilité», Studia Logica, 50 (1): 39–49.
  • Joosten, JJ et Visser, A., 2000, «La logique d'interprétabilité de toutes les théories arithmétiques raisonnables», Erkenntnis, 53 (1-2): 3–26.
  • Montagna, F., 1987, «Provability in Finite Subtheories of PA», Journal of Symbolic Logic, 52 (2): 494–511.
  • Shavrukov, V. Yu., 1988, «La logique de l'interprétabilité relative sur Peano Arithmetic», Rapport technique n ° 5, Moscou: Steklov Mathematical Institute (en russe).
  • Švejdar, V., 1983, «Analyse modale des phrases de Rosser généralisées», Journal of Symbolic Logic, 48: 986–999.
  • Visser, A., 1990, «Interprétabilité Logique», dans PP Petkov (éd.), Mathematical Logic: Proceedings of the Heyting 1988 Summer School in Varna, Bulgaria, Boston: Plenum Press, pp. 175–209.
  • –––, 1998, «Un aperçu de la logique d'interprétabilité», dans M. Kracht et al. (eds.), Advances in Modal Logic (Volume 1), Stanford: Publications CSLI, pp. 307–359.

Quantificateurs propositionnels

  • Artemov, SN et LD Beklemishev, 1993, «Sur les quantificateurs propositionnels dans la logique de la provabilité», Notre Dame Journal of Formal Logic, 34: 401–419.
  • Shavrukov, V. Yu., 1997, «Indécidabilité dans les algèbres diagonalisables», Journal of Symbolic Logic, 62: 79–116.

Logiques de prouvabilité bimodales et polymodales de Japaridze

  • Beklemishev, LD, 2004, «Algèbres de preuve et ordinaux de preuve théorique, I», Annals of Pure and Applied Logic, 128: 103–123.
  • –––, 2010a, «Kripke Semantics for Provability Logic GLP», Annals of Pure and Applied Logic, 161 (6): 756–774.
  • –––, 2010b, «On the Craig Interpolation and the Fixed Point Properties of GLP», dans S. Feferman et al. (eds.), Proofs, Categories and Computations (Tributes, 13), Londres: College Publications, pp. 49–60.
  • –––, 2011a, «Une preuve simplifiée du théorème de complétude arithmétique pour la logique de la prouvabilité GLP», Proceedings Steklov Institute of Mathematics, 274 (1): 25–33.
  • –––, 2011b, «Ordinal Completeness of Bimodal Provability Logic GLB», dans N. Bezhanishvili et al. (eds.), Logic, Language, and Computation, 8th International Tbilisi Symposium TbiLLC 2009 (Notes de cours en informatique: volume 6618), Heidelberg: Springer, pp. 1–15.
  • Beklemishev, LD et D. Gabelaia, 2013, «Complétude topologique de la logique de prouvabilité GLP», Annals of Pure and Applied Logic, 164 (12): 1201–1223.
  • –––, 2014, «Topological Interprétations of Provability Logic», dans G. Bezhanishvili (éd.), Leo Esakia on Duality in Modal and Intuitionistic Logics (Outstanding Contributions to Logic: Volume 4), Heidelberg: Springer, pp. 257– 290.
  • Beklemishev, LD, J. Joosten et M. Vervoort, 2005, «Un traitement finitaire du fragment fermé de la logique de provabilité de Japaridze», Journal of Logic and Computation, 15 (4): 447–463.
  • Fernández-Duque, D. et JJ Joosten, 2014, «Well-orders on the Transfinite Japaridze Algebra», Journal logique de l'IGPL, 22 (6): 933–963.
  • Ignatiev, KN, 1993, «Sur les prédicats forts de prouvabilité et les logiques modales associées», Journal of Symbolic Logic, 58: 249-290.
  • Japaridze, G., 1988, «La logique polymodale de la prouvabilité», dans Intensional Logics and the Logical Structure of Theories: Material from the Fourth Soviet-Finnish Symposium on Logic, Telavi, pp. 16–48.
  • Pakhomov, FN, 2014, «Sur la complexité du fragment fermé de la logique de provabilité de Japaridze», Archive for Mathematical Logic, 53 (7-8): 949–967.

Logique de prouvabilité des prédicats

  • Artemov, SN, 1985a, «Nonarithméticité de la vérité Prédicat Logiques de la prouvabilité», Doklady Akademii Nauk SSSR, 284: 270-271 (en russe); Traduction anglaise dans soviétique Mathematics Doklady, 32: 403–405.
  • McGee, V. et G. Boolos, 1987, «Le degré de l'ensemble des phrases de la logique de prouvabilité des prédicats qui sont vraies sous chaque interprétation», Journal of Symbolic Logic, 52: 165–171.
  • Vardanyan, VA, 1986, «Complexité arithmétique des logiques de prédicat de la prouvabilité et de leurs fragments», Doklady Akademii Nauk SSSR, 288: 11–14 (en russe); Traduction anglaise en mathématiques soviétiques Doklady, 33: 569-572.
  • Visser, A. et M. de Jonge, 2006, «Aucune évasion du théorème de Vardanyan», Archive of Mathematical Logic, 45 (5): 539–554.

Autres généralisations

  • Alberucci, L. et A. Facchini, 2009, «Sur le μ-calcul modal et la logique de Gödel-Löb», Studia Logica, 91: 145-169.
  • Artemov, SN, 1985b, «On Modal Logics Axiomatizing Provability», Izvestiya Akadademii Nauk SSSR, Seriya Matematicheskaya, 49 (6): 1123–1154 (en russe); Traduction anglaise en mathématiques de l'URSS-Izvestiya, 27 (3): 402–429.
  • –––, 1994, «Logic of Proofs», Annals of Pure and Applied Logic, 67 (2): 29–59.
  • –––, 2001, «Explicit Provability and Constructive Semantics», Bulletin of Symbolic Logic, 7: 1–36.
  • Artemov, SN et R. Iemhoff, 2007, «La logique intuitionniste de base des preuves», Journal of Symbolic Logic, 72 (2): 439–451.
  • Artemov, SN et F. Montagna, 1994, «Sur les théories du premier ordre avec opérateur de prouvabilité», Journal of Symbolic Logic, 59 (4): 1139–1153.
  • Beklemishev, LD, 1989, «Sur la classification des logiques de provabilité propositionnelles», Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya., 53 (5): 915–943 (en russe); Traduction anglaise en mathématiques de l'URSS-Izvestiya, 35 (1990) 247-275.
  • –––, 1994, «Sur les logiques bimodales de la prouvabilité», Annals of Pure and Applied Logic, 68: 115-160.
  • –––, 1996, «Bimodal Logics for Extensions of Arithmetical Theories», Journal of Symbolic Logic, 61: 91–124.
  • –––, 1999, «Induction sans paramètre et fonctions calculables totales prouvées», Theoretical Computer Science, 224: 13–33.
  • –––, 2005, «Principes de réflexion et algèbres de prouvabilité en arithmétique formelle», Uspekhi Matematicheskikh Nauk, 60 (2): 3–78. (en russe); Traduction anglaise en: Russian Mathematical Surveys, 60 (2) (2005): 197-268.
  • –––, 2006, «The Worm Principle», dans Lecture Notes in Logic 27. Logic Colloquium '02, Z. Chatzidakis, P. Koepke et W. Pohlers (éd.), Natick (MA): AK Peters, pp 75–95.
  • –––, 2012, «Calibrating Provability Logic: From Modal Logic to Reflection Calculus», dans T. Bolander, T. Braüner, S. Ghilardi et L. Moss (éds.), Advances in Modal Logic (Volume 9), Londres: College Publications, pp. 89–94.
  • –––, 2014, «Logique de preuve positive pour des principes de réflexion uniformes», Annals of Pure and Applied Logic, 165 (1): 82–105.
  • Beklemishev, LD, D. Fernández-Duque et JJ Joosten, 2014, «On Provability Logics with Linearly Ordered Modencies», Studia Logica, 102 (3): 541–566.
  • Beklemishev, LD, M. Pentus et N. Vereshchagin, 1999, Provability, Complexity, Grammars, American Mathematical Society Translations (Series 2, Volume 192).
  • Beklemishev, LD et A. Visser, 2006, «Problems in the Logic of Provability», in DM Gabbay, SS Goncharov et M. Zakharyashev (eds.), Mathematical Problems from Applied Logic I: Logics for the XXIst Century (International Mathematical Series, Volume 4), New York: Springer, pp. 77-136.
  • van Benthem, J., 2006, «Correspondances de trames modales et points fixes», Studia Logica, 83 (1-3): 133–155.
  • Carlson, T., 1986, «Logiques modales avec plusieurs opérateurs et interprétations de prouvabilité», Israel Journal of Mathematics, 54 (1): 14–24.
  • Dashkov, EV, 2012, «Sur le fragment positif de la logique de prouvabilité polymodale GLP», Notes mathématiques, 91 (3): 318–333.
  • Fernández-Duque, D., 2014, «Les polytopologies de la logique de prouvabilité transfinie», Archive for Mathematical Logic, 53 (3-4): 385–431.
  • Fernández-Duque, D. et JJ Joosten, 2013a, «Hyperations, Veblen Progressions et Transfinite Iteration of Ordinal Functions», Annals of Pure and Applied Logic 164 (7-8): 785–801, [disponible en ligne].
  • Fernández-Duque, D. et JJ Joosten, 2013b, «Models of Transfinite Provability Logic», Journal of Symbolic Logic, 78 (2): 543-561, [disponible en ligne].
  • Guaspari, D. et RM Solovay, 1979, «Sentences de Rosser», Annals of Mathematical Logic, 16: 81–99.
  • Iemhoff, R., 2000, «Une analyse modale de certains principes de la logique de prouvabilité de l'arithmétique de Heyting», dans Advances in Modal Logic (Volume 2), M. Zakharyashev et al. (eds.), Stanford: Publications CSLI, pp. 319–354.
  • –––, 2001, «Sur les règles admissibles de la logique propositionnelle intuitionniste», Journal of Symbolic Logic, 66: 281-294.
  • –––, 2003, «Logique de préservation: un analogue de la logique d'interprétabilité pour les théories constructives», Mathematical Logic Quarterly, 49 (3): 1–21.
  • Lindström, P., 1994, «La logique modale de la prouvabilité parikh», Filosofiska Meddelanden, Gröna Serien, Göteborg: Göteborgs Universitetet.
  • Lindström, P., 2006, «On Parikh Provability: An Exercise in Modal Logic», dans H. Lagerlund, S. Lindström et R. Sliwinski (eds.), Modality Matters: Twenty-Five Essays in Honour of Krister Segerberg, Uppsala: Uppsala Philosophical Studies (Volume 53), pp. 53-287.
  • Montagna, F., 1978, «Sur l'algébraisation d'un prédicat de Feferman», Studia Logica, 37 (3): 221-236.
  • –––, 1979, «Sur l'algèbre diagonalisable de Peano Arithmetic», Bollettino della Unione Matematica Italiana, B (5), 16: 795–812.
  • –––, 1980a, «Interprétations de la théorie du premier ordre des algèbres diagonalisables en arithmétique peano», Studia Logica, 39: 347–354.
  • –––, 1980b, «Indécidabilité de la théorie du premier ordre des algèbres diagonalisables», Studia Logica, 39: 355–359.
  • –––, 1984, «La logique modale du prédicat de la prouvabilité», Notre Dame Journal of Formal Logic, 25 (2): 179–189.
  • –––, 1992, «Preuves polynomialement et superexponentiellement plus courtes dans des fragments d'arithmétique», Journal of Symbolic Logic, 57: 844–863.
  • Pakhomov, FN, 2012, «Indécidabilité de la théorie élémentaire du semi-treillis des mots GLP», Sbornik: Mathématiques, 203 (8): 1211.
  • Shapirovsky, I., 2008, «PSPACE-décidabilité de la logique polymodale de Japaridze», Advances in Modal Logic, 7: 289–304.
  • Shavrukov, V. Yu., 1993a, «Une note sur les algèbres diagonalisables de PA et ZF», Annals of Pure and Applied Logic, 61: 161–173.
  • –––, 1993b, «Sous-algèbres des algèbres diagonalisables des théories contenant de l'arithmétique», Dissertationes Mathematicae, 323.
  • –––, 1994, «Un enfant intelligent de Peano», Notre Dame Journal of Formal Logic, 35 (2): 161–185.
  • Troelstra, AS, 1973, Enquête métamathématique de l'arithmétique et de l'analyse intuitionnistes, Berlin: Springer-Verlag.
  • Visser, A., 1980, Aspects of Diagonalization and Provability, Ph. D. Thèse, Utrecht: Université d'Utrecht.
  • –––, 1982, «Sur le principe de complétude: une étude de la preuve dans l'arithmétique et les extensions de Heyting», Annals of Mathematical Logic, 22 (3): 263-295.
  • –––, 1989, «Les enfants intelligents de Peano: une étude logique de preuve de systèmes avec cohérence intégrée», Notre Dame Journal of Formal Logic, 30 (2): 161–196.
  • –––, 1999, «Rules and Arithmetics», Notre Dame Journal of Formal Logic, 40 (1): 116-140.
  • –––, 2002, «Substitutions of (Sigma_1) Sentences: Explorations between Intuitionistic Propositional Logic and Intuitionistic Arithmetic», Annals of Pure and Applied Logic, 114: 227-271.
  • –––, 2005, «Löb's Logic Meets the μ-Calculus», dans A. Middeldorp, V. van Oostrom, F. van Raamsdonk et R. de Vrijer (eds.), Processes, Terms and Cycles: Steps on the Road à Infinity, Berlin: Springer, pp. 14–25.
  • –––, 2008, «Fragments fermés de logique de prouvabilité des théories constructives», Journal of Symbolic Logic, 73: 1081–1096.
  • Zambella, D., 1994, «Théorème de Shavrukov sur les sous-algèbres des algèbres diagonalisables pour les théories contenant (I / Delta_0 + / exp),» Notre Dame Journal of Formal Logic, 35: 147-157.

Signification philosophique

  • Davis, M., 1990, «Is Mathematical Insight Algorithmic?», Commentaire sur Roger Penrose, New Mind, Behavioral and Brain Sciences de l'Empereur, 13: 659–660.
  • –––, 1993, «Quelle est la subtilité du théorème de Gödel?» (Commentaire sur Roger Penrose, Le nouvel esprit de l'empereur), Behavioral and Brain Sciences, 16: 611–612.
  • Egré, P., 2005, «Le paradoxe du connaisseur à la lumière des interprétations de la prouvabilité des logiques modales», Journal of Logic, Language, and Information, 14 (1): 13–48.
  • Kaplan, D. et R. Montague, 1960, «Un paradoxe retrouvé», Notre Dame Journal of Formal Logic, 1 (3): 79–90.
  • Montague, R., 1963, «Traitements syntaxiques de la modalité, avec des corollaires sur les principes de réflexion et l'axiomatisabilité finie», Acta Philosophica Fennica, 16: 153–67.
  • Quine, WV, 1966, «La vérité nécessaire», dans Quine, WV, The Ways of Paradox and Other Essays, New York: Random House, pp. 48–56.
  • –––, 1953, «Trois degrés d'implication modale», dans Actes du 11e Congrès international de philosophie, Amsterdam: Hollande du Nord, pp. 65-81; réimprimé dans WV Quine, The Ways of Paradox and Other Essays, New York: Random House, 1966, pp. 156–174.

Outils académiques

icône de l'homme Sep
icône de l'homme Sep
Comment citer cette entrée.
icône de l'homme Sep
icône de l'homme Sep
Prévisualisez la version PDF de cette entrée à la Friends of the SEP Society.
icône inpho
icône inpho
Recherchez cette rubrique d'entrée sur le projet d'ontologie de philosophie Internet (InPhO).
icône de papiers phil
icône de papiers phil
Bibliographie améliorée pour cette entrée chez PhilPapers, avec des liens vers sa base de données.

Autres ressources Internet

Articles et présentations

  • Fernández-Duque, D. et JJ Joosten, 2013, «L'interprétation des règles oméga de la logique de la provabilité transfinie», manuscrit en ligne sur arxiv.org.
  • Henk, P., and Pakhomov, F., 2016, «Slow and Ordinary Provability for Peano Arithmetic», manuscrit sur arxiv.org.
  • Pakhomov, F., 2014, «On Elementary Theories of GLP-algebras», manuscrit sur arxiv.org.
  • Pakhomov, F., 2015, «Sur les théories élémentaires des systèmes de notation ordinale basés sur les principes de réflexion», manuscrit sur arxiv.org.
  • Visser, Albert, On formelle provability versus human provability (en néerlandais), manuscrit en ligne, Université d'Utrecht.
  • Verbrugge, Rineke, diapositives de présentation sur la logique de la prouvabilité, diapositives, Université de Groningen

Autres sites

  • Problèmes ouverts dans Provability Logic, maintenu par Lev Beklemishev
  • Liste de diffusion Foundations of Mathematics, New York University

Recommandé: