Fibring is defined as a mechanism for combining logics with a first-order base, at both the semantic and deductive levels. A completeness theorem is established for a wide class of such logics, using a variation of the Henkin method that takes advantage of the presence of equality and inequality in the logic. As a corollary, completeness is shown to be preserved when fibring logics in that class. A modal first-order logic is obtained as a fibring where (...) neither the Barcan formula nor its converse hold. (shrink)

I consider the first-order modal logic which counts as valid those sentences which are true on every interpretation of the non-logical constants. Based on the assumptions that it is necessary what individuals there are and that it is necessary which propositions are necessary, Timothy Williamson has tentatively suggested an argument for the claim that this logic is determined by a possible world structure consisting of an infinite set of individuals and an infinite set of worlds. He notes that (...) only the cardinalities of these sets matters, and that not all pairs of infinite sets determine the same logic. I use so-called two-cardinal theorems from model theory to investigate the space of logics and consequence relations determined by pairs of infinite sets, and show how to eliminate the assumption that worlds are individuals from Williamson’s argument. (shrink)

We seem to have a good grasp of how the subject matters of truth-functional composites depends on their components: it's simply fusion (Hawke, 2018; Fine, 2020; Plebani and Spolaore, 2021 and 2023; Berto 2022). But what relation should the subject matter of subsentential components bear to the subject matter of the sentences they feature in, and what to say about the quantified sentences of first-order predicate logic? Given how well we seem to understand sentential subject matter in the (...) context of propositional logic, I propose a reduction of the subject matter of subsentential components and of quantified sentences to the subject matter of quantifier-free sentences. I argue that the view squares with the Fregean intuitions that gave rise to the construction of first-order logic as we know it today, motivating its adequacy as a theory of subject matter for first-order languages. I then show that this first-order aboutness theory has predictive and explanatory power, leading us to accept a modified version of Yablo's (2014) principle of immanent closure, as well as a new conception of arbitrary objects/reference. Finally, I propose some potential developments and restrictions. (shrink)

This completely self-contained study, widely considered the best book in the field, is intended to serve both as an introduction to quantification theory and as ...

The logics of formal inconsistency (LFIs, for short) are paraconsistent logics (that is, logics containing contradictory but non-trivial theories) having a consistency connective which allows to recover the ex falso quodlibet principle in a controlled way. The aim of this paper is considering a novel semantical approach to first-order LFIs based on Tarskian structures defined over swap structures, a special class of multialgebras. The proposed semantical framework generalizes previous aproaches to quantified LFIs presented in the literature. The case (...) of QmbC, the simpler quantified LFI expanding classical logic, will be analyzed in detail. An axiomatic extension of QmbC called QLFI1o is also studied, which is equivalent to the quantified version of da Costa and D'Ottaviano 3-valued logic J3. The semantical structures for this logic turn out to be Tarkian structures based on twist structures. The expansion of QmbC and QLFI1o with a standard equality predicate is also considered. (shrink)

Sedlár and Vigiani [18] have developed an approach to propositional epistemic logics wherein (i) an agent’s beliefs are closed under relevant implication and (ii) the agent is located in a classical possible world (i.e., the non-modal fragment is classical). Here I construct first-order extensions of these logics using the non-Tarskian interpretation of the quantifiers introduced by Mares and Goldblatt [12], and later extended to quantified modal relevant logics by Ferenz [6]. Modular soundness and completeness are proved for constant (...) domain semantics, using non-general frames with Mares–Goldblatt truth conditions. I further detail the relation between the demand that classical possible worlds have Tarskian truth conditions and incompleteness results in quantified relevant logics. (shrink)

This is a thorough treatment of first-order modal logic. The book covers such issues as quantification, equality (including a treatment of Frege's morning star/evening star puzzle), the notion of existence, non-rigid constants and function symbols, predicate abstraction, the distinction between nonexistence and nondesignation, and definite descriptions, borrowing from both Fregean and Russellian paradigms.

This paper introduces two languages and associated logics designed to afford perspicuous representations of a range of natural language arguments involving adverbs and the like: first-order logic with basic adverbs (FOL-BA) and first-order logic with scoped adverbs (FOL-SA). The guiding logical idea is that an adverb can come between a term and the rest of the statement it is a part of, resulting in a logically stronger statement. I explain various interesting challenges that arise in the (...) attempt to implement the guiding idea, and provide solutions for some but not all of them. I conclude by outlining some directions for further research. (shrink)

We provide first-order axioms for the theories of finite trees with bounded branching and finite trees with arbitrary (finite) branching. The signature is chosen to express, in a natural way, those properties of trees most relevant to linguistic theories. These axioms provide a foundation for results in linguistics that are based on reasoning formally about such properties. We include some observations on the expressive power of these theories relative to traditional language complexity classes.

We generalize two well-known model-theoretic characterization theorems from propositional modal logic to first-order modal logic. We first study FML-definable frames and give a version of the Goldblatt–Thomason theorem for this logic. The advantage of this result, compared with the original Goldblatt–Thomason theorem, is that it does not need the condition of ultrafilter reflection and uses only closure under bounded morphic images, generated subframes and disjoint unions. We then investigate Lindström type theorems for first-order modal logic. (...) We show that FML has the maximal expressive power among the logics extending FML which satisfy compactness, bisimulation invariance and the Tarski union property. (shrink)

The paper focuses on extending to the first order case the semantical program for modalities first introduced by Dana Scott and Richard Montague. We focus on the study of neighborhood frames with constant domains and we offer in the first part of the paper a series of new completeness results for salient classical systems of first order modal logic. Among other results we show that it is possible to prove strong completeness results for normal (...) systems without the Barcan Formula (like FOL + K)in terms of neighborhood frames with constant domains. The first order models we present permit the study of many epistemic modalities recently proposed in computer science as well as the development of adequate models for monadic operators of high probability. Models of this type are either difficult of impossible to build in terms of relational Kripkean semantics [40].We conclude by introducing general first order neighborhood frames with constant domains and we offer a general completeness result for the entire family of classical first order modal systems in terms of them, circumventing some well-known problems of propositional and first order neighborhood semantics (mainly the fact that many classical modal logics are incomplete with respect to an unmodified version of either neighborhood or relational frames). We argue that the semantical program that thus arises offers the first complete semantic unification of the family of classical first order modal logics. (shrink)

We study first-order concatenation theory with bounded quantifiers. We give axiomatizations with interesting properties, and we prove some normal-form results. Finally, we prove a number of decidability and undecidability results.

This paper extends implication-space semantics to include first-order quantification. Implication-space semantics has recently been introduced as an inferentialist formal semantics that can capture nonmonotonic and nontransitive material inferences. Extant versions, however, include only propositional logic. This paper extends the framework so as to recover classical first-order logic. The goal is to formulate a theory in which consequence relations can be nonmonotonic and supraclassical, while obeying the deduction-detachment theorem and disjunction simplification, while also including conjunctions that behave (...) multiplicatively as premises and counterexamples to the usual quantifier rules. The paper explains these constraints and shows how they can be met jointly. The result is a first-order version of implication-space semantics that has all the virtues for which inferentialists and inferential expressivists praise propositional implication-space semantics. (shrink)

Edward Nieznanski developed in 2007 and 2008 two different systems in formal logic which deal with the problem of evil. Particularly, his aim is to refute a version of the logical problem of evil associated with a form of religious determinism. In this paper, we revisit his first system to give a more suitable form to it, reformulating it in first-order modal logic. The new resulting system, called N1, has much of the original basic structure, and many (...) axioms, definitions, and theorems still remain; however, some new results are obtained. If the conclusions attained are correct and true, then N1 solves the problem of evil through the refutation of a version of religious determinism, showing that the attributes of God in Classical Theism, namely, those of omniscience, omnipotence, infallibility, and omnibenevolence, when adequately formalized, are consistent with the existence of evil in the world. We consider that N1 is a good example of how formal systems can be applied in solving interesting philosophical issues, particularly in Philosophy of Religion and Analytic Theology, establishing bridges between such disciplines. (shrink)

In this paper the language of first-order modal logic is enriched with an operator @ ('actually') such that, in any model, the evaluation of a formula @A at a possible world depends on the evaluation of A at the actual world. The models have world-variable domains. All the logics that are discussed extend the classical predicate calculus, with or without identity, and conform to the philosophical principle known as serious actualism. The basic logic relies on the system K, (...) whereas others correspond to various properties that the actual world may have. All the logics are axiomatized. (shrink)

First - order modal logic is very much under current development, with many different semantics proposed. The use of rigid objects goes back to Saul Kripke. More recently, several semantics based on counterparts have been examined, in a development that goes back to David Lewis. There is yet another line of research, using intensional objects, that traces back to Richard Montague. I have been involved with this line of development for some time. In the present paper, I briefly (...) sketch several of the approaches to first - order modal logic. Then I present one that I call FOIL in the Montague tradition that, I believe, is both expressive and natural. I briefly discuss in what sense it can be made to encompass the other approaches. Finally, I provide tableau rules to go with the FOIL semantics. (shrink)

We extend first-order logic to include variadic function symbols, and prove a substitution lemma. Two applications are given: one to bounded quantifier elimination and one to the definability of certain Borel sets.

The volume includes the proceedings from the conference FOL75 -- 75 Years of First-Order Logic held at Humboldt University, Berlin, September 18 - 21, 2003 on the occasion of the anniversary of the publication of Hilbert's and Ackermann's Grundzuge der theoretischen Logik. The papers provide analyses of the historical conditions of the shaping of FOL, discuss several modern rivals to it, and show the importance of FOL for interdisciplinary research. While there is no doubt that the celebrated book (...) marks a most important step in the development of logic, the volume in hand proves the actuality of the question "Which logic is the right logic." The volume contains articles by: H. Andreka, J. X. Madarasz, I. Nemeti, A. Avron, K. Brunnler, A. Guglielmi, G. Englebretsen, W. Ewald, P. Hajek, J. Hintikka, W. Hodges, M. Kracht, R. Lanzet, H. Ben-Yami, C. Toke, S. P. Odintsov, H. Wansing, J. A. Robinson, M. Rossberg, M. Thielscher, D. E. Willard, andJ. Wole 'nski. (shrink)

Well-written undergraduate-level introduction begins with symbolic logic and set theory, followed by presentation of statement calculus and predicate calculus. First-order theories are discussed in some detail, with special emphasis on number theory. After a discussion of truth and models, the completeness theorem is proved. "...an excellent text."—Mathematical Reviews. Exercises. Bibliography.

First-order Gödel logics are a family of finite- or infinite-valued logics where the sets of truth values V are closed subsets of [0,1] containing both 0 and 1. Different such sets V in general determine different Gödel logics GV (sets of those formulas which evaluate to 1 in every interpretation into V). It is shown that GV is axiomatizable iff V is finite, V is uncountable with 0 isolated in V, or every neighborhood of 0 in V is (...) uncountable. Complete axiomatizations for each of these cases are given. The r.e. prenex, negation-free, and existential fragments of all first-order Gödel logics are also characterized. (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)

In preference aggregation a set of individuals express preferences over a set of alternatives, and these preferences have to be aggregated into a collective preference. When preferences are represented as orders, aggregation procedures are called social welfare functions. Classical results in social choice theory state that it is impossible to aggregate the preferences of a set of individuals under different natural sets of axiomatic conditions. We define a first-order language for social welfare functions and we give a complete (...) axiomatisation for this class, without having the number of individuals or alternatives specified in the language. We are able to express classical axiomatic requirements in our first-order language, giving formal axioms for three classical theorems of preference aggregation by Arrow, by Sen, and by Kirman and Sondermann. We explore to what extent such theorems can be formally derived from our axiomatisations, obtaining positive results for Sen’s Theorem and the Kirman-Sondermann Theorem. For the case of Arrow’s Theorem, which does not apply in the case of infinite societies, we have to resort to fixing the number of individuals with an additional axiom. In the long run, we hope that our approach to formalisation can serve as the basis for a fully automated proof of classical and new theorems in social choice theory. (shrink)

The transition semantics presented in Rumberg (J Log Lang Inf 25(1):77–108, 2016a) constitutes a fine-grained framework for modeling the interrelation of modality and time in branching time structures. In that framework, sentences of the transition language L_t are evaluated on transition structures at pairs consisting of a moment and a set of transitions. In this paper, we provide a class of first-order definable Kripke structures that preserves L_t-validity w.r.t. transition structures. As a consequence, for a certain fragment of (...) L_t, validity w.r.t. transition structures turns out to be axiomatizable. The result is then extended to the entire language L_t by means of a quite natural ‘Henkin move’, i.e. by relaxing the notion of validity to bundled structures. (shrink)

Panqualityism, recently defended by Sam Coleman, is a variety of Russellian monism on which the categorical properties of fundamental physical entities are qualities, or, in Coleman’s exposition, unconscious qualia. Coleman defends a quotationalist, higher-order thought version of panqualityism. The aim of this paper is, first, to demonstrate that a first-order representationalist panqualityism is also available, and to argue positively in its favor. For it shall become apparent that quotationalist and first-order representationalist panqualityism are, in (...) spite of their close similarities, radically different theories: quotationalist panqualityism locates qualities in the subject of an experience, while first-order panqualityism locates qualities in the world. I argue that this makes quotationalist panqualityism implausible and first-order, representationalist panqualityism a highly natural, elegant, and intuitive theory. (shrink)

What has been the historical relationship between set theory and logic? On the one hand, Zermelo and other mathematicians developed set theory as a Hilbert-style axiomatic system. On the other hand, set theory influenced logic by suggesting to Schröder, Löwenheim and others the use of infinitely long expressions. The questions of which logic was appropriate for set theory - first-order logic, second-order logic, or an infinitary logic - culminated in a vigorous exchange between Zermelo and Gödel around (...) 1930. (shrink)

We present an axiomatisation for the first-order temporal logic with connectives Until and Since over the class of all linear flows of time. Completeness of the axiom system is proved.We also add a few axioms to find a sound and complete axiomatisation for the first order temporal logic of Until and Since over rational numbers time.

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and finite satisfiability (...) problems are algorithmically solvable for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

The main aim of this paper is to introduce first-order versions of logics of evidence and truth, together with corresponding sound and complete Kripke semantics with variable and constant domains. According to the intuitive interpretation proposed here, these logics intend to represent possibly inconsistent and incomplete information bases over time. The paper also discusses the connections between Belnap-Dunn’s and da Costa’s approaches to paraconsistency, and argues that the logics of evidence and truth combine them in a very natural (...) way. (shrink)

In theTractatus, Wittgenstein advocates two major notational innovations in logic. First, identity is to be expressed by identity of the sign only, not by a sign for identity. Secondly, only one logical operator, called “N” by Wittgenstein, should be employed in the construction of compound formulas. We show that, despite claims to the contrary in the literature, both of these proposals can be realized, severally and jointly, in expressively complete systems of first-order logic. Building on early work (...) of Hintikka’s, we identify three ways in which the first notational convention can be implemented, show that two of these are compatible with the text of theTractatus, and argue on systematic and historical grounds, adducing posthumous work of Ramsey’s, for one of these as Wittgenstein’s envisaged method. With respect to the second Tractarian proposal, we discuss how Wittgenstein distinguished between general and non-general propositions and argue that, claims to the contrary notwithstanding, an expressively adequate N-operator notation is implicit in theTractatuswhen taken in its intellectual environment. We finally introduce a variety of sound and complete tableau calculi for first-order logics formulated in a Wittgensteinian notation. The first of these is based on the contemporary notion of logical truth as truth in all structures. The others take into account the Tractarian notion of logical truth as truth in all structures over one fixed universe of objects. Here the appropriate tableau rules depend on whether this universe is infinite or finite in size, and in the latter case on its exact finite cardinality.As it is obviously easy to express how propositions can be constructed by means of this operation and how propositions are not to be constructed by means of it, this must be capable of exact expression.5.503. (shrink)

We discuss first order theories in which individual concepts are admitted as mathematical objects along with the things that reify them. This allows very straightforward formalizations of knowledge, belief, wanting, and necessity in ordinary first order logic without modal operators. Applications are given in philosophy and in artificial intelligence. We do not treat general concepts, and we do not present any full axiomatizations but rather show how various facts can be expressed.

Glue has evolved significantly during the past decade. Although the recent move to type-theoretic notation was a step in the right direction, basing the current Glue system on System F (second-order λ-calculus) was an unfortunate choice. An extension to two sorts and ad hoc restrictions were necessary to avoid inappropriate composition of meanings. As a result, the current system is unnecessarily complicated. A first-order Glue system is hereby proposed as its replacement. This new system is not only (...) simpler and more elegant, as it captures the exact requirements for Glue-style compositionality without ad hoc improvisations, but it also turns out to be more powerful than the current two-sorted (pseudo-) second-order system. First-order Glue supports all existing Glue analyses as well as more elegant alternatives. It also supports new, more demanding analyses. (shrink)

"In his introduction to this most welcome republication (and second edition) of his logic text, Heil clarifies his aim in writing and revising this book: 'I believe that anyone unfamiliar with the subject who set out to learn formal logic could do so relying solely on [this] book. That, in any case, is what I set out to create in writing _An Introduction to First-Order Logic_.' Heil has certainly accomplished this with perhaps _the most explanatorily thorough and pedagogically (...) rich text I’ve personally come across_._ "Heil's text stands out as being remarkably careful in its presentation and illuminating in its explanations—especially given its relatively short length when compared to the average logic textbook. It hits all of the necessary material that must be covered in an introductory deductive logic course, and then some. It also takes occasional excursions into side topics, successfully whetting the reader’s appetite for more advanced studies in logic. " The book is clearly written by an expert who has put in the effort for his readers, bothering at every step to see the point and then explain it clearly to his readers_. Heil has found some very clever, original ways to introduce, motivate, and otherwise teach this material. The author's own special expertise and perspective—especially when it comes to tying philosophy of mind, linguistics, and philosophy of language into the lessons of logic—make for a creative and fresh take on basic logic. With its unique presentation and illuminating explanations, this book comes about as close as a text can come to imitating the learning environment of an actual classroom. Indeed, working through its presentations carefully, the reader feels as though he or she has just attended an illuminating lecture on the relevant topics!" —Jonah Schupbach, University of Utah. (shrink)

"In his introduction to this most welcome republication (and second edition) of his logic text, Heil clarifies his aim in writing and revising this book: 'I believe that anyone unfamiliar with the subject who set out to learn formal logic could do so relying solely on [this] book. That, in any case, is what I set out to create in writing _An Introduction to First-Order Logic_.' Heil has certainly accomplished this with perhaps _the most explanatorily thorough and pedagogically (...) rich text I’ve personally come across_._ "Heil's text stands out as being remarkably careful in its presentation and illuminating in its explanations—especially given its relatively short length when compared to the average logic textbook. It hits all of the necessary material that must be covered in an introductory deductive logic course, and then some. It also takes occasional excursions into side topics, successfully whetting the reader’s appetite for more advanced studies in logic. " The book is clearly written by an expert who has put in the effort for his readers, bothering at every step to see the point and then explain it clearly to his readers_. Heil has found some very clever, original ways to introduce, motivate, and otherwise teach this material. The author's own special expertise and perspective—especially when it comes to tying philosophy of mind, linguistics, and philosophy of language into the lessons of logic—make for a creative and fresh take on basic logic. With its unique presentation and illuminating explanations, this book comes about as close as a text can come to imitating the learning environment of an actual classroom. Indeed, working through its presentations carefully, the reader feels as though he or she has just attended an illuminating lecture on the relevant topics!" —Jonah Schupbach, University of Utah. (shrink)

From a logical point of view, Stone duality for Boolean algebras relates theories in classical propositional logic and their collections of models. The theories can be seen as presentations of Boolean algebras, and the collections of models can be topologized in such a way that the theory can be recovered from its space of models. The situation can be cast as a formal duality relating two categories of syntax and semantics, mediated by homming into a common dualizing object, in this (...) case 2.In the present work, we generalize the entire arrangement from propositional to first-order logic, using a representation result of Butz and Moerdijk. Boolean algebras are replaced by Boolean categories presented by theories in first-order logic, and spaces of models are replaced by topological groupoids of models and their isomorphisms. A duality between the resulting categories of syntax and semantics, expressed primarily in the form of a contravariant adjunction, is established by homming into a common dualizing object, now Sets, regarded once as a boolean category, and once as a groupoid equipped with an intrinsic topology.The overall framework of our investigation is provided by topos theory. Direct proofs of the main results are given, but the specialist will recognize toposophical ideas in the background. Indeed, the duality between syntax and semantics is really a manifestation of that between algebra and geometry in the two directions of the geometric morphisms that lurk behind our formal theory. Along the way, we give an elementary proof of Butz and Moerdijkʼs result in logical terms. (shrink)

This paper is part of a general programme of developing and investigating particular first-order modal theories. In the paper, a modal theory of propositions is constructed under the assumption that there are genuinely singular propositions, ie. ones that contain individuals as constituents. Various results on decidability, axiomatizability and definability are established.

Dependence logic, introduced in Väänänen [11], cannot be axiomatized. However, first-order consequences of dependence logic sentences can be axiomatized, and this is what we shall do in this paper. We give an explicit axiomatization and prove the respective Completeness Theorem.

This paper begins the study of first-order functions, which are a generalization of truth-functions. The concepts of truth-table and systems of truth-functions, both introduced in propositional logic by Post, are also generalized and studied in the quantificational setting. The general facts about these concepts are given in the first five sections, and constitute a “general theory” of first-order functions. The central theme of this paper is the relation of definition among notions expressed by formulas of (...) first-order logic. We emphasize that logic is not concerned only with the consequence relation among notions expressed by formulas. It also attends to the relation of definition among notions, where a notion is defined from other notions. Sections 5 and 6 deal exclusively with the relation of definition among notions expressed by formulas of first-order logic. In these sections, we study the systems of first-order functions, which are the sets of first-order functions closed under definitions. Sections 7 and 8 are concerned with the relativization of first-order functions to a class of structures. The relativization to a class of structures is a fundamental operation which is used in order to relate the theory of first-order functions with set theory and first-order model theory, a subject which we have barely scratched the surface. The apparatus developed in this paper enables us to define what is a vehicle for the foundation of classical mathematics in set theory, and, in Sect. 8, we prove that first-order logic with one binary predicate variable is not a minimal vehicle for the foundation of classical mathematics in set theory. Sections 9 and 10 introduce further operations and ideals of first-order functions. Besides some results on the influence of the arguments of a first-order function, a result about definability is proved in Sect. 10.1. It is this theorem that provides necessary and sufficient conditions for a first-order function to be in a finitely generated ideal. In Sect. 11, this result is applied to the problem of predicate definability in classes of structures, the problem with which Beth’s theorem dealt in the case of elementary classes. (shrink)

We present a new proof of soundness/completeness of tableaux with respect to dialogical games in Classical First-Order Logic. As far as we know it is the first thorough result for dialogical games where finiteness of plays is guaranteed by means of what we call repetition ranks.

The paper studies first order extensions of classical systems of modal logic (see (Chellas, 1980, part III)). We focus on the role of the Barcan formulas. It is shown that these formulas correspond to fundamental properties of neighborhood frames. The results have interesting applications in epistemic logic. In particular we suggest that the proposed models can be used in order to study monadic operators of probability (Kyburg, 1990) and likelihood (Halpern-Rabin, 1987).

In this paper we introduce the notion of a first order topological structure, and consider various possible conditions on the complexity of the definable sets in such a structure, drawing several consequences thereof.Our aim is to develop, for a restricted class of unstable theories, results analogous to those for stable theories. The “material basis” for such an endeavor is the analogy between the field of real numbers and the field of complex numbers, the former being a “nicely behaved” (...) unstable structure and the latter the archetypal stable structure. In this sense we try here to situate our work ono-minimal structures [PS] in a general topological context. Note, however, that thep-adic numbers, and structures definable therein, will also fit into our analysis.In the remainder of this section we discuss several ways of studying topological structures model-theoretically. Eventually we fix on the notion of a structure in which the topology is “explicitly definable” in the sense of Flum and Ziegler [FZ]. In §2 we introduce the hypothesis that every definable set is a Boolean combination of definable open sets. In §3 we introduce a “dimension rank” on definable sets. In §4 we consider structures on which this rank is defined, and for which also every definable set has a finite number of definably connected definable components. We show that prime models over sets exist under such conditions. (shrink)

It is shown that a formula of modal propositional logic has precisely the same models as a sentence of the first-order language of a single dyadic predicate iff its class of models is closed under ultraproducts. as a corollary, any modal formula definable by a set of first-order conditions is always definable by a single such condition. these results are then used to show that the formula (lmp 'validates' mlp) is not first-order definable.

In the article we study the existence predicate \(\varepsilon\) in the context of semantics for first-order modal logic. For a formula \(\varphi\) we define \(\varphi^{\varepsilon}\) - the so called existence relativization. We point to a gap in the work of Fitting and Mendelsohn concerning the relationship between the truth of \(\varphi\) and \(\varphi^{\varepsilon}\) in classes of varying- and constant-domain models. We introduce operations on models which allow us to fill the gap and provide a more general perspective on (...) the issue. As a result we obtain a series of theorems describing the logical connection between the notion of truth of a formula with the existence predicate in constant-domain models and the notion of truth of a formula without the existence predicate in varying-domain models. (shrink)

For first order languages with no individual constants, empty structures and truth values (for sentences) in them are defined. The first order theories of the empty structures and of all structures (the empty ones included) are axiomatized with modus ponens as the only rule of inference. Compactness is proved and decidability is discussed. Furthermore, some well known theorems of model theory are reconsidered under this new situation. Finally, a word is said on other approaches to the (...) whole problem. (shrink)

Kolmogorov introduced an informal calculus of problems in an attempt to provide a classical semantics for intuitionistic logic. This was later formalised by Medvedev and Muchnik as what has come to be called the Medvedev and Muchnik lattices. However, they only formalised this for propositional logic, while Kolmogorov also discussed the universal quantifier. We extend the work of Medvedev to first-order logic, using the notion of a first-order hyperdoctrine from categorical logic, to a structure which we (...) will call the hyperdoctrine of mass problems. We study the intermediate logic that the hyperdoctrine of mass problems gives us, and we study the theories of subintervals of the hyperdoctrine of mass problems in an attempt to obtain an analogue of Skvortsova’s result that there is a factor of the Medvedev lattice characterising intuitionistic propositional logic. Finally, we consider Heyting arithmetic in the hyperdoctrine of mass problems and prove an analogue of Tennenbaum’s theorem on computable models of arithmetic. (shrink)

In this paper first order theories for nonmonotone inductive definitions are introduced, and a proof-theoretic analysis for such theories based on combined operator forms a la Richter with recursively inaccessible and Mahlo closure ordinals is given.

A first-order logic of belief with identity is proposed, primarily to give an account of possible de re contradictory beliefs, which sometimes occur as consequences of de dicto non-contradictory beliefs. A model has two separate, though interconnected domains: the domain of objects and the domain of appearances. The satisfaction of atomic formulas is defined by a particular S-accessibility relation between worlds. Identity is non-classical, and is conceived as an equivalence relation having the classical identity relation as a subset. (...) A tableau system with labels, signs, and suffixes is defined, extending the basic language $\mathscr{L}_{\mathbf{QB}}$ by quasiformulas (to express the denotations of predicates). The proposed logical system is paraconsistent since $\phi \wedge \neg\phi$ does not ``explode'' with arbitrary syntactic consequences. (shrink)

The relationship between formal and informal provability has been a significant subject of philosophical and mathematical investigation. Formal systems such as Gödel-Löb logic (GL) capture formal provability but do not validate the reflection schema—a principle stating that if a statement is provable, it must be true. This schema is intuitively valid for the informal notion of provability as understood and used in mathematical practice. Several logical systems have been developed to capture this informal notion of provability, including BAT, CABAT, and (...) T-BAT. However, a first-order version of T-BAT logic has not yet been developed. This paper aims to address this research gap by providing such an extension. (shrink)

We show how to interpret the language of first-order set theory in an elementary topos endowed with, as extra structure, a directed structural system of inclusions (dssi). As our main result, we obtain a complete axiomatization of the intuitionistic set theory validated by all such interpretations. Since every elementary topos is equivalent to one carrying a dssi, we thus obtain a first-order set theory whose associated categories of sets are exactly the elementary toposes. In addition, we (...) show that the full axiom of Separation is validated whenever the dssi is superdirected. This gives a uniform explanation for the known facts that cocomplete and realizability toposes provide models for Intuitionistic Zermelo—Fraenkel set theory (IZF). (shrink)