Topološka potpunost logika dokazivosti

diplomski rad

• Autor: Luka Mikec
• Mentor: Mladen Vuković (mentor)
• Član povjerenstva: Mladen Vuković (predsjednik povjerenstva)
• Član povjerenstva: Vedran Čačić (član povjerenstva)
• Član povjerenstva: Tin Perkov (član povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2016-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Sustav GLP je sustav modalne logike kojeg je 1986. uveo Giorgi Japaridze. Ovaj sustav sadrži prebrojivo mnogo modalnih operatora \([n]\), po jedan za sve \(n \in \omega\). Ako je dana "dovoljno snažna" teorija aritmetike, onda sustav GLP adekvatno i potpuno opisuje jedan njen fragment. Većina sustava modalne logike ima tzv. relacijsku semantiku (poznatu i kao Kripkeova semantika, ili semantika mogućih svjetova). U određenom smislu, ne postoji zadovoljavajuća relacijska semantika za sustav GLP. Postoje i drugi tipovi semantika. Lev Beklemishev i David Gabelaia su 2011. dokazali da je GLP potpun u odnosu na jednu klasu politopoloških prostora. Glavni cilj ovog rada je predstaviti taj dokaz. U prvom se poglavlju bavimo relacijskom semantikom. Osnovni cilj je prikazati probleme koji se javljaju kad se sustavu GLP pokuša dati (uobičajena) relacijska semantika. U drugom poglavlju, uvodimo topološke konstrukcije potrebne u dokazu teorema potpunosti. To uključuje tzv. lme-prostore, jednu klasu politopoloških prostora s poželjnim svojstvima. U trećem poglavlju se bavimo dokazom potpunosti. Pritom koristimo relacijsku semantiku još jednog sustava modalne logike, tzv. sustava J. Teoremi sustava GLP su u određenom smislu reducibilni na teoreme sustava J. Može se dokazati da za svaki J-adekvatan relacijski okvir postoji lme-prostor i preslikavanje između njih koje čuva valjanost. Koristeći te činjenice, za svaku GLP-nedokazivu formulu možemo izgraditi topološki model na kojem nije globalno istinita.

Sažetak (engleski)

System GLP is a system of modal logic introduced by Giorgi Japaridze in 1986. This system contains countably many modal operators \([n]\), one for each \(n \in \omega\). Given a "sufficiently strong" theory of arithmetic A, system GLP provides a sound and complete description of a fragment of A. Most systems of modal logic can be given a certain type of semantics known as relational semantics (also known as Kripke semantics, or possible world semantics). In a certain sense, such semantics cannot be given to GLP in a satisfactory way. There are other types of semantics. In 2011, Lev Beklemishev and David Gabelaia proved that GLP is complete with respect to a certain class of polytopological spaces. The main goal of this thesis is to present the proof of topological completeness. In the first chapter, we work with relational semantics. This is mainly to showcase the issues that arise when trying to give GLP a (typical) relational interpretation. In the second chapter, we introduce topological constructions needed to prove the completeness theorem. These include lme-spaces, a certain well-behaved class of polytopological spaces. In the third chapter, we present the proof of completeness. This is done by exploiting relational semantics of another system of modal logic, known as system J. Theorems of GLP are, in a certain sense, reducible to theorems of J. It can be shown that for any J-sound relational frame there exists a lme-space and a validity-preserving morphism between them. By exploiting these facts, we can build a topological model that falsifies any formula that is not provable in GLP.

• Ključne riječi: modalna logika; sustav GLP; Kripkeova semantika; relacijska semantika; teorem potpunosti; politopološki prostori; sustav J
• Ključne riječi (engleski): modal logic; system GLP; Kripke semantics; relational semantics; completeness theorem; polytopological spaces; system J
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:223951
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-01-24 11:08:55