Formalsprachliche Theorie der Logikfragmente

The present thesis consists of two parts. Based on syntactic closure axioms of formula sets, the first part gives a formal definition of logic fragments. It also shows the versatileness of this notion of logic fragments, inter alia, giving, C-variety descriptions of logic fragments and abstractly investigating the influence of certain predicates on the expressiveness of logic fragments. The second part considers two-variable first-order logic FO2. A combinatorial description in terms of so-called rankers is given for all full levels as well as all half levels of the quantifier alternation hierarchy of FO2 over the order predicate, both with and without the successor predicate. Also in the second part, effective algebraic criteria describing all full levels as well as all half levels of the quantifier alternation hierarchy of FO2 over several signatures are given, yielding in particular decidability of the definability problem.Die vorliegende Dissertation besteht aus zwei Teilen. Im ersten Teil wird, basierend auf syntaktischen Abschlusseigenschaften von Formelmengen, eine formale Definition von Logikfragmenten angegeben. Dort wird des Weiteren die Vielseitigkeit dieses Begriffs von Logikfragmenten aufgezeigt, unter anderem durch Beschreibungen von Logikfragmenten durch C-Varietäten und durch Untersuchungen des Einflusses gewisser Prädikate auf die Ausdrucksstärke von Logikfragmenten. Der zweite Teil beschäftigt sich mit dem Zweivariablenfragment FO2 der Logik erster Stufe. Es wird eine kombinatorische Beschreibung durch sogenannte Ranker für alle Volllevel und alle Halblevel der FO2-Quantorenalternierungshierarchie über dem Ordnungsprädikat angegeben, sowohl mit als auch ohne Nachfolgerprädikat. Außerdem werden im zweiten Teil effektive algebraische Kriterien angegeben, die alle Voll- sowie alle Halblevel der FO2-Quantorenalternierungshierarchie über diversen Signaturen beschreiben, woraus sich insbesondere die Entscheidbarkeit des Definierbarkeitsproblems ergibt