The Logic & Structure project is about the language of mathematical logic and how it can be of use in the visual arts. It involves a conversation between a mathematical logician and a group of artists. The project is ongoing, and this is a report on its first two phases. This text has two parts. The first, “Logic”, is a short introduction to certain aspects of logic, as it was presented to the participants. The second part, (...) “Structures”, describes some of the outcomes.The inspiration for the project comes from modern model theory whose advances revealed the extent to which formal methods may be helpful in describing and analysing mathematical structures. While the structures that are studied are often immensely complex, the formal language in which their properties can be expressed is simple. Its syntax is precisely defined and well understood, and this understanding often successfully guides us in our explorations of the rich world of mathematical objects. Our goal is to see the extent to which a similar approach could be of value when talking about works of art as structures. To this end, one could try to describe existing art objects in terms of suitably chosen formal languages, but we follow a reverse route. The language is described first, and the participating artists are asked to come up with artwork in which formal elements and their relations are chosen in advance, making it easier to identify those features of the created pieces that can be formally expressed. In other words, we are not thinking of applying formal methods to create art; rather we want to begin with samples that can serve as material for discussion. (shrink)

This article introduces, studies, and applies a new system of logic which is called ‘HYPE’. In HYPE, formulas are evaluated at states that may exhibit truth value gaps and truth value gluts. Simple and natural semantic rules for negation and the conditional operator are formulated based on an incompatibility relation and a partial fusion operation on states. The semantics is worked out in formal and philosophical detail, and a sound and complete axiomatization is provided both for the propositional and the (...) predicate logic of the system. The propositional logic of HYPE is shown to contain first-degree entailment, to have the Finite Model Property, to be decidable, to have the Disjunction Property, and to extend intuitionistic propositional logic conservatively when intuitionistic negation is defined appropriately by HYPE’s logical connectives. Furthermore, HYPE’s first-order logic is a conservative extension of intuitionistic logic with the Constant Domain Axiom, when intuitionistic negation is again defined appropriately. The system allows for simple model constructions and intuitive Euler-Venn-like diagrams, and its logical structure matches structures well-known from ordinary mathematics, such as from optimization theory, combinatorics, and graph theory. HYPE may also be used as a general logical framework in which different systems of logic can be studied, compared, and combined. In particular, HYPE is found to relate in interesting ways to classical logic and various systems of relevance and paraconsistent logic, many-valued logic, and truthmaker semantics. On the philosophical side, if used as a logic for theories of type-free truth, HYPE is shown to address semantic paradoxes such as the Liar Paradox by extending non-classical fixed-point interpretations of truth by a conditional as well-behaved as that of intuitionistic logic. Finally, HYPE may be used as a background system for modal operators that create hyperintensional contexts, though the details of this application need to be left to follow-up work. (shrink)

We extend natural deduction for first-order logic (FOL) by introducing diagrams as components of formal proofs. From the viewpoint of FOL, we regard a diagram as a deductively closed conjunction of certain FOL formulas. On the basis of this observation, we first investigate basic heterogeneous logic (HL) wherein heterogeneous inference rules are defined in the styles of conjunction introduction and elimination rules of FOL. By examining what is a detour in our heterogeneous proofs, we discuss that an (...) elimination-introduction pair of rules constitutes a redex in our HL, which is opposite the usual redex in FOL. In terms of the notion of a redex, we prove the normalization theorem for HL, and we give a characterization of the structure of heterogeneous proofs. Every normal proof in our HL consists of applications of introduction rules followed by applications of elimination rules, which is also opposite the usual form of normal proofs in FOL. Thereafter, we extend the basic HL by extending the heterogeneous rule in the style of general elimination rules to include a wider range of heterogeneous systems. (shrink)

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)

This textbook is a second edition of the successful, Mathematical Logic: On Numbers, Sets, Structures, and Symmetry. It retains the original two parts found in the first edition, while presenting new material in the form of an added third part to the textbook. The textbook offers a slow introduction to mathematical logic, and several basic concepts of model theory, such as first-order definability, types, symmetries, and elementary extensions. Part I, Logic Sets, and Numbers, shows how (...) mathematical logic is used to develop the number structures of classical mathematics. All necessary concepts are introduced exactly as they would be in a course in mathematical logic; but are accompanied by more extensive introductory remarks and examples to motivate formal developments. The second part, Relations, Structures, Geometry, introduces several basic concepts of model theory, such as first-order definability, types, symmetries, and elementary extensions, and shows how they are used to study and classify mathematical structures. The added Part III to the book is closer to what one finds in standard introductory mathematical textbooks. Definitions, theorems, and proofs that are introduced are still preceded by remarks that motivate the material, but the exposition is more formal, and includes more advanced topics. The focus is on the notion of countable categoricity, which analyzed in detail using examples from the first two parts of the book. This textbook is suitable for graduate students in mathematical logic and set theory and will also be of interest to mathematicians who know the technical aspects of the subject, but are not familiar with its history and philosophical background. (shrink)

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)

§1. Introduction. This paper deals with aspects of my doctoral dissertation which contributed to the early development of model theory. What was of use to later workers was less the results of my thesis, than the method by which I proved the completeness of first-order logic—a result established by Kurt Gödel in his doctoral thesis 18 years before.The ideas that fed my discovery of this proof were mostly those I found in the teachings and writings of Alonzo Church. (...) This may seem curious, as his work in logic, and his teaching, gave great emphasis to the constructive character of mathematical logic, while the model theory to which I contributed is filled with theorems about very large classes of mathematical structures, whose proofs often by-pass constructive methods.Another curious thing about my discovery of a new proof of Gödel's completeness theorem, is that it arrived in the midst of my efforts to prove an entirely different result. Such “accidental” discoveries arise in many parts of scientific work. Perhaps there are regularities in the conditions under which such “accidents” occur which would interest some historians, so I shall try to describe in some detail the accident which befell me.A mathematical discovery is an idea, or a complex of ideas, which have been found and set forth under certain circumstances. The process of discovery consists in selecting certain input ideas and somehow combining and transforming them to produce the new output ideas. The process that produces a particular discovery may thus be represented by a diagram such as one sees in many parts of science; a “black box” with lines coming in from the left to represent the input ideas, and lines going out to the right representing the output. To describe that discovery one must explain what occurs inside the box, i.e., how the outputs were obtained from the inputs. (shrink)

We start with a simple proof of Leivant's normal form theorem for ∑11 formulas over finite successor structures. Then we use that normal form to prove the following:1. over all finite structures, every ∑21 formula is equivalent to a ∑21 formula whose first-order part is a Boolean combination of existential formulas, and2. over finite successor structures, the Kolaitis-Thakur hierarchy of minimization problems collapses completely and the Kolaitis-Thakur hierarchy of maximization problems collapses partially.The normal form theorem for ∑21 (...) fails if ∑21 is replaced with ∑11 or if infinite structures are allowed. (shrink)

We present an adaptation of continuous first order logic to unbounded metric structures. This has the advantage of being closer in spirit to C. Ward Henson's logic for Banach space structures than the unit ball approach, as well as of applying in situations where the unit ball approach does not apply. We also introduce the process of single point emph{emboundment}, allowing to bring unbounded structures back into the setting of bounded continuous first order logic. Together with (...) results from cite{BenYaacov:Perturbations} regarding perturbations of bounded metric structures, we prove a Ryll-Nardzewski style characterisation of theories of Banach spaces which are separably categorical up to small perturbation of the norm. This last result is motivated by an unpublished result of Henson. (shrink)

The previous Part I of the paper discusses the option of the Gödel incompleteness statement (1931: whether “Satz VI” or “Satz X”) to be an axiom due to the pair of the axiom of induction in arithmetic and the axiom of infinity in set theory after interpreting them as logical negations to each other. The present Part II considers the previous Gödel’s paper (1930) (and more precisely, the negation of “Satz VII”, or “the completeness theorem”) as a necessary condition for (...) granting the Gödel incompleteness statement to be a theorem just as the statement itself, to be an axiom. Then, the “completeness paper” can be interpreted as relevant to Hilbert mathematics, according to which mathematics and reality as well as arithmetic and set theory are rather entangled or complementary rather than mathematics to obey reality able only to create models of the latter. According to that, both papers (1930; 1931) can be seen as advocating Russell’s logicism or the intensional propositional logic versus both extensional arithmetic and set theory. Reconstructing history of philosophy, Aristotle’s logic and doctrine can be opposed to those of Plato or the pre-Socratic schools as establishing ontology or intensionality versus extensionality. Husserl’s phenomenology can be analogically realized including and particularly as philosophy of mathematics. One can identify propositional logic and set theory by virtue of Gödel’s completeness theorem (1930: “Satz VII”) and even both and arithmetic in the sense of the “compactness theorem” (1930: “Satz X”) therefore opposing the latter to the “incompleteness paper” (1931). An approach identifying homomorphically propositional logic and set theory as the same structure of Boolean algebra, and arithmetic as the “half” of it in a rigorous construction involving information and its unit of a bit. Propositional logic and set theory are correspondingly identified as the shared zero-order logic of the class of all first-order logics and the class at issue correspondingly. Then, quantum mechanics does not need any quantum logics, but only the relation of propositional logic, set theory, arithmetic, and information: rather a change of the attitude into more mathematical, philosophical, and speculative than physical, empirical and experimental. Hilbert’s epsilon calculus can be situated in the same framework of the relation of propositional logic and the class of all mathematical theories. The horizon of Part III investigating Hilbert mathematics (i.e. according to the Pythagorean viewpoint about the world as mathematical) versus Gödel mathematics (i.e. the usual understanding of mathematics as all mathematical models of the world external to it) is outlined. (shrink)

This is the first comprehensive textbook on higher order logic that is written specifically to introduce the subject matter to graduate students in philosophy. The book covers both the formal aspects of higher-order languages -- their model theory and proof theory, the theory of λ-abstraction and its generalizations -- and their philosophical applications, especially to the topics of modality and propositional granularity. The book has a strong focus on non-extensional higher-order logics, making it more appropriate for (...) foundational metaphysics than other introductions to the subject from computer science, mathematics, and linguistics. A Philosophical Introduction to Higher Order Logics assumes only that readers have a basic knowledge of first-order logic. With an emphasis on exercises, it can be used as a textbook though is also ideal for self-study. Author Andrew Bacon organizes the book's 18 chapters around four main parts: I. Typed Language II. Higher Order Languages III. General Higher-Order Languages IV. Higher-Order Model Theory In addition, two appendices cover the Curry-Howard isomorphism and its applications for modeling propositional structure. Each chapter includes exercises that move from easier to more difficult, strategically placed throughout the chapter, and concludes with an annotated suggested reading list providing graduate students with most valuable additional resources. Key Features Is the first comprehensive introduction to higher-order logic as a grounding for addressing problems in metaphysics Introduces the basic formal tools that are needed to theorize in, and model, higher order languages Offers an abundance of: - Simple exercises throughout the book, serving as comprehension checks on basic concepts and definitions - More difficult exercises designed to facilitate long-term learning Contains annotated sections on further reading, pointing the reader to related literature, learning resources, and historical context. (shrink)

We introduce a general notion of semantic structure for first-order theories, covering a variety of constructions such as Tarski and Kripke semantics, and prove that, over Zermelo–Fraenkel set theory, the completeness of such semantics is equivalent to the Boolean prime ideal theorem. Using a result of McCarty, we conclude that the completeness of Kripke semantics is equivalent, over intuitionistic Zermelo–Fraenkel set theory, to the Law of Excluded Middle plus BPI. Along the way, we also prove the equivalence, (...) over ZF, between BPI and the completeness theorem for Kripke semantics for both first-order and propositional theories. (shrink)

A Dedekind Algebra is an ordered pair (B,h) where B is a non-empty set and h is an injective unary function on B. Each Dedekind algebra can be decomposed into a family of disjoint, countable subalgebras called configurations of the Dedekind algebra. There are N0 isomorphism types of configurations. Each Dedekind algebra is associated with a cardinal-valued function on omega called its configuration signature. The configuration signature of a Dedekind algebra counts the number of configurations in the decomposition of the (...) algebra in each isomorphism type.The configuration signature of a Dedekind algebra encodes the structure of that algebra in the sense that two Dedekind algebras are isomorphic iff their configuration signatures are identical. Configuration signatures are used to establish various results in the first-order model theory of Dedekind algebras. These include categoricity results for the first-order theories of Dedekind algebras and existence and uniqueness results for homogeneous, universal and saturated Dedekind algebras. Fundamental to these results is a condition on configuration signatures that is necessary and sufficient for elementary equivalence. (shrink)

This paper is a contribution to graded model theory, in the context of mathematical fuzzy logic. We study characterizations of classes of graded structures in terms of the syntactic form of their first-order axiomatization. We focus on classes given by universal and universal-existential sentences. In particular, we prove two amalgamation results using the technique of diagrams in the setting of structures valued on a finite MTL-algebra, from which analogues of the Łoś–Tarski and the Chang–Łoś–Suszko preservation theorems follow.

First-order logic with dependent sorts, such as Makkai's first-order logic with dependent sorts (FOLDS), or Aczel's and Belo's dependently typed (intuitionistic) first-order logic (DFOL), may be regarded as logic enriched dependent type theories. Categories with families (cwfs) is an established semantical structure for dependent type theories, such as Martin-Löf type theory. We introduce in this article a notion of hyperdoctrine over a cwf, and show how FOLDS and DFOL fit in this semantical framework. A (...) soundness and completeness theorem is proved for DFOL. The semantics is functorial in the sense of Lawvere, and uses a dependent version of the Lindenbaum-Tarski algebra for a DFOL theory. Agreement with standard first-order semantics is established. Applications of DFOL to constructive mathematics and categorical foundations are given. A key feature is a local propositions-as-types principle. (shrink)

_An enlightening introduction to the study of logic: its history, philosophical foundations, and formal structures_ _Logic: Inquiry, Argument, and Order_ is the first book of its kind to frame the study of introductory logic in terms of problems connected to wider issues of knowledge and judgment that arise in the context of racial, cultural, and religious diversity. With its accessible style and integration of philosophical inquiry and real-life concerns, this book offers a novel approach to the theory of logic (...) and its relevance to questions of meaning and value that arise in the world around us. The book poses four problems for logic: Is logic separate from experience? Does logic require dualisms? Can logic reconcile opposed ways of understanding the world? And when things are divided, does the boundary have a logic? The author begins the exploration of these questions with a discussion of the process of analyzing and constructing arguments. Using the logical theories of C. S. Peirce, John Dewey, and Josiah Royce to frame the investigation, subsequent chapters outline the process of inquiry, the concept of communicative action, the nature of validity, categorical reasoning through the theory of the syllogism, and inductive reasoning and probability. The book concludes with a presentation of modal logic, propositional logic, and quantification. Logic is presented as emerging from the activities of inquiry and communication, allowing readers to understand even the most difficult aspects of formal logic as straightforward developments of the process of anticipating and taking action. Numerous practice problems use arguments related to issues of diversity and social theory, and the book introduces methods of proving validity that include Venn diagrams, natural deduction, and the method of tableaux. _Logic: Inquiry, Argument, and Order_ is an ideal book for courses on philosophical methods and critical reasoning at the upper-undergraduate and graduate levels. It is also an insightful reference for anyone who would like to explore a cross-cultural approach to the topic of logic. (shrink)

We prove that the first-order logic of CZF is intuitionistic first-order logic. To do so, we introduce a new model of transfinite computation (Set Register Machines) and combine the resulting notion of realisability with Beth semantics. On the way, we also show that the propositional admissible rules of CZF are exactly those of intuitionistic propositional logic.

This is a remarkable new French language introduction to elementary logical methods. Although designed primarily for computer and information specialists, it is also sure to interest philosophers and logicians because of its diversity of subjects, emphasis on graphic calculation techniques, and extensive historical background. The book is intelligently divided into nine main chapters with detailed descriptive subsections. It begins with the most fundamental principles of Aristotelian syllogistic and Boolean algebra, working through the essentials of Frege's predicate calculus and Gödel's (...) consistency-completeness metaproofs before systematically articulating standard propositional and predicate logics, interestingly, from synthetic and then analytic perspectives. This leads to a largely informal exposition of Tarski-style model set theoretical semantics, and the modern limiting metatheoretical results underlying what the authors call the "crisis" in the foundations of mathematical logic. Here are included such typical and more unusual topics as Herbrand models, König's Lemma, Herbrand's Theorem, Post machines, Floyd's Theorem, and Church's Theorem. The volume culminates in an expansive treatment of first order theories, including theories of order and models, and decidability. The exposition is somewhat rigorous, but should not be excessively demanding for nonprofessionals interested in the important implications of logic for philosophy, foundations of mathematics, and informatique. Among the book's virtues must be mentioned its profuse illustration of so many different graphic methods in mathematical logic, including Venn diagrams, the square of opposition, Smullyan truth trees, Wallen's reduction technique, Beth's and Hintikka's semantic tableaux method, and several styles of axiomatic and natural deduction. The work is certain to be a valuable resource for French readers in need of a lucid, comprehensive guide to the history and practical techniques of logic in its elementary applications to the philosophy of mathematics and information sciences.--Dale Jacquette, The Pennsylvania State University. (shrink)

Topics covered in Discrete Mathematics have become essential tools in many areas of studies in recent years. This is primarily due to the revolution in technology, communications, and cyber security. The book treats major themes in a typical introductory modern Discrete Mathematics course: Propositional and predicate logic, proof techniques, set theory (including Boolean algebra, functions and relations), introduction to number theory, combinatorics and graph theory. An accessible, precise, and comprehensive approach is adopted in the treatment of each topic. The (...) ability of abstract thinking and the art of writing valid arguments are emphasized through detailed proof of (almost) every result. Developing the ability to think abstractly and roguishly is key in any areas of science, information technology and engineering. Every result presented in the book is followed by examples and applications to consolidate its comprehension. The hope is that the reader ends up developing both the abstract reasoning as well as acquiring practical skills. All efforts are made to write the book at a level accessible to first-year students and to present each topic in a way that facilitates self-directed learning. Each chapter starts with basic concepts of the subject at hand and progresses gradually to cover more ground on the subject. Chapters are divided into sections and subsections to facilitate readings. Each section ends with its own carefully chosen set of practice exercises to reenforce comprehension and to challenge and stimulate readers. As an introduction to Discrete Mathematics, the book is written with the smallest set of prerequisites possible. Familiarity with basic mathematical concepts (usually acquired in high school) is sufficient for most chapters. However, some mathematical maturity comes in handy to grasp some harder concepts presented in the book. (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)

This paperback is a programed text designed for teaching introductory logic, either in conjunction with a standard text based upon traditional logic or as a do-it-yourself supplement for students taking courses stressing symbolic logic. The student learns logical theory by answering a variety of short answer, objective type exercises. The correct answer is given directly below each question or exercise, and the student is required to cover the answer while working the exercise; the purpose of this immediate access to the (...) answer is to enable the student to determine quickly whether or not he comprehends the material. The content of the book concentrates primarily upon categorical statements, presenting both the existential and hypothetical interpretations of the square of opposition, but unfortunately continues to promulgate the historically inaccurate terminology of "Aristotelian" and "Boolean." [Categorical statements were first expressed as existential statements by Franz Brentano in 1874.] Categorical statements not in standard form are standardized, e.g., "No roaches feel despair" is standardized by being rewritten as "No roaches are entities who feel despair." In addition to considering the logical relations of opposition with respect to A, E, I, O statements, these same relations are extended to non-categorical statements, e.g., "George Washington did not die in Europe" and "George Washington did not die in Asia" are subcontraries, while "There is philosophical activity on Venus" and "There is philosophical activity in the universe" are alterns. Determining validity of syllogisms is based upon the distribution of terms, and also by the use of Venn diagrams. The traditional figures and moods of the syllogism are ignored, as is the distinction between major and minor terms, with these latter two being lumped together as end terms. Immediate inferences and non-syllogistic arguments are treated by Venn diagrams. One-, two-, three- and four-term Venn diagrams are utilized throughout a substantial part of the book.--T. G. N. (shrink)

The study of structure systems, an abstraction of the concept of first-order structures, is continued. Structure systems have algebraic systems as their algebraic reducts and their relational component consists of a collection of relation systems on the underlying functors. An analog of the expansion of a first-order structure by constants is presented. Furthermore, analogs of the Diagram Lemma and the Reduction Operator Lemma from the theory of equality-free first-order structures are provided in the framework (...) of structure systems. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

Classical first-order logic \ is commonly used to study logical connections between statements, that is sentences that in every context have an associated truth-value. Inquisitive first-order logic \ is a conservative extension of \ which captures not only connections between statements, but also between questions. In this paper we prove the disjunction and existence properties for \ relative to inquisitive disjunction Open image in new window and inquisitive existential quantifier \. Moreover we extend these results to (...) several families of theories, among which the one in the language of \. To this end, we initiate a model-theoretic approach to the study of \. In particular, we develop a toolkit of basic constructions in order to transform and combine models of \. (shrink)

In this paper we argue that there were several currents, ideas and problems in 19th-century logic that motivated John Venn to develop his famous logic diagrams. To this end, we first examine the problem of uncertainty or over-specification in syllogistic that became obvious in Euler diagrams. In the 19th century, numerous logicians tried to solve this problem. The most famous was the attempt to introduce dashed circles into Euler diagrams. The solution that John Venn developed for this (...) problem, however, came from a completely different area of logic: instead of orienting to syllogistic like Euler diagrams, Venn applied Boolean algebra to improve visual reasoning. Venn’s contribution to solving the problem of elimination also played an important role. The result of this development is still known today as the ‘Venn Diagram’. (shrink)

Inquisitive first-order logic, InqBQ, is a system which extends classical first-order logic with formulas expressing questions. From a mathematical point of view, formulas in this logic express properties of sets of relational structures. This paper makes two contributions to the study of this logic. First, we describe an Ehrenfeucht–Fraïssé game for InqBQ and show that it characterizes the distinguishing power of the logic. Second, we use the game to study cardinality quantifiers in the inquisitive (...) setting. That is, we study what statements and questions can be expressed in InqBQ about the number of individuals satisfying a given predicate. As special cases, we show that several variants of the question how many individuals satisfy α(x) are not expressible in InqBQ, both in the general case and in restriction to finite models. (shrink)

The Feferman–Vaught theorem provides a way of evaluating a first order sentence \(\varphi \) on a disjoint union of structures by producing a decomposition of \(\varphi \) into sentences which can be evaluated on the individual structures and the results of these evaluations combined using a propositional formula. This decomposition can in general be non-elementarily larger than \(\varphi \). We introduce a “tree” generalization of the prenex normal form (PNF) for first order sentences, and show that (...) for an input sentence in this form having a fixed number of quantifier alternations, a Feferman–Vaught decomposition can be obtained in time elementary in the size of the sentence. The sentences in the decomposition are also in tree PNF, and further have the same number of quantifier alternations and the same quantifier rank as the input sentence. We extend this result by considering binary operations other than disjoint union, in particular sum-like operations such as join, ordered sum and NLC-sum, that are definable using quantifier-free translation schemes. (shrink)

The Logical Reasoning with Diagrams and Sentences courseware package teaches the principles of analytical reasoning and proof construction using a carefully crafted combination of textbook, desktop, and online materials. This package is sure to be an essential resource in a range of courses incorporating logical reasoning, including formal linguistics, philosophy, mathematics, and computer science. Unlike traditional formal treatments of reasoning, this package uses both graphical and sentential representations to reflect common situations in everyday reasoning where information is expressed in many (...) forms, such as finding your way to a location using a map and an address. It also teaches students how to construct and check the logical validity of a variety of proofs--of consequence and non-consequence, consistency and inconsistency, and independence--using an intuitive proof system which extends standard proof treatments with sentential, graphical, and heterogeneous inference rules, allowing students to focus on proof content rather than syntactic structure. Building upon the widely used Tarski's World and Language, Proof and Logic courseware packages, Logical Reasoning with Diagrams and Sentences contains more than three hundred exercises, most of which can be assessed by the Grade Grinder online assessment service; is supported by an extensive website through which students and instructors can access online video lectures by the authors; and allows instructors to create their own exercises and assess their students' work. Logical Reasoning with Diagrams and Sentences is an expanded revision of the Hyperproof courseware package. (shrink)

Combinator logics are a broad family of substructual logics that are formed by extending the basic relevant logic B with axioms that correspond closely to the reduction rules of proper combinators in combinatory logic. In the Routley-Meyer relational semantics for relevant logic each such combinator logic is characterized by the class of frames that meet a first-order condition that also directly corresponds to the same combinator's reduction rule. A second family of logics is also introduced that extends B (...) with the addition of propositional constants that correspond to combinators. These are characterized by relational frames that meet first-order conditions that reflect the structures of the combinators themselves. (shrink)

The general methodology of "algebraizing" logics is used here for combining different logics. The combination of logics is represented as taking the colimit of the constituent logics in the category of algebraizable logics. The cocompleteness of this category as well as its isomorphism to the corresponding category of certain first-order theories are proved.

This paper introduces the logic _Q__L__E__T_ _F_, a quantified extension of the logic of evidence and truth _L__E__T_ _F_, together with a corresponding sound and complete first-order non-deterministic valuation semantics. _L__E__T_ _F_ is a paraconsistent and paracomplete sentential logic that extends the logic of first-degree entailment (_FDE_) with a classicality operator ∘ and a non-classicality operator ∙, dual to each other: while ∘_A_ entails that _A_ behaves classically, ∙_A_ follows from _A_’s violating some classically valid inferences. The (...) semantics of _Q__L__E__T_ _F_ combines structures that interpret negated predicates in terms of anti-extensions with first-order non-deterministic valuations, and completeness is obtained through a generalization of Henkin’s method. By providing sound and complete semantics for first-order extensions of _FDE_, _K3_, and _LP_, we show how these tools, which we call here the method of _anti-extensions + valuations_, can be naturally applied to a number of non-classical logics. (shrink)

We prove that if M is any model of a trivial, weakly minimal theory, then the elementary diagram T(M) eliminates quantifiers down to Boolean combinations of certain existential formulas.

The idea that the world is made of particles — little discrete, interacting objects that compose the material bodies of everyday experience — is a durable one. Following the advent of quantum theory, the idea was revised but not abandoned. It remains manifest in the explanatory language of physics, chemistry, and molecular biology. Aside from its durability, there is good reason for the scientific realist to embrace the particle interpretation: such a view can account for the prominent epistemic fact that (...) only limited knowledge of a portion of the material universe is needed in order to make reliable predictions about that portion. Thus, particle interpretations can support an abductive argument from the epistemic facts in favor of a realist reading of physical theory. However, any particle interpretation with this property is untenable. The empirical adequacy of modern particle theories requires adoption of a postulate known as permutation invariance — the claim that interchanging the role of two particles of the same kind in a dynamical state description results in a description of the identical state. It is the central claim of this essay that PI is incompatible with any particle interpretation strong enough to account for the epistemic facts. This incompatibility extends across all physical theories. To frame and motivate the inconsistency argument, I begin by fixing the relevant notion of particle. To single out those accounts of greatest appeal to the realist, I develop the logically weakest particle ontology that entails the epistemic fact that the world is piecewise predictable, an ontology I call ‘minimal atomism’. The entire series of scientific conceptions of the particle, from Newton’s mechanically interacting corpuscles to the ‘centers of force’ in classical field theories, all comport with MA. As long as PI is left out, even quantum mechanics can be viewed this way. To assess the impact of PI on this picture, I present a framework for rigorously connecting interpretations to physical theories. In particular, I represent MA as a set of formal conditions on the models of physical theories, the mathematical structures taken to represent states of the world. I also formulate PI — originally introduced as a postulate of non-relativistic quantum mechanics — in theory independent terms. With all of these pieces in hand, I am then able to present a proof of the inconsistency of PI and MA. In the second part of the essay, I survey responses to the inconsistency result open to the scientific realist. The two most plausible approaches involve abandoning particles in one way or another. The first alternative interpretation considered takes the property bearing objects of the world to be regions of space rather than particles. In this view, the properties once attributed to particles in quantum states are attributed instead to one or more regions of space. PI no longer obtains in this case, at least not as a statement about the permutation symmetry of property bearers. Rather, the new interpretation naturally imposes an analogous constraint on quantum states. The second major approach to evading the inconsistency result is to dispense with objects altogether. This is the recommendation of so-called ‘Ontic Structural Realism’. The central OSR thesis is that structure rather than entities are the basic ontological components of the world. OSR is intended to embrace the ‘miracle’ argument in favor of scientific realism while avoiding the pessimistic meta-induction. I demonstrate that one principal motivation for OSR based on the under-determination of interpretations in QM is actually dissolved by the incompatibility result. At the same time, I suggest reasons to think that OSR fares no better with respect to the pessimistic meta-induction than traditional realism does. Thus, while PI and MA may be incompatible, object ontologies remain the best option for the realist. (shrink)

© 2018, Springer International Publishing AG, part of Springer Nature. Aristotelian diagrams are used extensively in contemporary research in artificial intelligence. The present paper investigates the geometric and cognitive differences between two types of Aristotelian diagrams for the Boolean algebra B4. Within the class of 3D visualizations, the main geometric distinction is that between the cube-based diagrams and the tetrahedron-based diagrams. Geometric properties such as collinearity, central symmetry and distance are examined from a cognitive perspective, focusing on diagram design (...) principles such as congruence/isomorphism and apprehension. The cognitive effectiveness of the different visualizations is compared for the representation of implication versus opposition relations, and for subdiagram embeddings. (shrink)

This paper provides finitary jointly necessary and sufficient acceptance and rejection conditions for the logical constants of a first order quantificational language. By introducing the notion of making an assignment as a distinct object level practice—something you do with a sentence—(as opposed to a meta-level semantic notion) and combining this with the practice of (hypothetical and categorical) acceptance and rejection and the practice of making suppositions one gains a structure that is sufficiently rich to fully characterize the class (...) of classical first order theories. The analysis thus provides a way of characterizing classical first order quantification by expressivist means. (shrink)

Boolean-valued models generalize classical two-valued models by allowing arbitrary complete Boolean algebras as value ranges. The goal of my dissertation is to study Boolean-valued models and explore their philosophical and mathematical applications.In Chapter 1, I build a robust theory of first-order Boolean-valued models that parallels the existing theory of two-valued models. I develop essential model-theoretic notions like “Boolean-valuation,” “diagram,” and “elementary diagram,” and prove a series of theorems on Boolean-valued models, including (...) the (strengthened) Soundness and Completeness Theorem, the Löwenheim–Skolem Theorems, the Elementary Chain Theorem, and many more.Chapter 2 gives an example of a philosophical application of Boolean-valued models. I apply Boolean-valued models to the language of mereology to model indeterminacy in the parthood relation. I argue that Boolean-valued semantics is the best degree-theoretic semantics for the language of mereology. In particular, it trumps the well-known alternative—fuzzy-valued semantics. I also show that, contrary to what many have argued, indeterminacy in parthood entails neither indeterminacy in existence nor indeterminacy in identity, though being compatible with both.Chapter 3 (joint work with Bokai Yao) gives an example of a mathematical application of Boolean-valued models. Scott and Solovay famously used Boolean-valued models on set theory to obtain relative consistency results. In Chapter 3, I investigate two ways of extending the Scott–Solovay construction to set theory with urelements. I argue that the standard way of extending the construction faces a serious problem, and offer a new way that is free from the problem.Abstract prepared by Xinhe Wu.E-mail: [email protected]. (shrink)

We consider the theory Thprin of Boolean algebras with a principal ideal, the theory Thmax of Boolean algebras with a maximal ideal, the theory Thac of atomic Boolean algebras with an ideal where the supremum of the ideal exists, and the theory Thsa of atomless Boolean algebras with an ideal where the supremum of the ideal exists. First, we find elementary invariants for Thprin and Thsa. If T is a theory in a first (...) class='Hi'>order language and α is a linear order with least element, then we let Sentalg be the Lindenbaum-Tarski algebra with respect to T, and we let intalg be the interval algebra of α. Using rank diagrams, we show that Sentalg ⋍ intalg, Sentalg ⋍ intalg ⋍ Sentalg, and Sentalg ⋍ intalg. For Thmax and Thac we use Ershov's elementary invariants of these theories. We also show that the algebra of formulas of the theory Tx of Boolean algebras with finitely many ideals is atomic. (shrink)

This article studies the mathematical properties of two systems that model Aristotle's original syllogistic and the relationship obtaining between them. These systems are Corcoran's natural deduction syllogistic and ?ukasiewicz's axiomatization of the syllogistic. We show that by translating the former into a first-order theory, which we call T RD, we can establish a precise relationship between the two systems. We prove within the framework of first-order logic a number of logical properties about T RD that (...) bear upon the same properties of the natural deduction counterpart ? that is, Corcoran's system. Moreover, the first-order logic framework that we work with allows us to understand how complicated the semantics of the syllogistic is in providing us with examples of bizarre, unexpected interpretations of the syllogistic rules. Finally, we provide a first attempt at finding the structure of that semantics, reducing the search to the characterization of the class of models of T RD. (shrink)

We give a construction assigning classes of Boolean algebras to first-order theories; several classes of Boolean algebras considered previously in the literature can be thus obtained. In particular it turns out that the class of semigroup algebras can be defined in this way, in fact by a Horn theory, and it is the largest class of Boolean algebras defined by a Horn theory.

What good is logic? -- Seventeen ways this book is different -- The two logics -- All of logic in two pages : an overview -- The three acts of the mind -- I. The first act of the mind : understanding -- Understanding : the thing that distinguishes man from both beast and computer -- Concepts, terms and words -- The problem of universals -- The comprehension and extension of terms -- II. Terms -- Classifying terms -- Categories (...) -- Predicables -- Division -- III. Material fallacies -- Fallacies of language -- Fallacies of diversion -- Fallacies of oversimplification -- Fallacies of argumentation -- Inductive fallacies -- Procedural fallacies -- Metaphysical fallacies -- Short story : love is a fallacy -- IV. Definition -- The nature of definition -- The rules of definition -- The kinds of definition -- The limits of definition -- V. Second act of the mind : judgment -- Judgments, propositions, and sentences -- What is truth? -- The four kinds of categorical propositions -- Logical form -- Euler's circles -- Tricky propositions -- The distribution of terms -- VI. Changing propositions -- Immediate inference -- Conversion -- Obversion -- Contraposition -- VII. Contradiction -- What is contradiction? -- The square of opposition -- Existential import -- Tricky propositions on the square -- Some practical uses of the square of opposition -- VIII. The third act of the mind : reasoning -- What does reason mean? -- The ultimate foundations of the syllogism -- How to detect arguments -- Arguments vs. explanations -- Truth and validity -- IX. Different kinds of arguments -- Three meanings of because -- The four causes -- A classification of arguments -- Simple argument maps -- Deductive and inductive arguments -- Combining deduction and induction : socratic method -- X. Syllogisms -- The structure and strategy of the syllogism -- The skeptics objection to the syllogism -- The empiricist's objection to the syllogism -- Demonstrative syllogisms -- How to construct convincing syllogisms -- XI. Checking syllogisms for validity -- By Euler's circles -- By Aristotle's six rules -- Barbara Celarent : mood and figure -- Venn diagrams -- XII. More difficult syllogisms -- Enthymemes : abbreviated syllogisms -- Sorites : chain syllogisms -- Epicheiremas : multiple syllogisms -- Complex argument maps -- XIII. Compound syllogisms -- Hypothetical syllogisms -- Reductio ad absurdum arguments -- The practical syllogism : arguing about means and ends -- Disjunctive syllogisms -- Conjunctive syllogisms -- Dilemmas -- XIV. Induction -- What is induction? -- Generalization -- Causal induction : Mill's methods -- Scientific hypotheses -- Statistical probability -- Arguments from analogy -- A fortiori and a minore arguments -- XV. Some practical applications of logic -- How to write a logical essay -- How to write a socratic dialogue -- How to have a socratic debate -- How to use socratic method on difficult people -- How to read a book socratically -- XVI. Some philosophical applications of logic -- Logic and theology -- Logic and metaphysics -- Logic and cosmology -- Logic and philosophical anthropology -- Logic and epistemology -- Logic and ethics. (shrink)

Hyperproof is a system for learning the principles of analytical reasoning and proof construction, consisting of a text and a Macintosh software program. Unlike traditional treatments of first-order logic, Hyperproof combines graphical and sentential information, presenting a set of logical rules for integrating these different forms of information. This strategy allows students to focus on the information content of proofs, rather than the syntactic structure of sentences. Using Hyperproof the student learns to construct proofs of both consequence and (...) nonconsequence using an intuitive proof system that extends the standard set of sentential rules to incorporate information represented graphically. Hyperproof is compatible with various natural-deduction-style proof systems, including the system used in the authors' Language of First-Order Logic. (shrink)

Intuitionistic epistemic logic by Artemov and Protopopescu (Rev Symb Log 9:266–298, 2016) accepts the axiom “if A, then A is known” (written $$A \supset K A$$ ) in terms of the Brouwer–Heyting–Kolmogorov interpretation. There are two variants of intuitionistic epistemic logic: one with the axiom “ $$KA \supset \lnot \lnot A$$ ” and one without it. The former is called $$\textbf{IEL}$$, and the latter is called $$\textbf{IEL}^{-}$$. The aim of this paper is to study first-order expansions (with equality (...) and function symbols) of these two intuitionistic epistemic logics. We define Hilbert systems with additional axioms called geometric axioms and sequent calculi with the corresponding rules to geometric axioms and prove that they are sound and complete for the intended semantics. We also prove the cut-elimination theorems for both sequent calculi. As a consequence, the disjunction property and existence property are established for the sequent calculi without geometric implications. Finally, we establish that our sequent calculi can also be formulated with admissible structural rules (i.e., in terms of a G3-style sequent calculus). (shrink)

In this paper the class of Fidel-structures for the paraconsistent logic mbC is studied from the point of view of Model Theory and Category Theory. The basic point is that Fidel-structures for mbC (or mbC-structures) can be seen as first-order structures over the signature of Boolean algebras expanded by two binary predicate symbols N (for negation) and O (for the consistency connective) satisfying certain Horn sentences. This perspective allows us to consider notions and results from Model Theory (...) in order to analyze the class of mbC-structures. Thus, substructures, union of chains, direct products, direct limits, congruences and quotient structures can be analyzed under this perspective. In particular, a Birkhoff-like representation theorem for mbC-structures as subdirect poducts in terms of subdirectly irreducible mbC-structures is obtained by adapting a general result for first-order structures due to Caicedo. Moreover, a characterization of all the subdirectly irreducible mbC-structures is also given. An alternative decomposition theorem is obtained by using the notions of weak substructure and weak isomorphism considered by Fidel for Cn-structures. (shrink)

Elementary set theory accustoms the students to mathematical abstraction, includes the standard constructions of relations, functions, and orderings, and leads to a discussion of the various orders of infinity. The material on logic covers not only the standard statement logic and first-order predicate logic but includes an introduction to formal systems, axiomatization, and model theory. The section on algebra is presented with an emphasis on lattices as well as Boolean and Heyting algebras. Background for recent research (...) in natural language semantics includes sections on lambda-abstraction and generalized quantifiers. Chapters on automata theory and formal languages contain a discussion of languages between context-free and context-sensitive and form the background for much current work in syntactic theory and computational linguistics. The many exercises not only reinforce basic skills but offer an entry to linguistic applications of mathematical concepts. For upper-level undergraduate students and graduate students in theoretical linguistics, computer-science students with interests in computational linguistics, logic programming and artificial intelligence, mathematicians and logicians with interests in linguistics and the semantics of natural language. (shrink)

We define the notion of a combinatorics of a first order structure, and a relation of covering between first order structures and propositional proof systems. Namely, a first order structure M combinatorially satisfies an L-sentence Φ iff Φ holds in all L-structures definable in M. The combinatorics Comb(M) of M is the set of all sentences combinatorially satisfied in M. Structure M covers a propositional proof system P iff M combinatorially satisfies all Φ for (...) which the associated sequence of propositional formulas 〈Φ〉 n , encoding that Φ holds in L-structures of size n, have polynomial size P-proofs. That is, Comb(M) contains all Φ feasibly verifiable in P. Finding M that covers P but does not combinatorially satisfy Φ thus gives a super polynomial lower bound for the size of P-proofs of 〈Φ〉 n . We show that any proof system admits a class of structures covering it; these structures are expansions of models of bounded arithmetic. We also give, using structures covering proof systems R * (log) and PC, new lower bounds for these systems that are not apparently amenable to other known methods. We define new type of propositional proof systems based on a combinatorics of (a class of) structures. (shrink)

This book offers a state-of-the-art introduction to the basic techniques and results of neighborhood semantics for modal logic. In addition to presenting the relevant technical background, it highlights both the pitfalls and potential uses of neighborhood models – an interesting class of mathematical structures that were originally introduced to provide a semantics for weak systems of modal logic. In addition, the book discusses a broad range of topics, including standard modal logic results ; bisimulations for neighborhood models and other (...) model-theoretic constructions; comparisons with other semantics for modal logic ; neighborhood semantics for first-order modal logic, applications in game theory ; applications in epistemic logic ; and non-normal modal logics with dynamic modalities. The book can be used as the primary text for seminars on philosophical logic focused on non-normal modal logics; as a supplemental text for courses on modal logic, logic in AI, or philosophical logic ; or as the primary source for researchers interested in learning about the uses of neighborhood semantics in philosophical logic and game theory. (shrink)

In this paper we study the set of MV-algebras with given prime spectrum and we introduce the class of spectral MV-algebras. An MV-algebra is spectral if it is generated by the union of all its prime ideals (or proper ideals, or principal ideals, or maximal ideals). Among spectral MV-algebras, special attention is devoted to bipartite MV-algebras. An MV-algebra is bipartite if it admits an homomorphism onto the MV-algebra of two elements. We prove that both bipartite MV-algebras and spectral MV-algebras can (...) be finitely axiomatized in first order logic. We also prove that there is only, up to isomorphism, a set of MV-algebras with given prime spectrum. A further part of the paper is devoted to some relations between bipartite MV-algebras and their states. Recall that a state on an MV-algebra is a generalization of a probability measure on a Boolean algebra. Particular states are the states with Bayes’ property. We show that an MV-algebra admits a state with the Bayes’ property if and only if it is bipartite. (shrink)

In previous work we gave a mathematical foundation, referred to as DisCoCat, for how words interact in a sentence in order to produce the meaning of that sentence. To do so, we exploited the perfect structural match of grammar and categories of meaning spaces. Here, we give a mathematical foundation, referred to as DisCoCirc, for how sentences interact in texts in order to produce the meaning of that text. First we revisit DisCoCat. While in DisCoCat (...) all meanings are fixed as states, in DisCoCirc word meanings correspond to a type, or system, and the states of this system can evolve. Sentences are gates within a circuit which update the variable meanings of those words. Like in DisCoCat, word meanings can live in a variety of spaces e.g. propositional, vectorial, or cognitive. The compositional structure are string diagrams representing information flows, and an entire text yields a single string diagram in which word meanings lift to the meaning of the entire text. While the developments in this paper are independent of a physical embodiment, both the compositional formalism and suggested meaning model are highly quantum-inspired, and implementation on a quantum computer would come with a range of benefits. We also praise Jim Lambek for his role in mathematical linguistics in general, and the development of the DisCo program more specifically. (shrink)