Speaker
Mariami Gamsakhurdia
Vienna University of Technology
Talks at this conference:
Friday, 14:25, J330 
Goedel logics: prenex fragments 
Authors: Matthias Baaz and Mariami Gamsakhurdia One of the first recognised characteristics of classical logic is the existence of prenex forms for each formula. The quantifiershifting rules are used nonuniquely to construct these prenex forms. The expressive power of prenex fragments is easy to see in classical logic because it coincides with the whole logic, and in Intuitionistic logic since the prenex formulas are very weak (the validity of the prenex formula is decidable). However, because Gödel logics are intermediary logics, the expressibility of its prenex is relatively important. It is clear that prenex normal forms cannot be constructed in the usual sense in Gödel logics because some of the quantifiershift rules may fail, but this does not imply that no prenex normal form exists. However, demonstrating that such prenex forms do not exist is more difficult. Prenexation does not work for \(G_{[0,1]}\) when \(0\) is not isolated, since the formula \((\neg \forall x A(x)\wedge \forall x \neg \neg A(x))\) does not allow a prenex normal form. To prove this fact, we use the glueing argument, which is not easy to see. This result can be extended to all Gödel logics where there is one accumulation point from above, even if it is not \(0\). In this talk, we provide the complete classification for the firstorder Gödel logics after the property that the formulas admit logically equivalent prenex normal forms. We show that the only firstorder Gödel logics that admit such prenex forms are those with finite truth value sets since they allow all quantifiershift rules and the logic \(G_\uparrow\) with only one accumulation point at \(1\). In all the other cases, when there is at least one accumulation point from above, all accumulation points are from above, and all accumulation points are from below; there are no logically equivalent prenex normal forms. We will also see that \(G_\uparrow\) is the intersection of all finite firstorder Gödel logics. The second stage of our research investigates the existence of the validity equivalent prenex normal form. Gödel logics with a finite truth value set admit such prenex forms. Gödel logics with an uncountable truth value set have the prenex normal form if and only if every surrounding of \(0\) is uncountable or \(0\) is an isolated point. Otherwise, uncountable Gödel logics are incomplete, and the prenex fragment is always complete with respect to the uncountable truth value set. Therefore, there is no effective translation to the valid formula and the valid prenex form. The countable case, however, is still up for debate. Bibliography
