This paper studies effective aspects of semiperfect rings from the standpoint of reverse mathematics. Based on first-order Jacobson radicals of rings, we define a ring R with the Jacobson radical Jac(R) to be semiperfect if the quotient ring R/Jac(R) is semisimple, and idempotents of the quotient ring can be lifted to R. Using elementary matrix operations in linear algebra, we show that RCA₀ proves a characterization of semiperfect rings in terms of idempotents of rings. Semiperfect rings are generalizations of semisimple rings and local rings, and semiperfect rings R with R/Jac(R) simple are isomorphic to matrix rings over local rings. Based on the effective characterization of semiperfect rings via idempotents, we prove the structure theorem of semiperfect rings R with R/Jac(R) simple in RCA₀. Left perfect rings or right perfect rings are always semiperfect. Finally, we provide a proof for the structure theorem of one-sided perfect rings R with R/Jac(R) simple in WKL₀.

In [S. Celani and L. Cabrer. Duality for finite Hilbert algebras. Discrete Math., 305(1-3):74{99, 2005.] the authors proved that every finite Hilbert algebra A is isomorphic to the Hilbert algebra H_K(X) = {w ⇒ _i v : w ∈ K and v ⊆ w}, where X is a finite poset, K is a distinguished collection of subsets of X, and the implication ⇒_i is defined by: w ⇒_i  v = {x ∈ X : w ∩ [x) ⊆ v}, where [x) = {y ∈ X : x ≤ y.} The Hilbert implication on H_K(X) is the usual Heyting implication ⇒ _i  (as just defined) given on the increasing subsets. In the same article, Celani and Cabrer extended this representation to a full categorical duality. The aim of the present article is to obtain an algebraic characterization of the Hilbert algebras H_K(X) for all structures (X, ≤, K) defined by Celani and Cabrer but not necessarily finite. Then, we shall extend this  representation to a full dual equivalence generalizing the finite setting given by Celani and Cabrer.

We show that a variety with J´onsson terms t₁, . . . , t_n–1 has directed J´onsson terms d₁, . . . , d_n–1 for the same value of the indices, solving a problem raised by Kazda et al. Refined results are obtained for locally finite varieties.

Contact logics are modal logic that is developed for reasoning about region-based theories of space. We develope a tableaux approach for contact logics interpreted over intervals (CLIOI) on the reals. For obtaining sound and complete tableaux-based decision procedures, the main technical tool is the semantic tableaux approach. We use intensively the following concepts: tableaux methods, termination of tableaux methods, saturated tableaux, termination theorem, soundness theorem, truth lemma, and completeness theorem.

AMS subject classification: 03G05, 03B60, 03B70, 68T27

We continue the work of [1, 2, 3] by analyzing the equivalence relation of bi-embeddability on various classes of countable planes, most notably the class of countable non-Desarguesian projective planes. We use constructions of the author from [13] to show that these equivalence relations are invariantly universal, in the sense of [3], and thus in particular complete analytic. We also introduce a new kind of Borel reducibility relation for standard Borel G-spaces, which requires the preservation of stabilizers, and explain its connection with the notion of full embeddings commonly considered in category theory.

AMS subject classification: 03E15

A previous version of this paper has appeared on the ArXiv with co-author F. Calderoni. The author and F. Calderoni have agreed that the present paper is presented as G. Paolini as the only author. We thank F. Calderoni for his contributions to the writing of this paper.

We present the model theoretic concepts that allow mathematics to be developed with the notion of the potential infinite instead of the actual infinite. The potential infinite is understood as a dynamic notion, being an indefinitely extensible finite. The main adoption is the interpretation of the universal quantifier, which has an implicit reection principle. Each universal quantification refers to an indefinitely large, but finite set. The quantified sets may increase, so after a reference by quantification, a further reference typically uses a larger, still finite set. We present the concepts for classical first-order logic and show that these dynamic models are sound and complete with respect to the usual inference rules. Moreover, a finite set of formulas requires a finite part of the increasing model for a correct interpretation.

AMS subject classification: 03C68, 03C30, 03C13.

Contrary to the finitary case, the set Γ(A) of all the non-generators of an infinitary algebra A is not necessarily a subalgebra of A. We show that the phenomenon is ubiquitous: every algebra with at least one infinitary operation can be embedded into some algebra B such that Γ(B) is not a subalgebra of B. As far as expansions are concerned, there are examples of infinite algebras A such that in every expansion B of A the set Γ(B) is a subalgebra of B. However, under relatively weak assumptions on A, it is possible to get some expansion B of A such that Γ(B) fails to be a subalgebra of B.

AMS subject classification: Primary 08A65.

Menger's graph theorem equates the minimum size of a separating set for non-adjacent vertices a and b with the maximum number of disjoint paths between a and b. By capturing separating sets as models of an entailment relation, we take a formal approach to Menger's result. Upon showing that inconsistency is characterised by the existence of suficiently many disjoint paths, we recover Menger's theorem by way of completeness.

AMS subject classification: 05C40, 05C20, 03B35.

Let pbe a prime number, Fp a finite field with pelements, Fan algebraic extension of Fp and z a variable. We consider the structure of addition and the Frobenius map (i.e., x →x^p) in the polynomial rings F[z] and in fields F(z) of rational functions. We prove that any question about F[z] in the structure of addition and Frobenius map may be effectively reduced to questions about the similar structure of the field F. Furthermore, we provide an example which shows that a fact which is true for addition and the Frobenius map in the polynomial rings F[z] fails to be true in F(z). As a consequence, certain methods used to prove model completeness for polynomials do not suffice to prove model completeness for similar structures for fields of rational functions F(z), a problem that remains open even for F= Fp.

Primary 03B25, 12L05, Secondary 03C10, 03C60, 13A35, 13L05.

In this paper we prove a Lindström like theorem for the logic consisting of arbitrary Boolean combinations of first order sentences. Specifically we show the logic obtained by taking arbitrary, possibly infinite, Boolean combinations of first order sentences in countable languages is the unique maximal abstract logic which is closed under finitary Boolean operations, has occurrence number ω1, has the downward Lüowenheim-Skolem property to ωand the upward Lüowenheim-Skolem property to uncountability, and contains all complete first order theories in countable languages as sentences of the abstract logic. We will also show a similar result holds in the continuous logic framework of [5], i.e. we prove a Lindström like theorem for the abstract continuous logic consisting of Boolean combinations of first order closed conditions. Specifically we show the abstract continuous logic consisting of arbitrary Boolean combinations of closed conditions is the unique maximal abstract continuous logic which is closed under approximate isomorphisms on countable structures, is closed under finitary Boolean operations, has occurrence number ω1, has the downward Lüowenheim-Skolem property toω, the upward Lüowenheim-Skolem property to uncountability and contains all first order theories in countable languages as sentences of the abstract logic.

AMS subject classification: 03C66, 03C95, 03B10.
 

We extend the concepts of splitting, reaping, and independent families to families of functions and permutations on ω and define associated cardinal characteristics s_f , s_p, r_f , r_p, if , and i_p. We study relationships among cov(M), non(M), and these cardinals. In this paper, we show that sf = non(M) = s_p, r_f = cov(M) ≤ r_p, and cov(M) ≤ i_f , i_p.

AMS subject classification: 03E17.

The aim of this paper is to investigate the relation between the strong and the "weak" or intuitionistic negation in Nelson algebras. To do this, we define the variety of Kleene algebras with intuitionistic negation and explore the Kalman's construction for pseudocomplemented distributive lattices. We also study the centered algebras of this variety.

AMS subject classification: 06D16, 03G25.

We define a procedure for translating a given first-order formula to an equivalent modal formula, if one exists, by using tableau-based bisimulation invariance test. A previously developed tableau procedure tests bisimulation invariance of a given first-order formula, and therefore tests whether that formula is equivalent to the standard translation of some modal formula. Using a closed tableau as the starting point, we show how an equivalent modal formula can be effectively obtained.

AMS subject classification: 03B45.

We investigate an expansion of positive intuitionistic logic obtained by adding a constant Ω  introduced by Lloyd Humberstone. Our main results include a sound and strongly complete axiomatization, some comparisons to other expansions of intuitionistic logic obtained by adding actuality and empirical negation, and an algebraic semantics. We also brie y discuss its connection to classical logic.

AMS subject classification: 03B20, 03B50.

We provide some statements equivalent in ZFC to GCH, and also to GCH above a given cardinal. These statements express the validity of the notions of replete and well-replete car- dinals, which are introduced and proved to be specially relevant to the study of cardinal exponentiation. As a byproduct, a structure theorem for linear orderings is proved to be equivalent to GCH: for every linear ordering L, at least one of L and its converse is universal for the smaller well-orderings.

AMS subject classification: 03E05.

AMS subject classification: 03C64, 12L12.

We investigate the structure theory of the variety of PBZ*-lattices and some of its proper subvarieties. These lattices with additional structure originate in the foundations of quantum mechanics and can be viewed as a common generalisation of orthomodular lattices and Kleene algebras expanded by an extra unary operation. We lay down the basics of the theories of ideals and of central elements in PBZ*-lattices, we prove some structure theorems, and we explore some connections with the theories of subtractive and binary discriminator varieties.

AMS Subject Classification: primary 08B15; secondary 06B10, 08B26, 03G25, 03G12.

We give a constructive account of the frequentist approach to probability, by means of natural density. Then we discuss some probabilistic variants of the Limited Principle of Omniscience.

AMS Subject Classification: 03F65, 60A05.

We prove that no quantifier-free formula in the language of group theory can define the ℵ₁-half graph in a Polish group, thus generalising some results from [6]. We then pose some questions on the space of groups of automorphisms of a given Borel complete class, and observe that this space must contain at least one uncountable group. Finally, we prove some results on the structure of the group of automorphisms of a locally finite group: firstly, we prove that it is not the case that every group of automorphisms of a graph of power λ is the group of automorphism of a locally finite group of power λ; secondly, we conjecture that the group of automorphisms of a locally finite group of power λ has a locally finite subgroup of power λ, and reduce the problem to a problem on p-groups, thus settling the conjecture in the case λ = ℵ₀.

AMS Subject Classification: 03E15, 20K30, 20B27.

It is quite well-known from Kurt G¨odel’s (1931) ground-breaking Incompleteness Theorem that rudimentary relations (i.e., those definable by bounded formulae) are primitive recursive, and that primitive recursive functions are representable in sufficiently strong arithmetical theories. It is also known, though perhaps not as well-known as the former one, that some primitive recursive relations are not rudimentary. We present a simple and elementary proof of this fact in the first part of the paper. In the second part, we review some possible notions of representability of functions studied in the literature, and give a new proof of the equivalence of the weak representability with the (strong)  representability of functions in sufficiently strong arithmetical theories.

AMS Subject Classification: primary 03F40; secondary 03D20, 03F30

We use a variation on Mason’s α-function as a pre-dimension function to construct a not one-based ω–stable plane P (i.e. a simple rank 3 matroid) which does not admit an algebraic representation (in the sense of matroid theory) over any field. Furthermore, we characterize forking in Th(P), we prove that algebraic closure and intrinsic closure coincide in Th(P), and we show that Th(P) fails weak elimination of imaginaries, and has Morley rank ω.

AMS Subject Classification: 03C45, 05B35

While topology given by a linear order has been extensively studied, this cannot be said about the case when the order is given only locally. The aim of this paper is to fill this gap. We consider relation between local orderability and separation axioms and give characterisation of those regularly locally ordered spaces which are connected, locally connected or Lindel¨of. We prove that local orderability is hereditary on open, connected or compact subsets. A collection of interesting examples is also offered.

AMS Subject Classification: primary 54F05; secondary 54E99, 54D10, 06F30

AMS Subject Classification: 03D30

We study the existence of Borel sets B ⊆ ω2 admitting a sequence 〈ηα : α<λ〉 of distinct elements of ω2 such that |(ηα +B)∩(ηβ +B)| ≥ 6 for all α,β< λ but with no perfect set of such η’s. Our result implies that under the Martin Axiom, if ℵα < c, α< ω1 and 3 ≤ ι< ω, then there exists a Σ0 2 set B ⊆ ω2 which has ℵα many pairwise 2ι–nondisjoint translations but not a perfect set of such translations. Our arguments closely follow Shelah [7, Section 1]

Received 16 June 2018

Publication 1138 of the second author.

AMS subject classification: Primary 03E35; Secondary 03E15, 03E50

It is proved that the Tang-Pequignot reducibility (or reducibility by relatively continuous relations) on a  second countable, T₀ space X either coincides with the Wadge reducibility for the given topology, or there is no topology on X that can turn it into Wadge reducibility.

Received 11 July 2018

AMS subject classificastion: Primary 03E15; Secondary 03D55

The paper first covers several properties of the extension of the divisibility relation to a set *N of nonstandard integers, including an analogue of the basic theorem of arithmetic. After that, a connection is established with the divisibility in the Stone–Čech compactification βN, proving that the divisibility of ultrafilters introduced by the author is equivalent to divisibility of some elements belonging to their respective monads in an enlargement. Some earlier results on ultrafilters on lower levels on the divisibility hierarchy are illuminated by nonstandard methods. Using limits by ultrafilters we obtain results on ultrafilters above these finite levels, showing that for them a distribution by levels is not possible.

Received 16 July 2018

AMS subject classification: Primary 54D80; Secondary 11U10, 03H15, 54D35

Given the congruence lattice L of a finite algebra A that generates a congruence permutable variety, we  look for those sequences of operations on L that have the properties of higher commutator operations of expansions of A. If we introduce the order of such sequences in the natural way the question is whether exists or not the largest one. The answer is positive. We provide a description of the largest element and as a consequence we obtain that the sequences form a complete lattice.

Received 18 September 2018

Supported by the Austrian Science Fund (FWF):P29931 and the Scientific Project 174018 of the Ministry of Science and Education of the Republic of Serbia.

AMS subject classification: Primary 06B10; Secondary 06A07, 08A40

We show that there are 0-definably complete ordered fields which are not real closed. Therefore, the theory of definably with parameters complete ordered fields does not follow from the theory of 0-definably complete ordered fields. The mentioned completeness notions for ordered fields are the definable versions of completeness in the sense of Dedekind cuts. In earlier joint work, we had shown that it would become successively weakened if we just required nonexistence of definable regular gaps and then disallowing parameters. The result in this note shows reducing in the opposite order, at least one side is sharp.

Received 27 October 2018

AMS subject classification: Primary 03C64; Secondary 12L12

A relational structure is homomorphism-homogeneous if every homomorphism between finite substructures extends to an endomorphism of the structure. A point-line geometry is a non-empty set of elements called points, together with a collection of subsets, called lines, in a way that every line contains at least two points and any pair of points is contained in at most one line. A line which contains more than two points is called a regular line. Point-line geometries can alternatively be formalised as relational structures. We establish a correspondence between the point-line geometries investigated in this paper and the firstorder structures with a single ternary relation L satisfying certain axioms (i.e. that the class of point-line geometries corresponds to a subclass of 3-uniform hypergraphs). We characterise the homomorphism-homogeneous point-line geometries with two regular non-intersecting lines. Homomorphism-homogeneous pointline geometries containing two regular intersecting lines have already been classified by Mašulović.

Received 15 November 2018

AMS subject classification: Primary 05B25; Secondary 03B10.

In this work, we consider two families of incidence problems, C₁ and C₂,, which are related to real numbers and countable subsets of the real line. Instances of problems of C₁ are as follows: given a real number x, pick randomly a countable set of reals A hoping that x ∈ A, whereas instances of problems of C₂ are as follows: given a countable set of reals A, pick randomly a real number x hoping that x ∉ A. One could arguably defend that, at least intuitively, problems of C₂ are easier to solve than problems of C₁. After some suitable formalization, we prove (within ZFC) that, on one hand, problems of C₂ are, indeed, at least as easy to solve as problems of C₁. On the other hand, the statement “Problems of C₁ have the exact same complexity of problems of C₂” is shown to be an equivalent of the Continuum Hypothesis.

Received 18 February 2019

AMS subject classification: Primary 03E50; Secondary 18A05, 18A15

We consider the weak truth-table reducibility ≤_wtt and we prove the existence of wtt-introimmune sets in ∆⁰₂. This closes the gap on the existence of arithmetical r-introimmune sets for all the known reducibilities ≤_r strictly contained in the Turing reducibility.

Received 21 May 2016 

This work was supported by the PRIN 2012 project Logic Models and Sets. 

AMS subject classification: 03D30 [view classification]

We investigate the complexity of the standard translation of lambda calculus into combinatory logic. The main result shows that the asymptotic growth rate of the size of a translated term is Ø(n³) in worst-case, where n denotes the size of the lambda term.

Received 8 June 2017

This work was partially supported by the grant 2013/11/B/ST6/00975 funded by the Polish National Science Center.

AMS subject classification: 03B40, 68Q25, 68N18.

We analyze semantically the logical inference rules in cut-free sequent calculi for the modal logics hich are obtained from the least normal logic K by adding axioms from T, 4, 5, D and B. This implies Kripke completeness, as well as the cutelimination property or the subformula property of the calculi. By slightly modifying the arguments, the  nite model property of the logics also follows.

Received 9 June 2017

AMS subject classification: 03B45, 03F05

By means of a forcing argument, it was shown by Pereira that if CH holds then there is a separable PCF space of height ω1 + 1 which is not Fréchet-Urysohn. In this paper, we give a direct proof of Pereira’s theorem by means of a forcing-free argument, and we extend his result to PCF spaces of any height δ + 1 where δ<ω2 with cf(δ) = ω1.

Received 12 June 2017

Research supported by the Spanish Ministry of Education DGI grant MTM2014-59178-P and by the Catalan DURSI grant 2014SGR437.

AMS subject classification: 03E35, 03E04, 03E75, 06E05, 54A25, 54G12

The typical indirect proof of an abstract extension theorem, by the Kuratowski-Zorn lemma, is based on a onestep extension argument. While Bell has observed this in case of the axiom of choice, for subfunctions of a given relation, we now consider such extension patterns on arbitrary directed-complete partial orders. By postulating the existence of so-called total elements rather than maximal ones, we can single out an immediate consequence of the Kuratowski-Zorn lemma from which quite a few abstract extension theorems can be deduced more directly, apart from certain definitions by cases. Applications include Baer’s criterion for a module to be injective. Last but not least, our general extension theorem is equivalent to a suitable form of the Kuratowski-Zorn lemma over constructive set theory.

Received 27 June 2017

AMS subject classification: 03E25, 03F65

In this paper, we introduce a proof system NQGL for a Kripke complete predicate extension of the logic GL of provability. While GL is defined by K and the Lӧb formula □(□p ⊃p) ⊃□p, NQGL does not have the L¨ob formula as its axiom, but has a non-compact rule, that is, a derivation rule with countably many premises, instead. We show that NQGL enjoys cut admissibility and is complete with respect to the class of Kripke frames such that for each world, the supremum of the length of the paths from the world is finite.

Received 21 February 2018

AMS subject classification: 03F05, 03F45

In this paper we isolate a property for forcing notions, the *-Prikry condition, that is similar to the Prikry condition but that is topological: A forcing P satisfies it iff for every p ∈Pand for every open dense D ⊆P, there are n ∈ωand q ≤∗p such that for any r ≤q with l(r) = l(q) + n, r ∈D, for some length notion l. This is implicit in many proofs in literature. We prove this for the tree Prikry forcing and the long extender Prikry forcing.

Received 16 October 2017

Revised 2 June 2018

AMS subject classifications: 03E55, 03E05, 03E35(03E45)

Inconsistency-tolerant temporal reasoning with sequential (i.e., ordered or hierarchical) information is gaining increasing importance in computer science applications. A logical system for representing such reasoning is thus required for obtaining a theoretical basis for such applications. In this paper, we introduce a new logic called paraconsistent sequential linear-time temporal logic (PSLTL), which is an extension of the standard linear-time temporal logic (LTL). PSLTL can appropriately represent inconsistency-tolerant temporal reasoning with sequential information. The cut-elimination, decidability, and completeness theorems for PSLTL are proved in this paper.

The beliefs of other people about our own beliefs affect our decision making strategies (and beliefs). In epistemic game theory, player’s beliefs about other players’ beliefs are formalized, and the way how people may reason about other players (before they make their final choice in a game) is explored. In this paper, we introduce a non-self-referential paradox (called “Yablo-like Brandenburger-Keisler paradox”) in epistemic game theory which shows that modeling players’ epistemic beliefs and assumptions in a complete way is impossible. We also present an interactive temporal (belief and) assumption logic to give an appropriate formalization for this Yablo–like Brandenburger-Keisler paradox. Formalizing the new paradox turns it into a theorem in the interactive temporal assumption logic.

In this short note we show that the full generalized models of any extension of a logic can be determined from the full generalized models of the base logic in a simple way. The result is a consequence of two central theorems of the theory of full generalized models of sentential logics. As applications we investigate when the full generalized models of an extension can also be full generalized models of the base logic, and we prove that each Suszko filter of a logic determines a Suszko filter  of each of its extensions, also in a simple way.

During the Autumn School on Strongly Finite Sentential Calculi held in Międzygórze in 1977, Wójcicki conjectured that a propositional logic has a strongly adequate matrix semantics consisting of matrices with a singleton designated filter, which we call a Rasiowa semantics since it is possessed by all implicative logics of Rasiowa, if and only if it satisfies a simple technical condition that we name the Wójcicki condition. Malinowski proved the conjecture in 1978. We revisit Malinowski's Theorem in the setting of logics formalized as π-institutions.

A refutation system for Wansing's logicW(which is an expansion of Nelson's logic) is given. The refutation system provides an efficient decision procedure for W. The procedure consists in constructing for any normal form a finite syntactic tree with the property that the origin is non-valid if some end node is non-valid. The finite model property is also established.

We give a normalizing system of natural deduction for positive contraction - less relevant logic . The specific characteristic of our calculus is that it has a simple translational relationship to a particular sequent calculus for , such that normal natural deduction derivations correspond to cut-free sequent calculus derivations and vice versa. By translations from natural deduction to sequent calculus derivations, and back, together with cut-elimination, we obtain an indirect proof of the normalization.

We prove that a variety of double-Heyting algebras is a discriminator variety if and only if it is semisimple if and only if it has equationally definable principal congruences. The result also applies to the class of Heyting algebras with a dual pseudocomplement operation and to the class of regular double p-algebras.

The well-known embedding of full intuition- istic propositional calculus into the atomic polymorphic system Fat is possible due to the intriguing phenomenon of instantiation overflow. Instantiation overflow ensures that (in Fat) we can instantiate certain universal formulas by any formula of the system, not necessarily atomic. Until now only three types in Fat were identified with such property: the types that result from the Prawitz translation of the propositional connectives (?, ^, _) into Fat (or Girard's system F). Are there other types in Fat with instantiation overflow? In this paper we show that the answer is yes and we isolate a class of formulas with such property.

Some years ago, Lokhorst proposed an intuitionistic reformulation of Mally's deontic logic (1926). This reformulation was unsatisfactory, because it provided a striking theorem that Mally himself did not mention. In this paper, we present an alternative reformulation of Mally's deontic logic that does not provide this theorem.

Let ZC -  I (respectively, ZF -  I) be the theory obtained by deleting the axiom of infinity from the usual list of axioms for Zermelo set theory with choice (respectively, the usual list of axioms for Zermelo-Fraenkel set theory). In this note, we present a collection of sentences 9x'(x) for which (ZC -  I) + 9x'(x) (respectively, (ZF - I)+9x'(x)) proves the existence of an infinite set.

In this paper we will introduce N-Vietoris families and prove that homomorphic images of distributive nearlattices are dually characterized by N-Vietoris families. We also show a topological approach of the existence of the free distributive lattice extension of a distributive nearlattice.

We consider sl-semantics in which first order sentences are interpreted in potentially infinite domains. A potentially innite domain is a growing sequence of infinite  models. We prove the completeness theorem for first order logic under this semantics. Additionally we characterize the logic of such domains as having a learnable, but not recursive, set of axioms. The work is a part of author's research devoted to computationally motivated foundations of mathematics

Wójcicki introduced in the late 1970s the concept of a referential semantics for propositional logics. Referential semantics incorporate features of the Kripke possible world semantics for modal logics into the realm of algebraic and matrix semantics of arbitrary sentential logics. A well-known theorem of Wójcicki asserts that a logic has a referential semantics if and only if it is selfextensional. A second theorem of Wójcicki asserts that a logic has a weakly referential semantics if and only if it is weakly self- extensional. We formulate and prove an analog of this theorem in the categorical setting. We show that a π-institution has a weakly referential semantics if and only if it is weakly self-extensional.

The logic RM3 is the 3-valued extension of the logic R-Mingle (RM). RM (and so, RM3) does not have the variable- sharing property (vsp), but RM3 (and so, RM) lacks the more "offending" paradoxes of relevance", such as A → (B → A) or A → (A → B). Thus, RM and RM3 can be useful when some relevance", but not the full vsp, is needed. Sublogics of RM3 with the vsp are well known, but this is not the case with those lacking this property. The rst aim of this paper is to dene an ample family of sublogics of RM3 without the vsp. The second one is to provide these sublogics and RM3 itself with a general Routley-Meyer semantics, that is, the semantics devised for relevant logics in the early seventies of the past century.

The present note corrects an error made by the author in answering an open problem of axiomatizing an expansion of Nelson's logic introduced by Heinrich Wansing. It also gives a correct axiomatization that answers the problem by importing some results on subintuitionistic logics presented by Greg Restall.

It is known that Craig interpolation theorem does not hold for LTL. In this paper, Craig interpolation theo- rems are shown for some fragments and extensions of LTL. These theorems are simply proved based on an embedding-based proof method with Gentzen-type sequent calculi. Maksimova separation theorems (Maksimova principle of variable separation) are also shown for these LTL variants.

In this note we prove that a Tarski algebra is determined by the monoid of its endomorphisms as well as by the lattice of its subalgebras.

The present note oers an axiomatization for an expansion of Nelson's logic motivated by Heinrich Wansing which serves as a base logic for the framework of nonmonotonic reasoning considered by Dov Gabbay and Raymond Turner. We also show that the expansion of Wansing is not conservative  intuitionistic logic, but at least as strong as Jankov's logic.

After defining continuous extensions of binary relations on the set N of natural numbers to its Stone-ˇCech compactification βN, we establish some results about one of such extensions. This provides us with one possible divisibility relation on βN, | , and we introduce a few more, defined in a natural way. For some of them we find equivalent conditions for divisibility. Finally, we mention a few facts about prime and irreducible elements of (βN,·). The motivation behind all this is to try to translate problems in elementary number theory into βN

Generalizing ordinary topological and pretopological spaces, we introduce the notion of peritopology where neighborhoods of a point need not contain that point, and some points might even have an empty neighborhood. We brie y describe various intrinsic aspects of this notion. Applied to modal logic, it gives rise to peritopological models, a generalization of topo- logical models, a spacial case of neighborhood semantics. A new cladding for bisimulation is presented. The concept of Alexandro peritopology is used in order to determine the logic of all peritopo- logical spaces, and we prove that the minimal logic K is strongly complete with respect to the class of all peritopological spaces. We also show that the classes of T0, T1 and T2-peritopological spaces are not modal denable, and that D is the logic of all proper peritopological spaces. Finally, among our conclusions, we show that the question whether T0, T1 peritopological spaces are modal denable in H(@) remains open.

We introduce the notion of an everywhere strongly logiable algebra: a nite non-trivial algebra A such that for every F 2 P(A) r f;;Ag the logic determined by the matrix hA; Fi is a strongly algebraizable logic with equivalent algebraic semantics the variety generated by A. Then we show that everywhere strongly logiable algebras belong to the eld of universal algebra as well as to the one of logic by characterizing them as the nite non-trivial simple algebras that are constantive and generate a congruence distributive and n-permutable variety for some n > 2. This result sets everywhere strongly logiable algebras surprisingly close to primal algebras. Nevertheless we shall provide examples everywhere strongly logiable algebras that are not primal. Finally, some conclusion on the problem of determining whether the equivalent algebraic semantics of an algebraizable logic is a variety is obtained.

We investigate minimal rst-order structures and consider interpretability and denability of orderings on them. We also prove the minimality of their canonical substructures.

We introduce the variety of Hilbert algebras with a modal operator , called H-algebras. The variety of H-algebras is the algebraic counterpart of the f!;g-fragment of the intuitionitic modal logic IntK. We will study the theory of representation and we will give a topological duality for the variety of H-algebras. We are going to use these results to prove that the basic implicative modal logic IntK! and some axiomatic extensions are canonical. We shall also to determine the simple and subdirectly irreducible algebras in some subvarieties of H-algebras.

We will introduce the special kind of the order relations into recursively enumerable sets and prove that they can be used to distinguish (albeit in a non-constructive way) between recursive and non-recursive sets.

We study the problem of deciding, whether a given partial order is embeddable into two consecutive layers of a Boolean lattice. Employing an equivalent condition for such em- beddability similar to the one given by J. Mittas and K. Reuter [5], we prove that the decision problem is NP-complete by showing a polynomial-time reduction from the not-all-equal variant of the Satisability problem.

In the present paper, which is a sequel to [20, 4, 12], we investigate further the structure theory of quasi-MV algebras and √ quasi-MV algebras. In particular: we provide a new representation of arbitrary √ qMV algebras in terms of √ qMV algebras arising out of their MV* term subreducts of regular elements; we investigate in greater detail the structure of the lattice of √ qMV varieties, proving that it is uncountable, providing equational bases for some of its members, as well as analysing a number of slices of special interest; we show that the variety of √ qMV algebras has the amalgamation property; we provide an axiomatisation of the 1-assertional logic of √ qMV algebras; lastly, we reconsider the correspondence between Cartesian √ qMV algebras and a category of Abelian lattice-ordered groups with operators first addressed in [10].

Kronecker called his programme of arithmetization “General Arithmetic” (Allgemeine Arithmetik). In his view, arithmetic is the building block of the whole edifice of mathematics. The aim of this paper is to show that Kronecker’s arithmetical philosophy and mathematical practice have exerted a permanent influence on a long tradition of mathematicians from Hilbert to Weil, Grothendieck and Langlands. The conclusion hints at a constructivist finitist stance in contemporary mathematical logic, especially proof theory, beyond Hilbert’s programme of finitist foundations which can be seen as the continuation of Kronecker’s arithmetization programme by metamathematical or logical means. It is finally argued that the introduction of higher-degree polynomials by Kronecker inspired Hilbert’s notion of functionals, which in turn influenced G¨odel’s functional Dialectica interpretation for his intuitionistic proof of the consistency of arithmetic.

The paper studies the logics which algebraic semantics comprises of the Hilbert algebras endowed with additional operations - the regular algebras. With any finite subdirectly irreducible regular algebra one can associate a Jankov formula. In its turn, the Jankov formulas can be used as anti-axioms for a refutation system. It is proven that a logic has a complete refutation system based on Jankov formulas if and only if this logic enjoys finite model property. Also, such a refutation system is finite, that is, it contains a finite number of axioms and anti-axioms, if and and only if the logic is tabular.

In this paper we shall study some extensions of the semilattice based deductive systems S (N) and S (N, 1), where N is the variety of bounded distributive lattices with a negation operator. We shall prove that S (N) and S (N, 1) are the deductive systems generated by the local consequence relation and the global consequence relation associated with ¬-frames, respectively. Using algebraic and relational methods we will prove that S (N) and some of its extensions are canonical and frame complete.

A tableau procedure that tests bisimulation invariance of a given first-order formula, and therefore tests if that formula is equivalent to the standard translation of some modal formula, is presented. The test is sound and complete: a given formula is bisimulation invariant if and only if there is a closed tableau for that formula. The test generally does not terminate, but it does if a given formula is bisimulation invariant, i.e., the test is positive.

In recent work the notion of a secrecy logic S over a given deductive system S was introduced. Secrecy logics capture the essential features of structures that are used in performing secrecy-preserving reasoning in practical applications. More precisely, they model knowledge bases that consist of information, part of which is considered known to the user and part of which is to remain secret from the user. S-secrecy structures serve as the models of secrecy logics. Several of the universal algebraic and model theoretic properties of the class of S-secrecy structures of a given S-secrecy logic have already been studied. In this paper, our goal is to show how techniques from the theory of abstract alge-braic logic may be used to analyze the structure of a secrecy logic and draw conclusions about its algebraic character. In particular, the notion of a protoalgebraic S-secrecy logic is introduced and several characterizing properties are provided. The relationship between protoalgebraic S-secrecy logics and the protoalgebraicity
of their underlying deductive systems is also investigated.

Linear-time temporal logics (LTLs) are known to be useful for verifying concurrent systems, and a simple natural deduction framework for LTLs has been required to obtain a good computational interpretation. In this paper, a typed -calculus B[l] with a Curry-Howard correspondence is introduced for an in-tuitionistic bounded linear-time temporal logic B[l], of which the time domain is bounded by a fixed positive integer l. The strong normalization theorem for B[l] is proved as a main result. The base logic B[l] is defined as a Gentzen-type sequent calculus, and despite the restriction on the time domain, B[l] can derive almost all the typical temporal axioms of LTLs. The proposed frame-work allows us to obtain a uniform and simple proof-theoretical treatment of both natural deduction and sequent calculus, i.e., the equivalence between them, the cut-elimination theorem, the decidability theorem, the Curry-Howard correspondence and the strong normalization theorem can be obtained uniformly.

The standard omniscience principles are interpreted in a systematic way within the context of binary trees. With this dictionary at hand we revisit the weak Konig lemma (WKL) and Brouwer’s fan theorem (FAN). We first study how one can arrive from FAN at WKL, and then give a direct decomposition, without coding, of WKL into the lesser limited principle of omniscience and an instance of the principle of dependent choices. As a complement we provide, among other equivalents of the standard omniscience principles, a uniform method to formulate most of them.

We investigate semantics for an intuitionistic modal logic in which the “possibility” modality does not distribute over disjunction. In particular, the main aim of this paper is to study such intuitionistic modal logic as a variant of classical non-normal modal logic. We first give a neighborhood semantics together with a sound and complete axiomatization. Next, we study relationships between our approach and the relational (Kripke-style) semantics considered in the literature. It is shown that a relational model can be represented as a neighborhood model, and the converse direction holds under a slight restriction. Also, by considering degenerate cases of neighborhood and relational semantics, we demonstrate that a certain classical monotone modal logic has relational semantics, and can be embedded into a classical normal bimodal logic.

The methods of categorical abstract algebraic logic are employed to show that the classical process of the coordinatization of abstract (affine plane) geometry can be viewed under the light of the algebraization of logical systems. This link offers, on the one hand, a new perspective to the coordinatization of geometry and, on the other, enriches abstract algebraic logic by bringing under its wings a very well-known geometric process, not known hitherto to be related or amenable to its methods and techniques. The algebraization takes the form of a deductive equivalence between two institutions, one corresponding to affine plane geometry and the other to Hall ternary rings.

As is stated in its title, in this paper consistency is understood as the absence of the negation of any implicative theorem. Then, a series of logics adequate to this concept of consistency is defined within the context of the ternary relational semantics with a set of designated points, negation being modelled with the Routley operator. Soundness and completeness theorems are provided for each one of these logics. In some cases, strong (i.e., in respect of deducibility) soundness and completeness theorems are also proven. All logics in this paper are included in Lewis’ S4. They are all paraconsistent, but none of them is relevant.

The paper deals with functional properties of three-valued logics. We consider the family of regular three-valued Kleene’s logics (strong, weak, intermediate) and it’s extensions by adding an implicative connectives (“natural” implications). The main result of our paper is the lattice that describes the relations between implicative extensions of regular logics.

Formulas for computing the number of Df2-algebra structures that can be defined over Bn, where Bn is the Boolean algebra with n atoms, as well as the fine spectrum of Df2 are obtained. Properties of the lattice of all subvarieties of Df2, (Df 2), are exhibited. In particular, the poset Sifin(Df2) is described.

It is known that classical logic CL is the single maximal consistent logic over intuitionistic logic Int, which is moreover the single one even over the substructural logic FLew. On the other hand, if we consider maximal consistent logics over a weaker logic, there may be uncountablymany of them. Since the subvariety lattice of a given variety V of residuated lattices is dually isomorphic to the lattice of logics over the corresponding substructural logic L(V), the number of maximal consistent logics is equal to the number of minimal subvarieties of the subvariety lattice of V. Tsinakis and Wille have shown that there exist uncountably many atoms in the subvariety lattice of the variety of involutive residuated lattices. In the present paper, we will show that while there exist uncountably many atoms in the subvariety lattice of the variety of bounded representable involutive residuated lattices with mingle axiom x2 ≤ x, only two atoms exist in the subvariety lattice of the variety of bounded representable involutive residuated lattices with the idempotency x = x2.

The notion of “sequences” is fundamental to practical reasoning in computer science, because it can appropriately represent “data (information) sequences”, “program (execution) sequences”, “action sequences”, “time sequences”, “trees”, “orders” etc. The aim of this paper is thus to provide a basic logic for reasoning with sequences. A propositional modal logic LS of sequences is introduced as a Gentzen-type sequent calculus by extending Gentzen’s LK for classical propositional logic. The completeness theorem with respect to a sequence-indexed semantics for LS is proved, and the cut-elimination theorem for LS is shown. Moreover, a first-order modal logic FLS of sequences, which is a first-order extension of LS, is introduced. The completeness theorem with respect to a first-order sequence-indexed semantics for FLS is proved, and the cut-elimination theorem for FLS is shown. LS and the monadic fragment of FLS are shown to be decidable.

Interpretability logic is a modal description of the interpretability predicate. The modal system IL is an extension of the provability logic GL (Gödel–Löb). Bisimulation quotients and largest bisimulations have been well studied for Kripke models. We examine interpretability logic and consider how these results extend to Veltman models
 

In [4, Definition 8.1], some important subvarieties of the variety SH of semi-Heyting algebras are defined. The purpose of this paper is to introduce and investigate the subvariety ISSH of SH, characterized by the identity(0 - 1)* v (0 - 1)** = 11. We prove that ISSH contains all the subvarieties introduced by Sankappanavar and it is in fact the least subvariety of SH with this property. We also determine the sublattice generated by the subvarieties introduced in [4, Definition 8.1] within the lattice of subvarieties of semi-Heyting algebras.

This paper presents a complete classification of the complexity of the SAT and equivalence problems for two-element algebras. Cases of terms and polynomials are considered. We show that for any fixed two-element algebra the considered SAT problems are either in P or NP-complete and the equivalence problems are either in P or coNP-complete. We show that the complexity of the considered problems, parametrized by an algebra, are determined by the clone of term operations of the algebra and does not depend on generating functions for the clone.
 

This paper studies some properties of the so-called semilattice-based logics (which are defined in a standard way using only the order relation from a variety of algebras that have a semilattice reduct with maximum) under the assumption that its companion assertional logic (defined from the same variety of algebras using the top element as representing truth) is algebraizable. This describes a very common situation, and the conclusion of the paper is that these semilattice-based logics exhibit some of the good behaviour of protoalgebraic logics, without being necessarily so. The main result is that all these logics have enough Leibniz filters, a fact previously known in the literature to occur only for protoalgebraic logics. Another significant result is that the two companion logics coincide if and only if one of them enjoys the characteristic property of the other, that is, if and only if the semilattice-based logic is algebraizable, and if and only if its assertional companion is selfextensional. When these conditions are met, then the (unique) logic is finitely, regularly and strongly algebraizable and fully Fregean; this places it at some of the highest ranks in both the Leibniz hierarchy and the Frege hierarchy.

We describe properties of simply axiomatized modal logics, which are called pseudo-Euclidean modal logics. We will then give a complete description of the inclusion relationship among these logics by showing inclusion relationships for pairs of their logics with fixed m and n.

Firstly, a contraction-free sequent system G4np for Nelson’s paraconsistent 4-valued logic N4 is introduced by modifying and extending a contraction-free system G4ip for intuitionistic propositional logic. The structural rule elimination theorem for G4np can be shown by combining Dyckhoff and Negri’s result for G4ip and an existing embedding result for N4. Secondly, a resolution system Rnp for N4 is introduced by modifying an intuitionistic resolution system Rip, which is originally introduced by Mints and modified by Troelstra and Schwichtenberg. The equivalence between Rnp and G4np can be shown. Thirdly, a typed λ-calculus for N4 is introduced based on Prawitz’s natural deduction system for N4 via the Curry-Howard correspondence. The strong normalization theorem of this calculus can be proved by using Joachimski and Matthes’ proof method for intuitionistic typed λ-calculi with premutative conversions.

This paper is devoted to investigation of the lattice properties of p-consequences. Our main goal is to compare the
algebraic features of the lattices composed of all p-consequences and all consequence operations defined on the same propositional language.

For, not necessarily similar, single-sorted algebras Fujiwara defined, through the concept of family of basic mappingformulas between single-sorted signatures, a notion of morphism which generalizes the ordinary notion of homomorphism between algebras. Subsequently he also defined an equivalence relation, the relation of conjugation, on the families of basic mapping-formulas. In this article we extend the theory of Fujiwara to the, not necessarily similar, many-sorted algebras, by defining the concept of polyderivor between many-sorted signatures under which are subsumed the standard signature morphisms, the derivors of Goguen-Thatcher-Wagner, and the basic mapping-formulas of Fujiwara.

In the first part of this paper (RML No. 42) a spectrum of constructive logics without the K axiom is defined. Negation is introduced with a propositional falsity constant. The aim of this second part is to build up logics definitionally equivalent to those displayed in the first part, negation being now introduced as a primitive unary connective. Relational ternary semantics is provided for all logics defined in the paper.

Given a LE-structure E, where LE  is an infinitary language, we show that  and  can be chosen in such way that every orbit of the group G of automorphisms of E is LE -definable. It follows that two sequences of elements of the domain D of E satisfy the same set of L-formulas if and only if they are in the same orbit of G.

The aims of the present paper are to introduction and investigate of notions of complementary pairs of quasi-antiorders and half-space quasi-antiorder on a given set. For a pair α and β of quasi-antiorders on a given set A we say that they are complementary pair if α ∪ β =6=A and α ∩ β = ∅. In that case, α (and β ) is called half-space on A. Assertion, if α is a half-space quasi-antiorder on A, then the induced anti-order θ on A/(α ∪ α−1) is a half-space too, is the main result of this paper.

Anderson and Belnap’s implicational system RMO can be extended conservatively by the usual axioms for fusion and for the Ackermann truth constant t. The resulting system RMO is algebraized by the quasivariety IP of all idempotent commutative residuated po-monoids. Thus, the axiomatic extensions of RMO are in one-to-one correspondence with the relative subvarieties of IP. An algebra in IP is called semiconic if it decomposes subdirectly (in IP) into algebras where the identity element t is order-comparable with all other elements. The semiconic algebras in IP are locally finite. It is proved here that a relative subvariety of IP consists of semiconic algebras if and only if it satisfies x ≈ (x → t) → x. It follows that if an axiomatic extension of RMO has ((p → t) → p) → p among its theorems then it is locally tabular. In particular, such an extension is strongly decidable, provided that it is finitely axiomatized.

In the present paper, which is a sequel to [14] and [3], we investigate further the structure theory of quasi-MV algebras and √′quasi-MV algebras. In particular: we provide an improved version of the subdirect representation theorem for both varieties; we characterise the Ursini ideals of quasi-MV algebras; we establish a restricted version of J´onsson’s lemma, again for both varieties; we simplify the proof of standard completeness for the variety of √′ quasi-MV algebras; we show that this same variety has the finite embeddability property; finally, we investigate the structure of the lattice of subvarieties of √′quasi-MV algebras.

A frontal operator in a Heyting algebra is an expansive operator preserving finite meets which also satisfies the equation (x) ≤ y ∨ (y → x). A frontal Heyting algebra is a pair (H, ), where H is a Heyting algebra and  a frontal operator on H. Frontal operators are always compatible, but not necessarily new or implicit in the sense of Caicedo and Cignoli (An algebraic approach to intuitionistic connectives. Journal of Symbolic Logic, 66, No4 (2001), 1620-1636). Classical examples of new implicit frontal operators are the functions, (op. cit., Example 3.1), the successor (op. cit., Example 5.2), and Gabbay’s operation (op. cit., Example 5.3).
We study a Priestley duality for the category of frontal Heyting algebras and in particular for the varieties of Heyting algebras with each one of the implicit operations given as examples. The topological approach of the compatibility of operators seems to be important in the research of affin completeness of Heyting algebras with additional compatible operations. This problem have also a logical point of view. In fact, we look for some complete propositional intuitionistic calculus enriched with implicit connectives.

Contrary to the variety of Heyting algebras, finite Heyting algebras with successor only generate a proper subvariety of that of all Heyting algebras with successor. In particular, all finite chains generate a proper subvariety, SLH!, of the latter. There is a categorical duality between Heyting algebras with successor and certain Priestley spaces. Let X be the Heyting space associated by this duality to the Heyting algebra with successor H.
If there is an ordinal  and a filtration S on X such that X =  X, the height of X is the minimun ordinal  ≤  such that Xc  = ∅. In this case, we also say that H has height . This filtration allows us to write the space X as a disjoint union of antichains. We may think that these antichains define levels on this space.
We study the way of characterize subalgebras and homomorphic images in finite Heyting algebras with successor by means of their Priestley spaces. We also depict the spaces associated to the free algebras in various subcategories of SLH!..