# Categorical Abstract Algebraic Logic: Meet-Combination of Logical Systems

Authors: George Voutsadakis
Journal: Journal of Mathematics
 (2013)

---

## Abstract

The widespread and rapid proliferation of logical systems in several areas of computer science has led to a resurgence of interest in various methods for combining logical systems and in investigations into the
properties inherited by the resulting combinations. One of the oldest such methods isfibring. In fibring the shared connectives of the combined logics inherit properties from both component logical systems, and this leads often to inconsistencies. To deal with such undesired effects, Sernadas et al. (2011, 2012)  have recently introduced a novel way of combining logics, called meet-combination, in which the combined connectives share only the common logical properties they enjoy in the component systems. In their investigations they provide a sound and concretely complete calculus for the meet-combination based on available sound and complete calculi for the component systems. In this work, an effort is made to abstract those results to a categorical level amenable to categorical abstract algebraic logic techniques.


---

## Body

## 1. Introduction

The widespread and rapid proliferation of logical systems in several areas of computer science has led to a resurgence of interest in various methods for combining logical systems and in investigations into the properties inherited by the resulting combinations. One of the oldest methods for combining connectives isfibring [1]. In fibring one combines two logical systems by possibly imposing some sharing of common connectives or identification of connectives from the constituent logical systems. When such interaction occurs, the combined connectives inherit all properties of the components from both logical systems, and this leads often to inconsistencies. A typical example of this strong interaction is the combination of an intuitionistic negation from one logical system with a classical negation from another. The combined connective behaves like a classical negation, and this outcome defeats any intended purpose for the combination. Fibring has been studied substantially since its original introduction, and both its virtues and its vices are relatively well understood. For instance in [2], fibring was presented as a categorical construction (see also [3]), in [4] fibred logical systems were investigated from the point of view of preserving completeness, in [5] some work was carried out on the effect of fibring in logics belonging to specific classes of the classical abstract algebraic logic hierarchy [6–8], and more recently, in [9] fibring was employed to obtain some modal logics, first considered in [10], in a structured way and to draw some conclusions regarding their algebraic character.To avoid some of the drawbacks and undesired effects involved in the application of fibring, Sernadas et al. [11, 12] introduced, recently, another way of combining logical systems, called meet-combination, in which the combined connectives, instead of inheriting all properties they enjoy in the component logical systems, inherit only those properties that are common to both connectives. A very illuminating example of the difference that this entails as contrasted to the fibring method consists of the result of combining two logics ℒ∧ and ℒ∨, one including a classical conjunction ∧ and one including a classical disjunction ∨, with the intention of obtaining a combined connective “identifying" these two connectives from the component logics. Roughly speaking, if fibring is used, then, since in the combination the combined connective [∧∨] has all properties that are enjoyed by each of the connectives in either logic, the derivation
(1)ϕϕ[∧∨]ψ(by  the  Property  of  Disjunction  inℒ2)ψ(by  the  Property  of  Conjunction  inℒ1)
shows that in the combined logic a single formula entails all other formulas; that is, there are only two possible theories, the empty theory and the entire set of formulas. On the other hand, this derivation would not be valid in the meet-combination of the two logics, since the afore-used Properties of Disjunction and Conjunction in ℒ2 and ℒ1, respectively, are not shared by ∧ in ℒ1 and by ∨ in ℒ2, respectively. Commutativity, however, is a shared property, whence the derived rule ϕ[∧∨]ψ/ψ[∧∨]ϕ is a derived rule of the meet-combination.In [11] Sernadas et al. start from a given logical system ℒ with a Hilbert style calculus and with a matrix semantics and define a new logic ℒ× that incorporates all meet-combinations of connectives of ℒ of the same arity. Moreover, this system includes in a canonical way the connectives of the original logical system. Roughly speaking, the Hilbert calculus of the combination consists of all old Hilbert rules plus two new rules that ensure that the combined connectives inherit the common properties of the component connectives and only those properties. The matrix semantics consists, also roughly speaking, of the direct squares of the matrices in the original matrix semantics. In the main results, [11, Theorems 3.9 and 3.13], it is shown that soundness and a special form of completeness, called concrete completeness, are inherited in ℒ× from ℒ. Moreover, Sernadas et al. [11] investigate in some detail the case of classical propositional logic, which constitutes the main motivation and paradigmatic example behind their work. Based on classical propositional calculus, they present several interesting examples, which, in addition, serve as illustrations for various sensitive points of the general theory.In the present paper, we adapt the framework of [11] to a categorical level, using notions and techniques of categorical abstract algebraic logic [13, 14]. Our main goal is providing a framework in which, starting from a π-institution whose closure system is axiomatized by a set of rules of inference, we may construct a new π-institution that includes, in a precise technical sense, natural transformations corresponding to meet-combinations of operations available in the original π-institution. The closure system of this new π-institution is created by essentially mimicking the process of [11] to create a new set of rules of inference, suitable for the new sentence functor, and by using this new set of rules to define the inferences in the newly created structure. Under conditions analogous to those imposed by Sernadas et al. in [11], we are also able to establish a form of soundness and a form of restricted completeness for the new system, with respect to a suitably constructed matrix system semantics, under the proviso that these properties are satisfied by the original system.We close this section by providing an outline of the contents of the paper. In Section2, we introduce the basic notions underlying the framework in which our work will be carried out. The inspiration comes from categorical abstract algebraic logic [13, 14] and, more specifically, uses the notion of a category of natural transformations on a given sentence functor and, implicitly, many aspects of the theory of N-rule based π-institutions, where N is a category of natural transformations on the sentence functor of the π-institution under consideration. A recent reference on this material is [15]. The reader should be aware that basic categorical notions are used rather heavily, but the elementary references to the subject [16–18] should be enough for necessary terminology and notation.In Section3 the basic constructions that take after corresponding constructions in [11] are presented. Here the meet-combination of logical systems refers to logical systems based on sentence functors, whose “signatures" are categories of natural transformations on the sentence functors and whose rules of inference and model classes are all categorical in nature. The goal is to work in a framework that would be amenable to categorical abstract algebraic logic methods and techniques so as to be able to consider aspects drawing from both theories.In Sections4 and 5, we show that a form of soundness and a form of restricted completeness are inherited by the meet-combination, subject to the condition that it is present in the components being combined. These results yield also results on conservativeness and on consistency, which are presented in Section 6.Finally, based on the thorough work of [11], we present in Section 7 some examples showcasing various aspects of the general theory. These examples are relevant to both the theory developed in [11] and to its extension elaborated on in the present paper and, whenever appropriate, we draw attention to points where the two theories overlap and points where some differences occur.


## 2. Basic Framework

In the sequel we consider an arbitrary but fixed category Sign, called the category of signatures, and an arbitrary but fixed Set-valued functorSEN:Sign→Set, called the  sentence functor. Also into the picture in a critical way will be an arbitrary but fixed category N of natural transformations on SEN, which we view as the clone of all algebraic operations on SEN. We remind the reader here of the precise definition of such a category, as presented, for example, in [15]. The clone of all natural transformations on SEN is defined to be the locally small category with collection of objects {SENα:αanordinal} and collection of morphisms τ:SENα→SENββ-sequences of natural transformations τi:SENα→SEN. Composition
(2)SENα→〈τi:i<β〉SENβ→〈σj:j<γ〉SENγ
is defined by
(3)〈σj:j<γ〉∘〈τi:i<β〉=〈σj(〈τi:i<β〉):j<γ〉.
A subcategory N of this category containingall objects of the form SENk for k<ω, and all projection morphisms pk,i:SENk→SEN, i<k, k<ω, with pΣk,i:SEN(Σ)k→SEN(Σ) given by
(4)pΣk,i(ϕ→)=ϕi,∀ϕ→∈SEN(Σ)k,
and such that, for every family {τi:SENk→SEN:i<l} of natural transformations in N, the sequence 〈τi:i<l〉:SENk→SENl is also in N, is referred to as a  category of natural transformations on SEN.A natural transformationσ:SENn→SEN in N is called a  constant if, for all Σ∈|Sign| and all ϕ→,ψ→∈SEN(Σ)n,
(5)σΣ(ϕ→)=σΣ(ψ→).
If σ:SENn→SEN is a constant, then we set σΣ∶=σΣ(ϕ→), to denote the value of the constant in SEN(Σ), which is independent of ϕ→∈SEN(Σ)n.AnN-rule of inference or simply an N-rule is a pair of the form 〈{σ0,…,σn-1},τ〉, sometimes written more legibly σ0,…,σn-1/τ, where σ0,…,σn-1, τ are natural transformations in N. The elements σi,  i<n, are called the premises and τ the  conclusion of the rule.AnN-Hilbert calculus ℛ is a set of N-rules. Using the N-rules in ℛ, one may define  derivations of a natural transformation σ in N from a set Δ of natural transformations in N. Such a derivation is denoted by Δ⊢ℛσ. If the calculus ℛ is fixed and clear in a particular context, we might simply write Δ⊢σ.Given two functorsSEN:Sign→Set and SEN′:Sign′→Set, with categories of natural transformations N,N′ on SEN,SEN′, respectively, a pair 〈F,α〉, where F:Sign→Sign′ is a functor and α:SEN→SEN′∘F is a natural transformation, is called a  translation from SEN to SEN′. Moreover, it is said to be (N,N′)-epimorphic if there exists a correspondence σ↦σ′ between the natural transformations in N and N′ that preserves projections (and, thus, also arities), such that, for all σ:SENk→SEN, all Σ∈|Sign| and all ϕ→∈SEN(Σ)k,
(6)αΣ(σΣ(ϕ→))=σF(Σ)′(αΣk(ϕ→)).
An (N,N′)-epimorphic translation from SEN to SEN′ will be denoted by 〈F,α〉:SEN→SEN′, with the relevant categories N,N′ of natural transformations on SEN,SEN′, respectively, understood from context.AnN-algebraic system 𝒜=〈SEN′,〈F,α〉〉 consists of  (i)
a functorSEN′:Sign′→Set, with a category N′ of natural transformations on SEN′;(ii)
an(N,N′)-epimorphic translation 〈F,α〉:SEN→SEN′.An N-matrix system or, simply, N-matrix 𝔄=〈𝒜,T〉 is a pair consisting of  (i)
anN-algebraic system 𝒜=〈SEN′,〈F,α〉〉;(ii)
an axiom familyT∈AxFam(SEN′) on SEN′, that is, a collection T={TΣ}Σ∈|Sign′| of subsets TΣ⊆SEN′(Σ),Σ∈|Sign′|. We perceive of the elements of SEN′(F(Σ)) as truth values for evaluating the natural transformations in N and those of TF(Σ) as being the  designated ones. An N-matrix semantics ℳ is a class of N-matrices. Given a natural transformation σ:SENk→SEN in N, we set
(7)σΣ′(f(ϕ→))∶=σΣ′(SEN(f)k(ϕ→)),
where f∈Sign(Σ,Σ′) and ϕ→∈SEN(Σ)k. The matrix 𝔄=〈𝒜,T〉  satisfies σ  at ϕ→∈SEN(Σ)k  under f∈Sign(Σ,Σ′), written 𝔄⊨Σσ[ϕ→,f], if αΣ′(σΣ′(f(ϕ→)))∈TF(Σ′). An N-rule σ0,…,σn-1/τ is a rule of an N-matrix semantics ℳ, written
(8)σ0,…,σn-1⊨ℳτ,
if 𝔄⊨Σσi[ϕ→,f], for all i<n, implies 𝔄⊨Στ[ϕ→,f], for every N-matrix 𝔄∈ℳ, all Σ∈|Sign|, all Σ-assignments ϕ→ in 𝔄, and all f∈Sign(Σ,Σ′). If the semantics is clear from context, we simply write σ0,…,σn-1⊨τ.In the remainder of this paper, by a  logical system, or simply a  logic, we understand a pentupleℒ=〈Sign,SEN,N,ℛ,ℳ〉, where  (i)
Sign is a category;(ii)
SEN:Sign→Set is a sentence functor;(iii)
N is a category of natural transformations on SEN;(iv)
ℛ is an N-Hilbert calculus;(v)
ℳ is a N-matrix semantics.


## 3. Meet-Combinations

Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logical system. Define the product logical system or, simply, product logic ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉 as follows:the logicℒ× has the same signature category Sign as ℒ.The sentence functorSEN×:Sign→Set is defined by setting
(9)SEN×(Σ)=SEN(Σ)×SEN(Σ),
for all Σ∈|Sign|, and, similarly, for morphisms.The categoryN× of natural transformations on SEN× has the same objects as N and its morphisms (SEN×SEN)n≅SENn×SENn into SEN×SEN are pairs σ→=〈σ′,σ′′〉 of natural transformations σ′,σ′′:SENn→SEN in N. We call the members of N× the  combined natural transformations or combined operations or, following [11], but rather apologetic for abusing terminology, combined connectives.Givenσ:SENk→SEN in N, we set σ-=〈σ,σ〉 in N× and, accordingly, given σ→=〈σ′,σ′′〉 in N×, we set
(10)σ-′=〈σ′,σ′〉,σ-′′=〈σ′′,σ′′〉.
Every N-rule r=σ0,…,σn-1/τ gives rise to an N×-rule
(11)r-=σ-0,…,σ-n-1τ-.
The calculus ℛ× is an “enrichment" of ℛ in the sense that it contains all rules of the form r-, for r∈ℛ, and some additional N×-rules devised for dealing with the combined operations:  (i)
for eachσ→:(SEN×)k→SEN× in N×, the lifting rule (LFT)
(12)σ-′,σ-′′σ→
is included in ℛ× to enforce inheritance by σ→ in ℒ× of all the common properties of σ′ and σ′′ in ℒ;(ii)
for each constantσ→:(SEN×)k→SEN× in N×, the  special colifting rules (cLFT)
(13)σ→σ-′,σ→σ-′′
are included in ℛ× to enforce that σ→ should enjoy in ℒ× only those properties that are common properties of σ′ and σ′′ in ℒ. The reason for allowing only the special co-lifting rules (i.e., ones that admit only constants), rather than the (general) co-lifting rules, is that, unless this restriction is imposed, the rules are not in general sound. This will become apparent in the analysis to follow.Before introducing the semanticsℳ× of ℒ×, we show, following [11], that given constant natural transformations σ′,σ′′:(SEN×)k→SEN× in N, the two combined constructors 〈σ′,σ′′〉 and 〈σ′′,σ′〉 are closely related.Theorem 1 (Sernadas, Sernadas, and Rasga).
Letℒ=〈Sign,SEN,N,R,ℳ〉 be a logical system. Consider a constant natural transformation σ→=〈σ′,σ′′〉:(SEN×)k→SEN× in N× and set σ←=〈σ′′,σ′〉. Then σ→ and σ← are interderivable in ℒ×.Proof.
Apply first cLFT twice and then LFT, in each direction. One gets the following proof:(14)(σ→/σ-′′)(σ→/σ-′)σ←.Let𝒜α=〈SEN′,〈F,α〉〉 and 𝒜β=〈SEN′,〈F,β〉〉 be N-algebraic systems with the same underlying sentence functors and the same signature functor component F:Sign→Sign′. Let SEN′×=SEN′×SEN′:Sign′→Set be defined, for all Σ∈|Sign′|, by
(15)SEN′×(Σ)=SEN′(Σ)×SEN′(Σ),
and similarly for morphisms, and let 〈F,α×β〉:SEN×→SEN′× be given, for all Σ∈|Sign|, by
(16)(α×β)Σ(ϕ,ψ)=〈αΣ(ϕ),βΣ(ψ)〉,∀〈ϕ,ψ〉∈SEN×(Σ).
Denote by 𝒜α×β the N×-algebraic system
(17)𝒜α×β=〈SEN′×,〈F,α×β〉〉.
Moreover, given two N-matrix systems 𝔄α=〈𝒜α,Tα〉 and 𝔄β=〈𝒜β,Tβ〉, let
(18)𝔄α×β=〈𝒜α×β,Tα×β〉,
where Tα×β={TΣα×β}Σ∈|Sign′|, such that, for all Σ∈|Sign′|,
(19)TΣα×β=TΣα×TΣβ.The  semanticsℳ× is the class consisting of all N×-matrix systems of the form 𝔄α×β, for 𝔄α,𝔄β∈ℳ, having underlying N-algebraic systems 𝒜α,𝒜β, respectively, with the same underlying sentence functors and the same signature functor components. The semantics ℳ× will be called the product semantics, taking after [11].Finally, we let⊢× and ⊨× stand for satisfaction and entailment in the product logic ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉.


## 4. Soundness

Recall that, given a natural transformationσ:SENk→SEN in N, we use the notation σ- to denote the natural transformation σ-=〈σ,σ〉 in N×.Proposition 2.
Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logical system and consider the product system ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉. Suppose that σ:SENk→SEN in N, Σ∈|Sign| and ϕ→∈SEN×(Σ)k, where the ith component ϕi→ of ϕ→ is ϕi→=〈ϕi′→,ϕi′′→〉, for all i<k. Then
(20)σ-Σ(ϕ→)=〈σΣ(ϕ′→),σΣ(ϕ′′→)〉.
Moreover, for all 𝔄α=〈〈SEN′,〈F,α〉〉,Tα〉, 𝔄β=〈〈SEN′,〈F,β〉〉,Tβ〉∈ℳ, all Σ′∈|Sign| and all f∈Sign(Σ,Σ′),
(21)𝔄α×β⊨Σσ-[ϕ→,f]iff𝔄α⊨Σσ[ϕ′→,f],𝔄β⊨Σσ[ϕ′′→,f].Proof.
We have the following equivalences:(22)𝔄α×β⊨Σσ-[ϕ→,f]iff(α×β)Σ′(σ-Σ′(f(ϕ→)))∈TF(Σ′)α×βiffαΣ′(σΣ′(f(ϕ′→)))∈TF(Σ′)α and βΣ′(σΣ′(f(ϕ′′→)))∈TF(Σ′)β,iff𝔄α⊨Σσ[ϕ′→,f], and 𝔄β⊨Σσ[ϕ′′→,f].This proves the Proposition.Proposition 3.
Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logical system. If the N-rule 〈{σ0,…,σn-1},τ〉 is sound in ℒ, then the N×-rule 〈{σ-0,…,σ-n-1},τ-〉 is sound in ℒ×.Proof.
Suppose that𝔄α=〈〈SEN′,〈F,α〉〉,Tα〉 and 𝔄β=〈〈SEN′,〈F,β〉〉,Tβ〉 are in ℳ so that 𝔄α×β∈ℳ×, Σ,Σ′∈|Sign|, ϕ→∈SEN×(Σ)k, and f∈Sign(Σ,Σ′), such that 𝔄α×β⊨Σσ-i[ϕ→,f], for all i<n. Then, by Proposition 2,
(23)𝔄α⊨Σσi[ϕ′→,f],𝔄β⊨Σσi[ϕ′′→,f],
for all i<n. Thus, by soundness of 〈{σ0,…,σn-1},τ〉 in ℒ, we get that 𝔄α⊨Στ[ϕ′→,f] and 𝔄β⊨Στ[ϕ′′→,f]. Therefore, again by Proposition 2, 𝔄α×β⊨Στ-[ϕ→,f] and, hence, 〈{σ-0,…,σ-n-1},τ-〉 is sound for ℒ×.Letσ→:(SEN×)k→SEN× be in N× and suppose that Σ,Σ′∈|Sign|, ϕ→∈SEN×(Σ)k and f∈Sign(Σ,Σ′). Then, by the definition of σ→,
(24)σ→Σ′(f(ϕ→))=〈σΣ′′(f(ϕ′→)),σΣ′′′(f(ϕ′′→))〉=〈σ-Σ′′(f(ϕ→))′,σ-Σ′′′(f(ϕ→))′′〉.Proposition 4.
Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logical system. The lifting rule  LFT is sound in ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉.Proof.
Suppose thatσ→ in N×, 𝔄α×β∈ℳ×, Σ∈|Sign| and ϕ→∈SEN×(Σ), such that, for some Σ∈|Sign′| and f∈Sign(Σ,Σ′),
(25)𝔄α×β⊨Σσ-′[ϕ→,f],𝔄α×β⊨Σσ-′′[ϕ→,f].
This implies that (α×β)Σ′(σ-Σ′′(f(ϕ→)))∈TF(Σ′)α×β and (α×β)Σ′(σ-Σ′′′(f(ϕ→)))∈TF(Σ′)α×β. These imply that (α×β)Σ′(〈σ-Σ′′(f(ϕ→))′,σ-Σ′′′(f(ϕ→))′′〉)∈TF(Σ′)α×β, whence, by (24),
(26)(α×β)Σ′(σ→Σ′(f(ϕ→)))∈TF(Σ′)α×β.
This proves the soundness of lifting.LetSign be a category and SEN:Sign→Set a sentence functor with N a category of natural transformations on SEN. Recall that a natural transformation σ:SENk→SEN is called aconstant if, for all Σ∈|Sign|, all ϕ→,ψ→∈SEN(Σ)kσΣ(ϕ→)=σΣ(ψ→) and that we use the notation σΣ∶=σΣ(ϕ→), for this value, which is independent of ϕ→∈SEN(Σ)k.A class ofN-matrix systems ℳ is said to be a c-semantics if, for all 𝔄α=〈〈SEN′,〈F,α〉〉,Tα〉 and 𝔄β=〈〈SEN′,〈F,β〉〉,Tβ〉 in ℳ, every constant σ:SENk→SEN in N and all Σ∈|Sign|,
(27)αΣ(σΣ)∈TF(Σ)α,iffβΣ(σΣ)∈TF(Σ)β.
Intuitively, a semantics ℳ is a c-semantics if and only if every constant is consistently interpreted as true or false under all matrix systems in the semantics, that is, under all combinations of interpretations and designated truth values included in the semantics.Proposition 5.
Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logical system, where ℳ is a c-semantics. For all constants σ→:(SEN×)k→SEN× in N×, the special co-lifting rules
(28)σ→σ-′,σ→σ-′′
are sound in ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉.Proof.
Let𝔄α×β∈ℳ×, σ→ a constant in N×, Σ∈|Sign|, and ϕ→∈SEN×(Σ)k, such that, for some Σ′∈|Sign| and f∈Sign(Σ,Σ′),
(29)𝔄α×β⊨Σσ→[ϕ→,f].
Then (recalling the notation for constants) (α×β)Σ′(σ→Σ′)∈TF(Σ′)α×β, whence
(30)αΣ′(σΣ′′)∈TF(Σ′)α,βΣ′(σΣ′′′)∈TF(Σ′)β.
Since ℳ is a c-semantics, we get that the four following relations hold:
(31)αΣ′(σΣ′′)∈TF(Σ′)α,βΣ′(σΣ′′)∈TF(Σ′)β,αΣ′(σΣ′′′)∈TF(Σ′)α,βΣ′(σΣ′′′)∈TF(Σ′)β.
Therefore, we obtain that
(32)𝔄α×β⊨Σσ-′[ϕ→,f],𝔄α×β⊨Σσ-′′[ϕ→,f],
which show that the special co-lifting rules are sound in ℒ×.Theorem 6 (soundness).
Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logical system, where ℳ is a c-semantics. If ℒ is sound, then the product logic ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉 is also sound.Proof.
We have shown in Proposition3 that all rules inherited by ℒ are sound in ℒ×. By Proposition 4, the lifting rule is sound in ℒ× and, since ℳ is assumed to be a c-semantics, by Proposition 5, the special co-lifting rules are sound in ℒ×. Therefore the product logic ℒ× is also sound.


## 5.c-Completeness

A logicℒ=〈Sign,SEN,N,ℛ,ℳ〉 is c-complete if it is complete with respect to constant natural transformations. More precisely, for all sets Δ∪{σ} of constants in N, we have that
(33)Δ⊨σimpliesΔ⊢σ.Proposition 7.
If a logicℒ=〈Sign,SEN,N,ℛ,ℳ〉 is c-complete, then, for all sets of constants Δ∪{σ} in N,
(34)Δ-⊬×σ-impliesΔ-⊭×σ-.Proof.
Suppose thatΔ-⊬×σ-. Then, since ℛ× includes all N×-rules of the form r-, for all r∈ℛ, we get that Δ⊬σ. Therefore, by the c-completeness of ℒ, we get that Δ⊭σ. Thus, there exists a model 𝔄α=〈〈SEN′,〈F,α〉〉,Tα〉∈ℳ, together with Σ,Σ′∈|Sign|, ϕ→∈SEN(Σ)k and f∈Sign(Σ,Σ′), such that 𝔄α⊨ΣΔ[ϕ→,f] and 𝔄α⊭Σσ[ϕ→,f]. Hence, the model 𝔄α×α∈ℳ× is such that 𝔄α×α⊨Σ×Δ-[〈ϕ→,ϕ→〉,f] and 𝔄α×α⊭Σ×σ-[〈ϕ→,ϕ→〉,f]. Therefore Δ-⊭×σ-, showing that ℒ× is also c-complete.Proposition 8.
Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logic and suppose that, for some Δ∪{σ,τ} in N,
(35)(Δ-⊬×σ-impliesΔ-⊭×σ-),(Δ-⊬×τ-impliesΔ-⊭×τ-).
Then it is also the case that
(36)Δ-⊬×〈σ,τ〉impliesΔ-⊭×〈σ,τ〉.Proof.
Suppose thatΔ-⊬×〈σ,τ〉. By the lifting rule, we must have Δ-⊬×σ- or Δ-⊬×τ-. Therefore, by hypothesis, Δ-⊭×σ- or Δ-⊭×τ-. Suppose, without loss of generality, that the first holds. Thus, there exists a model 𝔄α×β∈ℳ×, Σ,Σ′∈|Sign|,ϕ→∈SEN×(Σ)k and f∈Sign(Σ,Σ′), such that
(37)(α×β)Σ′(Δ-Σ′(f(ϕ→)))⊆TF(Σ′)α×β,(α×β)Σ′(σ-Σ′(f(ϕ→)))∉TF(Σ′)α×β.
Thus, we must have
(38)αΣ′(ΔΣ′(f(ϕ′→)))⊆TF(Σ′)α,αΣ′(σΣ′(f(ϕ′→)))∉TF(Σ′)α
or
(39)βΣ′(ΔΣ′(f(ϕ′′→)))⊆TF(Σ′)β,βΣ′(σΣ′(f(ϕ′′→)))∉TF(Σ′)β.
This implies that either 𝔄α×α or 𝔄β×β bears witness to Δ-⊭×〈σ,τ〉 and concludes the proof.To formulate the following proposition we introduce a convenient notation: given a setΔ of natural transformations in N×, we write
(40)Δ-′={σ-′:σ→∈Δ},Δ-′′={σ-′′:σ→∈Δ}.Proposition 9.
Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logic and suppose for some set of constants Δ∪{σ→} in N×(41)Δ-′∪Δ-′′⊬×σ→impliesΔ-′∪Δ-′′⊭×σ→.
Then it is also the case that
(42)Δ⊬×σ→impliesΔ⊭×σ→.Proof.
IfΔ⊬×σ→, then, by the special co-lifting property, Δ-′∪Δ-′′⊬×σ→. Thus, by hypothesis, Δ-′∪Δ-′′⊭×σ→. Hence, there exists 𝔄α×β∈ℳ×, Σ,Σ′∈|Sign|, ϕ→∈SEN×(Σ)k and f∈Sign(Σ,Σ′), such that
(43)(α×β)Σ′((Δ-′∪Δ-′′)Σ′(f(ϕ→)))⊆TF(Σ′)α×β,
while, at the same time,
(44)(α×β)Σ′(σ→Σ′(f(ϕ→)))∉TF(Σ′)α×β.
These relations imply that
(45)(α×β)Σ′(ΔΣ′(f(ϕ→)))⊆TF(Σ′)α×βbut(α×β)Σ′(σ→Σ′(f(ϕ→)))∉TF(Σ′)α×β,
whence Δ⊭×σ→.Theorem 10 (c-completeness).
If the logicℒ=〈Sign,SEN,N,ℛ,ℳ〉 is c-complete, then the product logic ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉 is c-complete also.Proof.
Ifℒ is c-complete, then, by Proposition 7, we get that, for all sets of constants Δ∪{σ} in N,
(46)Δ-⊬×σ-impliesΔ-⊭×σ-.
Thus, by Proposition 8, for all sets of constants Δ∪{σ,τ} in N,
(47)Δ-⊬×〈σ,τ〉impliesΔ-⊭×〈σ,τ〉.
Finally, by Proposition 9, we get that, for all sets of constants Δ∪{σ→} in N×,
(48)Δ⊬×σ→impliesΔ⊭×σ→.
This proves that ℒ× is c-complete.


## 6. Conservativeness and Consistency

Theorem 11 (conservativeness).
Letℒ=〈Sign,SEN,N,ℛ,ℳ〉 be a logic. For every set of natural transformations Δ∪{σ} in N,
(49)Δ-⊨×σ-impliesΔ⊨σ.Proof.
SupposeΔ-⊨×σ-. If 𝔄α=〈〈SEN′,〈F,α〉〉,Tα〉 is such that, for some Σ,Σ′∈|Sign|, ϕ→∈SEN(Σ)k, f∈Sign(Σ,Σ′), 𝔄α⊨ΣΔ[ϕ→,f], then, we get that 𝔄α×α⊨Σ×Δ-[ϕ2→,f], whence, by the hypothesis, 𝔄α×α⊨Σ×σ-[ϕ2→,f], and, therefore, 𝔄α⊨Σσ[ϕ→,f]. This shows that Δ⊨σ.Theorem 12 (consistency).
If the logicℒ=〈Sign,SEN,N,ℛ,ℳ〉 is consistent, then so is the product logic ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉.Proof.
This follows directly from conservativeness.


## 7. Examples from Classical Propositional Logic

We present a simple example, essentially borrowed from [11], with the twofold goal of, first, seeing how the theory of [11] can be easily accommodated in the categorical framework (becoming actually a trivial case) and, second, showcasing the difference between the soundness of special co-lifting and the lack of soundness obtained by allowing the full power of the general co-lifting rule.Suppose, first, thatℒ=〈Sign,SEN,N,ℛ,ℳ〉 is a logic, such that N contains two binary natural transformations ∧,∨:SEN2→SEN and two constants T,F that obey the usual laws of conjunction, disjunction, truth, and falsity of classical propositional logic. Then, if A,B∈{T,F}2, we have that
(50)〈∧,∨〉(A,B)⊢×〈∧,∨〉(B,A).
This can be shown by observing that the hypothesis yields, by special co-lifting, 〈∧,∧〉(A-′,B-′) and 〈∨,∨〉(A-′′,B-′′). These, by following usual derivations in ℒ, yield 〈∧,∧〉(B-′,A-′) and 〈∨,∨〉(B-′′,A-′′), whence, by lifting, we finally obtain the conclusion. In fact, if we arrange for ℳ to consist, essentially, of Boolean algebras and evaluations together with Boolean filters, it is the case that
(51)〈∧,∨〉⊨×〈∧,∨〉(p1,1,p1,0),
where p1,0,p1,1:(SEN×)2→SEN× are the two projection natural transformations; that is, “commutativity" is valid in general, not just for constants. However, the derivation (50) cannot be inferred directly from this using c-completeness, since there are nonconstant natural transformations involved.To illustrate, using the same example, that the general co-lifting rule fails, we may employ Boolean models to show that(52)〈∧,∨〉⊭×〈∧,∧〉.
In fact, note that
(53)〈∧,∨〉Σ((1,0),(1,1))=(∧Σ(1,1),∨Σ(0,1))=(1,1),
whereas
(54)〈∧,∧〉Σ((1,0),(1,1))=(∧Σ(1,1),∧Σ(0,1))=(1,0),
the first belonging to the product filter of 2-element Boolean algebras, the second failing to do so.Note, next, that(55)〈∧,∨〉(〈T,F〉,〈T,T〉)⊭×〈∨,∧〉(〈T,F〉,〈T,T〉).
A straightforward computation shows that in the direct product of 2-element Boolean algebras, the left-hand side evaluates to (1,1), whereas the right-hand side to (1,0). Even though this serves as a counterexample for an analog of Theorem 1 concerning the exchangeability of components in the context of [11], this problem does not arise in our context. In fact, our reformulation of [11, Theorem 2.1] in the form of Theorem 1 would only ensure that
(56)〈∧,∨〉(〈T,F〉,〈T,T〉)⊨×〈∨,∧〉(〈F,T〉,〈T,T〉).Suppose now that inℒ=〈Sign,SEN,N,ℛ,ℳ〉, one has the, possibly derived, rule σ/τ, where σ,τ are both constants in N. Then it can be shown that
(57)〈σ,τ〉⊣⊢×σ-.
In fact, 〈σ,τ〉⊢×σ- follows from the special co-lifting, whereas lifting helps establish the opposite direction
(58)(σ-/σ-)(σ-/τ-)〈σ,τ〉.
Finally, if one has available in ℒ a disjunction ∨ and an implication →, both behaving classically, then, since both derived rules
(59)p1,1⊢∨,p1,1⊢→
are rules of ℒ, one obtains the rule p1,1¯⊢×〈∨,→〉 in ℒ× by an application of lifting.We close with a generally phrased (rather informally formulated) problem that would be of interest in the context developed in the present work from the point of view ofabstract algebraic logic. For more details on the motivations and the state of the art in that theory, as well as the precise definitions and more insights on the notions employed in the phrasing of this problem, the reader is referred to [13–15] and further references therein.Problem for Investigation. Suppose that we have some knowledge about the algebraic classification of the π-institution ℐ=〈Sign,SEN,Cℛ〉, where ℒ=〈Sign,SEN,N,ℛ,ℳ〉 is a logic in the sense of the present paper, possibly satisfying some additional conditions. The closure system Cℛ is the system induced by the set ℛ of N-rules, as detailed in, for example, [15]. What corresponding information may then be drawn about the π-institution ℐ=〈Sign,SEN×,Cℛ×〉, that corresponds, in a similar manner, to the product logic ℒ×=〈Sign,SEN×,N×,ℛ×,ℳ×〉?



---

*Source: 126347-2013-04-16.xml*