Sémantique de Kripke - Kripke semantics

La sémantique de Kripke (également connue sous le nom de sémantique relationnelle ou sémantique de cadre , et souvent confondue avec la sémantique du monde possible ) est une sémantique formelle pour les systèmes logiques non classiques créée à la fin des années 1950 et au début des années 1960 par Saul Kripke et André Joyal . Il a d'abord été conçu pour les logiques modales , puis adapté à la logique intuitionniste et à d'autres systèmes non classiques. Le développement de la sémantique de Kripke a été une percée dans la théorie des logiques non classiques, car la théorie modèle de telles logiques était presque inexistante avant Kripke (la sémantique algébrique existait, mais était considérée comme une « syntaxe déguisée »).

Sémantique de la logique modale

Le langage de la logique modale propositionnelle se compose d'un ensemble infiniment dénombrable de variables propositionnelles , d'un ensemble de connecteurs fonctionnels de vérité (dans cet article et ) et de l'opérateur modal ("nécessairement"). L'opérateur modal (« éventuellement ») est (classiquement) le dual de et peut être défini en termes de nécessité comme ceci : (« éventuellement A » est défini comme équivalent à « pas nécessairement pas A »). ${\style d'affichage \to }$${\style d'affichage \neg }$${\displaystyle \Box }$${\displaystyle \Diamant }$${\displaystyle \Box }$${\displaystyle \Diamond A:=\neg \Box \neg A}$

Définitions basiques

Un cadre de Kripke ou un cadre modal est une paire , où W est un ensemble (éventuellement vide) et R est une relation binaire sur W . Les éléments de W sont appelés nœuds ou mondes , et R est appelé relation d'accessibilité . ${\displaystyle \langle W,R\rangle }$

Un modèle Kripke est un triple , où est une trame Kripke, et est une relation entre les noeuds de W et les formules modales, tel que pour tout w  ∈  W et formules modales A et B : ${\displaystyle \langle W,R,\Vdash \rangle }$${\displaystyle \langle W,R\rangle }$${\style d'affichage \Vdash }$

• ${\displaystyle w\Vdash \neg A}$si et seulement si ,${\style d'affichage avec\nVdash A}$
• ${\displaystyle w\Vdash A\to B}$si et seulement si ou ,${\style d'affichage avec\nVdash A}$${\style d'affichage avec\Vdash B}$
• ${\displaystyle w\Vdash \Box A}$si et seulement si pour tout ce que .${\displaystyle u\Vdash A}$${\displaystyle u}$${\style d'affichage w\;R\;u}$

Nous lisons comme " w satisfait A ", " A est satisfait dans w " ou " w force A ". La relation est appelée relation de satisfaction , d' évaluation ou relation de forçage . La relation de satisfaction est uniquement déterminée par sa valeur sur les variables propositionnelles. ${\displaystyle w\Vdash A}$${\style d'affichage \Vdash }$

Une formule A est valable dans :

• un modèle , si pour tout w  ∈  W ,${\displaystyle \langle W,R,\Vdash \rangle }$${\displaystyle w\Vdash A}$
• un cadre , s'il est valable dans pour tous les choix possibles de ,${\displaystyle \langle W,R\rangle }$${\displaystyle \langle W,R,\Vdash \rangle }$${\style d'affichage \Vdash }$
• une classe C de cadres ou de modèles, si elle est valable dans chaque membre de C .

Nous définissons Thm( C ) comme l'ensemble de toutes les formules valides en C . Inversement, si X est un ensemble de formules, soit Mod( X ) la classe de tous les cadres qui valident chaque formule de X .

Une logique modale (c'est-à-dire un ensemble de formules) L est valable par rapport à une classe de cadres C , si L  Thm( C ). L est complet par rapport à C si L  Thm( C ).

Correspondance et exhaustivité

La sémantique n'est utile pour étudier une logique (c'est-à-dire un système de dérivation ) que si la relation de conséquence sémantique reflète sa contrepartie syntaxique, la relation de conséquence syntaxique ( dérivabilité ). Il est vital de savoir quelles logiques modales sont solides et complètes par rapport à une classe de trames de Kripke, et de déterminer également de quelle classe il s'agit.

Pour toute classe C de cadres de Kripke, Thm( C ) est une logique modale normale (en particulier, les théorèmes de la logique modale normale minimale, K , sont valables dans tout modèle de Kripke). Cependant, l'inverse n'est pas vrai en général : alors que la plupart des systèmes modaux étudiés sont complets de classes de cadres décrits par des conditions simples, il existe des logiques modales normales incomplètes de Kripke. Un exemple naturel d'un tel système est la logique polymodale de Japaridze .

Une logique modale normale L correspond à une classe de trames C , si C  = Mod( L ). En d'autres termes, C est la plus grande classe de trames telle que L est le son par rapport à C . Il s'ensuit que L est Kripke complet si et seulement si il est complet de sa classe correspondante.

Considérons le schéma T  : . T est valable dans n'importe quel cadre réflexif : si , alors puisque w R w . D'autre part, un cadre qui valide T doit être réflexif : fixer w  ∈  W , et définir la satisfaction d'une variable propositionnelle p comme suit : si et seulement si w R u . Alors , donc par T , ce qui signifie w R w en utilisant la définition de . T correspond à la classe des cadres de Kripke réflexifs. ${\displaystyle \Box A\to A}$${\displaystyle \langle W,R\rangle }$${\displaystyle w\Vdash \Box A}$${\displaystyle w\Vdash A}$  ${\displaystyle u\Vdash p}$  ${\displaystyle w\Vdash \Box p}$${\displaystyle w\Vdash p}$  ${\style d'affichage \Vdash }$

Il est souvent beaucoup plus facile de caractériser la classe correspondante de L que de prouver sa complétude, ainsi la correspondance sert de guide pour les preuves de complétude. La correspondance est également utilisée pour montrer l' incomplétude des logiques modales : supposons que L ₁  ⊆  L ₂ soient des logiques modales normales qui correspondent à la même classe de trames, mais L ₁ ne prouve pas tous les théorèmes de L ₂ . Alors L ₁ est Kripke incomplet. Par exemple, le schéma génère une logique incomplète, car il correspond à la même classe de cadres que GL (c'est-à-dire les cadres transitifs et inverses bien fondés), mais ne prouve pas la GL -tautologie . ${\displaystyle \Box (A\leftrightarrow \Box A)\to \Box A}$${\displaystyle \Box A\to \Box \Box A}$

Schémas d'axiome modaux communs

Le tableau suivant répertorie les axiomes modaux courants ainsi que leurs classes correspondantes. La dénomination des axiomes varie souvent.

Nom	Axiome	État du cadre
K	${\displaystyle \Box (A\to B)\to (\Box A\to \Box B)}$	N / A
T	${\displaystyle \Box A\to A}$	réflexif :${\style d'affichage w\,R\,w}$
4	${\displaystyle \Box A\to \Box \Box A}$	transitif :${\style d'affichage w\,R\,v\coin v\,R\,u\Flèche droite w\,R\,u}$
	${\displaystyle \Box \Box A\to \Box A}$	dense :${\displaystyle w\,R\,u\Rightarrow \exists v\,(w\,R\,v\land v\,R\,u)}$
ré	${\displaystyle \Box A\to \Diamond A}$ ou ${\displaystyle \Diamond \top }$	série :${\displaystyle \forall w\,\existe v\,(w\,R\,v)}$
B	${\displaystyle A\to \Box \Diamond A}$	symétrique  : ${\style d'affichage w\,R\,v\Flèche droite v\,R\,w}$
5	${\displaystyle \Diamond A\to \Box \Diamond A}$	Euclidien :${\style d'affichage w\,R\,u\land w\,R\,v\Flèche droite u\,R\,v}$
GL	${\displaystyle \Box (\Box A\to A)\to \Box A}$	R transitif, R −1 bien fondé
Grz	${\displaystyle \Box (\Box (A\à \Box A)\à A)\à A}$	R réflexif et transitif, R −1 − Id bien fondé
H	${\displaystyle \Box (\Box A\to B)\lor \Box (\Box B\to A)}$	${\displaystyle w\,R\,u\land w\,R\,v\Rightarrow u\,R\,v\lor v\,R\,u}$
M	${\displaystyle \Box \Diamond A\to \Diamond \Box A}$	(une propriété compliquée du second ordre )
g	${\displaystyle \Diamond \Boîte A\à \Boîte \Diamond A}$	convergent: ${\displaystyle w\,R\,u\land w\,R\,v\Rightarrow \exists x\,(u\,R\,x\land v\,R\,x)}$
	${\style d'affichage A\à \Boîte A}$	discret: ${\style d'affichage w\,R\,v\Flèche droite w=v}$
	${\displaystyle \Diamond A\to \Box A}$	fonction partielle : ${\displaystyle w\,R\,u\land w\,R\,v\Rightarrow u=v}$
	${\displaystyle \Diamond A\leftrightarrow \Box A}$	fonction: ${\displaystyle \forall w\,\existe !u\,w\,R\,u}$
	${\style d'affichage \Boîte A}$ ou ${\displaystyle \Box \bot }$	vide: ${\displaystyle \forall w\,\forall u\,\neg (w\,R\,u)}$

Systèmes modaux communs

Le tableau suivant répertorie plusieurs systèmes modaux normaux courants. Les conditions de trame pour certains systèmes ont été simplifiées : les logiques sont complètes en ce qui concerne les classes de trames données dans le tableau, mais elles peuvent correspondre à une classe de trames plus large.

Nom	Axiomes	État du cadre
K	-	tous les cadres
T	T	réfléchi
K4	4	transitif
S4	T, 4	Pré-commander
S5	T, 5 ou D, B, 4	relation d'équivalence
S4.3	T, 4, H	précommande totale
S4.1	T, 4, M	Pré-commander, ${\displaystyle \forall w\,\existe u\,(w\,R\,u\land \forall v\,(u\,R\,v\Rightarrow u=v))}$
S4.2	T, 4, G	précommande dirigée
GL , K4W	GL ou 4, GL	ordre partiel strict fini
Grz, S4Grz	Grz ou T, 4, Grz	ordre partiel fini
ré	ré	en série
J45	D, 4, 5	transitif, sériel et euclidien

Modèles canoniques

Pour toute logique modale normale, L , un modèle de Kripke (appelé modèle canonique ) peut être construit qui réfute précisément les non-théorèmes de L , par une adaptation de la technique standard consistant à utiliser des ensembles cohérents maximaux comme modèles. Les modèles canoniques de Kripke jouent un rôle similaire à la construction algébrique de Lindenbaum-Tarski en sémantique algébrique.

Un ensemble de formules est L - cohérent si aucune contradiction ne peut en être déduite en utilisant les théorèmes de L , et Modus Ponens. Un ensemble L-cohérent maximal (un L - MCS en abrégé) est un ensemble L -cohérent qui n'a pas de sur-ensemble L -cohérent propre .

Le modèle canonique de L est un modèle de Kripke , où W est l'ensemble de tous les L - MCS , et les relations R et sont les suivantes : ${\displaystyle \langle W,R,\Vdash \rangle }$${\style d'affichage \Vdash }$

${\style d'affichage X\;R\;Y}$si et seulement si pour chaque formule , si alors ,${\style d'affichage A}$${\displaystyle \Box A\in X}$${\style d'affichage A\dans Y}$

${\displaystyle X\Vdash A}$si et seulement si .${\style d'affichage A\dans X}$

Le modèle canonique est un modèle de L , comme chaque L - MCS contient tous les théorèmes de L . D'après le lemme de Zorn , chaque ensemble L -cohérent est contenu dans un L - MCS , en particulier chaque formule non démontrable dans L a un contre-exemple dans le modèle canonique.

La principale application des modèles canoniques sont les preuves d'exhaustivité. Les propriétés du modèle canonique de K impliquent immédiatement la complétude de K par rapport à la classe de toutes les trames de Kripke. Cet argument ne fonctionne pas pour L arbitraire , car il n'y a aucune garantie que le cadre sous-jacent du modèle canonique satisfasse les conditions de cadre de L .

On dit qu'une formule ou un ensemble X de formules est canonique par rapport à une propriété P des cadres de Kripke, si

• X est valide dans chaque trame qui satisfait P ,
• pour toute logique modale normale L qui contient X , le cadre sous-jacent du modèle canonique de L satisfait P .

Une union d'ensembles canoniques de formules est elle-même canonique. Il résulte de la discussion précédente que toute logique axiomatisée par un ensemble canonique de formules est Kripke complète et compacte .

Les axiomes T, 4, D, B, 5, H, G (et donc toute combinaison d'entre eux) sont canoniques. GL et Grz ne sont pas canoniques, car ils ne sont pas compacts. L'axiome M en lui-même n'est pas canonique (Goldblatt, 1991), mais la logique combinée S4.1 (en fait, même K4.1 ) est canonique.

En général, il est indécidable si un axiome donné est canonique. Nous connaissons une belle condition suffisante : Henrik Sahlqvist a identifié une large classe de formules (maintenant appelées formules de Sahlqvist ) telles que

• une formule de Sahlqvist est canonique,
• la classe de cadres correspondant à une formule de Sahlqvist est définissable au premier ordre ,
• il existe un algorithme qui calcule la condition de trame correspondante à une formule de Sahlqvist donnée.

C'est un critère puissant : par exemple, tous les axiomes répertoriés ci-dessus comme canoniques sont (équivalents à) des formules de Sahlqvist.

Propriété de modèle fini

Une logique a la propriété de modèle fini (FMP) si elle est complète par rapport à une classe de cadres finis. Une application de cette notion est la question de décidabilité : il résulte du théorème de Post qu'une logique modale axiomatisée récursivement L qui a FMP est décidable, à condition qu'il soit décidable si un cadre fini donné est un modèle de L . En particulier, toute logique finiment axiomatisable avec FMP est décidable.

Il existe différentes méthodes pour établir le FMP pour une logique donnée. Les raffinements et les extensions de la construction du modèle canonique fonctionnent souvent, à l'aide d'outils tels que la filtration ou l' effilochage . Comme autre possibilité, les preuves de complétude basées sur des calculs séquentiels sans coupure produisent généralement directement des modèles finis.

La plupart des systèmes modaux utilisés dans la pratique (y compris tous ceux énumérés ci-dessus) ont un FMP.

Dans certains cas, nous pouvons utiliser FMP pour prouver l' exhaustivité Kripke d'une logique: toute logique modale normale est complète par rapport à une classe de algèbres modales , et finie l' algèbre modale peut être transformé en un cadre Kripke. A titre d'exemple, Robert Bull a prouvé en utilisant cette méthode que chaque extension normale de S4.3 a FMP, et est Kripke complet.

Logiques multimodales

La sémantique de Kripke a une généralisation directe aux logiques avec plus d'une modalité. Un cadre de Kripke pour un langage avec comme ensemble de ses opérateurs de nécessité est constitué d'un ensemble non vide W muni de relations binaires R _i pour chaque i  ∈  I . La définition d'une relation de satisfaction est modifiée comme suit : ${\displaystyle \{\Box _{i}\mid \,i\in I\}}$

${\displaystyle w\Vdash \Box _{i}A}$ si et seulement si ${\displaystyle \forall u\,(w\;R_{i}\;u\Rightarrow u\Vdash A).}$

Une sémantique simplifiée, découverte par Tim Carlson, est souvent utilisée pour les logiques de provabilité polymodale . Un modèle Carlson est une structure d'une seule relation d'accessibilité R , et des sous - ensembles D _i  ⊆  W pour chaque modalité. La satisfaction est définie comme ${\displaystyle \langle W,R,\{D_{i}\}_{i\in I},\Vdash \rangle }$

${\displaystyle w\Vdash \Box _{i}A}$ si et seulement si ${\displaystyle \forall u\in D_{i}\,(w\;R\;u\Rightarrow u\Vdash A).}$

Les modèles Carlson sont plus faciles à visualiser et à utiliser que les modèles Kripke polymodaux habituels ; il existe cependant des logiques polymodales complètes de Kripke qui sont Carlson incomplètes.

Sémantique de la logique intuitionniste

La sémantique de Kripke pour la logique intuitionniste suit les mêmes principes que la sémantique de la logique modale, mais elle utilise une définition différente de la satisfaction.

Un modèle de Kripke intuitionniste est un triple , où est un référentiel de Kripke pré - ordonné , et satisfait les conditions suivantes : ${\displaystyle \langle W,\leq ,\Vdash \rangle }$${\displaystyle \langle W,\leq \rangle }$${\style d'affichage \Vdash }$

• si p est une variable propositionnelle, , et , alors ( condition de persistance (cf. monotonie )),${\displaystyle w\leq u}$${\displaystyle w\Vdash p}$${\displaystyle u\Vdash p}$
• ${\displaystyle w\Vdash A\land B}$si et seulement si et ,${\displaystyle w\Vdash A}$${\style d'affichage avec\Vdash B}$
• ${\displaystyle w\Vdash A\lor B}$si et seulement si ou ,${\displaystyle w\Vdash A}$${\style d'affichage avec\Vdash B}$
• ${\displaystyle w\Vdash A\to B}$si et seulement si pour tout , implique ,${\style d'affichage u\geq w}$${\displaystyle u\Vdash A}$${\displaystyle u\Vdash B}$
• non .${\displaystyle w\Vdash \bot }$

La négation de A , A , pourrait être définie comme une abréviation de A → ⊥. Si pour tout u tel que w ≤ u , pas u ⊩ A , puis w ⊩ A → ⊥ est vacuously vrai , alors w ⊩ ¬ A .

La logique intuitionniste est saine et complète en ce qui concerne sa sémantique de Kripke, et elle a la propriété de modèle fini .

Logique du premier ordre intuitionniste

Soit L un langage du premier ordre . Un modèle de Kripke L est un triple , où est une trame Kripke intuitionistic, M _w est un (classique) L -structure pour chaque noeud w  ∈  W , et les conditions de compatibilité suivantes sont vérifiées chaque fois que u  ≤  v : ${\displaystyle \langle W,\leq ,\{M_{w}\}_{w\in W}\rangle }$${\displaystyle \langle W,\leq \rangle }$

• le domaine de M _u est inclus dans le domaine de M _v ,
• les réalisations des symboles de fonction dans M _u et M _v s'accordent sur les éléments de M _u ,
• pour chaque n -aire prédicat P et les éléments d' un ₁ , ..., a _n  ∈  M _u : si P ( a ₁ , ..., a _n ) tient en M _u , il en va de M _v .

Etant donné une évaluation e des variables par des éléments de M _w , on définit la relation de satisfaction : ${\displaystyle w\Vdash A[e]}$

• ${\displaystyle w\Vdash P(t_{1},\dots ,t_{n})[e]}$si et seulement si est vérifié dans M _w ,${\displaystyle P(t_{1}[e],\dots ,t_{n}[e])}$
• ${\displaystyle w\Vdash (A\land B)[e]}$si et seulement si et ,${\displaystyle w\Vdash A[e]}$${\displaystyle w\Vdash B[e]}$
• ${\displaystyle w\Vdash (A\lor B)[e]}$si et seulement si ou ,${\displaystyle w\Vdash A[e]}$${\displaystyle w\Vdash B[e]}$
• ${\displaystyle w\Vdash (A\à B)[e]}$si et seulement si pour tout , implique ,${\style d'affichage u\geq w}$${\displaystyle u\Vdash A[e]}$${\displaystyle u\Vdash B[e]}$
• non ,${\displaystyle w\Vdash \bot [e]}$
• ${\displaystyle w\Vdash (\exists x\,A)[e]}$si et seulement s'il existe un tel que ,${\displaystyle a\in M_{w}}$${\displaystyle w\Vdash A[e(x\to a)]}$
• ${\displaystyle w\Vdash (\forall x\,A)[e]}$si et seulement si pour chaque , .${\style d'affichage u\geq w}$${\displaystyle a\in M_{u}}$${\displaystyle u\Vdash A[e(x\to a)]}$

Ici e ( x → a ) est l' évaluation qui donne à x la valeur a , et sinon s'accorde avec e .

Voir une formalisation légèrement différente dans.

Sémantique Kripke–Joyal

Dans le cadre du développement indépendant de la théorie des faisceaux , on s'est rendu compte vers 1965 que la sémantique de Kripke était intimement liée au traitement de la quantification existentielle dans la théorie des topos . C'est-à-dire que l'aspect « local » de l'existence pour les sections d'une gerbe était une sorte de logique du « possible ». Bien que ce développement ait été l'œuvre d'un certain nombre de personnes, le nom de sémantique Kripke-Joyal est souvent utilisé à cet égard.

Constructions modèles

Comme dans la théorie des modèles classique , il existe des méthodes pour construire un nouveau modèle de Kripke à partir d'autres modèles.

Les homomorphismes naturels dans la sémantique de Kripke sont appelés p-morphismes (qui est l'abréviation de pseudo-épimorphisme , mais ce dernier terme est rarement utilisé). Un p-morphisme de cadres de Kripke et est une application telle que ${\displaystyle \langle W,R\rangle }$${\displaystyle \langle W',R'\rangle }$${\displaystyle f\colon W\à W'}$

• f préserve la relation d'accessibilité, c'est-à-dire que u R v implique f ( u )  R'  f ( v ),
• chaque fois que f ( u )  R'  v ', il existe un v  ∈  W tel que u R v et f ( v ) =  v '.

Un p-morphisme des modèles de Kripke et est un p-morphisme de leurs cadres sous-jacents , qui satisfait ${\displaystyle \langle W,R,\Vdash \rangle }$${\displaystyle \langle W',R',\Vdash '\rangle }$${\displaystyle f\colon W\à W'}$

${\displaystyle w\Vdash p}$si et seulement si , pour toute variable propositionnelle p .${\displaystyle f(w)\Vdash 'p}$

Les P-morphismes sont un type particulier de bisimulations . En général, une bisimulation entre trames et est une relation B W × W' , qui satisfait la propriété de « zig-zag » suivante : ${\displaystyle \langle W,R\rangle }$${\displaystyle \langle W',R'\rangle }$

• si u B u' et u R v , il existe v'  ∈  W' tel que v B v' et u' R' v' ,
• si u B u ' et u' R 'v' , il existe v  ∈  W tel que v B v » et u R v .

Une bisimulation des modèles est en outre requise pour conserver le forçage des formules atomiques :

si w B w' , alors si et seulement si , pour toute variable propositionnelle p .${\displaystyle w\Vdash p}$${\displaystyle w'\Vdash 'p}$

La propriété clé qui découle de cette définition est que les bisimulations (donc aussi les p-morphismes) de modèles préservent la satisfaction de toutes les formules, pas seulement des variables propositionnelles.

Nous pouvons transformer un modèle de Kripke en arbre en utilisant unraveling . Etant donné un modèle et un noeud fixe w ₀  ∈  W , on définit un modèle , où W » est l'ensemble de toutes les séquences finies de telle sorte que w _i  r w _{i + 1} pour tout i  <  n , et si et seulement si pour une propositionnelle variable p . La définition de la relation d'accessibilité R' varie ; dans le cas le plus simple on pose ${\displaystyle \langle W,R,\Vdash \rangle }$${\displaystyle \langle W',R',\Vdash '\rangle }$${\displaystyle s=\langle w_{0},w_{1},\dots ,w_{n}\rangle }$${\displaystyle s\Vdash p}$${\displaystyle w_{n}\Vdash p}$

${\displaystyle \langle w_{0},w_{1},\dots ,w_{n}\rangle \;R'\;\langle w_{0},w_{1},\dots ,w_{n}, w_{n+1}\rangle }$,

mais de nombreuses applications nécessitent la fermeture réflexive et/ou transitive de cette relation, ou des modifications similaires.

La filtration est une construction utile qui utilise pour prouver FMP pour de nombreuses logiques. Soit X un ensemble de formules fermées par prise de sous-formules. Une X -filtration d'un modèle est une application f de W à un modèle tel que ${\displaystyle \langle W,R,\Vdash \rangle }$${\displaystyle \langle W',R',\Vdash '\rangle }$

• f est une surjection ,
• f préserve la relation d'accessibilité, et (dans les deux sens) Satisfaction de variables p  ∈  X ,
• si f ( u )  R'  f ( v ) et , où , alors .${\displaystyle u\Vdash \Box A}$${\displaystyle \Box A\in X}$${\displaystyle v\Vdash A}$

Il s'ensuit que f préserve la satisfaction de toutes les formules de X . Dans des applications typiques, nous prenons f comme la projection sur le quotient de W sur la relation

u ≡ _X  v si et seulement si pour tout A  ∈  X , si et seulement si .${\displaystyle u\Vdash A}$${\displaystyle v\Vdash A}$

Comme dans le cas de l'effilochage, la définition de la relation d'accessibilité sur le quotient varie.

Sémantique générale des cadres

Le principal défaut de la sémantique de Kripke est l'existence de logiques incomplètes de Kripke, et de logiques complètes mais non compactes. On peut y remédier en équipant les cadres de Kripke d'une structure supplémentaire qui restreint l'ensemble des évaluations possibles, en utilisant des idées de la sémantique algébrique. Cela donne lieu à la sémantique générale du cadre .

Applications en informatique

Blackburn et al. (2001) soulignent que parce qu'une structure relationnelle est simplement un ensemble avec une collection de relations sur cet ensemble, il n'est pas surprenant que des structures relationnelles se retrouvent un peu partout. A titre d'exemple de l'informatique théorique , ils donnent des systèmes de transition étiquetés , qui modélisent l'exécution du programme . Blackburn et al. prétendent donc à cause de cette connexion que les langages modaux sont idéalement adaptés pour fournir « une perspective interne et locale sur les structures relationnelles ». (p. xii)

Histoire et terminologie

Des travaux similaires antérieurs aux percées sémantiques révolutionnaires de Kripke :

• Rudolf Carnap semble avoir été le premier à avoir l'idée qu'on peut donner une sémantique du monde possible pour les modalités de nécessité et de possibilité en donnant à la fonction d'évaluation un paramètre qui s'étend sur les mondes possibles leibniziens. Bayart développe davantage cette idée, mais ni l'un ni l'autre n'a donné de définitions récursives de la satisfaction dans le style introduit par Tarski ;
• JCC McKinsey et Alfred Tarski ont développé une approche de modélisation des logiques modales qui est toujours influente dans la recherche moderne, à savoir l'approche algébrique, dans laquelle les algèbres booléennes avec opérateurs sont utilisées comme modèles. Bjarni Jónsson et Tarski ont établi la représentabilité des algèbres booléennes avec des opérateurs en termes de référentiels. Si les deux idées avaient été mises ensemble, le résultat aurait été précisément des modèles de cadre, c'est-à-dire des modèles de Kripke, des années avant Kripke. Mais personne (pas même Tarski) n'a vu le lien à l'époque.
• Arthur Prior , en s'appuyant sur les travaux inédits de CA Meredith , a développé une traduction de la logique modale propositionnelle en logique des prédicats classique qui, s'il l'avait combinée avec la théorie des modèles habituelle pour cette dernière, aurait produit une théorie des modèles équivalente aux modèles de Kripke pour le ancien. Mais son approche était résolument syntaxique et anti-modèle-théorique.
• Stig Kanger a donné une approche un peu plus complexe de l'interprétation de la logique modale, mais qui contient bon nombre des idées clés de l'approche de Kripke. Il a d'abord noté la relation entre les conditions sur les relations d'accessibilité et les axiomes de style Lewis pour la logique modale. Kanger n'a cependant pas réussi à prouver l'intégralité de son système ;
• Jaakko Hintikka a donné dans ses articles une sémantique introduisant la logique épistémique qui est une simple variation de la sémantique de Kripke, équivalente à la caractérisation des évaluations au moyen d'ensembles cohérents maximaux. Il ne donne pas de règles d'inférence pour la logique épistémique, et ne peut donc pas donner une preuve d'exhaustivité ;
• Richard Montague avait de nombreuses idées clés contenues dans le travail de Kripke, mais il ne les considérait pas comme significatives, car il n'avait aucune preuve d'exhaustivité, et donc n'a publié qu'après que les articles de Kripke aient fait sensation dans la communauté logique ;
• Evert Willem Beth a présenté une sémantique de la logique intuitionniste basée sur les arbres, qui ressemble étroitement à la sémantique de Kripke, sauf pour utiliser une définition plus lourde de la satisfaction.

Voir également

• Topologie d'Alexandrov
• Logique modale normale
• Le bidimensionnel
• Puzzle enfants boueux

Remarques

a ^ Après Andrzej Grzegorczyk .

Les références

• Blackburn, P.; de Rijke, M. ; Venema, Yde (2002). Logique modale . La presse de l'Universite de Cambridge. ISBN 978-1-316-10195-7.
• Bull, Robert A.; Segerberg, K. (2012) [1984]. "Logique modale de base" . À Gabbay, DM ; Guenthner, F. (éd.). Extensions de la logique classique . Manuel de logique philosophique. 2 . Springer. p. 1–88. ISBN 978-94-009-6259-0.
• Chagrov, A.; Zakharyaschev, M. (1997). Logique modale . Presse Clarendon. ISBN 978-0-19-853779-3.
• Dummett, Michael AE (2000). Éléments d'intuitionnisme (2e éd.). Presse Clarendon. ISBN 978-0-19-850524-2.
• Montage, Melvin (1969). Logique intuitionniste, théorie des modèles et forçage . Hollande du Nord. ISBN 978-0-444-53418-7.
• Goldblatt, Robert (2006). « Logique modale mathématique : une vue de son évolution » (PDF) . Dans Gabbay, Dov M. ; Woods, John (éd.). Logique et modalités au vingtième siècle (PDF) . Manuel d'histoire de la logique. 7 . Elsevier. p. 1–98. ISBN 978-0-08-046303-2.
• Cresswell, MJ ; Hughes, GE (2012) [1996]. Une nouvelle introduction à la logique modale . Routledge. ISBN 978-1-134-80028-5.
• Mac Lane, Saunders ; Moerdijk, Ieke (2012) [1991]. Les faisceaux en géométrie et logique : une première introduction à la théorie des topos . Springer. ISBN 978-1-4612-0927-0.
• van Dalen, Dirk (2013) [1986]. "Logique intuitionniste" . Dans Gabbay, Dov M. ; Guenthner, Franz (dir.). Alternatives à la logique classique . Manuel de logique philosophique. 3 . Springer. p. 225-339. ISBN 978-94-009-5203-4.

Liens externes

• Garson, James. "Logique modale" . L'Encyclopédie de philosophie de Stanford .
• Moschovakis, Jeanne (2018). "Logique intuitionniste" . Encyclopédie de philosophie de Stanford . Laboratoire de recherche en métaphysique, Université de Stanford.
• Detlovs, V. ; Podnieks, K. "4.4 Logique propositionnelle constructive — Sémantique de Kripke" . Introduction à la logique mathématique . Université de Lettonie. NB : Constructif = intuitionniste.
• Burgess, John P. "Modèles Kripke" . Archivé de l'original le 2004-10-20.
• "Modèles de Kripke" , Encyclopédie des mathématiques , EMS Press , 2001 [1994]