In 1950, B.A. Trakhtenbrot showed that the set of first-order tautologies associated to finite models is not recursively enumerable. In 1999, P. Hájek generalized this result to the first-order versions of Łukasiewicz, Gödel and Product logics, w.r.t. their standard algebras. In this paper we extend the analysis to the first-order versions of axiomatic extensions of MTL. Our main result is the following. Let K be a class of MTL-chains. Then the set of all first-order tautologies associated to the finite models over chains in K , {fTAUT^K}_∀ , is {Π^0}_1 -hard. Let TAUT_K be the set of propositional tautologies of K . If TAUT_K is decidable, we have that {fTAUT^K}_∀ is in {Π^0}_1 . We have similar results also if we expand the language with the Δ operator.

Trakhtenbrot Theorem and First-Order Axiomatic Extensions of MTL / M. Bianchi, F. Montagna. - In: STUDIA LOGICA. - ISSN 0039-3215. - 103:6(2015 May 16), pp. 1163-1181. [10.1007/s11225-015-9614-3]

Trakhtenbrot Theorem and First-Order Axiomatic Extensions of MTL

M. Bianchi;
2015

Abstract

In 1950, B.A. Trakhtenbrot showed that the set of first-order tautologies associated to finite models is not recursively enumerable. In 1999, P. Hájek generalized this result to the first-order versions of Łukasiewicz, Gödel and Product logics, w.r.t. their standard algebras. In this paper we extend the analysis to the first-order versions of axiomatic extensions of MTL. Our main result is the following. Let K be a class of MTL-chains. Then the set of all first-order tautologies associated to the finite models over chains in K , {fTAUT^K}_∀ , is {Π^0}_1 -hard. Let TAUT_K be the set of propositional tautologies of K . If TAUT_K is decidable, we have that {fTAUT^K}_∀ is in {Π^0}_1 . We have similar results also if we expand the language with the Δ operator.
Trakhtenbrot theorem; Many-valued logics; MTL logic; Residuated lattices; Completeness; Arithmetical complexity
Settore INF/01 - Informatica
Settore MAT/01 - Logica Matematica
Settore MAT/02 - Algebra
16-mag-2015
dic-2015
Article (author)
File in questo prodotto:
File Dimensione Formato  
art%3A10.1007%2Fs11225-015-9614-3.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 554.01 kB
Formato Adobe PDF
554.01 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/276815
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact