Properties of Monadic Fuzzy Predicate Logics

Petr Hájek, Prague

Ł∀, G∀, Π∀ denote the three most important particular t-norm predicate logics: Łukasiewicz, Gödel and product logic. Their set of thruth values is the real unit interval and the semantics is fully determined by the corresponding continuous t-norm as the truth function of conjunction. (See [1] for metamathematics of t-norm based logics.) Each of them has two monadic counterparts: mon-Ł∀ is Ł∀ with only unary predicates and mon_{1}-Ł∀ is Ł∀ with only unary predicates and only one object variable. Similarly for G∀ and Π∀. For each logic, TAUT is the set of all tautologies (formulas true, i.e. having truth value 1 in each interpretation), f-TAUT is the set of all finite tautologies (true in each finite interpretation) and similarly for SAT, f-SAT (true in at least one [finite] interpretation). Finite model properties: FMP1 is TAUT = f-TAUT, FMP2 is SAT = f-SAT. What is the arithmetical complexity of these sets? What finite model properties hold? We summarize the results (some of them are found in [1], [2], [3]).

Theorem (1) For Ł∀, TAUT is Π_{2}-complete, f-TAUT is Π_{1}-complete, both FMP1 and FMP2 is false. For mon-Ł∀, FMP1 is true but FMP2 not; TAUT = f-TAUT is in Π_{1}. For mon_{1}Ł∀, both FMP1 and FMP2 is true, TAUT = f-TAUT is Δ_{1}.

(2) Both FMP1 and FMP2 are false for mon_{1}-G∀ (hence for mon-G∀ and G∀). For G∀, TAUT is Σ_{1}-complete and f-TAUT is Π_{1}-complete.

(3) For Π∀, TAUT is Π_{2}-hard and f-TAUT is Π_{1}-complete. Both FMP1 and FMP2 fails for mon_{1}-Π∀.

References [1] P. Hájek: Metamathematics of fuzzy logic, Kluwer 1998.

[2] P. Hájek: Trakhtenbrot theorem and fuzzy logic. In: (Gottlob et al., ed.) Computer Science Logic, Springer Verlag 1999, p. 1-8.

[3] M. Ragaz: Die Unentscheidbarkeit der einstelligen unendlichwertigen Prädikatenlogik. Arch. Math. Logik 23 (1983) 129-139.

Address: Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod vodarenskou vezi 2, 182 07 Prague, Czech Republic

E-mail: hajek@cs.cas.cz