modalna logika

Topološka semantika modalne logike

Bojan Pažek, Tin Perkov

Sažetak
Modalna logika prvenstveno je formalizacija relacijskih struktura, što se može reći i za logiku prvog reda, ali nasuprot njoj ima jednostavniju sintaksu koja omogućuje odlučivost, te specifični lokalni pogled iznutra na relacijske strukture. U ovom radu1 predstavit ćemo alternativnu, topološku semantiku modalne logike. Formule modalnog jezika interpretirat ćemo kao topološke objekte, razmotriti adekvatnost i potpunost modalne logike u odnosu na odgovarajuće topološke prostore, kao i njenu izražajnu snagu, odnosno razmotriti koja svojstva topoloških prostora možemo definirati modalnim formulama.

1Uvod

Navest ćemo tri slogana iz predgovora knjige [1] koji odlično opisuju ulogu modalne logike:

(1) Modalni jezici su jednostavni, ali izražajni jezici za opis relacijskih struktura.
(2) Modalni jezici omogućuju interni, lokalni pogled na relacijske strukture.
(3) Modalni jezici nisu izolirani formalni sistemi.


Standardni uvod u modalnu logiku stoga mora opisati njen jezik, interpretaciju u relacijskim strukturama i vezu s drugim formalizmima, prije svega s logikom prvog reda. No, slogani su primjenjivi i na alternativni pogled na modalnu logiku, jer lokalna perspektiva iz drugog slogana asocira na topološke pojmove, dok nas treći slogan upućuje da alternativnu semantiku ne moramo graditi od nule, već je možemo povezati s već uspostavljenom relacijskom semantikom.

Topološka semantika modalne logike nije jednoznačna. Jedan pristup, pogodan za logiku dokazivosti, već je opisan u članku [3]. U tom članku su prezentirani i osnovni pojmovi modalne logike, pa ćemo ih ovdje samo ukratko ponoviti.

Jezik modalne logike proširuje jezik logike sudova modalnim operatorima. Ako je potrebno, kao podsjetnik na osnovne pojmove logike sudova može poslužiti npr. udžbenik [6]. Mi ćemo promatrati samo osnovni modalni jezik, koji u alfabetu uz propozicionalne varijable i logičke veznike ima modalni operator \Box, uz dodatno pravilo izgrađivanja formula: ako je \varphi formula, onda je i \Box \varphi formula. Koristit ćemo i dualni modalni operator \Diamond, no nećemo smatrati da je u alfabetu, nego \Diamond \varphi definiramo kao pokratu za \neg\Box\neg \varphi.

Okvir za osnovni modalni jezik je relacijska struktura (W,R), gdje je W\neq\emptyset skup koji zovemo nosač, a R binarna relacija na W koju zovemo relacija dostiživosti. Elementi nosača obično se zovu svjetovi, no u topološkoj interpretaciji prirodnije ih je zvati točke.

Model je uređena trojka (W,R,V), gdje je (W,R) okvir, a V valuacija, funkcija koja svakoj propozicionalnoj varijabli p pridružuje podskup nosača V(p). Kažemo da je propozicionalna varijabla p istinita u svijetu w\in W i pišemo w\Vdash p ako je w\in V(p). Definicija istinitosti se na prirodan način proširuje na formule nastale primjenom logičkih veznika, a posebno ćemo navesti samo dio definicije koji se odnosi na formule nastale primjenom modalnog operatora: w\Vdash\Box \varphi ako za svaki v\in W takav da je wRv vrijedi v\Vdash \varphi. Lako se vidi da vrijedi w\Vdash\Diamond \varphi ako i samo ako postoji v\in W takav da je wRv i v\Vdash \varphi.

U topološkoj semantici ulogu okvira igrat će topološki prostor (W,\mathcal{T}), a valuacija se definira kao i kod relacijske semantike. Razlika je u definiciji istinitosti formule oblika \Box \varphi, koja će biti istinita u w ako postoji otvoreni skup U koji sadrži w takav da je \varphi istinita u svakoj točki skupa U. Drugim riječima, w je u interioru skupa točaka u kojima je istinita formula \varphi. Lako se vidi da je w\Vdash\Diamond \varphi ako i samo ako je w u zatvaraču tog skupa.

Kažemo da je formula valjana na okviru (W,R), odnosno (W,\mathcal{T}), ako je istinita u svakom svijetu za svaku valuaciju na tom okviru.

Nije teško dokazati:

\bullet \Box p\to p je valjana na (W,R) ako i samo ako je R refleksivna relacija,
\bullet \Box p\to \Box\Box p je valjana na (W,R) ako i samo ako je R tranzitivna.


Možemo reći da formula \Box p\to p definira refleksivnost, a \Box p\to \Box\Box p definira tranzitivnost, te da su stoga refleksivnost i tranzitivnost primjeri modalno definabilnih svojstava relacija. S druge strane, te formule su valjane na svakom topološkom okviru.

Na kraju uvoda vratit ćemo se napomeni o razlozima korištenja različitih topoloških semantika. U već citiranom članku [3] promatrana je logika dokazivosti, za koju je ključna formula \Box(\Box p\to p)\to\Box p, koja je valjana točno na okvirima čije su pripadne relacije dostiživosti tranzitivne i inverzno dobro fundirane, tj. ne postoji beskonačan niz w_{0}Rw_{1}Rw_{2}\dots Posebno, R je tada irefleksivna (u suprotnom bismo imali wRwRw\dots za neki w\in W). Stoga formula \Box p\to p, koja definira refleksivnost, nije valjana ni na jednom takvom okviru. Međutim, valjana je na svakom topološkom okviru. To znači da topološku semantiku za logiku dokazivosti moramo drukčije definirati. Modifikacija se sastoji u tome da se formula \Box \varphi definira istinitom u w ako postoji otvoreni skup U koji sadrži w takav da je \varphi istinita u svakoj točki skupa U različitoj od w. Lako je provjeriti da je uz takvu definiciju \Diamond \varphi istinita u w ako i samo ako je w gomilište skupa točaka u kojima je istinita \varphi. No, mi ćemo u nastavku ovog članka promatrati ranije definiranu semantiku, po kojoj \Box \varphi i \Diamond \varphi korespondiraju s topološkim pojmovima interiora i zatvarača. U članku pretpostavljamo poznavanje osnovnih pojmova topologije (po potrebi v. [4]).

2Interpretacija modalnih operatora

Neka je \mathcal{W}=(W,\mathcal{T}, V) topološki model, a \varphi proizvoljna modalna formula. Označimo s A_{\varphi} skup svih točaka iz W u kojima je formula \varphi istinita. Zapišimo istinitost modalne formule \Box\varphi u točki w\in W topološkog modela \mathcal{W} pomoću kvantifikatora:

\mathcal{W},w\Vdash \Box\varphi\hspace{0.5cm} \text{ako i samo ako}\hspace{0.5cm} \exists\ U\in\mathcal{T}\ \Big(w\in U\ \land\ U\subseteq A_{\varphi}\Big).

Kako je za proizvoljan podskup A skupa W po definiciji interiora skupa A ispunjeno:

w\in\text{Int}\left(A\right)\hspace{0.5cm} \text{ako i samo ako}\hspace{0.5cm} \exists\ U\in\mathcal{T}\ \Big(w\in U\ \land\ U\subseteq A\Big),

to možemo uočiti da vrijedi sljedeće:

(1)
\begin{split} A_{\Box\varphi} &=\left\lbrace w\in W\mid~ \exists\ U\in\mathcal{T}\ \Big(w\in U\ \land\ U\subseteq A_{\varphi}\Big)\right\rbrace \\ &=\text{Int}\left(A_{\varphi}\right). \end{split}

Dakle, formuli oblika \Box\varphi odgovara interior skupa A_{\varphi} i obratno, pa je na očit način uspostavljena korespondencija između modalnog operatora \Box i topološkog operatora \text{Int}. Budući da je po definiciji zatvarača

\text{Cl}\left(A\right):=X\setminus\text{Int}\left(X\setminus A\right),

a znamo da je modalni operator \Diamond definiran kao pokrata

\Diamond\varphi:=\neg\Box\neg\varphi,

to odmah imamo da operatoru \Diamond korespondira topološki operator \text{Cl}. Nadalje, kako za proizvoljne modalne formule \varphi i \psi jednostavno vrijedi:

\begin{align*} &A_{\top}=W,~A_{\bot}=\emptyset,\\ &A_{\neg\varphi}=A_{\varphi}^{c},\\ &A_{\varphi\land\psi}= A_{\varphi}\cap A_{\psi}\text{ i }A_{\varphi\lor\psi}= A_{\varphi}\cup A_{\psi}, \end{align*}

zaključujemo da svaka formula modalnog jezika opisuje određen podskup topološkog prostora. Prirodno se stoga nameće da pokušamo neka važna topološka svojstva kodirati modalnim formulama. Promotrimo sljedeći primjer.

Primjer 1. Neka je \mathcal{W}=(W,\mathcal{T}, V) topološki model. U topološkom prostoru (W,\mathcal{T}) vrijedi
(2)
\begin{align} W\subseteq\text{Int}\left(W\right). \end{align}
Uočimo da se relacija (2) može opisati modalnom formulom \top\to\Box\top. Zaista, ta formula je istinita u svim točkama topološkog modela:
(3)
A_{\top\to\Box\top}=A_{\neg\top~\lor~\Box\top}=A_{\bot}\cup A_{\Box\top}=\emptyset\cup W=W.


Naš je idući korak promotriti doseg ovako definirane topološke semantike. U uvodnom dijelu smo naglasili da postoje razni pristupi definiranju topološke semantike i svaki je pristup pogodan za opis nekog svojstva. U nastavku pokazujemo da je logika svih topoloških prostora u kojoj modalni operator \Box čitamo kao operator \text{Int} zapravo jednaka logici S4, koju ćemo definirati u sljedećoj točki.

3Adekvatnost i potpunost logike S4 u odnosu na topološku semantiku

U nastavku s Top označavamo klasu svih topoloških prostora. Neka je \textbf{W}=\left(W,\mathcal{T}\right) proizvoljan element klase Top. Nadalje, za modalnu formulu \varphi koja je valjana na \textbf{W} pišemo

\textbf{W}\Vdash\varphi.

Definiramo:

\begin{align} \Lambda_{\textbf{Top}}:=\left\lbrace \varphi\mid~ \forall ~ \textbf{W}\in\textbf{Top}~\left(\textbf{W}\Vdash\varphi\right)\right\rbrace . \end{align}

Drugim riječima, \Lambda_{\textbf{Top}} predstavlja skup svih modalnih formula koje su valjane na svim topološkim prostorima, tj. elementima klase Top. Stoga, \varphi\in\Lambda_{\textbf{Top}} ako i samo ako za proizvoljan prostor \left(W,\mathcal{T}\right)\in Top, proizvoljnu valuaciju V i svaki element w\in W imamo da je

\left(W,\mathcal{T},V\right),w~\Vdash\varphi.

Označimo s (K) formulu

\Box\left(p\to q\right)\to\left(\Box p\to\Box q\right).

Riječ je aksiomu sistema K, za koji vrijedi teorem adekvatnosti i potpunosti u odnosu na relacijsku semantiku, tj. svaka formula je teorem sistema K ako i samo ako je valjana na svim okvirima. Detaljniju definiciju sistema K ispuštamo, jer je već dana u članku [3].

Zadatak 2. Dokažite da je formula (K) valjana na svakom topološkom prostoru.


Pokušajte zadatak riješiti samostalno, a tek po potrebi pogledati rješenje. Za ostale zadatke u članku nećemo navoditi rješenja.

Rješenje. Neka je \textbf{W}=\left(W,\mathcal{T}\right)\in\textbf{Top} i neka je \mathcal{W}=\left(\textbf{W},V\right) proizvoljan topološki model baziran na \textbf{W}. Neka je w\in W po volji odabran element skupa W, takav da vrijedi:
(4)
\begin{align} \mathcal{W},w\Vdash\Box\left(p\to q\right). \end{align}
Želimo pokazati da vrijedi sljedeće:
\mathcal{W},w\Vdash\left(\Box p\to\Box q\right).
Iz relacije (4) odmah imamo da postoji neki element U_{1}\in\mathcal{T}, takav da je w\in U_{1} i za sve elemente v\in U_{1} vrijedi
(5)
\begin{align} \mathcal{W},v\Vdash~p\to q. \end{align}
Pretpostavimo da vrijedi:
\mathcal{W},w\Vdash~\Box p.
Tada po definiciji postoji neki element U_{2}\in\mathcal{T}, takav da je w\in U_{2} i za sve elemente u\in U_{2} vrijedi
(6)
\begin{align} \mathcal{W},u\Vdash~p. \end{align}
Prirodno je sada definirati skup U\subseteq W na sljedeći način:
U:=U_{1}\cap U_{2}.
Tada očito imamo da je w\in U\in\mathcal{T}. Nadalje, za proizvoljan element u\in U imamo da je:
\mathcal{W},u\Vdash p ~~ \text{ i }~ ~ \mathcal{W},u\Vdash p\to q.
Dakle, za proizvoljan element u\in U vrijedi \mathcal{W},u\Vdash q. Stoga jednostavno zaključujemo:
\mathcal{W},w\Vdash~\Box q.
Ovime smo pokazali da je formula
\Box\left(p\to q\right)\to\left(\Box p\to\Box q\right)
valjana na svim elementima klase Top, to jest da vrijedi \left(\text{K}\right)\in\Lambda_{\textbf{Top}}.
\ \blacksquare


Odavde lako slijedi da je \Lambda_{\textbf{Top}} proširenje sistema K, tj. sadrži sve njegove teoreme. U nastavku ćemo točno odrediti o kojem proširenju se radi.

Označimo sa S4 proširenje sistema K aksiomima

\Box p\to p,

za koji smo već u uvodu napomenuli da definira refleksivnost, te

\Box p\to\Box\Box p,

koji, kako je već napomenuto, definira tranzitivnost. Pokazuje se da je sistem S4 adekvatan i potpun u odnosu na refleksivne i tranzitivne okvire, tj. svaka formula je teorem sistema S4 ako i samo ako je valjana na svim refleksivnim i tranzitivnim okvirima.
Naš je cilj pokazati da je logika S4 adekvatna i potpuna i u odnosu na topološku semantiku, tj. da vrijedi sljedeće:

\begin{align} \textbf{S4}=\Lambda_{\textbf{Top}}. \end{align}

Razmotrimo najprije adekvatnost, tj. inkluziju \textbf{S4}\subseteq\Lambda_{\textbf{Top}}.

Zadatak 3. Dokažite da su formule \Box p\to p i \Box p\to\Box\Box p valjane na svakom topološkom prostoru.


Iz prethodnog zadatka lako slijedi teorem adekvatnosti.

Teorem 4.[adekvatnost] Neka je \varphi modalna formula. Ako je \varphi teorem sistema S4, onda je \varphi valjana na svakom topološkom prostoru.


U nastavku pokazujemo da vrijedi i potpunost, tj. obratna inkluzija

\Lambda_{\textbf{Top}}\subseteq\textbf{S4}.

U dokazu potpunosti poslužit ćemo se takozvanim konačno generiranim topološkim prostorima koje je uveo Pavel Sergejevič Aleksandrov, poznati ruski matematičar.

Definicija 5. Za topološki prostor \textbf{W}=\left(W,\mathcal{T}\right) kažemo da je konačno generiran ako je presjek proizvoljne familije otvorenih skupova u W također otvoren skup u W.


Uočimo da konačna generiranost zapravo zahtijeva da svaka točka w\in W, posjeduje najmanju otvorenu okolinu, naime presjek svih otvorenih skupova koji sadrže w. Označimo s Fin klasu svih konačno generiranih topoloških prostora. Kao ključnu tvrdnju za dokaz potpunosti pokazat ćemo:

\Lambda_{\textbf{Fin}}~~=~~\textbf{S4}.

Neka je \textbf{W}=\left(W,R\right) refleksivan i tranzitivan okvir. Kratko ćemo reći da je R kvaziuređaj. Za A\subseteq W definiramo:

\uparrow A=\left\lbrace w\in W\mid ~\exists ~ v\in A~~\colon~~vRw\right\rbrace .

Uočavamo da je \uparrow A skup svih elemenata nosača W koji su dostiživi iz A. Također, očito je:

(7)
\begin{align} A=~\uparrow A~~\iff~~\forall x\forall y\left(x\in A~\land~xRy~\to~y\in A\right). \end{align}

Za element w\in W, definiramo i takozvani bazni skup, u oznaci R[w], na sljedeći način:

R[w]=\left\lbrace v\in W\mid~ wRv\right\rbrace .

Sada možemo na skupu W definirati familiju \mathcal{T}_{R} stavljajući:

\mathcal{T}_{R}:=\left\lbrace A\subseteq W\mid~A=~\uparrow A\right\rbrace .

Jasno je da \mathcal{T}_{R} definira topologiju na skupu W i time smo propisali otvorene skupove u W.

Uočimo da je topološki prostor \left(W,\mathcal{T}_{R}\right) konačno generiran. Naime, neka je \left\lbrace A_{i}\right\rbrace _{i\in I} proizvoljan podskup od \mathcal{T}_{R}. Neka je w\in\cap_{i\in I}A_{i} i v\in W takav da vrijedi wRv. Kako je za sve i\in I, w\in A_{i} i A_{i}\in\mathcal{T}_{R}, to je i v\in A_{i} za sve i\in I (vidi relaciju (7)). Dakle, v\in\cap_{i\in I}A_{i}, to jest \cap_{i\in I}A_{i}\in\mathcal{T}_{R}.

Iz prethodnog razmatranja možemo zaključiti da je svaki kvaziuređaj \left(W,R\right), na prirodan način povezan s klasom Fin, pomoću relacije:

\left(W,\mathcal{T}_{R}\right)\in\textbf{Fin}.

Nadalje, na tom promatranom topološkom prostoru \left(W,\mathcal{T}_{R}\right), možemo sada, na prirodan način, izgraditi relaciju kanonskog uređaja, koju ćemo označiti s R_{\mathcal{T}_{R}}, tako da za proizvoljne elemente v,w\in W definiramo:

v R_{\mathcal{T}_{R}}w~~\iff~~ v\in\text{Cl}\left(\left\lbrace w\right\rbrace \right).

Vrlo se lagano, koristeći osnovna svojstva zatvarača, može provjeriti da je ovako definirana relacija R_{\mathcal{T}_{R}} refleksivna i tranzitivna. Drugim riječima, kanonski uređaj ima svojstva kvaziuređaja.

Stoga, polazeći od proizvoljnog refleksivnog i tranzitivnog okvira \textbf{W}=\left(W,R\right) dolazimo do činjenice da je \left(W,\text{Cl}{T}_{R}\right)\in\textbf{Fin}, koja nas nadalje vodi k novom kvaziuređaju \left(W,R_{\text{Cl}{T}_{R}}\right). Pritom vrijedi:

(8)
\begin{align} R= R_{\text{Cl}{T}_{R}}. \end{align}

Uočimo da je relacija (8) jednostavna posljedica sljedeće tvrdnje:

(9)
\begin{align} \text{Cl}(\lbrace w\rbrace )~=~\left\lbrace v\in W\mid~vRw\right\rbrace . \end{align}

Relacija (9) je posljedica refleksivnosti i tranzitivnosti relacije R. Naime, za svaki element v\in W, skup R[v] je otvoren u topologiji \mathcal{T}_{R}, što proizlazi iz tranzitivnosti relacije R te (7). Ako je v\in\text{Cl}(\lbrace w\rbrace ), onda svaka okolina točke v mora sjeći skup \lbrace w\rbrace. Refleksivnost relacije R nam daje da je v\in R[v], a time imamo da je i w\in R[v], to jest imamo vRw. Obratno, ako vrijedi vRw, onda je po definiciji w\in R[v]. Budući je R[v] zapravo najmanja otvorena okolina točke v, to svaka okolina točke v siječe skup \lbrace w\rbrace. Dakle imamo da je v\in\text{Cl}(\lbrace w\rbrace ).

Krenimo sada od proizvoljnog topološkog prostora \left(W,\mathcal{T}\right) koji je konačno generiran, to jest pretpostavimo \left(W,\mathcal{T}\right)\in \textbf{Fin}. Tom konačno generiranom topološkom prostoru pridružimo kvaziuređaj \left(W,R_{\mathcal{T}}\right) na sljedeći način:

vR_{\mathcal{T}}w~~\iff~~v\in\text{Cl}(\lbrace w\rbrace ).

Na ovako definiranom kvaziuređaju, promatramo topologiju

\mathcal{T}_{R_{\mathcal{T}}}:=\left\lbrace A\subseteq W\mid~A=~\uparrow A\right\rbrace .

Komentirali smo ranije da je topološki prostor (W,\mathcal{T}_{R_{\mathcal{T}}}) konačno generiran. U ovom slučaju, kada smo krenuli od konačno generiranog topološkog prostora \left(W,\mathcal{T}\right), vrijedi:

(10)
\begin{align} \mathcal{T}~=~\mathcal{T}_{R_{\mathcal{T}}}. \end{align}

Inkluzija koja je u relaciji (10) zaista zanimljiva je

(11)
\begin{align} \mathcal{T}_{R_{\mathcal{T}}}~\subseteq~\mathcal{T}. \end{align}

Naime, za proizvoljan topološki prostor imamo da je \mathcal{T}\subseteq\mathcal{T}_{R_{\mathcal{T}}}. No, pretpostavka konačne generiranosti topološkog prostora \left(W,\mathcal{T}\right) potrebna je upravo za dokaz inkluzije (11). Neka je V proizvoljan otvoren skup u topološkom prostoru (W,\mathcal{T}_{R_{\mathcal{T}}}). Neka je v\in V. Tvrdimo da postoji neki skup U\in\mathcal{T}, takav da je:

v\in U\subseteq V.

Prirodni kandidat za skup U je skup \lbrace u\in W\mid~vR_{\mathcal{T}}u\rbrace. Zaista, iz same definicije zatvarača imamo:

\lbrace u\in W\mid~vR_{\mathcal{T}}u\rbrace ~=~\bigcap_{\substack{A\in\mathcal{T} \\ v\in A}}A.

Sada konačna generiranost topološkog prostora \left(W,\mathcal{T}\right) povlači da je skup \lbrace u\in W\mid~vR_{\mathcal{T}}u\rbrace otvoren u W. Također, vrijedi:

\lbrace u\in W\mid~vR_{\mathcal{T}}u\rbrace \subseteq V,

jer je za u\in\lbrace u\in W\mid~vR_{\mathcal{T}}u\rbrace ispunjeno da je v\in\text{Cl}(\lbrace u\rbrace ), što povlači da svaka otvorena okolina točke v nužno sadrži u sebi i točku u, to jest u\in V.

Zadatak 6. Neka je \left(W,R\right) kvaziuređaj. Neka je \varphi proizvoljna modalna formula. Tada vrijedi:
(12)
\begin{align} \left(W,R\right)\Vdash\varphi~~~\iff~~~\left(W,\mathcal{T}_{R}\right)\Vdash\varphi. \end{align}


Kao posljedicu dobivamo potpunost sistema S4 u odnosu na konačno generirane topološke prostore, tj. 

(13)
\begin{align} \Lambda_{\textbf{Fin}}~~=~~\textbf{S4}. \end{align}

Naime, krenuvši od konačno generiranog topološkog prostora (W,\mathcal{T}), izgradimo kvaziuređaj (W,R_{\mathcal{T}}), a onda tvrdnja prethodnog zadatka povlači da je za svaku modalnu formulu \varphi ispunjeno

\left(W,R_{\mathcal{T}}\right)\Vdash\varphi~~~\iff~~~\left(W,\mathcal{T}_{R_{\mathcal{T}}}\right)\Vdash\varphi.

Međutim, kako smo krenuli od topološkog prostora (W,\mathcal{T}) koji je konačno generiran, imamo da je \mathcal{T}=\mathcal{T}_{R_{\mathcal{T}}}, iz čega zaključujemo (??).

No, naš cilj je bila potpunost u odnosu na sve topološke prostore, koja je također posljedica prethodnog zadatka. To iskazujemo u sljedećem teoremu.

Teorem 7.[potpunost] Neka je \varphi modalna formula. Ako je \varphi valjana na svakom topološkom prostoru, onda je \varphi teorem sistema S4.

Proof. Neka je \varphi\in\Lambda_{\textbf{Top}}. Kako bismo dokazali da je \varphi teorem sistema S4, koristimo potpunost u odnosu na relacijsku semantiku: dovoljno je dokazati da je \varphi valjana na svakom refleksivnom i tranzitivnom okviru. Neka je \left(W,R\right) takav okvir. Tada znamo da je \left(W,R\right) u korespondenciji s konačno generiranim topološkim prostorom \left(W,\mathcal{T}_{R}\right). Kako je \left(W,\mathcal{T}_{R}\right) topološki prostor, a \varphi\in\Lambda_{\textbf{Top}}, to je
\left(W,\mathcal{T}_{R}\right)\Vdash\varphi.
Prema tvrdnji prethodnog zadatka odmah dobivamo:
\left(W,R\right)\Vdash\varphi.
\ \blacksquare

4Izražajna snaga modalne logike u odnosu na topološke prostore

Označimo s \mathcal{K} neku klasu topoloških prostora. Kažemo da je klasa \mathcal{K} modalno definabilna, ako postoji skup modalnih formula \Gamma takav da za proizvoljan topološki prostor \textbf{W}=\left(W,\mathcal{T}\right) vrijedi:

\begin{align*} \textbf{W}~\in~\mathcal{K}~~\iff~~ \textbf{W}\Vdash \Gamma. \end{align*}

Kako je sistem S4 potpun u odnosu na topološku semantiku, imamo da je klasa \mathcal{K}=\textbf{Top} modalno definabilna i to formulom \varphi:=\top. Možemo kazati da formula \varphi definira klasu \textbf{Top}. Navedimo i jedan netrivijalan primjer.

Primjer 8. Lagano se vidi da modalna formula
\varphi:=p~\rightarrow~\Box~p
definira klasu svih diskretnih topoloških prostora, to jest prostora kod kojih su svi podskupovi otvoreni (odnosno zatvoreni). Naime, za topološki prostor \textbf{W}=\left(W,\mathcal{T}\right) vrijedi sljedeće: \textbf{W}\Vdash\varphi ako i samo ako je svaki podskup od W otvoren. Ključna je ovdje činjenica da su svi jednočlani podskupovi od W otvoreni u W. Tako, naprimjer, za proizvoljnu valuaciju V, te proizvoljan element w\in W, trivijalno vidimo da, ako vrijedi (W,\mathcal{T},V),w\Vdash p, onda za sve elemente v iz skupa A:=\lbrace w\rbrace \in\mathcal{T} vrijedi (W,\mathcal{T},V),v\Vdash p, to jest (W,\mathcal{T},V),w\Vdash\Box p.


Ipak, neke važne klase topoloških prostora, kao što je klasa povezanih ili pak klasa kompaktnih topoloških prostora, nisu modalno definabilne.

Kako bismo to pokazali, koristimo neke operacije na topološkim prostorima koje čuvaju valjanost modalnih formula.

Definicija 9. Neka je \left\lbrace \textbf{W}_{i}=\left(W_{i},\mathcal{T}_{i}\right)\mid~i \in I\right\rbrace familija disjunktnih topolo\-ških prostora. Definiramo novi topološki prostor \textbf{W}=\left(W,\mathcal{T}\right):
\begin{align*} W=\bigcup_{i\in I}X_{i}~~\text{ i }~~ \mathcal{T}=\left\lbrace A\subseteq W\mid~\forall~i\in I~\left(A\cap W_{i}\in\mathcal{T}_{i}\right)\right\rbrace . \end{align*}
Ovako definiran topološki prostor zovemo suma topoloških prostora.


Indukcijom po složenosti modalne formule jednostavno se vidi da za svaku modalnu formulu \varphi vrijedi sljedeće:

(14)
\begin{align} \textbf{W}\Vdash\varphi~~\iff~~\forall~ i\in I~\left(\textbf{W}_{i}\Vdash\varphi\right). \end{align}

Primjer 10. Klasa povezanih topoloških prostora i klasa kompaktnih topoloških prostora nisu modalno definabilne.

Naime, za svaki prirodan broj i, promotrimo jednočlan skup W_{i}:=\lbrace i\rbrace. Na skupu W_{i} definiramo topologiju \mathcal{T}_{i}:=\lbrace \emptyset,\lbrace i\rbrace \rbrace. Primijetimo da je za svaki i\in\mathbb{N} topološki prostor \textbf{W}_{i}=\left(W_{i},\mathcal{T}_{i}\right) kompaktan i povezan. Neka je nadalje \textbf{W}=\left(W,\mathcal{T}\right) topološka suma familije \lbrace \textbf{W}_{i}\mid~i\in\mathbb{N}\rbrace. Uočimo da je zapravo W=\mathbb{N}, a \mathcal{T}=\mathcal{P}(\mathbb{N}). Tada \textbf{W} nije povezan jer skup \mathbb{N} možemo separirati pomoću skupova \lbrace 1\rbrace i \mathbb{N}\setminus\lbrace 1\rbrace, koji su očito otvoreni u topologiji \mathcal{T}, međusobno disjunktni i neprazni. Također, \textbf{W} nije niti kompaktan, budući je \left\lbrace \left\lbrace i\right\rbrace \mid~i\in\mathbb{N}\right\rbrace familija otvorenih skupova u W, koja prekriva W, ali je nikako ne možemo reducirati na konačan potpokrivač. Stoga (14) povlači da klasa povezanih topoloških prostora i klasa kompaktnih topoloških prostora ne mogu biti modalno definabilne.

Definicija 11. Neka je \textbf{W}=\left(W,\mathcal{T}\right) topološki prostor. Svaki par oblika \mathcal{A}=\left(A,\mathcal{T}_{A}\right), gdje je A\in\mathcal{T}, a topologija \mathcal{T}_{A}:=\lbrace O\cap A\mid~O\in\mathcal{T}\rbrace inducirana topologijom \mathcal{T}, zovemo otvoreni potprostor od \textbf{W}.


Indukcijom po stupnju složenosti modalne formule pokazuje se da za svaku modalnu formulu \varphi iz \textbf{W}\Vdash\varphi nužno slijedi \mathcal{A}\Vdash\varphi.

Primjer 12. Klasa topoloških prostora koji nisu povezani nije modalno definabilna. Naime, na skupu W:=\lbrace 1,2\rbrace, možemo promatrati topologiju \mathcal{T}=\mathcal{P}(W). Očito, topološki prostor \textbf{W}=(W,\mathcal{T}) nije povezan, jer se npr. skup W može separirati pomoću skupa \lbrace 1\rbrace i skupa \lbrace 2\rbrace. No, otvoreni potprostor \left(\left\lbrace 1\right\rbrace ,\mathcal{T}_{\left\lbrace 1\right\rbrace }\right) je povezan.


Nadalje, koristeći činjenicu da otvorena preslikavanja, tj. funkcije koje otvorene skupove iz domene preslikavaju u otvorene skupove u kodomeni, čuvaju valjanost modalnih formula (v. teorem 36 u [5]), može se zaključiti da ni topološki aksiomi separacije T_{i}, za i\in\lbrace 0,D,1,2,3,3\frac{1}{2},4,5\rbrace također nisu modalno definabilni. Navedimo protuprimjer.

Primjer 13. Promotrimo skup W=\lbrace 1,2\rbrace i na njemu tzv. indiskretnu topologiju \mathcal{T}=\lbrace \emptyset,W\rbrace. Promotrimo funkciju koje sve racionalne brojeve preslikava u broj 1, a sve iracionalne brojeve u broj 2. Lako se vidi da je to otvoreno preslikavanje iz prostora \mathbb{R}, koji zadovoljava sve aksiome separacije, u prostor (W,\mathcal{T}), koji ne zadovoljava niti jedan.


Iako nismo definirali sve potrebne pojmove, jer bismo time nadišli okvire ovog članka, na kraju ćemo iskazati opći teorem o modalnoj definabilnosti topoloških svojstava, koji predstavlja analogon Goldblatt-Thomasonovog teorema (v. teorem 43 u [5]).

Teorem 14.[Gabelaia [2]] Neka je \mathcal{K} klasa topoloških prostora zatvorena na ultafilterska Alexandroffova proširenja. Tada je klasa \mathcal{K} modalno definabilna ako i samo ako je zatvorena na otvorene potprostore, topološke sume, surjektivna otvorena preslikavanja te ako reflektira ultrafilterska Alexandroffova proširenja.

{00}

Bibliografija
[1] P. Blackburn, M. de Rijke, Y. Venema: Modal Logic, Cambridge University Press, 2001.
[2] D. Gabelaia: Modal definability in topology, MScaster's thesis, ILLC, Amsterdam, 2001.
[3] L. Mikec, T. Perkov: Topološka semantika logika dokazivosti, Math.e 32 (2017) \url{http://e.math.hr/Vol32/Perkov} (pristupljeno 29. 10. 2018.)
[4] J. R. Munkres: Topology, Prentice Hall, 2000.
[5] B. ten Cate, D. Gabelaia, D. Sustretov: Modal languages for topology: expressivity and definability, Annals of Pure and Applied Logic 159 (2009) 146–170.
[6] M. Vuković: Matematička logika, Element, Zagreb 2009.
 


 

Broj 36

Poštovani,


u broju 36. časopisa math.e vam donosimo pregled rezultata na granici matematike i računarstva. U članku Prepoznavanje lica pomoću tenzorske dekompozicije singularnih vrijednosti autora Nele Bosner i Ivan Zirduma pokazujemo primjenu tenzorskih dekompozicija -- koji se dobivaju kao višedimenzionalna poopćenja dekompozicije singularnih vrijednosti -- u problemu prepoznavanja lica. Korištenje tenzora, kao višedimenzionalnih tablica i s tim povezanih operacija, u računarstvu je jedna od dominantnih istraživačkih tema posljednjih 10 godina. Veza optimizacije i problema modeliranja u podacima bogatom okruženju je ključna u razvoju informacijskih znanosti. Ovaj članak pruža vrlo ugodan uvod u ovo područje primijenjene matematike uključujući i MALTAB kodove osnovnih algoritama. U članku Topološka semantika modalne logike autora Bojana Pažeka i Tina Perkova prikazujemo jedan od pristupa modalnoj logici koja je u temelju distribuiranog računarstva. Članak istražuje veze logike i ostalih matematičkih disciplina i od interesa je čitateljima zainteresiranim za osnove računarstva. Konačno u članku, O indeksima snage u sustavima glasovanja da-ne autora Tomislava Maroševića i Marije Šarić prikazuju se osnove matematičke teorije odlučivanja. Ovo je izvrsna motivacija za proučavanje matematike u operacijskim istraživanjima te zainteresiranom čitatelju pokazuje još jedan most između matematike i primjena s posebnim osvrtom na primjenu matematike u rješavanju društveno relevantnih pitanja.


Želim vam ugodno čitanje.


Luka Grubišić