A graph-theoretic account of logics A. Sernadas1 C. Sernadas1 J. Rasga1 M. Coniglio2 1 Dep. Mathematics, Instituto Superior Técnico, TU Lisbon SQIG, Instituto de Telecomunicações, Portugal 2 Dep. of Philosophy and CLE State University of Campinas, Brazil {acs,css,jfr}@math.ist.utl.pt, coniglio@cle.unicamp.br March 12, 2009 Abstract A graph-theoretic account of logics is explored based on the general notion of m-graph (that is, a graph where each edge can have a finite sequence of nodes as source). Signatures, interpretation structures and deduction systems are seen as m-graphs. After defining a category freely generated by a m-graph, formulas and expressions in general can be seen as morphisms. Moreover, derivations involving rule instantiation are also morphisms. Soundness and completeness theorems are proved. As a consequence of the generality of the approach our results apply to very different logics encompassing, among others, substructural logics as well as logics with nondeterministic semantics, and subsume all logics endowed with an algebraic semantics. 1 Introduction Diagrammatic representation has been used in several areas of knowledge ranging from basic and human sciences to engineering as can be witnessed by several conferences in very different areas dedicated to the topic every year (for instance see [25, 30, 28]). One of the reasons is because diagrams are intuitive and provide a clear view of the phenomena they explain. Moreover, they can be used to make inferences about the reality they describe (see for instance [15] for a very broad introduction to diagrammatic techniques, [29] for a specific example in justice consisting of the use of a mathematical diagrammatic layout of arguments to make inferences instead of adopting only a traditional jurisprudential model, and [11] for applications in argumentation theory). Another example is category theory [20] that provides a diagrammatic notation for abstract algebra, where, for instance, an equation is substituted by a commutative diagram. The quest for rigorous diagrammatic reasoning has old roots and at the same time is very contemporary. For instance, L. Euler employed diagrams in order to illustrate relations between classes. J. Venn greatly improved the Euler's approach [31], and later on, an important contribution to the further development of Euler-Venn diagrams was made by C. S. Peirce [23]. Recently, 1 some effort has been dedicated to the definition of a formal system sound and complete for reasoning with diagrams [27, 17, 18]. For a nice discussion on diagrammatic logics see [6]. The right setting for defining logic systems has deserved a lot of attention from the scientific community. The most common approach, see [14, 7], is to look at specific logic systems and try to abstract its general features following the pioneering work in [3]. A promising direction is to incorporate diagrammatic features in logical reasoning [4, 5, 1] (as in Tarski's World, Hyperproof or Openproof). Herein, we propose diagrams as a unifying technique to present and reason with logics in an abstract way. More precisely, we use multi-graphs (or, for short, m-graphs) to define the language, the semantics and the deduction in a logic system. In signatures, the nodes of the m-graph are seen as sorts and the m-edges as language constructors. In interpretation structures, nodes are truth-values and m-edges are relations between truth-values (this approach to semantics can be seen as generalizing algebraic approaches to semantics of logics, see the overview in the classical monograph [24] and also in [14]). In deductive systems, the nodes are language expressions and the m-edges are inference rules. However, we need a bit more of structure to define language, denotation and derivation. For this purpose, we consider the category with non empty finite products freely generated from a given m-graph. At this stage, we look at formulas and at derivation steps as morphisms in that appropriate categories (here we are close to Lambek and Scott approach to categorical logic [19]). Furthermore, in this setting, we are able to cope appropriately with schematic reasoning. A novel feature of our approach is that interpretation structures and deductive systems are related to signatures through an abstraction process. That is, every m-graph corresponding to an interpretation structure is associated to the m-graph representing the underlying signature via an m-graph morphism. The same applies to deductive systems. This feature allows the definition of non-deterministic and partial semantics in a natural way. As a consequence of the generality of the approach we can define in this setting very different logics including substructural logics as well as logics with nondeterministic semantics and covering all logics endowed with an algebraic semantics [22, 21, 26, 10]. Our notion of derivation allows the rigorous control of the hypotheses used. Thus, it seems worthwhile to explore in the future this fine feature for logics where hypotheses are considered as resources. The structure of the paper is as follows. Section 2 is dedicated to defining signatures and interpretation structures as m-graphs. The central notions of m-graph and m-graph morphism are introduced in this section. Section 3 deals with formulas. They are morphisms in a category with non empty finite products freely generated from the signature m-graph. Section 4 concentrates on satisfaction and semantic entailment. In Section 5 we introduce deductive systems as an m-graph where the nodes are language expressions and m-edges include inference rules. Following this trend, in Section 6 we introduce derivation also with a diagrammatic intuition coping with the subtle notion of instan2 tiation of schematic rules and formulas. In Section 7, we state general results for soundness and completeness of logic systems. Finally, in Section 8, we give some insight of how to accommodate provisos and quantification in our setting. We assume a very moderate knowledge of category theory (the interested reader can consult [20]). 2 Signatures and models as m-graphs A signature is to be seen as a multi-graph whose nodes are the sorts (indicating the relevant kinds of notions) and whose m-edges are the language constructors. For instance, a propositional signature can be seen as a multi-graph with a node, named π, representing the notion of formula and including an m-edge ¬ from π to π for the negation constructor and an m-edge ⊃ for the implication constructor from ππ to π. π  ⊃ ¬ \\ Figure 1: Multi-graph for a propositional signature. Propositional symbols are zero-ary constructors and should also be represented in the multi-graph. For this purpose we consider a special node, named ♦, and an m-edge for each propositional symbol from ♦ to π. π  ⊃ ¬ \\♦ q1 ''q2 22 q3 88 Figure 2: Multi-graph for a propositional signature with propositional symbols. By a multi-graph, in short, an m-graph, we mean a tuple G = (V,E, src, trg) where: • V is a set (of vertexes or nodes); • E is a set (of m-edges); • src : E → V +; • trg : E → V ; 3 where V + denotes the set of all finite non-empty sequences of V . We may write e : s → v or e ∈ G(s, v) when e ∈ E, src(e) = s and trg(e) = v, and may write G(−,−) for the collection of m-edges in E. A language signature or, simply, a signature is a tuple Σ = (G, π, ♦) where G = (V,E, src, trg) is a m-graph, π and ♦ are in V , and such that no medge has ♦ as target. The nodes in V play the role of language sorts, node π being the propositions sort (the sort of schema formulas), and node ♦ being the concrete sort. The m-edges play the role of constructors for building expressions of the available sorts. The concrete sort allows the construction of concrete expressions. Example 2.1 Let Π be a set of propositional symbols. The propositional signature ΣΠ is a m-graph with sorts π and ♦ and the following m-edges: • p : ♦→ π for each p in Π; • ¬ : π → π; • ⊃ : ππ → π. The m-edges ¬ and ⊃ represent the connectives negation and implication, respectively. ∇ Example 2.2 The modal signature ΣΠ is a m-graph obtained from ΣΠ by adding the m-edge  : π → π for representing the modal operator  of necessity. ∇ Example 2.3 The propositional signature with conjunction and disjunction Σ∧,∨Π is a m-graph obtained from ΣΠ by adding the m-edges ∧,∨ : ππ → π for representing conjunction ∧ and disjunction ∨. ∇ Example 2.4 The propositional signature Σ∧,∨,◦Π is a m-graph obtained from Σ∧,∨Π by adding the m-edge ◦ : π → π. ∇ Example 2.5 Let F = {Fn}n∈N0 be a family where Fn is a set (with the function symbols of arity n). The equational signature ΣEQF is a m-graph with the sorts π, ♦ and θ, and the following m-edges: • f : ♦→ θ for each f in F0; • f : n{ }} { θ . . . θ → θ for each f in Fn; • ≈: θθ → π. The m-edge ≈ represents the equality symbol. ∇ An interpretation structure, also called a model, over a signature includes an m-graph where the nodes are values and the m-edges are operations on the 4 t f ¬f KK ¬t --⊃tt nn ⊃ft oo ⊃tf ?? ⊃ff  q′1 33 q′2  q′3 "" Figure 3: The operations m-graph for an interpretation structure over the propositional signature described in Figure 2. values. For instance, in the case of propositional logic, that m-graph could be the one specified in Figure 3. However, this is not enough because we need to know how the values are related to sorts and how operations are related to constructors, that is, we need to relate m-graphs, as depicted in Figure 4 and illustrated in Table 1 for the case of the propositional logic. π  ⊃ ¬ \\♦ q1 ''q2 22 q3 88 t f ¬f KK ¬t --⊃tt nn ⊃ft oo ⊃tf ?? ⊃ff  q′1 33 q′2  q′3 "" KS Figure 4: Abstraction map from the operations m-graph presented in Figure 3 and the signature m-graph presented in Figure 2. By a m-graph morphism h : G1 → G2 we mean a pair of maps{ hv : V1 → V2 he : E1 → E2 such that: 5 f , t π  ♦ q′1 q1 q′2 q2 q′3 q3 ¬f ,¬t ¬ ⊃ff ,⊃ft,⊃tf ,⊃tt ⊃ Table 1: Correspondence between the constructors and the operations for propositional logic. • src2 ◦ he = hv ◦ src1; • trg2 ◦ he = hv ◦ trg1. In the sequel we denote by mGraph the category of m-graphs and their morphisms where identities and compositions are defined as expected. Moreover, given a set S and s ∈ S+, we denote by |s| the length of s and, for each i = 1, . . . , |s|, we denote by (s)i the i-th element of s. Furthermore, given a map f : S → R, we let f+ be the map λ s . f((s)1) . . . f((s)n) : S+ → R+. For the sake of simplicity, we tend to write f for f+ when no confusion arises. We now define the concept of interpretation structure, which departs from a novel perspective in which semantics is abstracted into the syntax and not the other way around. In many cases an interpretation structure is an algebra (that is, it includes operations and sets for each sort) and the denotation consists of assigning to each logical constructor an operator over the appropriate sort. In other words, in many cases, denotation is a concretization process. In our case, we adopt a dual approach. We instead use a graph-theoretic approach (more general than an algebra) for representing truth-values and, possibly nondeterministic operations, and then we assign them to sorts and constructors. In a sense we abstract from the truth-values and operations the linguistic expressions assigned to them. An interpretation structure I over a signature (G, π, ♦) is a tuple (G′, α,D, ) such that G′ is an m-graph (the operations graph), α : G′ → G is an m-graph morphism (the abstraction morphism), D ⊆ (αv)−1(π) is a non-empty set and  ∈ (αv)−1(♦). The set V ′ of nodes of the operations graph is called the universe. Observe that V ′ is partitioned by α: we denote by V ′v the domain (α v)−1(v) of values for each v in V . The elements of V ′π are the truth values and the elements of V ′ ♦ are the concrete values. The elements of the set D are the distinguished truth values. The requirement on D excludes trivial cases. Given s in V + we denote by V ′+s the subset of V ′+ consisting of the set ((αv)+)−1(s), that is, {s′ : (αv)+(s′) = s}. The set E′ of m-edges of the operations graph is also partitioned by α: we denote by E′e the set (α e)−1(e) for each e in E. In the sequel, we may call the pair (G′, α) a basis over a m-graph G. 6 An interpretation structure is a pair (Σ, I) where Σ is a signature and I is an interpretation structure over Σ. An interpretation system I is a pair (Σ, I) where Σ is a signature and I is a class of interpretation structures over Σ. Example 2.6 Interpretation structure for propositional logic. Consider the signature ΣΠ as introduced in Example 2.1 where Π = {q1, q2, q3}. Let v : {q1, q2, q3} → {f , t} be a classical valuation such that v(q1) = t and v(q2) = v(q3) = f . The interpretation structure (G′, α,D, ) over ΣΠ corresponding to v is as follows: • G′ is such that1: V ′ = {f , t} ∪ {}; E′ = {q′1, q′2, q′3,¬f ,¬f ,⊃ff ,⊃ft,⊃tf ,⊃tt}; src′ and trg′ are such that: q′1 : → t; q′2 : → f ; q′3 : → f ; ¬f : f → t; ¬t : t→ f ; ⊃ff : f f → t; ⊃ft : f t→ t; ⊃tf : t f → f ; ⊃tt : t t→ t. • α : G′ → G is such that: αv(f) = π; αv(t) = π; αv() = ♦; αe(q′i) = qi for i = 1, 2, 3; αe(¬v′) = ¬ for each v′ in V ′π; αe(⊃v′1v′2) = ⊃ for each v ′ 1 and v ′ 2 in V ′ π. • D = {t}. Observe that V ′π = {f , t} and, for instance, E′¬ = {¬f : f → t,¬t : t→ f} where the m-edges ¬f and ¬t represent the pairs (f , t) and (t, f), respectively. ∇ 1Using module 2 arithmetical operations within V ′. 7 Example 2.7 Interpretation structure for modal logic T. Consider the signature ΣΠ as introduced in Example 2.2 where Π = {q1, q2, q3}. Let (A,∧,∨,−,⊥,>,) be a modal algebra for modal logic T , and v a valuation over the algebra, that is, a map from {q1, q2, q3} → A (see [9]). The interpretation structure (G′, α,D, ) over ΣΠ corresponding to the algebra and the valuation is as follows: • G′ is such that: V ′ = A ∪ {}; E′ = {q′1, q′2, q′3}∪{¬a : a ∈ A}∪{⊃a1a2 : a1 ∈ A and a2 ∈ A}∪{a : a ∈ A}; src′ and trg′ are such that: q′i : → v(qi) for i = 1, 2, 3; ¬a : a→ −a for each a in A; ⊃a1a2 : a1 a2 → ((−a1) ∨ a2) for each a1 and a2 in A; a : a→ a for each a in A. • α : G′ → G is such that: αv(a) = π; αv() = ♦; αe(q′i) = qi for i = 1, 2, 3; αe(¬a) = ¬; αe(⊃a1a2) = ⊃; αe(a) = . • D = {>}. ∇ Substructural logics can also be represented in our graph-theoretic context as we illustrate in the next example. Example 2.8 Interpretation structure for relevance logic R. Consider the signature Σ∧,∨Π as introduced in Example 2.3 where Π = {q1, q2}. Let m = (W,R, 0, ∗, v) be an R-frame for relevance logic R (see [12]) with a valuation v. The interpretation structure (G′, α,D, ) over Σ∧,∨Π corresponding to m is defined as follows: • G′ is such that: V ′ = ℘W ∪ {}; E′ = {q′1, q′2} ∪ {¬b : b ∈ ℘W} ∪ {⊃b1b2 : b1, b2 ∈ ℘W} ∪ {∧b1b2 : b1, b2 ∈ ℘W} ∪ {∨b1b2 : b1, b2 ∈ ℘W}; src′ and trg′ are such that: q′1 : → ∅; q′2 : →W ; 8 ¬b : b→ {w ∈W : w∗ /∈ b}; ⊃b1b2 : b1 b2 → {w ∈W : Rww1w2 and w1∈b1 implies w2 ∈ b2}; ∧b1b2 : b1 b2 → b1 ∩ b2; ∨b1b2 : b1 b2 → b1 ∪ b2. • α : G′ → G is such that: αv(b) = π; αv() = ♦; αe(q′i) = qi for i = 1, 2; αe(¬b) = ¬; αe(⊃b1b2) = ⊃; αe(∧b1b2) = ∧; αe(∨b1b2) = ∨. • D is the set of all subsets of W containing 0. ∇ Although in the examples above the graph-theoretic interpretation structures are algebraic in nature, that is not necessarily so. Indeed, graph-theoretic interpretation structures can even be non deterministic or partial. This is the case with the interpretation structure that we now consider. Example 2.9 Non-deterministic interpretation structure. Consider the signature Σ∧,∨,◦Π as introduced in Example 2.4 for Π = {q1, q2}, and the interpretation structure Ind = (G′, α,D, ) over Σ ∧,∨,◦ Π (inspired by [2]) where: • G′ is such that2: V ′ = {t, I, f} ∪ {}; E′ is composed of the following m-edges (note that src′ and trg′ are also being defined): q′1 : → f ; q′2 : → I; ¬v′1v′2 : v ′ 1 → v′2 where v′1 is in {I, f} and v′2 is in D; ¬tf : t→ f ; ◦v′1v′2 : v ′ 1 → v′2 where v′1 is in {t, f} and v′2 is in V ′π; ◦If : I→ f ; ⊃v′1v′2v′ : v ′ 1 v ′ 2 → v′ where v′1 is f or v′2 is in D, and v′ is in D; ⊃v′ff : v′ f → f for v′ is in D; ∧v′1v′2v′ : v ′ 1 v ′ 2 → v′ where v′1, v′2 and v′ are in D; 2Intuitively speaking, t represents a consistently true formula, that is, a true formula whose negation is false; I represents a inconsistently true formula, that is, a true formula whose negation is true; f represents a false formula. Observe that in Ind is not possible to have both a formula and its negation as false. 9 ∧v′1v′2f : v ′ 1 v ′ 2 → f where v′1 is f or v′2 is f ; ∨v′1v′2v′ : v ′ 1 v ′ 2 → v′ where v′1 or v′2 are in D, and v′ is in D; ∨fff : f f → f . • α : G′ → G is such that: αv(v′) = π with v′ in {t, I, f}; αv() = ♦; αe(q′1) = q1; αe(q′2) = q2; αe(¬v′1v′2) = ¬ for every ¬v′1v′2 in E ′; αe(◦v′1v′2) = ◦ for every ◦v′1v′2 in E ′; αe(⊃v′1v′2b) = ⊃ for every ⊃v′1v′2b in E ′; αe(∧v′1v′2b) = ∧ for every ∧v′1v′2b in E ′; αe(∨v′1v′2b) = ∨ for every ∨v′1v′2b in E ′. • D = {t, I}. A graphical perspective of part of the interpretation structure Ind, comprising negation and propositional symbols, can be seen in Figure 5. π ¬ cc♦ q1 ** q2 44  I t f q′1 11 q′2 "" ¬II  ¬It  ¬fI KK ¬ft GG¬tf  α KS Figure 5: Part of interpretation structure Ind described in Example 2.9. Observe that the denotation of the paraconsistent negation ¬ and of the consistency connective ◦ is not deterministic. ∇ Semantics of logics using several sorts can also be expressed very intuitively in our setting as we illustrate in the following example. 10 Example 2.10 Interpretation structure for equational logic. Consider the signature ΣEQF as introduced in Example 2.5. Let (A, {FnA : n ≥ 0}) be an algebra for (one-sorted) equational logic EQ where fA : An → A for each fA ∈ FnA (see [8, 16]). The interpretation structure (G′, α,D, ) over ΣEQF corresponding to the algebra is as follows: • G′ is such that: V ′ = A ∪ {} ∪ {0, 1}; E′ = {fa1...an : a1, . . . , an ∈ A} ∪ {≈a1a2 : a1, a2 ∈ A}; src′ and trg′ are such that: fa1...an : a1 . . . an → fA(a1 . . . an); ≈a1a2 : a1a2 → b where b is 1 iff a1 is equal to a2. • α : G′ → G is such that: αv(a) = θ; αv() = ♦; αv(0) = π; αv(1) = π; αe(fa1...an) = f ; αe(≈a1a2) is ≈. • D = {1}. ∇ 3 Formulas as paths At first sight a formula can be seen as a path over the signature m-graph. For instance, in the context of the signature for propositional logic presented in Example 2.1, the formula (¬ q1) ⊃ q2 corresponds to the path described in Figure 6. It is convenient however to work on the richer setting of the category ♦ q1 // π ¬ // π >> >> >> >> ⊃ // π ♦ q2 // π  Figure 6: Formula (¬ q1)⊃ q2 as a path in the signature m-graph. generated by the signature m-graph. In this setting sequences of sorts are first class citizens as well as pairing of morphisms. Moreover projections will be available (they are very useful for dealing with schema formulas). In this 11 ♦ π ⊃ ◦ 〈¬ ◦ q1, q2〉 // Figure 7: Formula (¬ q1)⊃ q2 as a morphism in the category generated by the signature m-graph. context, the formula (¬ q1) ⊃ q2 corresponds to the morphism presented in Figure 7. Before proceeding with the study of language expressions in the graphtheoretic account of logics proposed herein, we have to present first some technical preliminaries (we illustrate some of the constructions with the running example of the formula (¬ q1)⊃ q2). By a non-empty path en . . . e1 over a m-graph G we mean a finite and nonempty sequence of elements of E such that src(ek+1) = trg(ek) for k = 1, . . . , n− 1. The source of a non-empty sequence en . . . e1 is src(e1) and the target of that sequence is trg(en). To each element s of V + we associate an empty path, denoted by εs. The source and target of an empty sequence εs is s. A path w can be written as w : s → t whenever the source of w is s and the target of w is t. We denote by paths(G) the set of all paths over the m-graph G. The main objective now is to freely generate a category with non empty finite products out of a given m-graph. The idea is that the objects of the generated category are non-empty finite sequences of vertexes of the m-graph and that each path w : s → t induces a morphism ŵ : s → t. Moreover, the object v1 . . . vn is the object v1 × * * * × vn in the obtained category. The construction is done in several steps. (i) From a m-graph G we obtain a (classical) graph G† where the vertexes are in V + and the edges besides containing the m-edges in G contain also additional edges for projections and tuples; (ii) from G† we freely generate a category G‡ whose objects are the same as the vertexes of G† and including morphisms for edges, paths, projections and tuples; (iii) from G‡ we get the envisaged category G+ by making a quotient over the class of morphisms ensuring that projections and tuples have the required universal properties. Before presenting the construction we introduce some notation. Let fpCat be the category of categories with non empty finite products. As usual in a category with products, we denote by pb1×...×bni the i-th canonical projection of the product b1×. . .×bn for n ≥ 1. Given morphisms f1 : b→ b1, . . . , fn : b→ bn, we refer to 〈f1, . . . , fn〉 : b→ (b1 × . . .× bn) as the unique morphism such that pb1×...×bni ◦ 〈f1, . . . , fn〉 = fi for every i. If f1 : b1 → b′1, . . . , fn : bn → b′n are morphisms then f1 × . . .× fn : b1 × . . .× bn → b′1 × . . .× b′n will stand for the morphism 〈f1 ◦ pb1×...×bn1 , . . . , fn ◦ pb1×...×bnn 〉. As usual, 〈f1, . . . , fn〉 and f1 × . . .× fn will be identified with f1 when n is 1. The aim now is to define the category with non empty finite products G+ from a m-graph G, following the steps sketched above. 12 i. From a m-graph G to a graph G†. We start by defining a family {G†k = (V +, E†k, src † k, trg † k)}k≥1 of m-graphs such that • E†1 = E ∪ {p v1...vn i : v1, . . . , vn ∈ V, n ≥ 2, i = 1, . . . , n}; • src†1(e) = src(e) and trg † 1(e) = trg(e) whenever e is in E, src † 1(p v1...vn i ) = v1 . . . vn and trg † 1(p v1...vn i ) = vi; • E†k is the union of E † k−1 with ∪j=2,...,k{〈w1, . . . , wj〉 : w1, . . . , wj are paths over G†k−1 with target in V and with the same source}; • src†k(e) = src † k−1(e) and trg † k(e) = trg † k−1(e) if e ∈ E † k−1, otherwise e is 〈w1, . . . , wj〉, src†k(e) = src † k−1(w1) and trg † k(e) = trg † k−1(w1) . . . trg † k−1(wj). So G† is (V +, E†, src†, trg†) where E† is ∪k∈NE†k, src †(e) = src†j(e) and trg †(e) = trg†j(e) for e in E † j . ♦ ππ π 〈¬q1, q2〉 // ⊃ // Figure 8: Formula (¬ q1)⊃q2 represented as a path over the graph G† generated by the signature m-graph G described in Example 2.1. ii. From a graph G† to a category G‡. Given a graph G†, G‡ is the category freely generated by graph G†. That is, the category obtained as follows: • the objects are the vertexes of G†; • each path w : s→ t in over G† determines a unique morphism w‡ : s→ t in G‡ in such a way that if w is in E we set w‡ = w; • the identity morphism ids : s→ s is εs‡; • (w2)‡ ◦ (w1)‡ = (w2w1)‡ whenever w2 : s→ t and w1 : r → s. ♦ πππ ⊃ ◦ 〈¬q1, q2〉 ##〈¬q1, q2〉 // ⊃ // Figure 9: Formula (¬ q1) ⊃ q2 represented as a morphism in the category G‡ generated from the signature m-graph G described in Example 2.1. iii. From a category G‡ to a category G+ with non empty finite products. Given a category G‡, the category G+ is defined as follows: 13 • the set of objects of G+ is the same as the set of objects of G‡, i.e., is V +; • the collection G+(−,−) of morphisms in G+ is the quotient G‡(−,−)/∆‡ where ∆‡ ⊆ G‡(−,−)2 is the least equivalence relation such that: – ((pv1...vni 〈w1, . . . , wn〉) ‡, wi ‡) is in ∆‡ for i = 1, . . . , n, where wj : s→ vj are paths over G† and vj is in V for j = 1, . . . , n; – (w‡, 〈u1, . . . , un〉‡) is in ∆‡ if ((pv1...vni w) ‡, ui ‡) is in ∆‡ where w : s→ v1 . . . vn and ui : s→ vi are paths over G† and vi ∈ V , i = 1, . . . , n; – ((w2w1) ‡, (u2u1) ‡) is in ∆‡ if (w2‡, u2‡) and (w1‡, u1‡) are in ∆‡ where w2, u2 : s1 → t and w1, u1 : s→ s1 are paths over G†; • in G+ the identity in s is the morphism [εs‡]∆‡ ; • in G+ the operation ◦ is such that [w2‡]∆‡ ◦ [w1‡]∆‡ = [(w2w1) ‡]∆‡ . We denote by ŵ the equivalence class [w‡]∆‡ . The first clause of the equivalence relation establishes that the i-th projection has the expected behavior when applied to a tuple, that is, is equivalent to the i-th component. The second clause imposes the universal property of the product. Finally, the third clause asserts that composition preserves equivalence. ♦ ππ π ⊃ ◦ 〈¬ ◦ q1, q2〉 %%〈¬ ◦ q1, q2〉 // ⊃ // Figure 10: Formula (¬ q1) ⊃ q2 as a morphism in the category G+ generated from the signature m-graph G described in Example 2.1. The previous construction deserves some comments. Firstly, note that for any path en . . . e1 over G† where ei is in E† for i = 1, . . . , n, if ek is a projection and k > 1 then ek−1 is a tuple. Secondly, it is immediate to see that the domains and codomains of the morphisms in G+ are well defined. In fact it is very easy to prove the following lemma by induction on ∆‡: Lemma 3.1 Given a m-graph G, if (w1‡, w2‡) is in ∆‡ and w1 : s→ t then w2 is also a path from s to t. Thirdly, note that G+ is, by construction, a category with non empty finite products. Proposition 3.2 The category G+ has non empty finite products. 14 Proof: For simplicity, consider the objects v1, v2 which are sequences of length one. Their product is (v1v2, pv1v21 , p v1v2 1 ). Given morphisms ŵ1 : s → v1 and ŵ2 : s → v2. We will show that 〈w1, w2〉 is the unique morphism in G+ such that pv1v2i ◦ 〈w1, w2〉 = ŵi for i = 1, 2. (a) pv1v21 ◦ 〈w1, w2〉 = ŵ1. Note that pv1v21 ◦ 〈w1, w2〉 = [p v1v2 1 ‡]∆‡ ◦ [〈w1, w2〉 ‡]∆‡ which is [pv1v21 〈w1, w2〉 ‡]∆‡ = [w1‡]∆‡ = ŵ1. (b) Unicity. Assume that û : s → v1v2 such that pv1v2i ◦ û = ŵi for i = 1, 2. Hence, [pv1v2i u ‡]∆‡ = p v1v2 i ◦ û = ŵi = [wi‡]∆‡ . Therefore, ((p v1v2 i u) ‡, wi ‡) is in ∆‡ for i = 1, 2 and so (u‡, 〈w1, w2〉‡) is in ∆‡. Hence [u‡]∆‡ = [〈w1, w2〉 ‡]∆‡ . That is, û = 〈w1, w2〉. QED It is worthwhile to note that 〈ŵ1, . . . , ŵn〉 is 〈w1, . . . , wn〉 when wi : s → vi and vi ∈ V according to Proposition 3.2. Given the path wi : s → si over G† where si has length mi, for i = 1, . . . , n, the tuple 〈ŵ1, . . . , ŵn〉 is 〈ps11 w1, . . . , p s1 m1w1, . . . , p sn 1 wn, . . . , p sn mnwn〉. Moreover, for i = 1, . . . , n, let si in V + be vi1 . . . vimi , where vi1, . . . , vimi are in V . Then the product of s1, . . . , sn denoted by (s1 × . . .× sn, ps1×...×sn1 , . . . , p s1×...×sn n ) can be taken to be the object v11 . . . v1m1 . . . vn1 . . . vnmn with the morphisms 〈pv11...v1m1 ...vn1...vnmnm1+...+mi−1+1 , . . . , p v11...v1m1 ...vn1...vnmn m1+...+mi−1+mi 〉 for i = 1, . . . , n. Given a signature Σ = (G, π, ♦), the objects of G+ are the finite and nonempty sequences of sorts in the signature Σ and the morphisms of G+ play the role of expressions (schema formulas, schema terms, whatever) over Σ, and constitute the language generated by the signature, also denoted by L(Σ). More precisely, each morphism ŵ : s→ t in G+ represents an expression of type s→ t. Note that a morphism in G+ corresponds to a path over the signature m-graph G. For instance, using the constructors of signature ΣΠ, the morphism ⊃ ◦ 〈¬ ◦ q1, q2〉 corresponds to the path ⊃〈¬ q1, q2〉 over G† where q1 and q2 are propositional symbols, that is, are m-edges in E of type ♦→ π, since: • q1, q2,⊃,¬ ∈ E†1; • 〈¬ q1, q2〉 ∈ E†2; hence ⊃〈¬ q1, q2〉 is a path over G†2 and so over G†. Moreover, it is straightforward to see that ⊃ ◦ 〈¬ ◦ q1, q2〉 is ⊃〈¬ q1, q2〉. Indeed, ⊃ ◦ 〈¬ ◦ q1, q2〉 = ⊃ ◦ 〈¬ q1, q2〉 = ⊃ ◦ 〈¬ q1, q2〉 = ⊃ ◦ 〈¬ q1, q2〉. 15 In the sequel, when there is no ambiguity, we may denote a morphism ê of G+ where e is a m-edge of E simply by e. Expressions with the object ♦ as source are said to be concrete expressions. Thus, G+(♦, π) is the set of all concrete formulas, or simply the set of all formulas in the language of Σ. This set corresponds to the traditional (set-theoretic) notion of language of propositions over Σ. For instance, the morphism: ⊃ ◦ 〈¬ ◦ p1,⊃ ◦ 〈p2, p1〉〉 : ♦→ π is an expression of type ♦ → π and so is a formula, represented more simply as ((¬ p1) ⊃ (p2 ⊃ p1)). In the sequel we may simplify the representation of morphisms in a similar way. Clearly, it is possible to write expressions with a non-concrete object as source. Such expressions are said to be schema expressions because only part of their structure is known (or determined), and when its target is π we may call them schema formulas. So by a schema formula we mean a morphism in G+ whose target is π and with no constraints over the source. Schema variables are projections from π . . . π to π, or from π . . . π♦ to π, where the π-sequence at the source is non-empty, and are denoted by ξ, ξ′, ξ′′, . . . , ξ1, ξ ′ 1, ξ ′′ 1 , . . . , ξ2, ξ ′ 2, ξ ′′ 2 , . . .. Example 3.3 Consider the signature ΣΠ defined in Example 2.1. The schema formula (ξ1 ⊃ (ξ1 ⊃ ξ1))⊃ ξ2 is the morphism ⊃ ◦ 〈⊃ ◦ 〈ξ1,⊃ ◦ 〈ξ1, ξ1〉〉, ξ2〉 : ππ → π where ξi is pππi , for i = 1, 2; and the schema formula (ξ3 ⊃ (ξ1 ⊃ ξ2))⊃ ξ4 is the morphism ⊃ ◦ 〈⊃ ◦ 〈ξ3,⊃ ◦ 〈ξ1, ξ2〉〉, ξ4〉 : ππππ → π where ξi is pππππi , for i = 1, . . . , 4. Given the propositional symbol p : ♦ → π, the morphism ⊃ ◦ 〈⊃ ◦ 〈p ◦ pππ♦3 ,⊃ ◦ 〈ξ1, p ◦ p ππ♦ 3 〉〉, ξ2〉 : ππ♦→ π where ξi is pππ♦i , for i = 1, 2, corresponds to the schema formula (p⊃ (ξ1 ⊃ p))⊃ ξ2. Finally, given the propositional symbols p, q : ♦→ π, the morphism ⊃ ◦ 〈⊃ ◦ 〈p ◦ pπ♦2 ,⊃ ◦ 〈ξ1, q ◦ p π♦ 2 〉〉, ξ1〉 : π♦→ π represents the schema formula (p⊃ (ξ1 ⊃ q))⊃ ξ1 where ξ1 is pπ♦1 . ∇ 16 Non-concrete expressions are very useful for setting up deductive rules that can be instantiated using substitutions. Deductive rules with non-concrete expressions are called schema rules. Expression instantiation and rule instantiation is achieved using morphism composition. Given the expressions ŵ : s2 → s3 and û : s1 → s2, the expression instantiation of the former by the latter is the expression ŵ ◦ û. Example 3.4 Let φ be the schema formula ⊃ ◦ 〈⊃ ◦ 〈¬ ◦ ξ, ξ′〉,⊃ ◦ 〈ξ, ξ′′〉〉 where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 . We can interchange ξ with ξ ′ by instantiating φ with 〈ξ′, ξ, ξ′′〉 : πππ → πππ, obtaining the following schema formula φ ◦〈ξ′, ξ, ξ′′〉 = ⊃ ◦ 〈⊃ ◦ 〈¬ ◦ ξ, ξ′〉 ◦ 〈ξ′, ξ, ξ′′〉,⊃ ◦ 〈ξ, ξ′′〉 ◦ 〈ξ′, ξ, ξ′′〉〉 = ⊃ ◦ 〈⊃ ◦ 〈¬ ◦ ξ′, ξ〉,⊃ ◦ 〈ξ′, ξ′′〉〉 from πππ to π. On the other hand, if we want to make concrete the second slot of φ we could consider the propositional symbol p : ♦→ π, and then instantiate φ with 〈ξ1, p ◦pππ♦3 , ξ2〉 : ππ♦→ πππ where ξj = p ππ♦ j for j = 1, 2 obtaining the following schema formula φ ◦〈ξ1, p ◦pππ♦3 , ξ2〉 = = ⊃ ◦ 〈⊃ ◦ 〈¬ ◦ξ, ξ′〉 ◦ 〈ξ1, p ◦pππ♦3 , ξ2〉,⊃ ◦ 〈ξ, ξ′′〉 ◦ 〈ξ1, p ◦p ππ♦ 3 , ξ2〉〉 = ⊃ ◦ 〈⊃ ◦ 〈¬ ◦ ξ1, p ◦pππ♦3 〉,⊃ ◦ 〈ξ1, ξ2〉〉 from ππ♦ to π. ∇ 4 Satisfaction as a path The main objective of the section is to introduce the notion of denotation of an expression, and the notion of entailment of an expression from a set of expressions. Intutively, denotation of a formula in the context of an interpretation structure, is expected to be the set of the targets of all paths in the operations m-graph that are mapped by the abstraction map to the formula. Consider the denotation of the formula (¬ q1)⊃q2 in the interpretation structure described in Example 2.6. Then, it is not difficult to see that the denotation of that formula is the target of the path in Figure 11, that is, the truth value t. Equivalently, as we will see, denotation of a formula can also be defined as the set of targets of all morphisms in the category G′+, corresponding to the formula (¬ q1)⊃ q2. As an example see Figure 12. As a consequence, we need to extend the abstraction map α to a functor α+ from the category G′+ generated from the operations m-graph to the category G+ generated from the signature m-graph. 17  q′1 // t ¬t // f ;; ;; ;; ;; ⊃ff // t  q′2 // f  Figure 11: Path in the operations m-graph G′, introduced in Example 2.6 for propositional logic, corresponding to formula (¬ q1)⊃ q2.  ff t ⊃ff ◦ 〈¬f ◦ q′1, q′2〉 %%〈¬f ◦ q′1, q′2〉 // ⊃ff // Figure 12: Morphism in G′+ denoting formula (¬ q1)⊃ q2. So, given an m-graph morphism h : G′ → G, we now present a general way to induce a functor h+ : G′+ → G+. First, we need to induce a graph morphism h† from a m-graph morphism h. Given a m-graph morphism h : G′ → G we define inductively the graph morphism h† : paths(G′†)→ paths(G†) as follows: • h†(εv′1...v′n) = εhv(v′1)...hv(v′n) for v ′ 1, . . . , v ′ n in V ′; • h†(e′w′) = he(e′)h†(w′) where e′ is a m-edge in E′; • h†(pv ′ 1...v ′ n i w ′) = ph v(v′1)...h v(v′n) i h †(w′); • h†(〈w′1, . . . , w′n〉w′0) = 〈h†(w′1), . . . , h†(w′n)〉h†(w′0). Note that, if w′ : s′ → t′ then h†(w′) : (hv)+(s′) → (hv)+(t′). The main result to be stated is the following one: Proposition 4.1 Given a m-graph morphism h : G′ → G, the pair h+ = ((hv)+, (he)+), where (he)+(ŵ′) = ĥ†(w′) and (hv)+ is the extension of hv to sequences, is a functor from G′+ to G+. In order to prove the result above, we need an auxiliary technical lemma stating that (he)+ is well defined (that is, its value does not depend on the particular chosen representative of the equivalence class). Lemma 4.2 Given a m-graph morphism h : G′ → G, if (w′1 ‡, w′2 ‡) is in ∆′‡ then (h†(w′1) ‡ , h†(w′2) ‡) is in ∆‡. 18 Proof: We show by induction on ∆′‡ that (h†(w′1) ‡ , h†(w′2) ‡) is in ∆‡: - (w′1 ‡, w′2 ‡) is such that w′1 is p v′1...v ′ n i 〈u′1, . . . , u′n〉 and w′2 is u′i. The result follows since (ph v(v′1)...h v(v′n) i 〈h†(u′1), . . . , h†(u′n)〉 ‡ , h†(u′i) ‡) is in ∆‡, h†(w′1) ‡ is the first element of that pair and h†(w′2) ‡ is the second; - (w′1 ‡, w′2 ‡) is such that w′2 is 〈u′1, . . . , u′n〉 and ((p v′1...v ′ n i w ′ 1) ‡ , u′i ‡) ∈ ∆′‡ for i = 1, . . . , n. So ((ph v(v′1)...h v(v′n) i h †(w′1)) ‡ , h†(u′i) ‡) ∈ ∆‡ for i = 1, . . . , n by induction hypothesis. Then (h†(w′1) ‡ , 〈h†(u′1), . . . , h†(u′n)〉 ‡) is in ∆‡ by definition of ∆‡. The result follows since 〈h†(u′1), . . . , h†(u′n)〉 is h†(〈u′1, . . . , u′n〉); - (w′1 ‡, w′2 ‡) is such that w′1 is g ′ 1f ′ 1, w ′ 2 is g ′ 2f ′ 2, and (g ′ 1 ‡, g′2 ‡) and (f ′1 ‡, f ′2 ‡) are in ∆′‡. Hence, by induction hypothesis, (h†(g′1) ‡ , h†(g′2) ‡) and (h†(f ′1) ‡ , h†(f ′2) ‡) are in ∆‡, and so (h†(g′1)h †(f ′1) ‡ , h†(g′2)h †(f ′2) ‡) is also in ∆‡. The result follows since h†(w′1) ‡ is the first element of that pair and h†(w′2) ‡ is the second. - (w′1 ‡, w′2 ‡) is such that w′1 ‡ = w′2 ‡. Then by the uniqueness of the representation w′1 = w ′ 2 and so the result follows straightforwardly. - (w′1 ‡, w′2 ‡) is such that (w′2 ‡, w′1 ‡) is in ∆′‡. The result follows straightforwardly by induction hypothesis. - (w′1 ‡, w′2 ‡) is such that (w′1 ‡, g′‡) and (g′‡, w′2 ‡) are in ∆′‡. Then the result follows straightforwardly by induction hypothesis. QED Proof: (of Proposition 4.1) The map (he)+ is well defined by Lemma 4.2, and preserves identities since (he)+(idv′1...v′n) = (h e)+(εv′1...v′n) = h†(εv′1...v′n) = εhv(v′1)...hv(v′n) = idhv(v′1)...hv(v′n). The map (he)+ preserves compositions since (he)+(ŵ′2 ◦ ŵ′1) = (he)+(ŵ′2w′1) = h†(w′2w′1) = h†(w′2)h†(w′1) = ĥ†(w′2) ◦ ĥ†(w′1) = (he)+(ŵ′2) ◦ (he)+(ŵ′1). QED Finally, we observe that, from the results above, we obtain a functor *+ : mGraph→ fpCat defined in the obvious way. So, we are now able to define denotation of a path, and then, denotation of a morphism. With this purpose in mind, we have to give, for each sort, the starting values so that we can define denotation inductively. Observe that, as hinted before, the denotation of a path is a set of values. Recall that the concatenation A * B, or even AB, of the sets of sequences A and B is the set of sequences {ab : a ∈ A and b ∈ B}. Moreover, given an interpretation structure I over a signature Σ, and v1, . . . , vn in V , a subset S of V ′+v1...vn is a concatenation of basic sets whenever there exist S1 ⊆ V ′v1 , . . . , Sn ⊆ V ′ vn such that S is S1 . . . Sn. Given a concatenation of sets S1 . . . Sn we denote by (S1 . . . Sn)i its i-th component, that is, the set Si. The denotation of a concrete path w : ♦→ t over G† at I, represented by [[w]]I is a concatenation of basic sets contained in V ′+t , inductively defined on the complexity of the path w as follows: 19 • [[ε♦]]I is {}; • [[pv1...vmi w1]] I is ([[w1]] I)i where v1, . . . , vm are in V ; • [[〈w1, . . . , wn〉w0]]I is [[w1w0]]I . . . [[wnw0]]I ; • [[ew1]]I is the union of trg′(E′e(v′,−)) for each v′ in [[w1]] I , when e is in E. For instance, for evaluating ew1 over I, we start by evaluating w1 and getting a set of values. For each value s′ in the evaluation of w1, we pick all the medges in G′ with source s′ and which are mapped into e. Finally, the envisaged denotation is obtained by taking the collection of targets of such m-edges. Denotation is now extended to non-concrete paths. The denotation of the schema variables is given by an assignment, which must be also a component in the denotation process. An assignment ρ for an interpretation structure I over a signature Σ is a family {ρs}s∈V + such that ρs is [[ws]] I for some concrete path ws : ♦→ s. Observe that ρs is contained in V ′+s and is a concatenation of basic sets, and ρ♦ = {}. The denotation of a path w : s→ t over G† at I and ρ, denoted by [[w]]Iρ is a concatenation of basic sets contained in V ′+t , inductively defined on the complexity of the path w similarly to the denotation of a concrete path with the exception that [[εs]] Iρ is ρs. Example 4.3 Consider the interpretation structure Ind in Example 2.9. Then • [[q1 ∧ (¬ q1)]]Indρ = {I, t} since [[ε♦]] Indρ = {} [[q1]] Indρ = trg′(E′q1([[ε♦]] Indρ,−)) = trg′(E′q1({},−)) = trg′({q′1 : → I}) = {I} [[¬ q1]]Indρ = trg′(E′¬([[q1]]Indρ,−)) = trg′(E′¬(I,−)) = trg′({¬II : I→ I,¬It : I→ t} = {I, t} [[q1 ∧ (¬ q1)]]Indρ = trg′(E′∧([[q1]] Indρ[[¬ q1]]Indρ,−)) = trg′(E′∧({I}{I, t},−)) = trg′(E′∧({II, It},−)) = trg′({∧III : II→ I,∧IIt : II→ t, ∧ItI : It→ I,∧Itt : It→ t}) = {I, t}; 20 • [[ ◦ q1]]Indρ = {f} since [[ ◦ q1]]Indρ = trg′(E′◦([[q1]] Indρ,−)) = trg′(E′◦({I},−)) = trg′({◦If : I→ f}) = {f} ∇ As it is expected, the denotation of a path that is concrete does not depend on the assignments as the following result states. Proposition 4.4 Given an interpretation structure (Σ, I), assignments ρ1 and ρ2 over I, and a concrete path w, [[w]] Iρ1 = [[w]]Iρ2 . The next step is to extend denotation of paths to morphisms in order to evaluate expressions and, in particular, formulas. But first we have to state some technical lemmas. Proposition 4.5 Given an interpretation structure (Σ, I) and an assignment ρ over I such that ρs = [[ws]] I , then [[w]]Iρ = [[wws]] I for any path w : s→ t over G†. Proof: The proof follows by induction on the complexity of w: w is εs. Then [[w]] Iρ = ρs = [[ws]] I = [[wws]] I ; w is pŝiw0. Then [[w]] Iρ = [[pŝiw0]] Iρ = ([[w0]] Iρ)i = ([[w0ws]] I)i = [[pŝiw0ws]] I = [[wws]] I ; w is 〈u1, . . . , un〉u0. Then [[w]]Iρ = [[〈u1, . . . , un〉u0]]Iρ = [[u1u0]]Iρ . . . [[unu0]]Iρ = [[u1u0ws]] I . . . [[unu0ws]] I = [[〈u1, . . . , un〉u0ws]]I = [[wws]]I ; w is ew0. The thesis follows since [[w]] Iρ = [[ew0]] Iρ = ∪v′∈[w0]Iρtrg ′(E′e(v ′,−)) = ∪v′∈[w0ws]I trg ′(E′e(v ′,−)) = [[ew0ws]]I = [[wws]]I . QED In the sequel, we use ρs/[w]Iρ to refer to the assignment obtained from ρ by replacing ρs by the set [[w]] Iρ. Note that, by Poposition 4.5, ρ is well defined. The first result, in Proposition 4.6, is a substitution lemma adapted to our setting. Proposition 4.6 Given an interpretation structure (Σ, I) and an assignment ρ over I, [[w2w1]] Iρ=[[w2]] Iρ s/[w1] Iρ for paths w1 :s1→s2 and w2 :s2→s3 over G†. Proof: The proof follows by induction on the complexity of w2: w2 is εs. So [[w2w1]] Iρ = [[w1]] Iρ = (ρs/[w1]Iρ)s = [[w2]] Iρ s/[w1] Iρ ; w2 is psiw0. So [[w2w1]] Iρ = [[psiw0w1]] Iρ = ([[w0w1]] Iρ)i = ([[w0]] Iρ s/[w1] Iρ )i = [[psiw0]] Iρ s/[w1] Iρ = [[w2]] Iρ s/[w1] Iρ ; 21 w2 is 〈u1, . . . , un〉u0. Then [[w2w1]]Iρ = [[〈u1, . . . , un〉u0w1]]Iρ = [[u1u0w1]]Iρ . . . [[unu0w1]] Iρ = [[u1u0]] Iρ s/[w1] Iρ . . . [[unu0]] Iρ s/[w1] Iρ = [[〈u1, . . . , un〉u0]] Iρ s/[w1] Iρ = [[w2]] Iρ s/[w1] Iρ ; w2 is ew0. Therefore [[w2w1]] Iρ = [[ew0w1]] Iρ = trg′(E′e([[w0w1]] Iρ,−)) = trg′(E′e([[w0]] Iρ s/[w1] Iρ ,−)) = [[ew0]] Iρ s/[w1] Iρ = [[w2]] Iρ s/[w1] Iρ . QED The following result states that denotation is well defined. Proposition 4.7 Given an interpretation structure (Σ, I), if (w‡, u‡) is in ∆‡ then [[w]]Iρ = [[u]]Iρ for any assignment ρ over I. Proof: The proof follows by induction on ∆‡: - (w‡, u‡) is such that w is pv1...vni 〈w1, . . . , wn〉 and u is wi. Then [[w]] Iρ = [[pv1...vni 〈w1, . . . , wn〉]] Iρ = ([[〈w1, . . . , wn〉]]Iρ)i = ([[w1]]Iρ . . . [[wn]]Iρ)i = [[wi]]Iρ = [[u]]Iρ; - (w‡, u‡) is such that u is 〈u1, . . . , un〉, w : s → v1 . . . vn, ui : s → vi and ((pv1...vni w) ‡, ui ‡) is in ∆‡ for i = 1, . . . , n. Hence [[pv1...vni w]] Iρ = [[ui]] Iρ by induction hypothesis, for i = 1, . . . , n. So ([[w]]Iρ)i = [[ui]] Iρ for i = 1, . . . , n. Since [[w]]Iρ is a concatenation of basic sets then [[w]]Iρ = [[u1]] Iρ . . . [[un]] Iρ, and so the thesis follows straightforwardly; - (w‡, u‡) is such that w is w2w1, u is u2u1, and (w2‡, u2‡) and (w1‡, u1‡) are in ∆‡. So [[w1]] Iρ = [[u1]] Iρ and [[w2]] Iρ = [[u2]] Iρ by induction hypothesis for any assignment ρ. Then, by Proposition 4.6, [[w]]Iρ = [[w2w1]] Iρ = [[w2]] Iρ s/[w1] Iρ = [[u2]] Iρ s/[u1] Iρ = [[u2u1]] Iρ = [[u]]Iρ; - (w‡, u‡) is such that w‡ = u‡. Then by the uniqueness of the representation w = v and so the result follows straightforwardly; - (w‡, u‡) is such that (u‡, w‡) is in ∆‡. The result follows straightforwardly by induction hypothesis; - (w‡, u‡) is such that (w‡, u0‡) and (u0‡, u‡) are in ∆‡. Then the result follows straightforwardly by induction hypothesis. QED Capitalizing on Proposition 4.7, the denotation [[ŵ]]Iρ of a morphism ŵ in G+ over I and ρ is defined as [[ŵ]]Iρ = [[w]]Iρ. The notions of local and global satisfactions are the usual ones. A schema formula φ is said to be satisfied by I and ρ, written as I, ρ φ whenever [[φ]]Iρ is non-empty and is contained in D. Moreover, we say I satisfies φ, written as I φ 22 whenever I, ρ φ for every assignment ρ over I. Satisfaction is extended to sets of schema formulas as expected: I, ρ Γ if I, ρ γ for each γ ∈ Γ, and similarly for sequences of schema formulas: I, ρ φ1 . . . φn if I, ρ φi for i = 1, . . . , n. The definition of denotation given above is the usual for most logics. Examples of logics with a different notion of denotation are the paraconsistent logics referred to in [2]. In the case of these logics, although some of the operations are non deterministic, the denotation of a formula is always a fixed truth value. The definition in our approach of that variant of denotation seems feasible and we intend to explore the details in the future. Example 4.8 Consider the interpretation structure Ind in Example 2.9. Then Ind q1 ∧ (¬ q1) since [[q1 ∧ (¬ q1)]]Indρ = {I, t} is contained in D, see Example 4.3. Moreover, Ind 6 ◦q1 since [[ ◦ q1]]Indρ = {f} is not contained in D as shown in the same example. Therefore, Ind 6 (q1 ∧ (¬ q1))⊃ (◦q1) as expected for logics of formal inconsistency, see [10]. ∇ We are now ready to define semantic entailment. Given an interpretation system I = (Σ, I) and a set Γ ∪ {φ} of schema formulas over Σ, we say that Γ entails φ in I, written as Γ I φ, whenever I Γ implies I φ for every I in I. Similarly we define entailment over sequences of schema formulas as follows: ~γ I ~φ whenever I ~γ implies I ~φ for every I in I. The graph-theoretic semantics developed in this work can be said to subsume algebraic semantics, in the sense that, any logic endowed with an algebraic semantics can be presented in our setting in such a way that satisfaction and entailment are preserved. By a logic with an algebraic semantics we mean a pair composed by a signature and a class of algebras over that signature. Each algebra A is a triple (A, *, DA) composed by a set A of (truth values) with an operation cA : An → A for each constructor c of arity n in the signature and a subset DA contained in A of distinguished values. In this context the denotation [[φ]]A is homomorphic, that is [[c(φ1, . . . , φn)]] A = cA([[φ1]] A, . . . , [[φn]] A). A logic L with an algebraic semantics induces an interpretation system I(L) with the obvious signature and containing, for each algebra A, an interpretation structure IA = (G′, α,DA, ) defined as follows: • V ′ is the set of truth values of the algebra; 23 • E′ is composed, for each n-ary constructor c, by the set of m-edges ca1,...,an : a1 . . . an → cA(a1, . . . , an) for each a1, . . . , an ∈ A when n ≥ 1, or by c : → cA when n = 0; • αv(a) = π for each a ∈ A; • αe(ca1,...,an) = c for each a1, . . . , an ∈ A and αe(c) = c. The graph-theoretic semantics induced by the algebraic semantics coincides exactly in terms of denotation, satisfaction and entailment with the algebraic semantics, as we show now. Lemma 4.9 Given a logic with an algebraic semantics and an algebra A, then [[φ]]A = [[φ]]IA . Proof: By induction on the structure of φ: φ is c(φ1, . . . , φn). Therefore [[φ]]A = [[c(φ1, . . . , φn)]] A = cA([[φ1]] A, . . . , [[φn]] A) = cA([[φ1]] IA , . . . , [[φn]] IA) = trg′(c[φ1]IA ,...,[φn]IA ) = trg ′(E′c([[φ1]] IA . . . [[φn]] IA ,−)) = [[φ]]IA . QED Lemma 4.10 Given a logic with an algebraic semantics and an algebra A, then A φ iff IA φ. Proof: Assume that A φ. Then [[φ]]A ∈ DA. Hence [[φ]]IA ∈ DA by Lemma 4.9. So IA φ. The other direction follows similarly. QED Proposition 4.11 Let L be a logic with an algebraic semantics. Then, L and I(L) share the same entailment. Proof: Suppose Γ L φ and let IA be in I(L) such that IA Γ. Then A Γ by Lemma 4.10 and so A φ. Hence also by Lemma 4.10, IA φ as we wanted to show. The other direction follows similarly. QED 5 Deductive systems as m-graphs A deductive system is also described as a m-graph, the deductive m-graph. The nodes are formulas and inference rules are m-edges. The sources of each of those m-edges are the premises of the rule and the target is the conclusion. As an example consider the case of the well known Modus Ponens rule as depicted in Figure 13. The intuition behind this rule is as follows: starting with a pair of formulas, we select the first one (with the projection pππ1 ) and consider the formula obtained by their implication (with ⊃). Then, by MP, we conclude the second formula (with the projection pππ2 ). But, in a deductive system it is also necessary to consider an abstraction map to a deductive signature in order to abstract, to explain, the components of the deductive m-graph. So, herein, a deductive system is composed of three parts: the deductive signature, the deductive m-graph and the abstraction map. 24 ππ π pππ1  ππ π ⊃  ππ π pππ2  MP // Figure 13: Modus Ponens as an m-edge. The deductive signature is a language signature enriched with new m-edges for representing inference rules and new m-edges for axioms. By a deductive signature or, simply, a meta-signature we mean a tuple Φ = (Σ,>,R) where Σ = (G, π, ♦) is a language signature such that GΦ = (V Φ, EΦ, srcΦ, trgΦ) is a m-graph extending G with • V Φ = V ; • EΦ = E ∪ R where R = {Rn : n{ }} { π . . . π → π}n>0; and > is a set {>s : s→ π}s∈V + . As an example consider the enriched m-graph in Figure 14 for a deductive signature for propositional logic. π  ⊃,R2 . . . ¬,R1 cc♦ p // Figure 14: Enriched m-graph GΦ for the deductive signature of propositional logic. Each Rn is a symbolic expression for representing inference rules with n premises. Each >s is called s-verum and is important to represent, in our setting, axioms. An axiom is the target of a unary rule whose antecedent is a verum schema formula. The next step is to define deductive system. A deductive system over a deductive signature is a m-graph where the nodes are language expressions, that is, morphisms of the category generated by the deductive m-graph enriched with the verum edges, and the m-edges include, besides the language constructors (ensuring the commutativity of diagrams), the given inference rules. For instance, the well known Modus Ponens inference rule is seen as a m-edge whose source is the pair composed by the two morphisms corresponding to the premises and whose target is the morphism corresponding to the conclusion, see Figure 13. Given a deductive signature (Σ,>,R), where Σ is (G, π, ♦), we denote by G> the m-graph obtained by enriching G with the m-edges >s : s → π. We 25 say that a morphism ŵ of G+> is in G + whenever there is a path u over G† and û = ŵ. We may denote a schema formula of G+> not in G + as a verum schema formula. Given morphisms ŵ1 : s → s1 and ŵ2 : s1 → s2 of G+> in G + it is straightforward to see that ŵ2 ◦ ŵ1 is also in G+. Moreover given the morphism >s : s→ π of G+> it is straightforward to see that for any û : s→ s1 in G + > the morphism >s ◦ û is also not in G+. By a deductive system over a meta-signature Φ we mean a basis (G′′, β) over GΦ where G′′ = (V ′′, E′′, src′′, trg′′) is such that • V ′′ is the class of morphisms of G+> whose target is in V ; • E′′(ŵ1 : s→ v1 . . . ŵn : s→ vn, ŵ : s→ v), for ŵ in G+, contains, among others, the m-edges e : v1 . . . vn → v of E such that ŵ = e ◦ 〈ŵ1, . . . , ŵn〉 in G+; • E′′(ŵ1 : s1 → v1 . . . ŵn : sn → vn, ŵ : s→ v) = ∅ whenever ŵ is not in G+ or si 6= s for some i = 1, . . . , n, or ŵi is not in G+ and n 6= 1; and β is such that • βv(ŵ : s→ v) = v; • βe(e : (ŵ1 : s → v1 . . . ŵn : s → vn) → (ŵ : s → v)) = e if e is in E and ŵ = e ◦ 〈ŵ1, . . . , ŵn〉; • βe(f ′) ∈ R otherwise. The first condition on E′′ imposes that E′′ contains the language constructors, as it is usually considered in categorical logic. As imposed in the last condition for βe the other m-edges correspond to inference rules. All the medges corresponding to inference rules must have as premises and conclusion, expressions with the same source, and with target π. The same source condition is imposed by the second condition on E′′ and is crucial for defining instantiation as we will see below. The target is π by definition of β and of R. The m-edges in (βe)−1(Rn) are called n-ary inference rules or simply n-ary rules. By a deductive system D we mean a triple (Φ, G′′, β) such that Φ is a meta-signature and (G′′, β) is a deductive system over Φ. We now illustrate our notion of deductive system by presenting deductive systems for a variety of logics. Example 5.1 Deductive system for classical propositional logic. Consider the well known Hilbert axiomatization of classical propositional logic with three axiom schemas and Modus Ponens. This axiomatization can be represented as the deductive system (ΦΠ, G′′, β), denoted by DPLΠ , such that: • ΦΠ is the meta-signature (ΣΠ,>,R) where ΣΠ is the propositional signature (G, π, ♦) introduced in Example 2.1; 26 β KS π  ⊃,R2 . . . ¬,R1 cc♦ p // ππ π >ππ ππ π A1 ax1 // πππ π >πππ πππ π A2 ax2 // ππ π >ππ ππ π A3 ax3 // ππ π pππ1  ππ π ⊃  ππ π pππ2  MP // s π s π φ  ¬ ◦ φ  ¬ // . . . Figure 15: Part of the deductive system of Example 5.1. • G′′ has, besides the mandatory m-edges for connectives, the following ones for rules: – m-edge ax1 : >ππ → (ξ ⊃ (ξ′ ⊃ ξ)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax2 : >πππ → ((ξ ⊃ (ξ′ ⊃ ξ′′))⊃ ((ξ ⊃ ξ′)⊃ (ξ ⊃ ξ′′))) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; – m-edge ax3 : >ππ → (((¬ ξ) ⊃ (¬ ξ′)) ⊃ (ξ′ ⊃ ξ)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge MP : pππ1 ⊃ → pππ2 ; • β : G′′ → GΦΠ is such that: – βe(axi) = R1 for i = 1, 2, 3; – βe(MP) = R2. In the sequel, we can abbreviate the target of the m-edges corresponding to axioms as A. This deductive systems contains the three axiom schemes, represented as unary rules with a verum schema formula as antecedent, and the 2-ary inference rule of MP. Part of the deductive system is depicted in Figure 15. ∇ Example 5.2 Deductive system for classical propositional modal logic T. Consider the Hilbert axiomatization of the global consequence relation for the classical propositional modal logic T with three axiom schemas for the propositional part, Modus Ponens, a rule stating that (φ) holds for each theorem φ, the normality axiom K and the reflexivity axiom T. This axiomatization can be represented as the deductive system (ΦΠ, G′′, β) such that: 27 • ΦΠ is the meta-signature (ΣΠ,>,R) where ΣΠ is the propositional modal signature (G, π, ♦) introduced in Example 2.2; • G′′ has, besides the mandatory m-edges for connectives, the following ones: – m-edge ax1 : >ππ → (ξ ⊃ (ξ′ ⊃ ξ)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax2 : >πππ → ((ξ ⊃ (ξ′ ⊃ ξ′′))⊃ ((ξ ⊃ ξ′)⊃ (ξ ⊃ ξ′′))) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; – m-edge ax3 : >ππ → (((¬ ξ) ⊃ (¬ ξ′)) ⊃ (ξ′ ⊃ ξ)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge axK : >ππ → (((ξ ⊃ ξ′)) ⊃ ((ξ) ⊃ (ξ′))) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge axT : >ππ → ((ξ)⊃ ξ) where ξ is idπ; – m-edge MP : pππ1 ⊃ → pππ2 ; – m-edge  : idπ → ; • β : G′′ → GΦΠ is such that: – βe(axi) = R1 for i = 1, 2, 3,K, T ; – βe(MP) = R2; – βe() = R1. ∇ Example 5.3 Deductive system for intuitionistic propositional logic. Consider the well known Hilbert axiomatization of intuitionistic propositional logic with axiom schemas and Modus Ponens. This axiomatization can be represented as the deductive system (ΦΠ, G′′, β) such that: • ΦΠ is the meta-signature (Σ∧,∨Π ,>,R) where Σ ∧,∨ Π is the intuitionistic propositional signature (G, π, ♦) introduced in Example 2.3; • G′′ has, besides the mandatory m-edges for connectives, the following ones: – m-edge ax1 : >ππ → (ξ ⊃ (ξ′ ⊃ ξ)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax2 : >πππ → ((ξ ⊃ (ξ′ ⊃ ξ′′))⊃ ((ξ ⊃ ξ′)⊃ (ξ ⊃ ξ′′))) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; – m-edge ax3 : >ππ → (ξ ⊃ (ξ′ ⊃ (ξ ∧ ξ′)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax4 : >ππ → ((ξ ∧ ξ′)⊃ ξ) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax5 : >ππ → ((ξ ∧ ξ′)⊃ ξ′) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax6 : >ππ → (ξ ⊃ (ξ ∨ ξ′)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax7 : >ππ → (ξ′ ⊃ (ξ ∨ ξ′)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax8 : >πππ → ((ξ ⊃ ξ′′)⊃ ((ξ′ ⊃ ξ′′)⊃ ((ξ ∨ ξ′)⊃ ξ′′))) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; 28 – m-edge ax9 : >ππ → ((ξ ⊃ ξ′)⊃ ((ξ ⊃ (¬ ξ′))⊃ (¬ ξ))) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax10 : >ππ → (ξ ⊃ ((¬ ξ)⊃ ξ′)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge MP : pππ1 ⊃ → pππ2 ; • β : G′′ → GΦΠ is such that: – βe(axi) = R1 for i = 1, . . . , 10; – βe(MP) = R2. ∇ Example 5.4 Deductive system for propositional relevance logic R. Consider the Hilbert axiomatization of relevance logic R with axiom schemas, MP and AR. This axiomatization can be represented as the deductive system (ΦΠ, G′′, β) such that: • ΦΠ is the meta-signature (Σ∧,∨Π ,>,R) where Σ ∧,∨ Π is the intuitionistic propositional signature (G, π, ♦) introduced in Example 2.3; • G′′ has, besides the mandatory m-edges for connectives, the following ones: – m-edge ax1 : >ππ → (ξ ⊃ ξ) where ξ is idπ; – m-edge ax2 : >πππ → ((ξ ⊃ ξ′) ⊃ ((ξ′′ ⊃ ξ) ⊃ (ξ′′ ⊃ ξ′))) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; – m-edge ax3 : >ππ → ((ξ ⊃ (ξ ⊃ ξ′))⊃ (ξ ⊃ ξ′)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax4 : >πππ → ((ξ ⊃ (ξ′ ⊃ ξ′′)) ⊃ (ξ′ ⊃ (ξ ⊃ ξ′′))) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; – m-edge ax5 : >ππ → ((ξ ∧ ξ′)⊃ ξ) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax6 : >ππ → ((ξ ∧ ξ′)⊃ ξ′) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax7 : >πππ → (((ξ ⊃ ξ′) ∧ (ξ ⊃ ξ′′))⊃ (ξ ⊃ (ξ′ ∧ ξ′′))) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; – m-edge ax8 : >ππ → (ξ ⊃ (ξ ∨ ξ′)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax9 : >ππ → (ξ′ ⊃ (ξ ∨ ξ′)) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax10 : >πππ → (((ξ ⊃ ξ′′) ∧ (ξ′ ⊃ ξ′′))⊃ ((ξ ∨ ξ′)⊃ ξ′′)) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; – m-edge ax11 : >πππ → ((ξ ∧ (ξ′ ∨ ξ′′)) ⊃ ((ξ ∧ ξ′) ∨ ξ′′)) where ξ is pπππ1 , ξ ′ is pπππ2 and ξ ′′ is pπππ3 ; – m-edge ax12 : >π → ((ξ ⊃ (¬ ξ))⊃ (¬ ξ)) where ξ is idπ; – m-edge ax13 : >ππ → ((ξ ⊃ (¬ ξ′))⊃ (ξ′ ⊃ (¬ ξ))) where ξ is pππ1 and ξ′ is pππ2 ; – m-edge ax14 : >π → ((¬(¬ ξ))⊃ ξ) where ξ is idπ; – m-edge MP : pππ1 ⊃ → pππ2 ; – m-edge AR : pππ1 p ππ 2 → (∧ ◦ 〈pππ1 , pππ2 〉); 29 • β : G′′ → GΦΠ is such that: – βe(axi) = R1 for i = 1, . . . , 14; – βe(MP) = R2; – βe(AR) = R2. ∇ Example 5.5 Deductive system for (one-sorted) equational logic. Consider the Hilbert axiomatization of equational logic with one axiom schema and four inference rules. This axiomatization can be represented as the deductive system (ΦΠ, G′′, β) such that: • ΦΠ is the meta-signature (ΣEQF ,>,R) where Σ EQ F is the equational signature (G, π, ♦) introduced in Example 2.5; • G′′ has, besides the mandatory m-edges for connectives, the following ones: – ax : >θ →≈ ◦〈idθ, idθ〉; – SYM :≈→≈ ◦〈pθθ2 , pθθ1 〉; – TRANS : (≈ ◦〈pθθθ1 , pθθθ2 〉)(≈ ◦〈pθθθ2 , pθθθ3 〉)→ (≈ ◦〈pθθθ1 , pθθθ3 〉); – CONGf : (≈ ◦〈pθ...θ1 , pθ...θn+1〉) . . . (≈ ◦〈pθ...θn , pθ...θ2n 〉)→ (≈ ◦〈f ◦ 〈pθ...θ1 , . . . , pθ...θn 〉, f ◦ 〈pθ...θn+1, . . . , pθ...θ2n 〉〉); – SUBt′,t′′,t :≈ ◦〈t′, t′′〉 →≈ ◦〈t′, t′′〉 ◦ t for each t′, t′′ : s → θ and t : s1 → s morphisms of G+; • β : G′′ → GΦΠ is such that: – βe(ax) = R1; – βe(SYM) = R1; – βe(TRANS) = R2; – βe(CONGf ) = Rn whenever f is in Fn; – βe(SUBt′,t′′,t) = R1. ∇ 6 Derivation as a path The next step is to define derivation in the context of a deductive system. The basic ingredient is instantiation of rules. The instantiation of a rule r is accomplished by enriching G′′+ with new morphisms r û, denoting the result of the instantiation of r by û (see Figure 16). We will also denote by the simultaneous instantiation of several rules. Example 6.1 In order to understand better instantiation of rules in our setting, we make the parallel with the traditional view. Assume that MP is a schema rule of the form ξ1 (ξ1 ⊃ ξ2) ξ2 . 30 ππ π pππ1  ππ π ⊃  ππ π pππ2  MP // s ππ û  s π pππ1 ◦ û  s π ⊃ ◦ û  s π pππ1 ◦ û  MP û +3 Figure 16: Instantiation of MP by û. By instantiating ξ1 7→ q1 and ξ2 7→ (q3 ⊃ q2) we get the following inference: q1 (q1 ⊃ (q3 ⊃ q2)) q3 ⊃ q2 . This can be shortly written as MP[ξ1/q1, ξ2/(q3 ⊃ q2)] corresponding to the morphism MP 〈q1, q3 ⊃ q2〉. This example is illustrated in Figure 17. ∇ ππ π pππ1  ππ π ⊃  ππ π pππ2  MP //  ππ 〈q1, q3 ⊃ q2〉   π q1   π q1 ⊃ (q3 ⊃ q2)   π q3 ⊃ q2  MP 〈q1, q3 ⊃ q2〉 +3 Figure 17: Instantiation of MP as described in Example 6.1. Intuitively, derivations are seen as a sequence of derivation steps, also called derivation levels, see Figure 18 and Figure 22, where in each level one or several rules may be applied to different schema formulas coming from the preceding level. The morphism ididπ is applied in a level to a schema formula when no rule is applied to it in that level. Note that axioms are seen as unary rules whose antecedent is a verum schema formula. So, in order to define derivations, besides the operation , which denotes the instantiation of a derivation level by a substitution, we need to consider a new operation ⊗ for defining a derivation level. That operation interacts appropriately with . Before defining those operations we introduce some convenient notation. Given i = 1, . . . , n, si = vi1 . . . vimi in V + where vi1, . . . , vimi are in V , we 31 denote by ps1...snsi the tuple 〈p s1...sn m1+...+mi−1+1 , . . . , ps1...snm1+...+mi〉. Moreover, given âi : s → vi in G+ for i = 1, . . . , n we denote by (â1 . . . ân) ◦ û the sequence â1 ◦ û . . . ân ◦ û. So, in order to define derivations we consider a new category, G′′?, which is a smallest category with non empty finite products obtained from G′′+ by adding the morphisms • f1 ⊗ * * * ⊗ fn : (â11. . . â1m1)◦ ps1...sns1 . . . (ân1. . . ânmn)◦ p s1...sn sn → (ĉ1 ◦ p s1...sn s1 . . . ĉn ◦ p s1...sn sn ) where fi : âi1 . . . âimi → ĉi is ididπ or is in (βe)−1(R) and src(ci) = si; • ` û : (â1 . . . âm) ◦ û → (ĉ1 . . . ĉn) ◦ û whenever û in G+ is composable with ĉ1 and ` : â1 . . . âm → ĉ1 . . . ĉn is of the form f1 ⊗ * * * ⊗ fn; while imposing: • ididπ û = idbu; • ` ids = `; • (` û2) û1 = ` (û2 ◦ û1); • (f1 ⊗ * * * ⊗ fn) û = (f1 (ps1...sns1 ◦ û))⊗ * * * ⊗ (fn (p s1...sn sn ◦ û)). Given a morphism f1 ⊗ * * * ⊗ fn named ` in G′′?, denoting a derivation step, we denote by CONC(`) the target of ` and by ANT(`) the source of `. When presenting derivations it is more convenient not indicate explicitly the substitutions used, but instead the rule or axiom resulting from the instantiation by that substitution. For this purpose we write ` ? ~φ whenever there is a substitution û (a morphism in G+) with ~φ = ANT(`) ◦ û and such that ` ? ~φ = ` û. For instance, in Example 6.1, ~φ is q1, q1⊃ (q3⊃ q2) and û is 〈q1, q3⊃ q2〉. Note that, by definition, a substitution û never involves verum schema formulas since û is a morphism in G+. In the sequel we may use commas to separate elements in a sequence of formulas. We are now ready to define derivations. But first we give a bit of motivation. Example 6.2 Consider the following derivation in the Hilbert calculus for classical logic stating that p⊃ q follows from q: 1. q Hyp 2. q ⊃ (p⊃ q) A1 3. p⊃ q MP 1, 2 which is represented graphically in Figure 18. So p ⊃ q is obtained by an application of MP: q q ⊃ (p⊃ q) p⊃ q where only q is an hypothesis since the other premise q ⊃ (p ⊃ q) is an axiom. In more detail, the derivation can be seen as consisting of two steps, the first 32 q >ππ ◦ 〈q, p〉 ~φ1 q q ⊃ (p⊃ q) ~φ2 p⊃ q ~φ3 ididπ  ax1  XXXXXX XXX eeeeeee eee MP  l1 l2 Figure 18: Graphical representation of the derivation in Example 6.2 and in Example 6.3. one for concluding the axiom q ⊃ (p⊃ q), and the second step consisting of an application of MP with substitution ξ1 7→ q and ξ2 7→ p⊃ q. This second step, is represented, in our setting, by the morphism MP 〈q, p⊃ q〉 denoted, more conveniently, by MP ? q, q ⊃ (p⊃ q). The first step of the derivation is represented, in our setting, by the morphism (ididπ ⊗ ax1) 〈q, q, p〉 which can be denoted also by (ididπ ⊗ ax1) ? q,>ππ ◦ 〈q, p〉 (see Figure 18). ∇ Let D be a deductive system. A derivation step in D is a morphism of the form f1 ⊗ . . . ⊗ fm where fi is either ididπ or is an element of (βe)−1(R), for i = 1, . . . ,m and m > 0. An illustration of a derivation step is presented in Figure 20. By a derivation in D we mean a pair d = `1, . . . , `n; ~φ1 where each `i is a derivation step and ~φ1 is a sequence of morphisms in V ′′ such that the sequence given by ~φi+1 = CONC(`i ? ~φi), for i = 1, . . . , n, is well defined, and so there exists the composite morphism (`n ? ~φn) ◦ . . . ◦ (`1 ? ~φ1) 33 sπ sπ sπ sπ sπ sπ sπ sπ sπ sπ oo_ _ _ _ _ _ _ _ _ _ _ _ _ _...oo_ _ _ _ _ _ _ _ _ _ _ _ _ _ ~φ1 oo_ _ _ _ _ _ _ _ _ _ _ _ _ _...oo_ _ _ _ _ _ _ _ _ _ _ _ _ _ ~φ2 oo_ _ _ _ _ _ _ _ _ _ _ _ _ _...oo_ _ _ _ _ _ _ _ _ _ _ _ _ _ ~φ3 oo_ _ _ _ _ _ _ _ _ _ _ _ _ _...oo_ _ _ _ _ _ _ _ _ _ _ _ _ _ ~φn oo_ _ _ _ _ _ _ _ _ _ _ _ _ _...oo_ _ _ _ _ _ _ _ _ _ _ _ _ _  ~φ l1 ? ~φ1  l2 ? ~φ2  ... ... ln ? ~φn  ln ? ~φn ◦ . . . ◦ l1 ? ~φ1  Figure 19: (Effective) derivation as a composite morphism in G′′?. in G′′? (see Figure 19). The morphism above is called the effective derivation associated with the derivation `1, . . . , `n; ~φ1. When there is no ambiguity we may use the term derivation to refer also to the effective derivation. In the sequel we will denote by di the morphism (`i ? ~φi) ◦ . . . ◦ (`1 ? ~φ1). The set of hypothesis HYP(d) of the derivation d = `1, . . . , `n; ~φ1, where ~φ1 is of the form φ11 . . . φ1m1 for m1 > 0, is the set of the φ1i's that are in G +. As usual we write Γ `D ~φ if there is a derivation d in D such that CONC(dn) = ~φ and HYP(d) ⊆ Γ, where ~φ is a sequence and Γ a set of schema formulas of G+. The definition of consequence deserves some comments. Firstly, observe that ~φ is a sequence of formulas possibly containing more than one formula. So multi-conclusion derivations can be naturally defined. Secondly, a set of hypothesis was considered instead of a sequence. This classical perspective intends to reflect derivations in standard Hilbert systems, as it is treated in this work. However, instead of Γ itself, we could pick the subsequence of ~φ1 of hypothesis. This would provide us with more information about the effective number and even about the order of the premises used in the derivation, in line with some substructural logics of resources. Thirdly, note that it is possible to use several rules in parallel by means of the ⊗ operator in each step of the derivation. This could open the possibility of considering parallel reasoning. 34 πππ bpππ1oo_ _ _ _ _ πππ ⊃oo_ _ _ _ _ πππ bpππ2oo_ _ _ _ _ MP  ππ idπoo_ _ _ _ _ ππ idπoo_ _ _ _ _ ididπ ππππ bpππ1 ◦bpπππ1,2oo ______ ππππ ⊃◦bpπππ1,2oo ______ ππππ idπ◦bpπππ3oo ______ ππππ bpππ2 ◦bpπππ1,2oo ______ ππππ idπ◦bpπππ3oo ______ MP⊗ ididπ Figure 20: Graphical representation of the first derivation step in Example 6.4. Finally, observe that schema formulas not in G+, that is, morphisms involving verum schema formulas, can only appear as antecedents of the first step of a derivation, since: 1. the conclusion of a deductive rule, by definition, is in G+, 2. substitutions are morphisms in G+. So, axiom rules can only be used in the first step of a derivation. Example 6.3 The derivation in Example 6.2 depicted in Figure 18 can be expressed in our setting as the derivation d in DPL{p,q} given by MP, (ididπ ⊗ ax1); ~φ1 stating that q `DPL{p,q} p⊃ q where ~φ1 is the sequence q,>ππ ◦ 〈q, p〉. In fact, ~φ1 is ANT(ididπ ⊗ ax1) ◦ û1 for û1 = 〈q, q, p〉. So, ~φ2 = q, q⊃ (p⊃q) and ~φ2 = ANT(MP)◦ û2 for û2 = 〈q, p⊃q〉. Hence ~φ3 = p ⊃ q since ~φ3 = CONC(MP) ◦ û2. The set HYP(d) is {q} since >ππ ◦ 〈q, p〉, an instance of the ππ-verum, is a schema formula not in G+. ∇ Example 6.4 The derivation d given by MP, (MP⊗ ididπ); ξ1, ξ1 ⊃ ξ2, ξ2 ⊃ ξ3 where ξ1, ξ2 and ξ3 are the projections pπππ1 , p πππ 2 and p πππ 3 respectively, states that ξ1, (ξ1 ⊃ ξ2), (ξ2 ⊃ ξ3) `DPLΠ ξ3. In fact, the morphism û1 = 〈ξ1, ξ2, ξ2 ⊃ ξ3〉 is such that ~φ1 = ANT(MP⊗ ididπ) ◦ û1 since ANT(MP ⊗ ididπ) is the sequence pππ1 ◦ pπππ1,2 ,⊃ ◦ pπππ1,2 , idπ ◦ pπππ3 . Thus (MP⊗ ididπ) ? ~φ1 : ~φ1 → ~φ2 is a morphism in G′′? where ~φ2 = (pππ2 ◦ pπππ1,2 , idπ ◦ pπππ3 ) ◦ û1 = ξ2, ξ2 ⊃ ξ3. 35 πππ πππ bu1=〈ξ1,ξ2,ξ2⊃ξ3〉  ππππ ξ1=bpππ1 ◦bpπππ1,2 ◦bu1oo ______________ ππππ ξ1⊃ξ2=⊃◦bpπππ1,2 ◦bu1oo ______________ ππππ ξ2⊃ξ3=idπ◦bpπππ3 ◦bu1oo ______________ ππππ ξ2=bpππ2 ◦bpπππ1,2 ◦bu1=bpππ1 ◦bu2oo ______________ ππππ ξ2⊃ξ3=idπ◦bpπππ3 ◦bu1=⊃◦bu2oo ______________ (MP⊗ididπ)?~φ1 =(MP⊗ididπ)û1  πππ πππ bu2=〈ξ2,ξ3〉  MP ? ~φ2 = MP û2 ππππ ξ3=bpππ2 ◦bu2oo ______________ Figure 21: Graphical representation of the derivation in Example 6.4. The second derivation step is as follows: the morphism û2 = 〈ξ2, ξ3〉 is taken such that ~φ2 = (pππ1 ,⊃) ◦ û2 where the sequence pππ1 ,⊃ is ANT(MP). Hence, MP ? ~φ2 : ~φ2 → ~φ3 in G′′?, where ~φ3 = pππ2 ◦ û2 = ξ3. This derivation is graphically represented in Figure 21. ∇ Example 6.5 In the Hilbert calculus for classical logic we can derive ξ1 from ξ2 and ¬ ξ2, as follows: 1. ξ2 Hyp 2. ¬ ξ2 Hyp 3. (¬ ξ2)⊃ ((¬ ξ1)⊃ (¬ ξ2)) A1 4. (¬ ξ1)⊃ (¬ ξ2) MP 2, 3 5. ((¬ ξ1)⊃ (¬ ξ2))⊃ (ξ2 ⊃ ξ1) A3 6. ξ2 ⊃ ξ1 MP 4, 5 7. ξ1 MP 1, 6 In order to understand how derivations are expressed in our setting we should distinguish between the assumed formulas (hypothesis or axioms) and the formulas derived during the process. In the above derivation the formulas in steps 1., 2., 3. and 5. are assumed and the others are derived. Intuitively speaking, in our setting the assumed formulas are putted altogether in the initial sequence ~φ1. The intuition behind the derivation is depicted in Figure 22. Formally we can consider the derivation d in DPLΠ given by MP, (ididπ ⊗MP), (ididπ ⊗MP⊗ ididπ), (ididπ ⊗ ididπ ⊗ ax1 ⊗ ax3); ~φ1 36 ξ2 ¬ ξ2 >ππ ◦ 〈¬ ξ2,¬ ξ1〉 >ππ ◦ 〈ξ1, ξ2〉 ξ2 ¬ ξ2 ¬ ξ2 ⊃ (¬ ξ1 ⊃ ¬ ξ2) (¬ ξ1 ⊃ ¬ ξ2)⊃ (ξ2 ⊃ ξ1) ξ2 ¬ ξ1 ⊃ ¬ ξ2 (¬ ξ1 ⊃ ¬ ξ2)⊃ (ξ2 ⊃ ξ1) ξ2 ξ2 ⊃ ξ1 ξ1 YYYYYY hhhhh MP  ZZZZZZZ ZZZZZZZ Z cccccccccc cccccccccc c MP  ZZZZZZZZ ZZZZZZZZ Z cccccccc cccccccc c MP  ididπ  ididπ  ax1  ax3  ididπ  ididπ  ididπ  Figure 22: Deduction steps of the derivation of Examples 6.5. where ~φ1 is the sequence ξ2,¬ ξ2,>ππ ◦ 〈¬ ξ2,¬ ξ1〉,>ππ ◦ 〈ξ1, ξ2〉, and ξ1 and ξ2 are pππ1 and p ππ 2 , respectively, stating that ξ2,¬ξ2 `DPLΠ ξ1. In fact, taking û1 = 〈ξ2,¬ ξ2,¬ ξ2,¬ ξ1, ξ1, ξ2〉 we get ~φ2 equal to the sequence ξ2,¬ξ2,¬ξ2 ⊃ (¬ξ1 ⊃ ¬ξ2), (¬ξ1 ⊃ ¬ξ2) ⊃ (ξ2 ⊃ ξ1). Moreover taking û2 = 〈ξ2,¬ ξ2,¬ ξ1⊃¬ ξ2, (¬ ξ1⊃¬ ξ2)⊃ (ξ2⊃ ξ1)〉 we get ~φ3 = ξ2,¬ ξ1⊃¬ ξ2, (¬ ξ1⊃ ¬ ξ2) ⊃ (ξ2 ⊃ ξ1) by applying the second derivation step. Now, by taking û3 = 〈ξ2,¬ ξ1⊃¬ ξ2, ξ2⊃ξ1〉 we get ~φ4 = ξ2, ξ2⊃ξ1 by the third derivation step. Finally, û4 = 〈ξ2, ξ1〉 allows to conclude ~φ5 = ξ1 by the last inference step. This derivation can be visualized in Figure 22. ∇ The notion of relevant deduction can be expressed in our setting with minor adjustments by defining ~γ `D ~φ whenever there is a derivation d = `1, . . . , `n; ~φ1 such that CONC(dn) = ~φ and ~γ is ~φ1 without the schema formulas not in G+. 7 Putting semantics and deduction together We start by defining logic system, obtained by putting together a signature, a interpretation system and a deduction system. As seen in previous sections all 37 of these components are defined in terms of m-graphs. More rigorously, a logic system is a triple L = (Σ, I,D) such that: • I = (Σ, I) is an interpretation system; • D = (Φ, G′′, β) is a deductive system where Φ is a meta-signature over Σ. The logic system L is said to be sound if Γ I φ whenever Γ `D φ, where φ is a formula and Γ is a set of formulas of G+, and is said to be complete if the converse holds. A logic system is said to be weakly complete if `D φ whenever I φ, for each formula φ of G+. 7.1 Soundness Given a logic system L, I in I is said to be sound for a deductive rule r in D, if I, ρ CONC(r) whenever I, ρ proper(ANT(r)) for every assignment ρ over I, where the map proper(*) when applied to a sequence ~φ of schema formulas in G+> returns the subsequence of schema formulas that are in G +. These schema formulas are called proper. The logic system L is said to be sound for a deductive rule r in D, if all its interpretation structures over its signature are sound for r. We now prove two propositions useful to establish the soundness theorem. Proposition 7.1 A logic system L sound for a deductive rule r is such that I, ρ CONC(r) ◦ û whenever I, ρ proper(ANT(r)) ◦ û for I in I, assignment ρ over I and morphism û in G+ composable with the schema formulas in r. Proof: Let r : (ψ1 : s → π . . . ψm : s → π) → (φ : s → π) and denote by φ1, . . . , φn the proper antecedents of r. Assume that I, ρ proper(ANT(r)) ◦ û, that is, I, ρ φi ◦ û for i = 1, . . . , n. Hence, [[φi ◦ û]]Iρ ⊆ D, and so, using Proposition 4.6, [[φi]] Iρ s/[u]Iρ ⊆ D, for i = 1, . . . , n. Since L is sound for r, then [[φ]]Iρs/[u]Iρ ⊆ D, and by Proposition 4.6 and definition of denotation, [[φ ◦ û]]Iρ ⊆ D. So I, ρ CONC(r) ◦ û. QED Proposition 7.2 Given a logic system L sound for its rules, a derivation step `, and a morphism û in G+ such that ` û is definable, then I, ρ CONC(` û) whenever I, ρ proper(ANT(` û), for every I in I and assignment ρ over I. Proof: Assume I, ρ proper(ANT(` û) and let ` be f1 ⊗ . . . ⊗ fn where fi : â′i1 . . . â ′ im′i → ĉi is ididπ or is in (βe)−1(R), and i = 1, . . . , n. Denote by âi1 . . . âimi the subsequence of proper antecedents of fi. Then proper(ANT(` û) = ((â11 . . . â1m1)◦ps1...sns1 . . . (ân1 . . . ânmn)◦p s1...sn sn )◦û and CONC(`û) = (ĉ1◦ ps1...sns1 . . . ĉn◦ p s1...sn sn )◦ û. So I, ρ proper(ANT(fi)◦(p s1...sn si ◦ û) for i = 1, . . . , n. We now show that I, ρ CONC(` û) that is I, ρ CONC(fi) ◦ (ps1...snsi ◦ û) for i = 1, . . . , n. Let i ∈ {1, . . . , n}. There are two cases to consider: (i) fi is ididπ . Then CONC(fi) = proper(ANT(fi)) and so I, ρ CONC(fi) ◦ (ps1...snsi ◦ û) using the hypothesis. (ii) f1 is in (βe)−1(R), and so f1 is a deductive rule. Then the result follows by Proposition 7.1. QED 38 The soundness theorem establishes soundness for rules as a sufficient condition for a logic system to be sound. Theorem 7.3 A logic system is sound if it is sound for its deductive rules. Proof: Let L = (Σ, I,D) be a logic system sound for all its deductive rules, and assume that Γ `D ~φ for a sequence ~φ and a set Γ of formulas of G+. Let `1, . . . , `n; ~φ1 be a derivation for Γ `D ~φ, and I in I such that I Γ. Denote by ~φ1p the sequence with the proper formulas of ~φ1. Since the schema formulas in ~φ1p are in Γ, by definition of derivation, we can conclude that they are concrete formulas and that I ~φ1p using the hypothesis. We prove that I ~φ by induction on n. Let ρ be an assignment over I. Base (n = 1) Note that proper(ANT(`1 ? ~φ1)) = ~φ1p , and that there is a morphism û1 inG+ such that ~φ1p = proper(ANT(`1))◦û1 and `1?~φ1 = `1û1. Hence I proper(ANT(`1 û1)) and so, by Proposition 7.2, I, ρ CONC(`1 û1), that is, I, ρ CONC(`1 ? ~φ1). The thesis follows since CONC(`1 ? ~φ1) = ~φ. Step: Let ~φn = CONC(`n−1 ? ~φn−1 ◦ . . .◦`1 ? ~φ1). Note that the schema formulas in ~φn are in G+, that is, they do not involve verum schema formulas. On the other hand, `1, . . . , `n−1; ~φ1 is a derivation for Γ `D ~φn. Hence, by the induction hypothesis, Γ I ~φn. So I ~φn since I Γ. Therefore I ANT(`n ? ~φn), and there is a morphism ûn in G+ such that ~φn = ANT(`n)◦ûn and `n?~φn = `nûn. Hence I ANT(`n ûn) and so, by Proposition 7.2, I, ρ CONC(`n ûn), that is, I, ρ CONC(`n ? ~φn). The thesis follows since CONC(`n ? ~φn) = ~φ. QED 7.2 Completeness Our completeness result relies on the notion of a canonical interpretation structure generated by a deductive system and a set of formulas. More rigorously, let D be a deductive system and Γ a set of formulas in G+. The canonical interpretation structure SΓ(D) = (Σ, (G′, α,D, )) generated by D and Γ, is such that: • G′ = (V ′, E′, src′, trg′) where – V ′ are the morphisms of G+ whose target is an element of V ; – E′(ŵ1 . . . ŵn, ŵ) is composed by all the m-edges e of E such that ŵ = ê ◦ 〈ŵ1, . . . , ŵn〉 in G+; – the definition of src′ and trg′ is straightforward from the definition of m-edges; • αv(ŵ : s→ v) = v and αe(e) = e; • D = {ŵ ∈ V ′ : Γ `D ŵ}; •  is the morphism id♦ in G+. We may write S(D) for S∅(D). Denotation in the canonical structure has a very simple form as we show in the next lemma. 39 Lemma 7.4 Given a deductive system D, a set Γ of formulas in G+, a path w : s→ t over G†, and an assignment ρ over SΓ(D), then [[w]]S Γ(D),ρ = ŵ ◦ ρs. Proof: The proof follows by induction on the complexity of w: w is εs. Then [[w]] SΓ(D),ρ = ρs = ids ◦ ρs = εs ◦ ρs = ŵ ◦ ρs; w is ps1i w1. Then [[w]] SΓ(D),ρ = [[ps1i w1]] SΓ(D),ρ = ([[w1]] SΓ(D),ρ)i = (ŵ1 ◦ ρs)i = ps1i ◦ ŵ1 ◦ ρs = ŵ ◦ ρs; w is 〈w1, . . . , wn〉w0. Hence [[w]]S Γ(D),ρ = [[w1w0]] SΓ(D),ρ . . . [[wnw0]] SΓ(D),ρ = (ŵ1 ◦ ŵ0 ◦ ρs) . . . (ŵn ◦ ŵ0 ◦ ρs) = 〈w1, . . . , wn〉 ◦ ŵ0 ◦ ρs as we wanted to show; w is ew1. Therefore [[w]] SΓ(D),ρ = trg′(E′e([[w1]] SΓ(D),ρ,−)) = trg′(E′e(ŵ1 ◦ ρs,−)) = ê ◦ ŵ1 ◦ ρs = ŵ ◦ ρs. QED Capitalizing on the result of denotation in the canonical structure, it is possible to establish an important lemma relating satisfaction in the canonical structure with derivation. Lemma 7.5 Given a deductive system D, a set Γ of formulas and a schema formula φ : s→ π over the signature of D, Γ `D φ◦ρs if and only if SΓ(D), ρ φ, for every assignment ρ over SΓ(D). Proof: Let ρ be an assignment over SΓ(D). Then Γ `D φ ◦ ρs if and only if, by Lemma 7.4, Γ `D [[φ]]S Γ(D),ρ iff [[φ]]S Γ(D),ρ ⊆ D iff SΓ(D), ρ φ. QED In a subsequent proposition we show that SΓ(D) is sound for the rules in D, but first we show a useful lemma. Lemma 7.6 For every deductive rule r in D, set of formulas Γ, and expression û in G+, then Γ `D CONC(r) ◦ û whenever Γ `D proper(ANT(r)) ◦ û. Proof: Let ANT(r) be the sequence φ1 . . . φn. We start by considering the case that all the antecedents of r are in G+, that is, proper(ANT(r)) is equal to ANT(r). Assume that Γ `D φi ◦ û for i = 1, . . . , n. Let `i1, . . . , `imi ; ~φi1 be a derivation for Γ `D φi ◦ û for i = 1, . . . , n. Let m be the maximum of the mi, and let `imi+1, . . . , `im denote the morphism ididπ , for i = 1, . . . , n. Moreover, assume that `ij is fij1⊗. . .⊗fijmij for i = 1, . . . , n and j = 1, . . . ,m, and denote by `k the morphism f1k1 ⊗ . . .⊗ f1km1k ⊗ fnk1 ⊗ . . .⊗ fnkmnk for k = 1, . . . ,m. Note that `1, . . . , `m; ~φ11 . . . ~φn1 is a derivation for Γ `D φ1 ◦ û . . . φn ◦ û. So `1, . . . , `m, r; ~φ11 . . . ~φn1 is a derivation for Γ `D CONC(r) ◦ û as we wanted to show. Assume now that r has an antecedent a1 not in G+, that is, involving a verum schema formula. Then r has no other antecedent. So r; (a1 ◦ û) is a derivation for `D CONC(r) ◦ û and so for Γ `D CONC(r) ◦ û. QED Proposition 7.7 For every deductive rule r in D, set of formulas Γ, and assignment ρ over SΓ(D), SΓ(D), ρ CONC(r) if SΓ(D), ρ proper(ANT(r)). 40 Proof: Assume that SΓ(D), ρ proper(ANT(r)) and denote by φ1 . . . φn the sequence proper(ANT(r)). Then Γ `D φi ◦ ρs, by Lemma 7.5, for i = 1, . . . , n. Hence Γ `D CONC(r) ◦ ρs, by Lemma 7.6, and so, SΓ(D), ρ CONC(r), by Lemma 7.5. QED In order for completeness to hold in a logic system it is not necessary to impose as sufficient condition that its interpretation system contains canonical structures, as we show below. It is enough to guarantee that its interpretation system contains structures that share with canonical structures some characteristics. We call these structures, representatives of a canonical structure. A logic system contains a representative of the canonical structure over a set Γ when it contains an interpretation structure IΓ such that • IΓ φ implies SΓ(D) φ; • IΓ Γ; for every formula φ and set of formulas Γ in G+. Theorem 7.8 A logic system with representatives of the canonical structures over all sets of formulas is complete. Proof: Let Γ be a set of formulas and φ a formula. Assume that Γ 6`D φ. Let IΓ ∈ I be the representative of SΓ(D). Then SΓ(D) Γ and SΓ(D) 6 φ by Lemma 7.5. Then IΓ Γ and IΓ 6 φ. So Γ 6I φ since IΓ ∈ I. QED A similar theorem can be established for weak completeness. The proof of the theorem is omitted since it very similar to the proof of Theorem 7.8. Theorem 7.9 A logic system is weakly complete if it contains a representative of the canonical structure over the empty set. Corollary 7.10 A logic system is (weakly) complete whenever it contains all the interpretation structures that are sound with respect to the rules. Proof: Assume that L contains all the interpretation structures that are sound with respect to the rules. Then SΓ(D) ∈ I, for any set Γ, using Proposition 7.7 and so, by Theorem 7.8, we conclude that L is complete. QED We now present several cases of logic systems enjoying sufficient conditions for completeness. Example 7.11 Some logic systems to which Corollary 7.10 apply: • the logic system for classical propositional logic with the deductive system presented in Example 5.1 and all the interpretation structures sound for MP and the axioms; • the logic system for classical propositional modal logic T with the deductive system presented in Example 5.2 and all the interpretation structures sound for MP, K, T and the axioms; 41 • the logic system for intuitionistic propositional logic with the deductive system presented in Example 5.3 and all the interpretation structures sound for MP and the axioms; • the logic system for relevance logic R with the deductive system presented in Example 5.4 and all the interpretation structures sound for MP, AR and the axioms, provided some minor adjustments are made in the definition of consequence in order to accommodate the notion of relevant deduction. In this case we only apply Corollary 7.10 in order to establish weak completeness. • the logic system for one-sorted equational logic with the deductive system presented in Example 5.5 and all the interpretation structures sound for SYM, TRANS, CONGf , SUBt′,t′′,t and the axiom A. ∇ 8 Towards provisos and quantification The next step extending this work is to investigate how to accommodate quantification and provisos in deduction rules. We now give some preliminary ideas on how to proceed in this direction, using as example the logic in [13] including classical and intuitionistic connectives. More specifically we are interested in its axiom (φ⊃c (ψ ⊃i φ)) which has the proviso that φ is a persistent formula. A persistent formula is one where every occurrence of classical implication ⊃c and classical negation ¬c is in the scope of the intuitionistic implication ⊃i or in the scope of the intuitionistic negation ¬i. In our setting this proviso should be accommodated at all levels: at the signature level, at the semantic level and at the deductive level. At the signature level, a new sort ν and a m-edge P : π → ν should be introduced. At the semantic level, ν should be interpreted as either true or false and the m-edges mapping to P relate a truth value with true if the proviso is satisfied by all the (schema) formulas that may have as denotation that truth value, and to false otherwise. At the deductive level we should consider (φ⊃c (ψ⊃i φ)) as a unary rule having as antecedent P (φ) (stating that φ is persistent) and as consequent the axiom. Moreover, we should add specific rules for dealing with persistency. For instance, we should add a rule stating that for every formula φ, we have P ◦ ¬i ◦φ. Dealing with quantification is also a challenge. Besides accommodating the first-order provisos we have to deal with the definition in our setting of the substitution of variables and its relationship with quantification. In the presence of quantifiers, the interplay between the variables and term schema should also be clarified. 9 Concluding remarks We presented a uniform and diagrammatic way of describing logics systems using m-graphs. Signatures, interpretation structures and deductive systems are based on m-graphs. Under this perspective, formulas and derivations are 42 morphisms in the appropriate generated categories. The approach is general enough to represent logics in different guises, namely substructural logics and logics endowed with a nondeterministic semantics. Moreover, it subsumes all logics endowed with an algebraic semantics. It seems worthwhile to explore in our setting the notion of denotation of a formula as a single truth-value even in the presence of non-deterministic operations as in the case of some paraconsistent logics [2]. General soundness and completeness results were proved. One of the major challenges is to extend the graph-theoretic approach to logics that support provisos and quantification as we already anticipated in Section 8. Another topic of interest is to investigate how to adjust our approach for algebraizable and protoalgebraic logics. On the deductive side, herein we concentrated on Hilbert axiomatizations. We intend to extend it to other kinds of deductive systems, namely sequent calculi. Furthermore, deductive systems over higher-order languages are also worthwhile to explore. General results about cut elimination and interpolation are also envisaged in this extended framework. Acknowledgments This work was partially supported by FCT and EU FEDER, namely via QuantLog PPCDT/MAT/55796/2004 Project, KLog PTDC/MAT/68723/2006 Project, QSec PTDC/EIA/67661/2006 Project and under the GTF (Graph Theoretic Fibring) initiative of IT. Marcelo Coniglio acknowledges support from FAPESP, Brazil, namely via Thematic Project 2004/14107-2 ("ConsRel"), and by an individual research grant from CNPq, Brazil. The authors are grateful to the anonymous referee for the comments and suggestions. References [1] G. Allwein and J. Barwise, editors. Logical Reasoning with Diagrams, volume 6 of Studies in Logic and Computation. The Oxford University Press, 1996. [2] A. Avron. Non-deterministic semantics for logics with a consistency operator. International Journal of Approximate Reasoning, 45(2):271–287, 2007. [3] J. Barwise. Axioms for abstract model theory. Annals of Mathematical Logic, 7:221–265, 1974. [4] J. Barwise and J. Etchemendy. The language of first-order logic, volume 23 of CSLI Lecture Notes. Stanford University Center for the Study of Language and Information, second edition, 1991. [5] J. Barwise and J. Etchemendy. Hyperproof, volume 42 of CSLI Lecture Notes. CSLI Publications, 1994. 43 [6] J. Barwise and E. Hammer. Diagrams and the concept of logic system. In Allwein and Barwise [1], pages 49–78. [7] J.-Y. Beziau, editor. Logica Universalis. Birkhäuser Verlag, second edition, 2007. Towards a general theory of logic. [8] G. Birkhoff. On the structure of abstract algebras. Proceedings of the Cambridge Philosophical Society, 31:433–454, 1935. [9] P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic, volume 53 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2001. [10] W.A. Carnielli, M.E. Coniglio, and J. Marcos. Logics of formal inconsistency. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic (2nd. edition), volume 14, pages 15–107. Springer, 2007. [11] A. S. d'Avila Garcez, D. M. Gabbay, and L. C. Lamb. Value-based argumentation frameworks as neural-symbolic learning systems. Journal of Logic and Computation, 15(6):1041–1058, 2005. [12] J. Dunn. Relevance logic and entailment. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, Vol. 3, pages 117–224. Kluwer Academic Publishers, 1986. [13] L. Fariñas del Cerro and A. Herzig. Combining classical and intuitionistic logic. In Frontiers of Combining Systems, volume 3, pages 93–102. Kluwer Academic Publishers, 1996. [14] D. M. Gabbay, editor. What is a Logical System?, volume 4 of Studies in Logic and Computation. The Clarendon Press Oxford University Press, New York, 1994. [15] M. Gardner. Logic Machines and Diagrams. University of Chicago Press, second edition, 1982. [16] J. A. Goguen and J. Meseguer. Completeness of many-sorted equational logic. Houston Journal of Mathematics, 11(3):307–334, 1985. [17] E. Hammer and N. Danner. Towards a model theory of diagrams. Journal of Philosophical Logic, 25:463–482, 1996. [18] E. M. Hammer. Logic and Visual Information. Studies in Logic, Language and Information. CSLI Publications, 1995. [19] J. Lambek and P. J. Scott. Introduction to Higher Order Categorical Logic, volume 7 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1988. Reprint of the 1986 original. [20] S. Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1998. 44 [21] H. Ono. Substructural logics and residuated lattices-an introduction. In Trends in logic, volume 21 of Trends Logic Studies Log. Libr., pages 193– 228. Kluwer Acad. Publ., 2003. [22] F. Paoli. Substructural logics: A primer, volume 13 of Trends in Logic- Studia Logica Library. Kluwer Academic Publishers, 2002. [23] C. S. Peirce. Collected papers. Edited by Charles Hartshorne and Paul Weiss. The Belknap Press of Harvard University Press, 1960. [24] H. Rasiowa and R. Sikorski. The Mathematics of Metamathematics. PWN-Polish Scientific Publishers, third edition, 1970. [25] Stanford University Rehseis and the Suppes Foundation. The Role of Diagrams in Mathematics: History, Logic, Philosophy and Cognitive Sciences, 2008. [26] G. Restall and F. Paoli. The geometry of non-distributive logics. The Journal of Symbolic Logic, 70(4):1108–1126, 2005. [27] S.-J. Shin. The Logical Status of Diagrams. Cambridge University Press, 1994. [28] IEEE Symposium. Visual Languages and Human-Centric Computing, 2008. [29] S. E. Toulmin. The Uses of Argument. Cambridge University Press, second edition, 2003. [30] UK University of Brighton. International Conference on the Theory and Application of Diagrams, 2008. [31] J. Venn. Symbolic logic. Chelsea Publishing Co., 1971. Reprint of the 1894 second edition, revised and rewritten.