CEU Electronic Theses and Dissertations, 2016
| Author | Khaled, Mohamed |
|---|---|
| Title | Godel's incompleteness properties and the guarded fragment: An algebraic approach |
| Summary | The guarded fragment (GF), introduced by H. Andreka, J. van Benthem and I. Nemeti in [AvBN98], is a large decidable fragment of first order logic that has a wide range of applications in computer science, linguistics, among others, because of its good properties. Its logical properties were investigated by many logicians. By being decidable, GF gives up some expressive power relative to first order logic. A measure of expressive power of a logic is Godel’s Incompleteness Property (GIP). A logic is said to have GIP (wGIP, respectively) if there is a satisfiable formula in this logic which cannot be extended to a recursively (finitely, respectively) axiomatized complete theory of the logic in question. GIP fails for the guarded fragment, but we prove that wGIP holds for GF on infinite languages while for finite languages wGIP does not hold, either. On the other hand, we prove that the so-called solo-guarded fragment of GF has wGIP on finite languages, too. To prove the above, we use algebraic methods. Namely, we use the theorem from [Nem86] that a logic has wGIP if and only if its Lindenbaum-Tarski formula algebras are not atomic. The latter in the case of GF are closely related to the free cylindric relativized set algebras. We solve a long-standing open problem first asked in 1985 and then published in [Nem86], [AMN91] and [AFN13] by proving that most of the free cylindric relativized set algebras are non-atomic. We also give structural descriptions of these free algebras from the point of view of atoms. |
| Supervisor | Andréka, Hajnal and Németi, István |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2016/khalifa_mohamed.pdf |
Visit the CEU Library.
© 2007-2021, Central European University