zbMATH — the first resource for mathematics

Arithmetical complexity of first-order predicate fuzzy logics over distinguished semantics. (English) Zbl 1198.03032
There is a large family of mathematical fuzzy logics. All of them are (at least historically) t-norm-based, and they have quite different semantics, as discussed recently by P. Cintula et al. [Ann. Pure Appl. Logic 160, No. 1, 53–81 (2009; Zbl 1168.03052)]. For their first-order versions, the most prominent examples among them have undecidable \(\alpha\)-validity and \(\alpha\)-satisfiability problems, \(\alpha\) here means \((=1)\) or \((>0)\), as surveyed recently by P. Hájek [Ann. Pure Appl. Logic 161, No. 2, 212–219 (2009; Zbl 1182.03050)].
This interesting paper gives a more global approach to these arithmetical complexity issues. The authors restrict their considerations to core or \(\Delta\)-core fuzzy logics, i.e., they consider extensions of MTL that satisfy suitably generalized versions of a deduction theorem and of the substitutivity of equivalents. But they consider quite different semantics for these logics. The paper offers lower bounds for the complexities associated with general semantics, and it gives upper bounds as well as exact positions in the arithmetic hierarchy for certain distinguished semantics like finite-chain semantics, standard semantics, and also rational semantics.

03B52 Fuzzy logic; logic of vagueness
03D35 Undecidability and degrees of sets of sentences
03B50 Many-valued logic
PDF BibTeX Cite
Full Text: DOI