Trakhtenbrot Theorem and First-Order Axiomatic Extensions of MTL

Studia Logica 103 (6):1163-1181 (2015)
  Copy   BIBTEX


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 \ be a class of MTL-chains. Then the set of all first-order tautologies associated to the finite models over chains in \, fTAUT\, is \ -hard. Let TAUT\ be the set of propositional tautologies of \. If TAUT\ is decidable, we have that fTAUT\ is in \. We have similar results also if we expand the language with the Δ operator



    Upload a copy of this work     Papers currently archived: 92,369

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

n-Contractive BL-logics.Matteo Bianchi & Franco Montagna - 2011 - Archive for Mathematical Logic 50 (3-4):257-285.
Substructural Fuzzy Logics.George Metcalfe & Franco Montagna - 2007 - Journal of Symbolic Logic 72 (3):834 - 864.
On n -contractive fuzzy logics.Rostislav Horčík, Carles Noguera & Milan Petrík - 2007 - Mathematical Logic Quarterly 53 (3):268-288.
Generalized ordinal sums and translations.Nikolaos Galatos - 2011 - Logic Journal of the IGPL 19 (3):455-466.
The fundamental theorem of ultraproduct in Pavelka's logic.Mingsheng Ying - 1992 - Mathematical Logic Quarterly 38 (1):197-201.
First-order Nilpotent minimum logics: first steps.Matteo Bianchi - 2013 - Archive for Mathematical Logic 52 (3-4):295-316.
A note on the first‐order logic of complete BL‐chains.Petr Hájek & Franco Montagna - 2008 - Mathematical Logic Quarterly 54 (4):435-446.
Strict core fuzzy logics and quasi-witnessed models.Marco Cerami & Francesc Esteva - 2011 - Archive for Mathematical Logic 50 (5-6):625-641.
Interpretability over peano arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.


Added to PP

30 (#536,951)

6 months
13 (#202,760)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Lindström theorems in graded model theory.Guillermo Badia & Carles Noguera - 2021 - Annals of Pure and Applied Logic 172 (3):102916.

Add more citations