Arithmetical Complexity of First-Order Fuzzy Logics. Chapter 11

Authors: Petr Hájek, F. Montagna, C. Noguera
Publication year: 2011
Publication type: Kapitola v monografii
Periodical: Handbook of Mathematical Fuzzy Logic
Projects: Logical Models of Reasoning with Vague Information
Mathematical Fuzzy Logic in Computer Science
Bibliographic citation: HÁJEK, Petr, MONTAGNA, F., NOGUERA, C. Arithmetical Complexity of First-Order Fuzzy Logics. Chapter 11. In: CINTULA, P., HÁJEK, P., NOGUERA, C., eds. Handbook of Mathematical Fuzzy Logic. 2. London: College Publications, 2011, S. 853-908. Studies in Logic - Mathematical Logic and Foundations, 38. ISBN 978-1-84890-054-7.
ID: 372990

Abstract

The main problem in this chapter is not whether a given predicate logic is decidable or not, but rather how undecidable it is, i.e. what is its undecidability degree. For the general semantics, the undecidability degrees are low. For the standard semantics, it depends: in the cases where we have standard completeness, like MTL or IMTL, the undecidability degrees are trivially as in the general semantics, in other cases, like Łukasiewicz first-order logic, the undecidability degrees are higher but still in the arithmetical hierarchy, while in product logic or in BL logic both tautologicity and satisfiability for the standard semantics fall outside the arithmetical hierarchy.