Operator extensions of Gödel logics

Abstract

The main results of this thesis are, on one hand, the proof that a Hilbert-style calculus with finitely many axioms axiomatises the valid formulae of the propositional fragment of an extension of Gödel logic by an adding operator and, on the other, the demonstration of the conjecture that the valid formulae of the first-order fragment of the considered logic cannot be recursively enumerable so that, in particular, no recursive calculus for them can exist. The thesis includes also smaller results like the non-compactness of entailment in the propositional fragment as well as a variant of the lifting lemma and the complexity class of propositional satisfiability.<br />In the following, the motivation to investigate this extension of Gödel logic will be sketched:<br />Gödel logic and Łukasiewicz logic are, together with product logic, the three main t-norm-based fuzzy logics. The validity of formulae in the propositional fragment of these logics can be exactly characterised by calculi that result from Hájek's basic logic by adjunction of a single axiom scheme. For first-order logic, however, we see the phenomenon that Gödel logics admits such a characterisation of the valid formulae thanks to its order-theoretic nature, but that Łukasiewicz logic cannot feature such a calculus due to a result by Scarpellini (1962). In fact, Ragaz (1981) proved Łukasiewicz logic to be $\Pi_2$-complete. In the sense of Weiermann, this leads to a phase transition between Gödel logic and Łukasiewicz logic. This thesis contributes to a better understanding what constitutes this transition:<br />The ability of the considered operator to express distances of truth values is the feature that increases the complexity class of the valid formulae in Gödel logic.<br />

Die Hauptresultate dieser Dissertation sind einerseits der Nachweis der Axiomatisierbarkeit der gültigen Formeln des propositionellen Fragments einer Erweiterung der Gödellogik um einen addierenden Operator durch einen hilbertschen Kalkül mit endlich vielen Schemata und andererseits der Beweis der Vermutung, dass sich die gültigen prädikatenlogischen Formeln derselben Erweiterung nicht rekursiv aufzählen lassen und sie daher kein berechenbarer Kalkül charakterisieren kann. Diese Dissertation enthält auch Ergebnisse wie z.<br />B. die Nichtkompaktheit der Folgerungsrelation im propositionellen Fragment sowie eine Variante des Hebelemmas und die Komplexitätsklasse der propositionellen Erfüllbarkeit. Die Motivation, diese Erweiterung der Gödellogik zu untersuchen, war folgende:<br />Gödellogik und Łukasiewiczlogik sind gemeinsam mit der Produktlogik die Hauptvertreter der t-Norm-basierten Fuzzylogiken. Die Gültigkeit von Formeln in den propositionellen Fragmenten dieser Logiken kann genau durch Kalküle beschrieben werden, von denen jeder durch die Hinzunahme nur eines Axioms zum hájekschen Kalkül der Basislogik entsteht. Für die prädikatenlogischen Fragmente tritt hingegen das Phänomen ein, dass zwar die Gödellogik dank ihrem ordnungstheoretischen Hintergrund eine Charakterisierung der gültigen Formeln durch einen Kalkül zulässt, dass aber ein solcher Kalkül nach einem Resultat von Scarpellini (1962) für die Łukasiewiczlogik unmöglich ist. Nach Ragaz (1981) ist die Łukasiewiczlogik sogar $\Pi_2$-vollständig. Zwischen Gödellogik und Łukasiewiczlogik ergibt sich daher ein im weiermannschen Sinne aufgefasster Phasenübergang. Diese Dissertation trägt zum besseren Verständnis bei, was diesen Übergang ausmacht: Die Komplexitätsklasse der Gültigkeit von Formeln in der Gödellogik wird durch die Eigenschaft des betrachteten Operators, eine Distanz von Wahrheitswerten auszudrücken, gehoben.<br />