Modalna potpunost logika interpretabilnosti

master's thesis

• Author: Sebastijan Horvat
• Mentor: Mladen Vuković (mentor)
• Committee member: Mladen Vuković (predsjednik povjerenstva)
• Committee member: Tin Perkov (član povjerenstva)
• Committee member: Ivica Nakić (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-07-16, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: Visser; logika interpretabilnosti; De Jongh; Veltman; Goris; Joosten; step-by-step metoda; Lindenbaumova lema
• Keywords (english): Visser; interpretability logic; De Jongh; Veltman; Goris; Joosten; step-by-step method; Lindenbaum’s lemma
• Language: croatian
• URN:NBN: urn:nbn:hr:217:831141
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-11-23 13:17:07