Substructural fuzzy logics are substructural logics that are complete with respect to algebras whose lattice reduct is the real unit interval [0.1]. In this paper, we introduce Uninorm logic UL as Multiplicative additive intuitionistic linear logic MAILL extended with the prelinearity axiom ((A → B) ∧ t) ∨ ((B → A) ∧ t). Axiomatic extensions of UL include known fuzzy logics such as Monoidal t-norm logic MTL and Gödel logic G, and new weakening-free logics. Algebraic semantics for these logics are (...) provided by subvarieties of (representable) pointed bounded commutative residuated lattices. Gentzen systems admitting cut-elimination are given in the framework of hypersequents. Completeness with respect to algebras with lattice reduct [0, 1] is established for UL and several extensions using a two-part strategy. First, completeness is proved for the logic extended with Takeuti and Titani's density rule. A syntactic elimination of the rule is then given using a hypersequent calculus. As an algebraic corollary, it follows that certain varieties of residuated lattices are generated by their members with lattice reduct [0, 1]. (shrink)

This paper is a contribution to Mathematical fuzzy logic, in particular to the algebraic study of t-norm based fuzzy logics. In the general framework of propositional core and Δ-core fuzzy logics we consider three properties of completeness with respect to any semantics of linearly ordered algebras. Useful algebraic characterizations of these completeness properties are obtained and their relations are studied. Moreover, we concentrate on five kinds of distinguished semantics for these logics–namely the class of algebras defined over the real unit (...) interval, the rational unit interval, the hyperreals , the strict hyperreals and finite chains, respectively–and we survey the known completeness methods and results for prominent logics. We also obtain new interesting relations between the real, rational and hyperreal semantics, and good characterizations for the completeness with respect to the semantics of finite chains. Finally, all completeness properties and distinguished semantics are also considered for the first-order versions of the logics where a number of new results are proved. (shrink)

In the present paper we show that any at most countable linearly-ordered commutative residuated lattice can be embedded into a commutative residuated lattice on the real unit interval [0, 1]. We use this result to show that Esteva and Godo''s logic MTL is complete with respect to interpretations into commutative residuated lattices on [0, 1]. This solves an open problem raised in.

The monoidal t-norm based logic MTL is obtained from Hájek''s Basic Fuzzy logic BL by dropping the divisibility condition for the strong (or monoidal) conjunction. Recently, Jenei and Montgana have shown MTL to be standard complete, i.e. complete with respect to the class of residuated lattices in the real unit interval [0,1] defined by left-continuous t-norms and their residua. Its corresponding algebraic semantics is given by pre-linear residuated lattices. In this paper we address the issue of standard and rational completeness (...) (rational completeness meaning completeness with respect to a class of algebras in the rational unit interval [0,1]) of some important axiomatic extensions of MTL corresponding to well-known parallel extensions of BL. Moreover, we investigate varieties of MTL algebras whose linearly ordered countable algebras embed into algebras whose lattice reduct is the real and/or the rational interval [0,1]. These embedding properties are used to investigate finite strong standard and/or rational completeness of the corresponding logics. (shrink)

The monoidal t-norm based logic MTL is obtained from Hájek's Basic Fuzzy logic BL by dropping the divisibility condition for the strong conjunction. Recently, Jenei and Montgana have shown MTL to be standard complete, i.e. complete with respect to the class of residuated lattices in the real unit interval [0, 1] defined by left-continuous t-norms and their residua. Its corresponding algebraic semantics is given by pre-linear residuated lattices. In this paper we address the issue of standard and rational completeness of (...) some important axiomatic extensions of MTL corresponding to well-known parallel extensions of BL. Moreover, we investigate varieties of MTL algebras whose linearly ordered countable algebras embed into algebras whose lattice reduct is the real and/or the rational interval [0, 1]. These embedding properties are used to investigate finite strong standard and/or rational completeness of the corresponding logics. (shrink)

In this paper we provide a finite axiomatization (using two finitary rules only) for the propositional logic (called $L\Pi$ ) resulting from the combination of Lukasiewicz and Product Logics, together with the logic obtained by from $L \Pi$ by the adding of a constant symbol and of a defining axiom for $\frac{1}{2}$ , called $L \Pi\frac{1}{2}$ . We show that $L \Pi \frac{1}{2}$ contains all the most important propositional fuzzy logics: Lukasiewicz Logic, Product Logic, Gödel's Fuzzy Logic, Takeuti and Titani's (...) Propositional Logic, Pavelka's Rational Logic, Pavelka's Rational Product Logic, the Lukasiewicz Logic with $\Delta$ , and the Product and Gödel's Logics with $\Delta$ and involution. Standard completeness results are proved by means of investigating the algebras corresponding to $L \Pi$ and $L \Pi \frac{1}{2}$ . For these algebras, we prove a theorem of subdirect representation and we show that linearly ordered algebras can be represented as algebras on the unit interval of either a linearly ordered field, or of the ordered ring of integers, Z. (shrink)

We prove that the sets of standard tautologies of predicate Product Logic and of predicate Basic Logic, as well as the set of standard-satisfiable formulas of predicate Basic Logic are not arithmetical, thus finding a rather satisfactory solution to three problems proposed by Hájek in [H01].

In this paper we give a rather detailed algebraic investigation of interpolation and Beth’s property in propositional many-valued logics extending Hájek’s Basic Logic [P. Hájek, Metamathematics of Fuzzy Logic, Kluwer, 1998], and we connect such properties with amalgamation and strong amalgamation in the corresponding varieties of algebras. It turns out that, while the most interesting extensions of in the language of have deductive interpolation, very few of them have Beth’s property or Craig interpolation. Thus in the last part of the (...) paper we look for conservative extensions of having such properties. (shrink)

We investigate the variety corresponding to a logic, which is the combination of ukasiewicz Logic and Product Logic, and in which Gödel Logic is interpretable. We present an alternative axiomatization of such variety. We also investigate the variety, called the variety of algebras, corresponding to the logic obtained from by the adding of a constant and of a defining axiom for one half. We also connect algebras with structures, called f-semifields, arising from the theory of lattice-ordered rings, and prove that (...) every algebra can be regarded as a structure whose domain is the interval [0, 1] of an f-semifield, and whose operations are the truncations of the operations of to [0, 1]. We prove that such a structure is uniquely determined by up to isomorphism, and we establish an equivalence between the category of algebras and that of f-semifields. (shrink)

This paper is devoted to the algebraization of an arithmetical predicate introduced by S. Feferman. To this purpose we investigate the equational class of Boolean algebras enriched with an operation (g=rtail), which translates such predicate, and an operation τ, which translates the usual predicate Theor. We deduce from the identities of this equational class some properties of (g=rtail) and some ties between (g=rtail) and τ; among these properties, let us point out a fixed-point theorem for a sufficiently large class of (...) (g=rtail)-τ polynomials. The last part of this paper concerns the duality theory for (g=rtail)-τ algebras. (shrink)

.Given a class C of t-norm BL-algebras, one may wonder which is the complexity of the set Taut of predicate formulas which are valid in any algebra in C. We first characterize the classes C for which Taut is recursively axiomatizable, and we show that this is the case iff C only consists of the Gödel algebra on [0,1]. We then prove that in all cases except from a finite number Taut is not even arithmetical. Finally we consider predicate monadic (...) logics TautM of classes C of t-norm BL-algebras, and we prove that they are undecidable. (shrink)

Solovay's 1976 completeness result for modal provability logic employs the recursion theorem in its proof. It is shown that the uses of the recursion theorem can in this proof be replaced by the diagonalization lemma for arithmetic and that, in effect, the proof neatly fits the framework of another, enriched, system of modal logic (the so-called Rosser logic of Gauspari-Solovay, 1979) so that any arithmetical system for which this logic is sound is strong enough to carry out the proof, in (...) particular I0+EXP. The method is adapted to obtain a similar completeness result for the Rosser logic. (shrink)

We show that the modal prepositional logicILM (interpretability logic with Montagna's principle), which has been shown sound and complete as the interpretability logic of Peano arithmetic PA (by Berarducci and Savrukov), is sound and complete as the logic ofπ 1-conservativity over eachbE 1-sound axiomatized theory containingI⌆ 1 (PA with induction restricted tobE 1-formulas). Furthermore, we extend this result to a systemILMR obtained fromILM by adding witness comparisons in the style of Guaspari's and Solovay's logicR (this will be done in a (...) separate continuation of the present paper). (shrink)

Solovay's 1976 completeness result for modal provability logic employs the recursion theorem in its proof. It is shown that the uses of the recursion theorem can in this proof replaced by the diagonalization lemma for arithmetic and that, in effect, the proof neatly fits the framework of another, enriched, system of modal logic so that any arithmetical system for which this logic is sound is strong enough to carry out the proof, in particular $\text{I}\Delta _{0}+\text{EXP}$ . The method is adapted (...) to obtain a similar completeness result for the Rosser logic. (shrink)

This paper deals with Kripke-style semantics for many-valued logics. We introduce various types of Kripke semantics, and we connect them with algebraic semantics. As for modal logics, we relate the axioms of logics extending MTL to properties of the Kripke frames in which they are valid. We show that in the propositional case most logics are complete but not strongly complete with respect to the corresponding class of complete Kripke frames, whereas in the predicate case there are important many-valued logics (...) like BL, Ł and Π, which are not even complete with respect to the class of all predicate Kripke frames in which they are valid. Thus although very natural, Kripke semantics seems to be slightly less powerful than algebraic semantics. (shrink)

The present paper deals with the predicate version MTL of the logic MTL by Esteva and Godo. We introduce a Kripke semantics for it, along the lines of Ono''s Kripke semantics for the predicate version of FLew (cf. [O85]), and we prove a completeness theorem. Then we prove that every predicate logic between MTL and classical predicate logic is undecidable. Finally, we prove that MTL is complete with respect to the standard semantics, i.e., with respect to Kripke frames on the (...) real interval [0,1], or equivalently, with respect to MTL-algebras whose lattice reduct is [0,1] with the usual order. (shrink)

To the standard propositional modal system of provability logic constants are added to account for the arithmetical fixed points introduced by Bernardi-Montagna in [5]. With that interpretation in mind, a system LR of modal propositional logic is axiomatized, a modal completeness theorem is established for LR and, after that, a uniform arithmetical completeness theorem with respect to PA is obtained for LR.

A t-tautology is a propositional formula which is a tautology in all fuzzy logics defined by continuous triangular norms. In this paper we show that the problem of recognizing t-tautologies is coNP complete, and thus decidable.

In this paper we provide a categorical equivalence for the category \ of product algebras, with morphisms the homomorphisms. The equivalence is shown with respect to a category whose objects are triplets consisting of a Boolean algebra B, a cancellative hoop C and a map \ from B × C into C satisfying suitable properties. To every product algebra P, the equivalence associates the triplet consisting of the maximum boolean subalgebra B, the maximum cancellative subhoop C, of P, and the (...) restriction of the join operation to B × C. Although several equivalences are known for special subcategories of \ , up to our knowledge, this is the first equivalence theorem which involves the whole category of product algebras. The syntactic counterpart of this equivalence is a syntactic reduction of classical logic CL and of cancellative hoop logic CHL to product logic, and viceversa. (shrink)

In this paper we show that the subvarieties of BL, the variety of BL-algebras, generated by single BL-chains on [0, 1], determined by continous t-norms, are finitely axiomatizable. An algorithm to check the subsethood relation between these subvarieties is provided, as well as another procedure to effectively find the equations of each subvariety. From a logical point of view, the latter corresponds to find the axiomatization of every residuated many-valued calculus defined by a continuous t-norm and its residuum. Actually, the (...) paper proves the results for a more general class than t-norm BL-chains, the so-called regular BL-chains. (shrink)

The undecidability of the first-order theory of diagonalizable algebras is shown here.

.This paper is devoted to a logical and algebraic treatment of conditional probability. The main ideas are the use of non-standard probabilities and of some kind of standard part function in order to deal with the case where the conditioning event has probability zero, and the use of a many-valued modal logic in order to deal probability of an event φ as the truth value of the sentence φ is probable, along the lines of Hájek’s book [H98] and of [EGH96]. (...) To this purpose, we introduce a probabilistic many-valued logic, called FP, which is sound and complete with respect a class of structures having a non-standard extension [0,1]⋆ of [0,1] as set of truth values. We also prove that the coherence of an assessment of conditional probabilities is equivalent to the coherence of a suitably defined theory over FP whose proper axioms reflect the assessment itself. (shrink)

In Hájek et al. (J Symb Logic 65(2):669–682, 2000) the authors introduce the concept of supersound logic, proving that first-order Gödel logic enjoys this property, whilst first-order Łukasiewicz and product logics do not; in Hájek and Shepherdson (Ann Pure Appl Logic 109(1–2):65–69, 2001) this result is improved showing that, among the logics given by continuous t-norms, Gödel logic is the only one that is supersound. In this paper we will generalize the previous results. Two conditions will be presented: the first (...) one implies the supersoundness and the second one non-supersoundness. To develop these results we will use, between the other machineries, the techniques of completions of MTL-chains developed in Labuschagne and van Alten (Proceedings of the ninth international conference on intelligent technologies, 2008) and van Alten (2009). We list some of the main results. The first-order versions of MTL, SMTL, IMTL, WNM, NM, RDP are supersound; the first-order version of an axiomatic extension of BL is supersound if and only it is n-potent (i.e. it proves the formula ${\varphi^{n}\,\to\,\varphi^{n\,{+}\,1}}$ for some ${n\,\in\,\mathbb{N}^+}$ ). Concerning the negative results, we have that the first-order versions of ΠMTL, WCMTL and of each non-n-potent axiomatic extension of BL are not supersound. (shrink)

For every sequence |p n } n of formulas of Peano ArithmeticPA with, every formulaA of the first-order theory diagonalizable algebras, we associate a formula 0 A, called the value ofA inPA with respect to the interpretation. We show that, ifA is true in every diagonalizable algebra, then, for every, 0 A is a theorem ofPA.

In the field of many-valued logics, Hájek’s Basic Logic BL was introduced in Hájek (Metamathematics of fuzzy logic, trends in logic. Kluwer Academic Publishers, Berlin, 1998). In this paper we will study four families of n-contractive (i.e. that satisfy the axiom ${\phi^n\rightarrow\phi^{n+1}}$ , for some ${n\in\mathbb{N}^+}$ ) axiomatic extensions of BL and their corresponding varieties: BL n , SBL n , BL n and SBL n . Concerning BL n we have that every BL n -chain is isomorphic to an (...) ordinal sum of MV-chains of at most n + 1 elements, whilst every BL n -chain is isomorphic to an ordinal sum of MV n -chains (for SBL n and SBL n a similar property holds, with the difference that the first component must be the two elements boolean algebra); all these varieties are locally finite. Moving to the content of the paper, after a preliminary section, we will study generic and k-generic algebras, completeness and computational complexity results, amalgamation and interpolation properties. Finally, we will analyze the first-order versions of these logics, from the point of view of completeness and arithmetical complexity. (shrink)

A logic for classical conditional events was investigated by Dubois and Prade. In their approach, the truth value of a conditional event may be undetermined. In this paper we extend the treatment to many-valued events. Then we support the thesis that probability over partially undetermined events is a conditional probability, and we interpret it in terms of bets in the style of de Finetti. Finally, we show that the whole investigation can be carried out in a logical and algebraic setting, (...) and we find a logical characterization of coherence for assessments of partially undetermined events. (shrink)

In this paper we investigate the connections between quantifier elimination, decidability and Uniform Craig Interpolation in Δ-core fuzzy logics added with propositional quantifiers. As a consequence, we are able to prove that several propositional fuzzy logics have a conservative extension which is a Δ-core fuzzy logic and has Uniform Craig Interpolation.

In [10] it is claimed that the set of predicate tautologies of all complete BL-chains and the set of all standard tautologies coincide. As noticed in [11], this claim is wrong. In this paper we show that a complete BL-chain B satisfies all standard BL-tautologies iff for any transfinite sequence of elements of B, the condition ∧i ∈ I = 2 holds in B.

In this paper the modal operator "x is provable in Peano Arithmetic" is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.

In this paper we investigate fuzzy propositional and first order logics which are complete or strongly complete with respect to a single chain, and we relate this properties with the existence of a universal chain for the logic.

It is shown that the propositional modal logic IRM (interpretability logic with Montagna's principle and with witness comparisons in the style of Guaspari's and Solovay's logicR) is sound and complete as the logic ofII 1-conservativity over each∑ 1-sound axiomatized theory containingI∑ 1. The exact statement of the result uses the notion of standard proof predicate. This paper is an immediate continuation of our paper [HM]. Knowledge of [HM] is presupposed. We define a modal logic, called IRM, which includes both ILM (...) andR (the logic of [GS]) and prove an arithmetical completeness theorem in the style of [GS], thus showing that IRM is the logic ofII 1-conservativity with witness comparisons. The reader is recommended to have Smoryński's book [Sm] at his/her disposal. (shrink)

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. (shrink)

This note contains a correct proof of the fact that the set of all first-order formulas which are valid in all predicate Kripke frames for Hájek's many-valued logic BL is not arithmetical. The result was claimed in [5], but the proof given there was incorrect.

To the standard propositional modal system of provability logic constants are added to account for the arithmetical fixed points introduced by Bernardi-Montagna in [5]. With that interpretation in mind, a system LR of modal propositional logic is axiomatized, a modal completeness theorem is established for LR and, after that, a uniform arithmetical (Solovay-type) completeness theorem with respect to PA is obtained for LR.

We consider two players each of whom attempts to predict the behavior of the other, using no more than the history of earlier predictions. Behaviors are limited to a pair of options, conventionally denoted by 0, 1. Such players face the problem of learning to coordinate choices. The present paper formulates their situation recursion theoretically, and investigates the prospects for success. A pair of players build up a matrix with two rows and infinitely many columns, and are said to “learn” (...) each other if cofinitely many of the columns show the same number in both rows (either 0 or 1). Among other results we prove that there are two collections of players that force all other players to choose their camp. Each collection is composed of players that learn everyone else in the same collection, but no player that learns all members of one collection learns any member of the other. (shrink)

This paper is devoted to the algebraization of theories in which, as in Peano arithmetic, there is a formula, Theor(x), numerating the set of theorems, and satisfying Hilbert-Bernays derivability conditions. In particular, we study the diagonalizable algebras, which are been introduced by R. Magari in [6], [7]. We prove that for every natural number n, the n-freely generated algebra $\germ{J}_{n}$ is not functionally free in the equational class of diagonalizable algebras; we also prove that the diagonalizable algebra of Peano arithmetic (...) is not an element of the equational class generated by $\{\germ{J}_{n}\}$. (shrink)

We present a complete and cut-free proof-system for a fragment of MTL, where modal operators are only labelled by bounded intervals with rational endpoints.

Following some ideas of Roberto Magari, we propose trial and error probabilistic functions, i.e. probability measures on the sentences of arithmetic that evolve in time by trial and error. The set ℐ of the sentences that get limit probability 1 is a Π3—theory, in fact ℐ can be a Π3—complete set. We prove incompleteness results for this setting, by showing for instance that for every k > 0 there are true Π3—sentences that get limit probability less than 1/2k. No set (...) ℐ as above can contain the set of all true Π3—sentences, although we exhibit some ℐ containing all the true Σ2—sentences. We also consider an approach based on the notions of inner probability and outer probability, and we compare this approach with the one based on trial and error probabilistic functions. Although the two approaches are shown to be different, we single out an important case in which they are equivalent. (shrink)

It is shown that for arithmetical interpretations that may include free variables it is not the Guaspari-Solovay system R that is arithmetically complete, but their system R –. This result is then applied to obtain the nonvalidity of some rules under arithmetical interpretations including free variables, and to show that some principles concerning Rosser orderings with free variables cannot be decided, even if one restricts oneself to usual proof predicates.