Implicational (semilinear) logics I: a new hierarchy

In abstract algebraic logic, the general study of propositional non-classical logics has been traditionally based on the abstraction of the Lindenbaum-Tarski process. In this process one considers the Leibniz relation of indiscernible formulae. Such approach has resulted in a classification of logics partly based on generalizations of equivalence connectives: the Leibniz hierarchy. This paper performs an analogous abstract study of non-classical logics based on the kind of generalized implication connectives they possess. It yields a new classification of logics expanding Leibniz hierarchy: the hierarchy of implicational logics. In this framework the notion of implicational semilinear logic can be naturally introduced as a property of the implication, namely a logic L is an implicational semilinear logic iff it has an implication such that L is complete w.r.t. the matrices where the implication induces a linear order, a property which is typically satisfied by well-known systems of fuzzy logic. The hierarchy of implicational logics is then restricted to the semilinear case obtaining a classification of implicational semilinear logics that encompasses almost all the known examples of fuzzy logics and suggests new directions for research in the field.     

Symmetric implicational method of fuzzy reasoning

Fuzzy reasoning should take into account the factors of both the logic system and the reasoning model, thus a new fuzzy reasoning method called the symmetric implicational method is proposed, which contains the full implication inference method as its particular case. The previous full implication inference principles are improved, and unified forms of the new method are respectively established for FMP (fuzzy modus ponens) and FMT (fuzzy modus tollens) to let different fuzzy implications be used under the same way. Furthermore, reversibility properties of the new method are analyzed from some conditions that many fuzzy implications satisfy, and it is found that its reversibility properties seem fine. Lastly, the more general α-symmetric implicational method is put forward, and its unified forms are achieved.     

Proof complexity of intuitionistic implicational formulas

We study implicational formulas in the context of proof complexity of intuitionistic propositional logic (IPC). On the one hand, we give an efficient transformation of tautologies to implicational tautologies that preserves the lengths of intuitionistic extended Frege (EF) or substitution Frege (SF) proofs up to a polynomial. On the other hand, EF proofs in the implicational fragment of IPC polynomially simulate full intuitionistic logic for implicational tautologies. The results also apply to other fragments of other superintuitionistic logics under certain conditions.In particular, the exponential lower bounds on the length of intuitionistic EF proofs by Hrube? (2007), generalized to exponential separation between EF and SF systems in superintuitionistic logics of unbounded branching by Je?ábek (2009), can be realized by implicational tautologies.     

Robustness analysis of full implication inference method

This paper investigates the robustness of the full implication inference method and fully implicational restriction method for fuzzy reasoning based on two basic inference models: fuzzy modus ponens and fuzzy modus tollens. Some robustness results are proved based on general left continuous t-norms and induced residuated implications, and some important fuzzy implications.     

Pure morphisms in pro-categories

Pure epimorphisms in categories pro-C, which essentially are just inverse limits of split epimorphisms in C, were recently studied by J. Dydak and F.R.R. del Portal in connection with Borsuk’s problem of descending chains of retracts of ANRs. We prove that pure epimorphisms are regular epimorphisms whenever C has weak finite limits, or pullbacks, or copowers. This improves the results of the above paper, and the results of the present authors on pure subobjects in accessible categories. We also turn to pure monomorphisms in pro-C, essentially just inverse limits of split monomorphisms in C, and prove that they are regular monomorphisms whenever C has finite products or pushouts.     

Some properties of epimorphisms of Hilbert algebras

This paper represents a start in the study of epimorphisms in some categories of Hilbert algebras. Even if we give a complete characterization for such epimorphisms only for implication algebras, the following results will make possible the construction of some examples of epimorphisms which are not surjective functions. Also, we will show that the study of epimorphisms of Hilbert algebras is equivalent with the study of epimorphisms of Hertz algebras.     

Closure Operators in Convergence Spaces

We define two closure operators of some well-known topological categories and investigate the relationships between these closure operators and the one that is given in [9]. As a consequence, we characterize separation properties T ₀, T ₁, and T ₂ for these well-known categories and compare them with the ones that are given in [3] and [6]. Finally, we characterize the epimorphisms in the subcategories of these given categories. This revised version was published online in June 2006 with corrections to the Cover Date.     

Cut-free formulations for a quantified logic of here and there

A predicate extension SQHT⁼ of the logic of here-and-there was introduced by V. Lifschitz, D. Pearce, and A. Valverde to characterize strong equivalence of logic programs with variables and equality with respect to stable models. The semantics for this logic is determined by intuitionistic Kripke models with two worlds (here and there) with constant individual domain and decidable equality. Our sequent formulation has special rules for implication and for pushing negation inside formulas. The soundness proof allows us to establish that SQHT⁼ is a conservative extension of the logic of weak excluded middle with respect to sequents without positive occurrences of implication. The completeness proof uses a non-closed branch of a proof search tree. The interplay between rules for pushing negation inside and truth in the “there” (non-root) world of the resulting Kripke model can be of independent interest. We prove that existence is definable in terms of remaining connectives.     

On universal central extensions of precrossed and crossed modules

We study the connection between universal central extensions in the categories of precrossed and crossed modules. They are compared with several kinds of universal central extensions in the categories of groups, epimorphisms of groups, groups with operators and modules over a group. We study the relationship between the homologies defined in these categories. Applications to relative algebraic K-theory are also obtained.     

Exactness of direct limits for abelian categories with an injective cogenerator

We prove that the exactness of direct limits in an abelian category with products and an injective cogenerator J is equivalent to a condition on J which is well-known to characterize pure-injectivity in module categories, and we describe an application of this result to the tilting theory. We derive our result as a consequence of a more general characterization of when inverse limits in the Eilenberg–Moore category of a monad on the category of sets preserve regular epimorphisms.     

An embedding theorem for regular Mal'tsev categories

In this paper, we obtain a non-abelian analogue of Lubkin's embedding theorem for abelian categories. Our theorem faithfully embeds any small regular Mal'tsev category $\mathbb{C}$ in an n-th power of a particular locally finitely presentable regular Mal'tsev category. The embedding preserves and reflects finite limits, isomorphisms and regular epimorphisms, as in the case of Barr's embedding theorem for regular categories. Furthermore, we show that we can take n to be the (cardinal) number of subobjects of the terminal object in $\mathbb{C}$.     

Monomorphisms and epimorphisms in pro-categories

A morphism of a category which is simultaneously an epimorphism and a monomorphism is called a bimorphism. We give characterizations of monomorphisms (respectively, epimorphisms) in pro-category pro-C, provided C has direct sums (respectively, pushouts).Let E(C) (respectively, M(C)) be the subcategory of C whose morphisms are epimorphisms (respectively, monomorphisms) of C. We give conditions in some categories C for an object X of pro-C to be isomorphic to an object of pro-E(C) (respectively, pro-M(C)).A related class of objects of pro-C consists of X such that there is an epimorphism X→P∈Ob(C) (respectively, a monomorphism P∈Ob(C)→X). Characterizing those objects involves conditions analogous (respectively, dual) to the Mittag-Leffler property. One should expect that the object belonging to both classes ought to be stable. It is so in the case of pro-groups. The natural environment to discuss those questions are balanced categories with epimorphic images. The last part of the paper deals with that question in pro-homotopy.     

Problems in algebra inspired by universal algebraic geometry

Let Θ be a variety of algebras. In every variety Θ and every algebra H from Θ one can consider algebraic geometry in Θ over H. We also consider a special categorical invariant K _Θ of this geometry. The classical algebraic geometry deals with the variety Θ = Com-P of all associative and commutative algebras over the ground field of constants P. An algebra H in this setting is an extension of the ground field P. Geometry in groups is related to the varieties Grp and Grp-G, where G is a group of constants. The case Grp-F, where F is a free group, is related to Tarski’s problems devoted to logic of a free group. The described general insight on algebraic geometry in different varieties of algebras inspires some new problems in algebra and algebraic geometry. The problems of such kind determine, to a great extent, the content of universal algebraic geometry. For example, a general and natural problem is: When do algebras H ₁ and H ₂ have the same geometry? Or more specifically, what are the conditions on algebras from a given variety Θ that provide the coincidence of their algebraic geometries? We consider two variants of coincidence: 1) K _Θ(H ₁) and K _Θ(H ₂) are isomorphic; 2) these categories are equivalent. This problem is closely connected with the following general algebraic problem. Let Θ⁰ be the category of all algebras W = W(X) free in Θ, where X is finite. Consider the groups of automorphisms Aunt(Θ⁰) for different varieties Θ and also the groups of autoequivalences of Θ⁰. The problem is to describe these groups for different Θ.     

Separation and Epimorphisms in Quasi-Uniform Spaces

We study some categorical aspects of quasi-uniform spaces (mainly separation and epimorphisms) via closure operators in the sense of Dikranjan, Giuli, and Tholen. In order to exploit better the corresponding properties known for topological spaces we describe the behaviour of closure operators under the lifting along the forgetful functor T from quasi-uniform spaces to topological spaces. By means of appropriate closure operators we compute the epimorphisms of many categories of quasi-uniform spaces defined by means of separation axioms and study the preservation (reflection) of epimorphisms under the functor T.     

Embedding classical in minimal implicational logic

Consider the problem which set V of propositional variables suffices for whenever , where , and ?_c and ?_i denote derivability in classical and intuitionistic implicational logic, respectively. We give a direct proof that stability for the final propositional variable of the (implicational) formula A is sufficient; as a corollary one obtains Glivenko's theorem. Conversely, using Glivenko's theorem one can give an alternative proof of our result. As an alternative to stability we then consider the Peirce formula . It is an easy consequence of the result above that adding a single instance of the Peirce formula suffices to move from classical to intuitionistic derivability. Finally we consider the question whether one could do the same for minimal logic. Given a classical derivation of a propositional formula not involving ⊥, which instances of the Peirce formula suffice as additional premises to ensure derivability in minimal logic? We define a set of such Peirce formulas, and show that in general an unbounded number of them is necessary.     

Recovering a Logic from Its Fragments by Meta-Fibring

In this paper we address the question of recovering a logic system by combining two or more fragments of it. We show that, in general, by fibring two or more fragments of a given logic the resulting logic is weaker than the original one, because some meta-properties of the connectives are lost after the combination process. In order to overcome this problem, the categories Mcon and Seq of multiple-conclusion consequence relations and sequent calculi, respectively, are introduced. The main feature of these categories is the preservation, by morphisms, of meta-properties of the consequence relations, which allows, in several cases, to recover a logic by fibring of its fragments. The fibring in this categories is called meta−fibring. Several examples of well-known logics which can be recovered by meta-fibring its fragments (in opposition to fibring in the usual categories) are given. Finally, a general semantics for objects in Seq (and, in particular, for objects in Mcon) is proposed, obtaining a category of logic systems called Log. A general theorem of preservation of completeness by fibring in Log is also obtained.     

On WLI-ideal space and the properties of WLI-ideals in lattice implication algebra (LIA)

In classical logic and non-classical logic, Modus Ponens (MP rule) is very useful for a formal deduction. Firstly, we focus on the properties of WLI-ideal of lattice implication algebras based on the definition of ⊕ operation and ? operation, which are abstraction of MP rule. On the other hand, we consider the WLI-ideal topological space (L,T _W(L)) based on LIA, and its topological properties are investigated, it is an abstraction of MP rule-base. Finally, we consider the fuzzification of WLI-ideals in lattice implication algebras, and the properties of FWLI-ideals are investigated.     

Rings and Gödel algebras

In this paper, we study those rings whose semiring of ideals can be given the structure of a Gödel algebra. Such rings are called Gödel rings. We investigate such structures both from an algebraic and a topological point of view. Our main result states that every Gödel ring R is a subdirect product of prime Gödel rings R _i , and the Gödel algebra Id(R) associated to R is subdirectly embeddable as an algebraic lattice into ${{\prod_{i}}Id(R_{i})}$ , where each Id(R _i ) is the algebraic lattice of ideals of R _i that can be equipped with the structure of a Gödel algebra. We see that the mapping associating to each Gödel ring its Gödel algebra of ideals is functorial from the category of Gödel rings with epimorphisms into the full subcategory of frames whose objects are Gödel algebras and whose morphisms are complete epimorphisms.     

On the homeomorphism of continuous mappings

Denote by C(X) the partially ordered (PO) set of all continuous epimorphisms of a space X under the natural identification of homeomorphic epimorphisms. The following homeomorphism theorem for bicompacta is implicitly contained in Magill’s 1968 paper: two bicompacta X and Y are homeomorphic if and only if the PO sets C(X) and C(Y) are isomorphic. In the present paper, Magill’s theorem is extended to the category of mappings in which the role of bicompacta is played by perfect mappings. The results are obtained in two versions, namely, in the category TOP _Z (of triangular commutative diagrams) and in the category MAP (of quadrangular commutative diagrams).     

Lewis meets Brouwer: Constructive strict implication

C.I. Lewis invented modern modal logic as a theory of “strict implication” $?$. Over the classical propositional calculus one can as well work with the unary box connective. Intuitionistically, however, the strict implication has greater expressive power than $\square$ and allows to make distinctions invisible in the ordinary syntax. In particular, the logic determined by the most popular semantics of intuitionistic $\mathsf{K}$ becomes a proper extension of the minimal normal logic of the binary connective. Even an extension of this minimal logic with the “strength” axiom, classically near-trivial, preserves the distinction between the binary and the unary setting. In fact, this distinction has been discovered by the functional programming community in their study of “arrows” as contrasted with “idioms”. Our particular focus is on arithmetical interpretations of intuitionistic $?$ in terms of preservativity in extensions of $\mathsf{HA}$, i.e., Heyting’s Arithmetic.