Quine often argued for a simple, untyped system of logic rather than the typed systems that were championed by Russell and Carnap, among others. He claimed that nothing important would be lost by eliminating sorts, and the result would be additional simplicity and elegance. In support of this claim, Quine conjectured that every many-sorted theory is equivalent to a single-sorted theory. We make this conjecture precise, and prove that it is true, at least according to one (...) reasonable notion of theoretical equivalence. Our clarification of Quine’s conjecture, however, exposes the shortcomings of his argument against many-sorted logic. (shrink)

As noted in 1962 by Timothy Smiley, if Aristotle’s logic is faithfully translated into modern symbolic logic, the fit is exact. If categorical sentences are translated into many-sorted logic MSL according to Smiley’s method or the two other methods presented here, an argument with arbitrarily many premises is valid according to Aristotle’s system if and only if its translation is valid according to modern standard many-sorted logic. As William Parry observed in (...) 1973, this result can be proved using my 1972 proof of the completeness of Aristotle’s syllogistic. (shrink)

Prominent experts present papers which discuss problems regarding this subject. Coverage includes case studies in the translation of logics for second-order and propositional dynamic logic; many-sorted algebras and equational logic; logical foundations of artificial intelligence along with a variety of methods that exist to encode information; program verification techniques such as Floyd-Hoare, intermittent assertion and temporal logic of programs.

Basically, the connection of two many-sorted theories is obtained by taking their disjoint union, and then connecting the two parts through connection functions that must behave like homomorphisms on the shared signature. We determine conditions under which decidability of the validity of universal formulae in the component theories transfers to their connection. In addition, we consider variants of the basic connection scheme. Our results can be seen as a generalization of the so-called E-connection approach for combining modal logics (...) to an algebraic setting. (shrink)

We use connections between conjunctive game formulas and the theory of inductive definitions to define the notions of a coinductive formula and its approximations. Corresponding to the theory of conjunctive game formulas we develop a theory of coinductive formulas, including a covering theorem and a normal form theorem for many sorted languages. Applying both theorems and the results on "model interpolation" obtained in this paper, we prove a many-sorted interpolation theorem for ω 1 ω-logic, which (...) considers interpolation with respect to the language symbols, the quantifiers, the identity, and countably infinite conjunction and disjunction. (shrink)

In this paper we discuss an interpretation of intuitionistic type theory in many-sorted arithmetic with so-called conditional application. Via the formulas-as-types correspondence the arithmetical system in turn can be embedded in ML, resulting in a characterization of strong Σ-elimination by an axiom of conditional choice.

The purpose of the present paper is to prove the interpolation theorem for many-sorted languages which are, in terminology of Feferman neither restricted nor unrestricted. Such languages are often used in mathematical practice and have been investigated by several authors . The result is a generalization of the well-known Stern interpolation theorem for restricted m.s.l. and its proof depends heavily on that of Stern’s theorem. In place of the functions Rel + and Rel − our theorem treats the (...) functions T yp + and T yp − giving much more information about any formula. (shrink)

Implementation of formal specifications is very important in formal software development and can be described in terms of simple logical concepts. Formal specifications are presentations of theories in many-sorted first-order logic, and an implementation of a formal specification on another formal specification amounts to an interpretation of the former into a conservative extension of the latter. Here we present and analyse some sort introducing constructs akin to those found in many programming languages. This is of importance (...) because it occurs often in implementing formal specifications, when new sorts are ‘constructed’ from the concrete ones. We specify these constructs and show that these specifications provide extensions with behaviour close to that of the familiar extensions by definitions. (shrink)

This paper describes axiomatic theories SA and SAR, which are versions of second order arithmetic with countably many sorts for sets of natural numbers. The theories are intended to be applied in reverse mathematics because their multi-sorted language allows to express some mathematical statements in more natural form than in the standard second order arithmetic. We study metamathematical properties of the theories SA, SAR and their fragments. We show that SA is mutually interpretable with the theory of arithmetical (...) truth PATr obtained from the Peano arithmetic by adding infinitely many truth predicates. Corresponding fragments of SA and PATr are also mutually interpretable. We compare the proof-theoretical strengths of the fragments; in particular, we show that each fragment SAs with sorts <=s is weaker than next fragment SAs+1. (shrink)

We achieve several results. First, we develop a variant of the theory of absolute Galois groups in the context of many sorted structures. Second, we provide a method for coding absolute Galois groups of structures, so they can be interpreted in some monster model with an additional predicate. Third, we prove the “Weak Independence Theorem” for pseudo-algebraically closed (PAC) substructures of an ambient structure with no finite cover property (nfcp) and the property [Formula: see text]. Fourth, we describe (...) Kim-dividing in these PAC substructures and show several results related to the SOPnhierarchy. Fifth, we characterize the algebraic closure in PAC structures. (shrink)

Supervaluational theories of vagueness have achieved considerable popularity in the past decades, as seen in eg [5], [12]. This popularity is only natural; supervaluations let us retain much of the power and simplicity of classical logic, while avoiding the commitment to strict bivalence that strikes many as implausible. Like many nonclassical logics, the supervaluationist system SP has a natural dual, the subvaluationist system SB, explored in eg [6], [28].1 As is usual for such dual systems, the classical (...) features of SP (typically viewed as benefits) appear in SB in ‘mirror-image’ form, and the nonclassical features of SP (typically viewed as costs) also appear in SB in ‘mirror-image’ form. Given this circumstance, it can be difficult to decide which of two dual systems is better suited for an approach to vagueness.2 The present paper starts from a consideration of these two approaches— the supervaluational and the subvaluational—and argues that neither of them is well-positioned to give a sensible logic for vague language. §2 presents the systems SP and SB and argues against their usefulness. Even if we suppose that the general picture of vague language they are often taken to embody is accurate, we ought not arrive at systems like SP and SB. Instead, such a picture should lead us to truth-functional systems like strong Kleene logic (K3) or its dual LP. §3 presents these systems, and argues that supervaluationist and subvaluationist understandings of language are better captured there; in particular, that a dialetheic approach to vagueness based on the logic LP is a more sensible approach. §4 goes on to consider the phenomenon of higher-order vagueness within an LP-based approach, and §5 closes with a consideration of the sorites argument itself. (shrink)

This book marks the inauguration of the Historia Logicae book series, which seeks to publish high-quality monographs, dissertations, textbooks, proceedings, and anthologies on the history of logic in either German or English. Serving as the inaugural volume in this series, the book explores the contemporary interpretation of logic across many centuries and cultures. The first section of the volume comprises a compilation of papers dedicated to ancient and medieval logic, examining prominent thinkers such as Plato, Aristotle, (...) Seneca, Porphyry, Proclus, Boethius, Buridan, and Kilwardby. The second section shifts focus towards early-modern and contemporary logics, including the works of Caramuel, Kant, Drobisch, Husserl, and Jaskowski. Topics of discussion encompass the relationship between mathematics and logic, natural deduction, intuitionism, graph theory, categorical judgments, theories of truth, modal logic, opposition relations, logic diagrams, definitions of formal logic, many-sorted logic, model theory, and paraconsistent logic. (shrink)

Within the program of finding axiomatizations for various parts of computability logic, it was proven earlier that the logic of interactive Turing reduction is exactly the implicative fragment of Heyting’s intuitionistic calculus. That sort of reduction permits unlimited reusage of the computational resource represented by the antecedent. An at least equally basic and natural sort of algorithmic reduction, however, is the one that does not allow such reusage. The present article shows that turning the logic of the (...) first sort of reduction into the logic of the second sort of reduction takes nothing more than just deleting the contraction rule from its Gentzen-style axiomatization. The first sort of interactive reduction is also shown to come in three natural versions. While those three versions are very different from each other, their logical behaviors turn out to be indistinguishable, with that common behavior being precisely captured by implicative intuitionistic logic. Among the other contributions of the present article is an informal introduction of a series of new — finite and bounded — versions of recurrence operations and the associated reduction operations. (shrink)

Classical logic has proved inadequate in various areas of computer science, artificial intelligence, mathematics, philosopy and linguistics. This is an introduction to extensions of first-order logic, based on the principle that many-sorted logic (MSL) provides a unifying framework in which to place, for example, second-order logic, type theory, modal and dynamic logics and MSL itself. The aim is two fold: only one theorem-prover is needed; proofs of the metaproperties of the different existing calculi can (...) be avoided by borrowing them from MSL. To make the book accessible to readers from different disciplines, whilst maintaining precision, the author has supplied detailed step-by-step proofs, avoiding difficult arguments, and continually motivating the material with examples. Consequently this can be used as a reference, for self-teaching or for first-year graduate courses. (shrink)

Logical Options introduces the extensions and alternatives to classical logic which are most discussed in the philosophical literature: many-sorted logic, second-order logic, modal logics, intuitionistic logic, three-valued logic, fuzzy logic, and free logic. Each logic is introduced with a brief description of some aspect of its philosophical significance, and wherever possible semantic and proof methods are employed to facilitate comparison of the various systems. The book is designed to be useful (...) for philosophy students and professional philosophers who have learned some classical first-order logic and would like to learn about other logics important to their philosophical work. (shrink)

Ken Pledger devised a one-sorted approach to the incidence relation of plane geometries, using structures that also support models of propositional modal logic. He introduced a modal system 12g that is valid in one-sorted projective planes, proved that it has finitely many non-equivalent modalities, and identified all possible modality patterns of its extensions. One of these extensions 8f is valid in elliptic planes. These results were presented in his 1980 doctoral dissertation, which is reprinted in this (...) issue of the Australasian Journal of Logic. Here we show that 12g and 8f are strongly complete for validity in their intended one-sorted geometrical interpretations, and have the finite model property. The proofs apply standard technology of modal logic together with a step-by-step procedure introduced by Yde Venema for constructing two-sorted projective planes. (shrink)

In recent philosophy of science there has been much discussion of both pluralism, which embraces scientific terms with multiple meanings, and eliminativism, which rejects such terms. Some recent work focuses on the conditions that legitimize pluralism over eliminativism – the conditions under which such terms are acceptable. Often, this is understood as a matter of encouraging effective communication – the danger of these terms is thought to be equivocation, while the advantage is thought to be the fulfilment of ‘bridging roles’ (...) that facilitate communication between different scientists and specialisms. These theories are geared towards regulating communication between scientists qua scientists. However, this overlooks an important class of harmful equivocation that involves miscommunication between scientists and nonscientists, such as the public or policymakers. To make my case, I use the example of theory of mind, also known as ‘mindreading’ and ‘mentalizing’, and broadly defined as the capacity to attribute mental states to oneself and others. I begin by showing that ‘theory of mind’ has multiple meanings, before showing that this has resulted in harmful equivocations of a sort and in a way not accounted for by previous theories of pluralism and eliminativism. (shrink)

A class of many-sorted polyadic set algebras is introduced. These generalise structure and model in a way that is relevant in regards to the Entscheidungsproblem and to automated reasoning.A downward Löwenheim-Skolem property is shown in that each satisfiable finite conjunction of purely relational first-order prenex sentences has a finite generalised model. This property does, together with a construction related to doubling the size of a finite structure, provide several strict generalisations of the strategy of finite model search for (...) disproving. (shrink)

We begin with an introductory overview of contributions made by more than twenty scholars associated with the Philosophy Department at the University of Buffalo during the last half-century to our understanding and evaluation of Aristotle's logic. More well-known developments are merely mentioned in..

In Truth as One and Many, Michael Lynch offers a new theory of truth. There are two kinds of theory of truth in the literature. On the one hand, we have logical theories, which seek to construct formal systems that are consistent, while also containing a predicate which have as many as possible of the properties which we ordinarily take the English predicate ‘is true’ to have; salient examples include Tarski’s and Kripke’s theories of truth. On the other (...) hand, we have metaphysical theories, which seek to give a non-formal account of the nature of truth – of what truth consists in, of what it means to say that something is true; salient examples include correspondence, coherence and deflationary theories of truth. Lynch’s theory – functionalism about truth – is of the second sort.The theory takes its start from a number of principles which Lynch classifies as truisms about truth:Objectivity: The belief that p is true if, and only if, with respect to the belief that p, things are as they are believed to be.Norm of Belief: It is prima facie correct to believe that p if and only if the proposition that p is true.End of Inquiry: Other things being equal, true beliefs are a worthy goal of inquiry.Lynch argues that other familiar principles can be derived from these: for example, Objectivity together with some auxiliary principles and definitions yields versions of the T-schema, and of the principle that beliefs can be true without being warranted and vice versa. These principles are supposed to give the nominal essence of truth – to constitute our folk theory of truth. Lynch …. (shrink)

Ontological pluralism is the doctrine that there are different ways or modes of being. In contemporary guise, it is the doctrine that a logically perspicuous description of reality will use multiple quantifiers which cannot be thought of as ranging over a single domain. Although thought defeated for some time, recent defenses have shown a number of arguments against the view unsound. However, another worry looms: that despite looking like an attractive alternative, ontological pluralism is really no different than its counterpart, (...) ontological monism. In this paper, after explaining the worry in detail, I argue that considerations dealing with the nature of the logic ontological pluralists ought to endorse, coupled with an attractive philosophical thesis about the relationship between logic and metaphysics, show this worry to be unfounded. (shrink)

Since the time of Aristotle's students, interpreters have considered Prior Analytics to be a treatise about deductive reasoning, more generally, about methods of determining the validity and invalidity of premise-conclusion arguments. People studied Prior Analytics in order to learn more about deductive reasoning and to improve their own reasoning skills. These interpreters understood Aristotle to be focusing on two epistemic processes: first, the process of establishing knowledge that a conclusion follows necessarily from a set of premises (that is, on the (...) epistemic process of extracting information implicit in explicitly given information) and, second, the process of establishing knowledge that a conclusion does not follow. Despite the overwhelming tendency to interpret the syllogistic as formal epistemology, it was not until the early 1970s that it occurred to anyone to think that Aristotle may have developed a theory of deductive reasoning with a well worked-out system of deductions comparable in rigor and precision with systems such as propositional logic or equational logic familiar from mathematical logic. When modern logicians in the 1920s and 1930s first turned their attention to the problem of understanding Aristotle's contribution to logic in modern terms, they were guided both by the Frege-Russell conception of logic as formal ontology and at the same time by a desire to protect Aristotle from possible charges of psychologism. They thought they saw Aristotle applying the informal axiomatic method to formal ontology, not as making the first steps into formal epistemology. They did not notice Aristotle's description of deductive reasoning. Ironically, the formal axiomatic method (in which one explicitly presents not merely the substantive axioms but also the deductive processes used to derive theorems from the axioms) is incipient in Aristotle's presentation. Partly in opposition to the axiomatic, ontically-oriented approach to Aristotle's logic and partly as a result of attempting to increase the degree of fit between interpretation and text, logicians in the 1970s working independently came to remarkably similar conclusions to the effect that Aristotle indeed had produced the first system of formal deductions. They concluded that Aristotle had analyzed the process of deduction and that his achievement included a semantically complete system of natural deductions including both direct and indirect deductions. Where the interpretations of the 1920s and 1930s attribute to Aristotle a system of propositions organized deductively, the interpretations of the 1970s attribute to Aristotle a system of deductions, or extended deductive discourses, organized epistemically. The logicians of the 1920s and 1930s take Aristotle to be deducing laws of logic from axiomatic origins; the logicians of the 1970s take Aristotle to be describing the process of deduction and in particular to be describing deductions themselves, both those deductions that are proofs based on axiomatic premises and those deductions that, though deductively cogent, do not establish the truth of the conclusion but only that the conclusion is implied by the premise-set. Thus, two very different and opposed interpretations had emerged, interestingly both products of modern logicians equipped with the theoretical apparatus of mathematical logic. The issue at stake between these two interpretations is the historical question of Aristotle's place in the history of logic and of his orientation in philosophy of logic. This paper affirms Aristotle's place as the founder of logic taken as formal epistemology, including the study of deductive reasoning. A by-product of this study of Aristotle's accomplishments in logic is a clarification of a distinction implicit in discourses among logicians--that between logic as formal ontology and logic as formal epistemology. (shrink)

Some authors have studied in an ad hoc fashion the inclusive logics, that is the logics which admit or include objects or sets without element. These logics have been recently brought into the limelight because of the use of arbitrary topoi for interpreting languages. (In topoi there are usually many objects without element.)The aim of the paper is to present, for some inclusive logics, an axiomatization as natural and as simple as possible. Because of the intended applications to category (...) theory, the logics studied are many-sorted and intuitionistic. (shrink)

We present the Jaina theory of sevenfold predication as a 7-valued logic, in which every logical value consists in a 3-tuple of opinions. A question-answer semantics is used in order to give an intuitive characterization of these logical values in terms of opinion polls. Two different interpretations are plausible for the latest sort of opinion, depending upon whether "non-assertability" refers to incompleteness or inconsistency. It is shown hat the incomplete version of JL_{G} is equivalent to Kleene's logic K3, (...) whereas the inconsistent version of JL_{M} is equivalent to Priest's Logic of Paradox LP. Finally, it is argued that the Indian logics depart from Western logics by conflating truth and justified belief: the different preconditions for belief ascription accounts for the difference between pluralist and skeptic logics. (shrink)

Though deceptively simple and plausible on the face of it, Craig's interpolation theorem has proved to be a central logical property that has been used to reveal a deep harmony between the syntax and semantics of first order logic. Craig's theorem was generalized soon after by Lyndon, with application to the characterization of first order properties preserved under homomorphism. After retracing the early history, this article is mainly devoted to a survey of subsequent generalizations and applications, especially of (...) class='Hi'>many-sorted interpolation theorems. Attention is also paid to methodological considerations, since the Craig theorem and its generalizations were initially obtained by proof-theoretic arguments while most of the applications are model-theoretic in nature. The article concludes with the role of the interpolation property in the quest for "reasonable" logics extending first-order logic within the framework of abstract model theory. (shrink)

We introduce and study a new approach to the theory of abstract algebraic logic (AAL) that explores the use of many-sorted behavioral logic in the role traditionally played by unsorted equational logic. Our aim is to extend the range of applicability of AAL toward providing a meaningful algebraic counterpart also to logics with a many-sorted language, and possibly including non-truth-functional connectives. The proposed behavioral approach covers logics which are not algebraizable according to the (...) standard approach, while also bringing a new algebraic perspective to logics which are algebraizable using the standard tools of AAL. Furthermore, we pave the way toward a robust behavioral theory of AAL, namely by providing a behavioral version of the Leibniz operator which allows us to generalize the traditional Leibniz hierarchy, as well as several well-known characterization results. A number of meaningful examples will be used to illustrate the novelties and advantages of the approach. (shrink)

After defining, for each many-sorted signature Σ = (S, Σ), the category Ter(Σ), of generalized terms for Σ (which is the dual of the Kleisli category for $${\mathbb {T}_{\bf \Sigma}}$$, the monad in Set S determined by the adjunction $${{\bf T}_{\bf \Sigma} \dashv {\rm G}_{\bf \Sigma}}$$ from Set S to Alg(Σ), the category of Σ-algebras), we assign, to a signature morphism d from Σ to Λ, the functor $${{\bf d}_\diamond}$$ from Ter(Σ) to Ter(Λ). Once defined the mappings that (...) assign, respectively, to a many-sorted signature the corresponding category of generalized terms and to a signature morphism the functor between the associated categories of generalized terms, we state that both mappings are actually the components of a pseudo-functor Ter from Sig to the 2-category Cat. Next we prove that there is a functor TrΣ, of realization of generalized terms as term operations, from Alg(Σ) × Ter(Σ) to Set, that simultaneously formalizes the procedure of realization of generalized terms and its naturalness (by taking into account the variation of the algebras through the homomorphisms between them). We remark that from this fact we will get the invariance of the relation of satisfaction under signature change. Moreover, we prove that, for each signature morphism d from Σ to Λ, there exists a natural isomorphism θ d from the functor $${{{\rm Tr}^{\bf {\bf \Lambda}} \circ ({\rm Id} \times {\bf d}_\diamond)}}$$ to the functor $${{\rm Tr}^{\bf \Sigma} \circ ({\bf d}^* \times {\rm Id})}$$, both from the category Alg(Λ) × Ter(Σ) to the category Set, where d* is the value at d of the arrow mapping of a contravariant functor Alg from Sig to Cat, that shows the invariant character of the procedure of realization of generalized terms under signature change. Finally, we construct the many-sorted term institution by combining adequately the above components (and, in a derived way, the many-sorted specification institution), but for a strict generalization of the standard notion of institution. (shrink)

Some arguments use ‘generic’, or ‘typical’, objects. An explanation for this idea in terms of ‘almost all’ is suggested. The intuition of ‘almost all’ as ‘but for a few exceptions’ is rendered precise by means of ultrafilters. A logical system, with generalized quantifiers for ‘almost all’, is proposed as a basis for generic reasoning. This logic is monotonic, has a simple sound and complete deductive calculus, and is a conservative extension of classical first-order logic, with which it shares (...) several properties. For generic reasoning, generic individuals are introduced and internalized as generic constants, thereby producing conservative extensions where one can reason about generic objects as intended. A many-sorted version of this logic is introduced to handle distinct notions of ‘large’ subsets. Other possible applications for this logic are indicated. (shrink)

Recently, Caleiro, Gon¸calves and Martins introduced the notion of behaviorally algebraizable logic. The main idea behind their work is to replace, in the traditional theory of algebraizability of Blok and Pigozzi, unsorted equational logic with multi-sorted behavioral logic. The new notion accommodates logics over many-sorted languages and with non-truth-functional connectives. Moreover, it treats logics that are not algebraizable in the traditional sense while, at the same time, shedding new light to the equivalent algebraic semantics (...) of logics that are algebraizable according to the original theory. In this paper, the notion of an abstract multi-sorted π-institution is introduced so as to transfer elements of the theory of behavioral algebraizability to the categorical setting. Institutions formalize a wider variety of logics than deductive systems, including logics involving multiple signatures and quantifiers. The framework developed has the same relation to behavioral algebraizability as the classical categorical abstract algebraic logic framework has to the original theory of algebraizability of Blok and Pigozzi. (shrink)

Even though it is not very often admitted, partial functions do play a significant role in many practical applications of deduction systems. Kleene has already given a semantic account of partial functions using three-valued logic decades ago, but there has not been a satisfactory mechanization. Recent years have seen a thorough investigation of the framework of many-valued truth-functional logics. However, strong Kleene logic, where quantification is restricted and therefore not truthfunctional, does not fit the framework directly. (...) We solve this problem by applying recent methods from sorted logics. This paper presents a resolution calculus that combines the proper treatment of partial functions with the efficiency of sorted calculi. (shrink)

We consider two-sorted theories of vector spaces and prove a criterion for the assertion that such a theory allows elimination of quantifiers over vector variables.

Contrary to common misconceptions, today's logic is not devoid of existential import: the universalized conditional ∀ x [S→ P] implies its corresponding existentialized conjunction ∃ x [S & P], not in all cases, but in some. We characterize the proexamples by proving the Existential-Import Equivalence: The antecedent S of the universalized conditional alone determines whether the universalized conditional has existential import, i.e. whether it implies its corresponding existentialized conjunction.A predicate is an open formula having only x free. An existential-import (...) predicate Q is one whose existentialization, ∃ x Q, is logically true; otherwise, Q is existential-import-free or simply import-free.How abundant or widespread is existential import? How abundant or widespread are existential-import predicates in themselves or in comparison to import-free predicates? We show that existential-import predicates are quite abundant, and no less so than import-free predicates. Existential.. (shrink)

We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of ϕ are of tree width (...) at most k. For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic GSOL. We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle. Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result. (shrink)

In this paper we describe the Curry-Howard-De Bruijn isomorphism between Higher Order Many Sorted Intuitionistic Predicate Logic PREDω and the type system λPREDω, which can be considered a subsystem of the Calculus of Constructions. The type system is presented using the concept of a Pure Type System, which is a very elegant framework for describing type systems. We show in great detail how formulae and proof trees of the logic relate to types and terms of the (...) type system, respectively. Finally, we discuss some consequences of the isomorphism with respect to the relation between the systems discussed in this paper. (shrink)