Showing 1 to 19 of 19 matching Articles
Results per page:
Export (CSV)
By
Montagna, Franco
9 Citations
For every sequence ϕ ≡ p_{n}}_{n∈ω} of formulas of Peano ArithmeticPA with, every formulaA of the firstorder 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.
more …
By
Jongh, Dick; Montagna, Franco
3 Citations
It is shown that for arithmetical interpretations that may include free variables it is not the GuaspariSolovay 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.
more …
By
Montagna, Franco
27 Citations
We prove that the sets of standard tautologies of predicate Product Logic and of predicate Basic Logic, as well as the set of standardsatisfiable formulas of predicate Basic Logic are not arithmetical, thus finding a rather satisfactory solution to three problems proposed by Hájek in [H01].
more …
By
Montagna, Franco
6 Citations
The undecidability of the firstorder theory of diagonalizable algebras is shown here.
By
Jongh, Dick; Jumelet, Marc; Montagna, Franco
10 Citations
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 socalled Rosser logic of GauspariSolovay, 1979) so that any arithmetical system for which this logic is sound is strong enough to carry out the proof, in particular IΔ_{0}+EXP. The method is adapted to obtain a similar completeness result for the Rosser logic.
more …
By
Jenei, Sándor; Montagna, Franco
126 Citations
In the present paper we show that any at most countable linearlyordered 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.
more …
By
Montagna, Franco; Sommaruga, Giovanni
1 Citations
In this note, a fully modal proof is given of some conservation results proved in a previous paper by arithmetic means. The proof is based on the extendability of Kripke models.
By
Bianchi, Matteo; Montagna, Franco
In 1950, B.A. Trakhtenbrot showed that the set of firstorder tautologies associated to finite models is not recursively enumerable. In 1999, P. Hájek generalized this result to the firstorder versions of Łukasiewicz, Gödel and Product logics, w.r.t. their standard algebras. In this paper we extend the analysis to the firstorder versions of axiomatic extensions of MTL. Our main result is the following. Let
$${\mathbb{K}}$$
be a class of MTLchains. Then the set of all firstorder tautologies associated to the finite models over chains in
$${\mathbb{K}}$$
, fTAUT
$${_{\forall}^{\mathbb{K}}}$$
, is
$${\Pi_{1}^{0}}$$
hard. Let TAUT
$${_\mathbb{K}}$$
be the set of propositional tautologies of
$${\mathbb{K}}$$
. If TAUT
$${_{\mathbb{K}}}$$
is decidable, we have that fTAUT
$${_{\forall}^{\mathbb{K}}}$$
is in
$${\Pi_{1}^{0}}$$
. We have similar results also if we expand the language with the Δ operator.
more …
By
Montagna, Franco
3 Citations
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.
more …
By
Montagna, Franco; Simi, Giulia
1 Citations
We investigate many paradigms of identifications for classes of languages (namely: consistent learning, EX learning, learning with finitely many errors, behaviorally correct learning, and behaviorally correct learning with finitely many errors) in a measuretheoretic context, and we relate such paradigms to their analogues in learning on informants. Roughly speaking, the results say that most paradigms in measuretheoretic learning wrt some classes of distributions (called δ canonical) are equivalent to the corresponding paradigms for identification on informants.
more …
By
Esteva, Francesc; Gispert, Joan; Godo, Lluís; Montagna, Franco
Show all (4)
73 Citations
The monoidal tnorm 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 leftcontinuous tnorms and their residua. Its corresponding algebraic semantics is given by prelinear 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 wellknown 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.
more …
By
Montagna, Franco
12 Citations
Summary
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 ϱ, 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 ϱ and some ties between ϱ and τ; among these properties, let us point out a fixedpoint theorem for a sufficiently large class of ϱτ polynomials. The last part of this paper concerns the duality theory for ϱτ algebras.
more …
By
Montagna, Franco
3 Citations
Summary
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 HilbertBernays 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 numbern, thenfreely generated algebraF_{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 byF_{n}.
more …
By
Luchi, Duccio; Montagna, Franco
4 Citations
The logic of proofs was introduced by Artemov in order to analize the formalization of the concept of proof rather than the concept of provability. In this context, some operations on proofs play a very important role. In this paper, we investigate some very natural operations, paying attention not only to positive information, but also to negative information (i.e. information saying that something cannot be a proof). We give a formalization for a fragment of such a logic of proofs, and we prove that our fragment is complete and decidable.
more …
By
Montagna, Franco; Ono, Hiroakira
27 Citations
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 FL_{ew} (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 MTLalgebras whose lattice reduct is [0,1] with the usual order.
more …
By
Esteva, Fransesc; Godo, Lluís; Montagna, Franco
39 Citations
In this paper we show that the subvarieties of BL, the variety of BLalgebras, generated by single BLchains on [0, 1], determined by continous tnorms, 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 manyvalued calculus defined by a continuous tnorm and its residuum. Actually, the paper proves the results for a more general class than tnorm BLchains, the socalled regular BLchains.
more …
By
Montagna, Franco; Ugolini, Sara
6 Citations
In this paper we provide a categorical equivalence for the category
$${\mathcal{P}}$$
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
$${\vee_e}$$
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(P), the maximum cancellative subhoop C(P), of P, and the restriction of the join operation to B × C. Although several equivalences are known for special subcategories of
$${\mathcal{P}}$$
, 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.
more …
By
Jongh, Dick H. J.; Montagna, Franco
3 Citations
To the standard propositional modal system of provability logic constants are added to account for the arithmetical fixed points introduced by BernardiMontagna 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 (Solovaytype) completeness theorem with respect to PA is obtained for LR.
more …
