Modalna potpunost logika interpretabilnosti

diplomski rad

• Autor: Sebastijan Horvat
• Mentor: Mladen Vuković (mentor)
• Član povjerenstva: Mladen Vuković (predsjednik povjerenstva)
• Član povjerenstva: Tin Perkov (član povjerenstva)
• Član povjerenstva: Ivica Nakić (član povjerenstva)
• Član povjerenstva: Dijana Ilišević (č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: 2018-07-16, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Sistem \(IL\) je modalni sistem kojeg je 1988. uveo Albert Visser. Ovaj sistem sadrži jedan unarni modalni operator \(\Box\) i jedan binarni modalni operator \(\rhd\). Promatraju se i razna proširenja sistema \(IL\) s principima interpretabilnosti. Neka od tih proširenja su logike interpretabilnosti \(ILM\), \(ILP\), \(ILW\) i \(ILM_0\). De Jongh i Veltman su 1990. dokazali potpunost sistema \(IL\), \(ILM\) i \(ILP\), a nešto kasnije i potpunost sistema \(ILW\). Evan Goris i Joost Joosten su 2004. dali nove dokaze potpunosti sistema \(IL\) i \(ILM\) koristeći step-by-step metodu kojom su potom dokazali i modalnu potpunost sistema \(ILM_0\) i \(ILW^*\). Glavni cilj ovog rada je dokazati teoreme modalne potpunosti za logike interpretabilnosti \(IL\) i \(ILP\) koristeći step-by-step metodu. U prvom poglavlju bavimo se semantikom i sintaksom osnovne logike interpretabilnosti \(IL\). U ovom poglavlju dokazujemo adekvatnost sistema \(IL\) i teorem dedukcije za sistem \(IL\). Nakon što definiramo pojmove \(IL\)-konzistentnih i maksimalno \(IL\)-konzistentnih skupova, dokazujemo Lindenbaumovu lemu. U drugom poglavlju definiramo pojmove označenih, adekvatnih i kvazi--okvira, problema i nedostataka, te kritičnog i generaliziranog konusa. Dokazujemo lemu o egzistenciji i lemu o \(IL\)-proširenju. Osnovni cilj ovog poglavlja je dati dokaz potpunosti sistema \(IL\) korištenjem step-by-step metode. U trećem poglavlju dokazujemo potpunost sistema \(ILP\). Prvo dajemo definicije i rezultate vezane za logike interpretabilnosti \(ILX\). Potom navodimo glavne korake step-by-step metode, te formalno iskazujemo glavnu lemu. Dajemo detaljan dokaz potpunosti \(ILP\), pri čemu zapravo provjeravamo uvjete glavne leme kako bismo ju mogli primijeniti.

Sažetak (engleski)

System \(IL\) is a system of modal logic introduced by Albert Visser in 1988. This system contains one unary modal operator \(\Box\) and one binary modal operator \(\rhd\). We also consider extensions of system \(IL\). They are given by the intepretability principles, and some of these extensions are interpretability logics \(ILM\), \(ILP\), \(ILW\) and \(ILM_0\). Modal completeness of logics \(IL\), \(ILM\) and \(ILP\) was proven in 1990. by De Jongh and Veltman. Later they also proved modal completeness of the logic \(ILW\). In 2004. Evan Goris and Joost Joosten gave new proofs of completeness of logics \(IL\) and \(ILM\) using their step-by-step method. Using that method, they also proved modal completeness of logics \(ILM_0\) and \(ILW^∗\). The main goal of this thesis is to present the proof of modal completeness of interpretability logics \(IL\) and \(ILP\) by using step–by–step method. In the first chapter, we deal with syntax and semantic of the interpretability logic \(IL\). In this chapter we present proof of soundness theorem for logic \(IL\) and proof of deduction theorem for logic \(IL\). After presenting the notion of \(IL\)–consistent and maximal \(IL\)–consistent set, we give proof of Lindenbaum’s lemma. In the second chapter, we define the following notions: labeled frame, adequate frame, quasi–frame, problems, deficiencies, critical cone and generalized cone. We also prove existence lemma and \(IL\)–closure lemma. The main goal of this chapter is to prove model completeness of the logic \(IL\) by using the step–by–step method. In the third chapter, we present the proof of completeness of the logic \(ILP\). We first present definitions and results that are related to interpretability logics \(ILX\). Then we describe main steps of the step–by–step method. Also, we give formal statement of the main lemma. Finally, we present detailed proof of completeness of the logic \(ILP\). We are doing that by checking requirements of the main lemma.

• Ključne riječi: Visser; logika interpretabilnosti; De Jongh; Veltman; Goris; Joosten; step-by-step metoda; Lindenbaumova lema
• Ključne riječi (engleski): Visser; interpretability logic; De Jongh; Veltman; Goris; Joosten; step-by-step method; Lindenbaum’s lemma
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:831141
• 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: 2018-11-23 13:17:07