Toegankelijkheidsrelatie

In de filosofie en logica is een toegankelijkheidsrelatie of bereikbaarheidsrelatie een tweeplaatsige relatie tussen mogelijke werelden. De relatie duidt aan welke werelden toegankelijk zijn vanuit een bepaalde wereld en de verzameling werelden die toegankelijk is kan per wereld verschillen. Toegankelijkheidsrelaties worden gebruikt in modale logica, en logica's die daarop gebaseerd zijn.

Modale logica

In de modale logica is de toegankelijkheidsrelatie een onderdeel van een Kripkemodellen waarmee de semantiek van modale logica uitgedrukt kan worden. Een Kripkemodel ${\mathcal {M}}$ is een tupel $\langle W,R,V\rangle$ waarbij $W$ een verzameling werelden is, $R$ de toegankelijkheidsrelatie, een tweeplaatsige relatie tussen werelden, en $V$ een functie die aan een atomaire formule $p$ een verzameling werelden toekent waarin $p$ waar is. De verzameling $W$ en de toegankelijkheidsrelatie $R$ worden samen ook het 'frame' genoemd.

Om een modale logica te verkrijgen kan men propositielogica uitbreiden met twee operatoren, $\Box$ en $\Diamond$, om modaliteiten uit te drukken. Hierbij kan $\Box$ staan voor "Het is noodzakelijk dat ..." en $\Diamond$ voor "Het is mogelijk dat ...". Er geldt: $\Box \equiv \neg \Diamond \neg$. In deze modale logica bestaan logische formules uit propositionele formules waarin ook deze modale operatoren kunnen voorkomen. Voorbeelden van formules zijn $\Box p$, $\Box \Diamond q$ en $\Diamond \Diamond (p\rightarrow \Box q)$.

De semantiek van een formule in deze modale logica kan worden geïnterpreteerd met behulp van Kripkemodellen. Een formule kan gelden in een wereld van het model: als bijvoorbeeld de atomaire formules $p$ en $q$ gelden in een wereld $w$, formeel genoteerd als: ${\mathcal {M}},w\models p$ en ${\mathcal {M}},w\models q$, dan geldt ook $p\wedge q$, een propositionele formule, in die wereld $w$, ${\mathcal {M}},w\models p\wedge q$.

Als een formule modale operatoren bevat dan wordt de toegankelijkheidsrelatie gebruikt om een formule te interpreteren: een formule met de vorm $\Box \phi$ geldt in een wereld $w$ als in alle werelden die toegankelijk zijn vanuit $w$ de formule $\phi$ geldt. Een formule met de vorm $\Diamond \phi$ geldt als er ten minste een wereld is die toegankelijk is vanuit w waarin $\phi$ geldt. Formeel genoteerd:

${\mathcal {M}},w\models \Box \phi \Leftrightarrow \forall w'(w,w')\in R\rightarrow {\mathcal {M}},w'\models \phi$

${\mathcal {M}},w\models \Diamond \phi \Leftrightarrow \exists w'(w,w')\in R\wedge {\mathcal {M}},w'\models \phi$

Uit deze definities volgt dat een $\Box$-formule ook waar is als er geen $(w,w')\in R$ zijn voor een bepaalde wereld $w$ terwijl een $\Diamond$-formule alleen waar is als er ten minste een $(w,w')\in R$ is voor wereld $w$.

Kenmerken van een frame

Het is mogelijk om beperkingen op te leggen aan wat wel en niet een geldige toegankelijkheidsrelatie is. Zo kan men modellen beschouwen waarin elke wereld ook toegankelijk is vanuit zichzelf: de toegankelijkheidsrelatie $R$ is dan een reflexieve relatie aangezien er voor elke wereld $w$ een element $(w,w)\in R$ bestaat.

Enkele bekende kenmerken van een frame (de verzameling $W$ en de toegankelijkheidsrelatie $R$) zijn:

• $\forall w\in W\quad (w,w)\in R$ (reflexiviteit)
• $\forall w,v,u\in W\quad (w,v)\in R$ en $(v,u)\in R\Rightarrow (w,u)\in R$ (transitiviteit)
• $\forall w,v\in W\quad (w,v)\in R\Rightarrow (v,w)\in R$ (symmetrie)
• $\forall w,v,u\in W\quad (w,v)\in R$ en $(w,u)\in R\Rightarrow (v,u)\in R$ (euclidiciteit)
• $\forall w\in W\ \exists v\in W\ (w,v)\in R$ (serialiteit)

Door de toegankelijkheidsrelatie van een frame te beperken zijn er formules die waar zijn voor elke wereld in een model met dat frame. In een model met een reflexieve toegankelijkheidsrelatie geldt bijvoorbeeld de formule $\Box \phi \rightarrow \phi$ in elke wereld. In een propositionele modale logica waarbij er geen beperkingen op de toegankelijkheidsrelatie worden gelegd, zijn alle propositionele tautologieën en het K-axioma - $\Box (\phi \rightarrow \psi )\rightarrow (\Box \phi \rightarrow \Box \psi )$ - waar voor alle werelden in een model. In een model met beperkingen op de toegankelijkheidsrelatie zijn meer formules waar: het modale systeem wordt dus uitgebreid met meer axioma's die gelden.

Voor elk van de bovenstaande eigenschappen bestaat een axioma die geldt op frames met die eigenschap. Hieronder staan de axioma's die gelden op frames met bepaalde kenmerken:

• reflexiviteit: $\Box \phi \rightarrow \phi$ (ook bekend als het M-axioma)
• transitiviteit: $\Box \phi \rightarrow \Box \Box \phi$ (4-axioma)
• symmetrie: $\phi \rightarrow \Box \Diamond \phi$ (B-axioma)
• euclidiciteit: $\Diamond \phi \rightarrow \Box \Diamond \phi$ (5-axioma)
• serialiteit: $\Box \phi \rightarrow \Diamond \phi$ (D-axioma)

Men kan bewijzen dat voor elk frame met de eigenschap het bijbehorende axioma geldt en andersom. Deze overeenkomsten tussen axioma's die gelden in een modaal systeem en de eigenschappen van een frame wordt correspondentie genoemd.

Axiomatische systemen

De bovenstaande axioma's kunnen gebruikt worden om een logisch systeem samen te stellen dat alle modale formules op bepaalde frames kan afleiden. Zo is het mogelijk om met het volgende systeem alle formules af te leiden die geldig zijn op elk frame:

Alle propositionele tautologieën

Het K-axioma: $\Box (\phi \rightarrow \psi )\rightarrow (\Box \phi \rightarrow \Box \psi )$

De necessesitatie-regel: als $\phi$ dan $\Box \phi$

Modus ponens: als $\phi$ en $\phi \rightarrow \psi$ dan $\psi$.

Een modale formule wordt afgeleid door axioma's te introduceren en door afleidingsregels toe te passen hierop en eventueel de resultaten daarvan. Door axioma's toe te voegen aan het systeem wordt het systeem stricter gemaakt en gelden sommige afgeleide formules alleen nog op bepaalde typen frames. Door bijvoorbeeld aan het bovenstaande systeem het axioma $\Box \phi \rightarrow \phi$ toe te voegen, krijgt men een systeem dat formules kan afleiden die gelden op reflexieve frames.

Een voorbeeld van een afleiding: de formule $\Box p\rightarrow \Box p$ geldt op alle frames wat als volgt aangetoond kan worden:

1.	$p\rightarrow p$	axioma
2.	$\Box (p\rightarrow p)$	necessitatie, 1
3.	$\Box (p\rightarrow p)\rightarrow (\Box p\rightarrow \Box p)$	K-axioma
4.	$\Box p\rightarrow \Box p$	modus ponens, 2, 3

Websites

• (en) Stanford Encyclopedia of Philosophy. Modal Logic, 8 september 2018.

Voetnoten