Trakhtenbrot Theorem and First-Order Axiomatic Extensions of MTL (vol 103, pg 1163, 2015)

被引：0

作者：

Bianchi, Matteo ^{[1
]}

Montagna, Franco ^{[2
]}

机构：

[1] Univ Milan, Dept Comp Sci, I-20135 Milan, Italy

[2] Univ Siena, Dept Informat Engn & Math, I-53100 Siena, Italy

来源：

STUDIA LOGICA | 2015年 / 103卷 / 06期

关键词：

Arithmetical complexity; Completeness; Many-valued logics; MTL logic; Residuated lattices; Trakhtenbrot theorem;

D O I：

10.1007/s11225-015-9633-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1950, B.A. Trakhtenbrot showed that the set of first-order tautologies associated to finite models is not recursively enumerable. In 1999, P. Hajek generalized this result to the first-order versions of Aukasiewicz, Godel 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 Delta operator.

引用

页码：1183 / 1183

页数：1