Arithmetical complexity of first-order predicate fuzzy logics over distinguished semantics

From Mathfuzzlog
Jump to: navigation, search
Authors:
Franco Montagna
Carles Noguera
Title: Arithmetical complexity of first-order predicate fuzzy logics over distinguished semantics
Journal: Journal of Logic and Computation
Volume 20
Number 2
Pages: 399-424
Year: 2010
Preprint





Abstract

All promiment examples of first-order predicate fuzzy logics are undecidable. This leads to the problem of the arithmetical complexity of their sets of tautologies and satisfiable sentences. This paper is a contribution to the general study of this problem. We propose the classes of first-order core and $ \Delta $-core fuzzy logics as a good framework to address these arithmetical complexity issues. We obtain general results providing lower bounds for the complexities associated to arbitrary semantics and we compute upper bounds and exact positions in the arithmetical hierarchy for distinguished semantics: general semantics given by all chains, finite-chain semantics, standard semantics and rational semantics.