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.

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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..

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)

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)

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)

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)

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)

There are two general questions which many views in the philosophy of mathematics can be seen as addressing: what are mathematical objects, and how do we have knowledge of them? Naturally, the answers given to these questions are linked, since whatever account we give of how we have knowledge of mathematical objects surely has to take into account what sorts of things we claim they are; conversely, whatever account we give of the nature of mathematical objects must be accompanied (...) by a corresponding account of how it is that we acquire knowledge of those objects. The connection between these problems results in what is often called "Benacerraf's Problem", which is a dilemma that many philosophical views about mathematical objects face. It will be my goal here to present a view, attributed to Richard Dedekind, which approaches the initial questions in a different way than many other philosophical views do, and in doing so, avoids the dilemma given by Benacerraf's problem. (shrink)

cians concerned with using logical tools in philosophy have been keenly aware of the limitations that arise from the original con centration of symbolic logic on the idiom of mathematics, and many of them have worked to create extensions of the received logical theories that would make them more generally applicable in philosophy. Carnap's Testability and Meaning, published in 1936 and 1937, was a good early example of this sort of research, motivated by the inadequacy of first-order formalizations (...) of dis 'This sugar cube is soluble in water'. positional sentences like And in fact there is a continuous history of work on this topic, extending from Carnap's paper to Shoham's contribution to the present volume.. Much of the work in philosophical logic, and much of what has appeared in The Journal of Philosophical Logic, was mo tivated by similar considerations: work in modal logic, intensional logics, non declaratives, presuppositions, and many other topics. In this sort of research, sin.ce the main point is to devise new formalisms, the technical development tends to be rather shallow in comparison with mathematical logic, though it is sel dom absent: theorems need to be proved in order to justify the formalisms, and sometimes these are nontrivial. On the other hand, much effort has to go into motivating a logical innovation. (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)

The aim of this article is to strengthen links between cognitive brain research and formal logic. The work covers three fundamental sorts of logical inferences: reasoning in the propositional calculus, i.e. inferences with the conditional “if...then”, reasoning in the predicate calculus, i.e. inferences based on quantifiers such as “all”, “some”, “none”, and reasoning with n-place relations. Studies with brain-damaged patients and neuroimaging experiments indicate that such logical inferences are implemented in overlapping but different bilateral cortical networks, including parts of (...) the fronto-temporal cortex, the posterior parietal cortex, and the visual cortices. I argue that these findings show that we do not use a single deterministic strategy for solving logical reasoning problems. This account resolves many disputes about how humans reason logically and why we sometimes deviate from the norms of formal logic. (shrink)

W. V. Quine famously defended two theses that have fallen rather dramatically out of fashion. The first is that intensions are “creatures of darkness” that ultimately have no place in respectable philosophical circles, owing primarily to their lack of rigorous identity conditions. However, although he was thoroughly familiar with Carnap’s foundational studies in what would become known as possible world semantics, it likely wouldn’t yet have been apparent to Quine that he was fighting a losing battle against intensions, due in (...) large measure to developments stemming from Carnap’s studies and culminating in the work of Kripke, Hintikka, and Bayart. These developments undermined Quine’s crusade against intensions on two fronts. First, in the context of possible world semantics, intensions could after all be given rigorous identity conditions by defining them (in the simplest case) as functions from worlds to appropriate extensions, a fact exploited to powerful and influential effect in logic and linguistics by the likes of Kaplan, Montague, Lewis, and Cresswell. Second, the rise of possible world semantics fueled a strong resurgence of metaphysics in contemporary analytic philosophy that saw properties and propositions widely, fruitfully, and unabashedly adopted as ontological primitives in their own right. This resurgence — happily, in my view — continues into the present day. -/- For a time, at any rate, Quine experienced somewhat better success with his second thesis: that higher-order logic is, at worst, confused and, at best, a quirky notational alternative to standard first-order logic. However, Quine notwithstanding, a great deal of recent work in formal metaphysics transpires in a higher-order logical framework in which properties and propositions fall into an infinite hierarchy of types of (at least) every finite order. Initially, the most philosophically compelling reason for embracing such a framework since Russell first proposed his simple theory of types was simply that it provides a relatively natural explanation of the paradoxes. However, since the seminal work of Prior there has been a growing trend to consider higher-order logic to be the most philosophically natural framework for metaphysical inquiry, many of the contributors to this volume being among the most important and influential advocates of this view. Indeed, this is now quite arguably the dominant view among formal metaphysicians. -/- In this paper, and against the current tide, I will argue in §1 that there are still good reasons to think that Quine’s second battle is not yet lost and that the correct framework for logic is first-order and type-free — properties and propositions, logically speaking, are just individuals among others in a single domain of quantification — and that it arises naturally out of our most basic logical and semantical intuitions. The data I will draw upon are not new and are well-known to contemporary higher-order metaphysicians. However, I will try to defend my thesis in what I believe is a novel way by suggesting that these basic intuitions ground a reasonable distinction between “pure” logic and non-logical theory, and that Russell-style semantic paradoxes of truth and exemplification arise only when we move beyond the purely logical and, hence, do not of themselves provide any strong objection to a type-free conception of properties and propositions. -/- Most of my arguments in §1 are largely independent of any specific account of the nature of properties and propositions beyond their type-freedom. However, I will in addition argue that there are good reasons to take propositions, at least, to be very fine-grained. My arguments are thus bolstered significantly if it can be shown that there are in fact well-defined examples of logics that are not only type-free but which comport with such a conception of propositions. It is the purpose of §2 to lay out a logic of this sort in some detail, drawing especially upon work by George Bealer and related work of my own. With the logic in place, it will be possible to generalize the line of argument noted above regarding Russell-style paradoxes and, in §3, apply it to two propositional paradoxes — the Prior-Kaplan paradox and the Russell-Myhill paradox — that are often taken to threaten the sort of account developed here. (shrink)

Theories of adverbial modification can be roughly distinguished into two sorts. One kind of theory takes logical form to follow surface grammatical form. Adverbs are treated as unanalyzable logical operators that turn a predicate or sentence into a different predicate or sentence respectively. And new rules of logic are stated for these operators. -/- A different kind of theory does not suppose that logical form must parallel surface grammatical form. It allows that logical form may have more to do (...) with deeper structures that might be studied in transformational grammar. Adverbs are treated as surface forms of the underlying predicates represented by corresponding adjectives and verbs. 'Slowly' is derived from 'slow'; 'intentionally' from 'intentional' or 'intend'; etc. And new rules of logic are avoided where they can be. -/- In this paper I attempt to state some of the advantages of the second sort of theory. My procedure will be this. First, I will try to say in outline what theories of logical form are. Then I will state five principles for evaluating such theories. Next, I will sketch the sorts of analyses acceptance of principles (1)-(5) leads to. In particular I will talk about adverbial phrases (e.g. locatives) that are best analyzed in terms of implicit references to events, relative modifiers (like 'large') which relate something to a comparison class, and 'that' clauses taken as names of propositions. By appealing to principles (1)-(5) I will defend these analyses against certain others, one that appeals to many logical operators, a second that treats all sentences as names of propositions, and a third that sees implicit reference to possible worlds in the language being analyzed. Finally, I will offer a pragmatic defense of my approach in terms of principles (1)-(5) as against a different approach that appeals to possible world semantics. (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)

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)

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)