Semantics for Gödel Logics

Logic (and mathematics) can be considered as the study of the interplay between syntax - strings of symbols which are transformed into other strings of symbols - and semantics - the (intended) interpretation of these strings of symbols. This was the important step: to separate these two parts allowing logicians at the beginning of the last century to advance logics and mathematics and thus initiating a golden century of mathematics. But why do we deal with semantics at all, couldn`t we restrict ourselves to purely syntactic methods, i.e. to methods accessible by computational means? This was the idea of Hilbert`s program at the beginning of the last century, to create a solid foundation of mathematics which can be treated with only syntactical methods - the dream of every student, the universal computer where you feed a mathematical question and get the correct answer. Kurt Gödel destroyed this hope by exhibiting that with purely syntactical methods we can never cover all mathematical truths. So the study of semantics, especially in the case of different semantics for the same syntactical system, cannot be replaced by purely syntactical methods. The study of different semantics is actually the study of the very objects of mathematics that logic is related to. What we today call `Gödel logics` was developed from and for the analyzation of very different mathematical objects: The real numbers, Kripke frames, and Heyting algebras. The semantics based on subsets of the real interval [0,1] are concerned with the topological and order-theoretic properties of the reals, and the expressiveness of first order language with respect to these properties. These semantics have been mainly developed by Baaz et al. with substantial contributions by the applicant. Kripke frames form the prime semantics for Intuitionistic Logic and Modal Logics, and the study of logics of specific Kripke frames (linear with constant domains) has been carried out mainly by Japanese scientists. These Kripke frames can also be considered as a semantic for Gödel logics as was recently shown by the applicant in the course of the MC fellowship. Besides their function as semantics for Intuitionistic Logic, Kripke frames have been used in the development of modal and temporal logics. Algebraic semantics based on special Heyting algebras were introduced by Hàjek, whereas Heyting algebras are special instances of lattices. In his work Hàjek considered t-norm based logics as the foundation of fuzzy logics. In the wide class of t-norm based logics three fundamental logics form a basis of all the other logics: ?ukasiewicz logic, Product logic, and Gödel logic. By combining these logics we get all possible continuous t-norm based logics. If all these semantics were the same, it would be useless to deal with all of them. But while semantics can coincide in the base case (e.g. the propositional logic), their extensions often exhibit interesting properties and differences of the semantics. A typical example is the class of finite Kripke frames versus the class of all Kripke frames: The propositional logics for both classes coincide, but the quantified propositional logic of the former class is decidable, while the one of the later is not even recursively enumerable. While the semantics do exhibit different properties for different extensions, they are still linked together via the syntax of these logics. This syntax-semantic relation is one of the most important ones in logic. In fact modern logic can be seen as a history of the interplay between syntactical and semantical studies, and their relations. We aim at a unified presentation of these semantics, a transfer of results and techniques between these semantics, and the development of criteria for discussing and comparing semantics for first order many valued logics.

This project deals with non-standard logics, i.e., logics that are neither classical - bi-valued - nor intuitionistic logic. Within this group, those based on linearly ordered truth values have gained prime importance and increased attention, starting from the early 1920s when Lukasiewicz and Gödel introduced first examples of these logics. The aim of this project was the study of different semantics for Gödel logics, and targeting computationally interesting questions around the decidability of satisfiability and validity. The most important results of the project are on satisfiability and validity of various subclasses of Gödel logics. Although the full first order is way too powerful to be decided, subclasses not providing the full expressive power might still be decidable, and at the same time being strong enough for real-world applications. This is the case for e.g., the monadic fragment of classical logic, or the Horn class (logic programming). Possible classes under consideration are the monadic class, the one-variable class, and fragments specifically tweaked for applications. As in classical logics or modal logics, questions turning around decidability of properties like satisfiability or validity are of core importance for actual computational implementations and applications. During this project several break-through results in this area have been obtained. One being the full characterization of satisfiability in monadic Gödel logics. The other being the decidability of a fragment of Gödel logics with Delta powerful enough to formalize important properties of fuzzy rule-based medical expert systems. Together these results constitute a big step forward from theoretical discussions of Gödel logics to actual applying them in the real world.