In several areas of Mathematical Logic and Computer Science one would ideally like to use the set F orm(L) of all formulas of some first-order language L for some goal, but this cannot be done safely. In such a case it is necessary to select a subset of F orm(L) that can safely be used. Three main examples of this phenomenon are: • The main principle of naive set theory is the comprehension schema: ∃Z(∀x.x ∈ Z ⇔ (...) A). (shrink)

In this paper we investigate some mathematical consequences of the Equivocation Principle, and the Maximum Entropy models arising from that, for first order languages. We study the existence of Maximum Entropy models for these theories in terms of the quantifier complexity of the theory and will investigate some invariance and structural properties of such models.

We investigate an approach for drawing logical inference from inconsistent premisses. The main idea in this approach is that the inconsistencies in the premisses should be interpreted as uncertainty of the information. We propose a mechanism, based on Kinght’s [14] study of inconsistency, for revising an inconsistent set of premisses to a minimally uncertain, probabilistically consistent one. We will then generalise the probabilistic entailment relation introduced in [15] for propositional languages to the first order case to draw logical (...) inference from a probabilistic set of premisses. We will show how this combination can allow us to limit the effect of uncertainty introduced by inconsistent premisses to only the reasoning on the part of the premise set that is relevant to the inconsistency. (shrink)

I examine notions of equivalence between logics (understood as languages interpreted model-theoretically) and develop two new ones that invoke not only the algebraic but also the string-theoretic structure of the underlying language. As an application, I show how to construe modal operator languages as what might be called typographical notational variants of _bona fide_ first-order languages.

A first-order language with a defined identity predicate is proposed whose apparatus for atomic predication is sensitive to grammatical categories of natural language. Subatomic natural deduction systems are defined for this naturalistic first-order language. These systems contain subatomic systems which govern the inferential relations which obtain between naturalistic atomic sentences and between their possibly composite components. As a main result it is shown that normal derivations in the defined systems enjoy the subexpression property (...) which subsumes the subformula property with respect to atomic and identity formulae as a special case. The systems admit a proof-theoretic semantics which does not only apply to logically compound but also to atomic and identity formulae—as well as to their components. The potential of the defined systems for a meticulous first-order analysis of natural inferences whose validity crucially depends on expressions of some of the aforementioned categories is demonstrated. (shrink)

The Language of First-Order Logic is a complete introduction to first-order symbolic logic, consisting of a computer program and a text. The program, an aid to learning and using symbolic notation, allows one to construct symbolic sentences and possible worlds, and verify that a sentence is well formed. The truth or falsity of a sentence can be determined by playing a deductive game with the computer.

Standard models for model predicate logic consist of a Kripke frame whose worlds come equipped with relational structures. Both modal and two-sorted predicate logic are natural languages for speaking about such models. In this paper we compare their expressivity. We determine a fragment of the two-sorted language for which the modal language is expressively complete on S5-models. Decidable criteria for modal definability are presented.

We present Property Theory with Curry Typing (PTCT), an intensional first-order logic for natural language semantics. PTCT permits fine-grained specifications of meaning. It also supports polymorphic types and separation types. We develop an intensional number theory within PTCT in order to represent proportional generalized quantifiers like “most.” We use the type system and our treatment of generalized quantifiers in natural language to construct a type-theoretic approach to pronominal anaphora that avoids some of the difficulties that (...) undermine previous type-theoretic analyses of this phenomenon. (shrink)

Here is an account of logical consequence inspired by Bolzano and Tarski. Logical validity is a property of arguments. An argument is a pair of a set of interpreted sentences (the premises) and an interpreted sentence (the conclusion). Whether an argument is logically valid depends only on its logical form. The logical form of an argument is fixed by the syntax of its constituent sentences, the meanings of their logical constituents and the syntactic differences between their non-logical constituents, treated as (...) variables. A constituent of a sentence is logical just if it is formal in meaning, in the sense roughly that its application is invariant under permutations of individuals.1 Thus ‘=’ is a logical constant because no permutation maps two individuals to one or one to two; ‘∈’ is not a logical constant because some permutations interchange the null set and its singleton. Truth functions, the usual quantifiers and bound variables also count as logical constants. An argument is logically valid if and only if the conclusion is true under every assignment of semantic values to variables (including all non-logical expressions) under which all its premises are true. A sentence is logically true if and only if the argument with no premises of which it is the conclusion is logically valid, that is, if and only if the sentence is true under every assignment of semantic values to variables. An interpretation assigns values to all variables. (shrink)

This paper is about the concept of semantically closed languages. Roughly speaking, those are languages which can name their own sentences and apply to them semantic predicates, such as the truth or satisfaction predicates. Hence, they are “self-referential languages,” in the sense that they are capable of producing sentences about themselves or other sentences in the same language. In section one, we introduce the concept informally; in section two, we provide the formal definition of first-order semantically closed (...) languages, which is the Tarskian definition with some technical modifications. Then, we construct a semantic for this kind of language, and prove that the language is indeed semantically closed (according to Definition 1). Finally, we discuss whether the logic underlying the construction is classical, and future goals of this research. (shrink)

Online trading invariably involves dealings between strangers, so it is important for one party to be able to judge objectively the trustworthiness of the other. In such a setting, the decision to trust a user may sensibly be based on that user’s past behaviour. We introduce a specification language based on linear temporal logic for expressing a policy for categorising the behaviour patterns of a user depending on its transaction history. We also present an algorithm for checking whether the (...) transaction history obeys the stated policy. To be useful in a real setting, such a language should allow one to express realistic policies which may involve parameter quantification and quantitative or statistical patterns. We introduce several extensions of linear temporal logic to cater for such needs: a restricted form of universal and existential quantification; arbitrary computable functions and relations in the term language; and a “counting” quantifier for counting how many times a formula holds in the past. We then show that model checking a transaction history against a policy, which we call the history-based transaction monitoring problem, is PSPACE-complete in the size of the policy formula and the length of the history, assuming that the underlying interpreted func-. (shrink)

This book is intended, along with the computer program, to introduce the user to some of the most important concepts and tools of logic, including learning a new computer language.

In its first meaning, a logic is a collection of closely related artificial languages. There are certain languages called first‐order languages, and together they form first‐order logic. In the same spirit, there are several closely related languages called modal languages, and together they form modal logic. Likewise second‐order logic, deontic logic and so forth.

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)

We contest two claims: (1) that language, understood as the processing of abstract symbolic forms, is an instrument of cognition and rational thought, and (2) that conventional notions of turn-taking, exchange structure, and move analysis, are satisfactory as a basis for theorizing communication between living, feeling agents. We offer an enkinaesthetic theory describing the reciprocal affective neuro-muscular dynamical flows and tensions of co- agential dialogical sense-making relations. This “enkinaesthetic dialogue” is characterised by a preconceptual experientially recursive temporal dynamics forming (...) the deep extended melodies of relationships in time. An understanding of how those relationships work, when we understand and are ourselves understood, when communication falters and conflict arises, will depend on a grasp of our enkinaesthetic intersubjectivity. (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)

Audrito and Viale introduced the new large cardinal notion of an (α)‐uplifting cardinal (for an ordinal α). We shall show that this notion cannot be defined (or expressed) in the standard first‐order language of set theory for every tranfinite α.

This paper is an attempt to develop the many-valued first-order fuzzy logic. The set of its truth, values is supposed to be either a finite chain or the interval 0, 1 of reals. These are special cases of a residuated lattice L, , , , , 1, 0. It has been previously proved that the fuzzy propositional logic based on the same sets of truth values is semantically complete. In this paper the syntax and semantics of the (...) class='Hi'>first-order fuzzy logic is developed. Except for the basic connectives and quantifiers, its language may contain also additional n-ary connectives and quantifiers. Many propositions analogous to those in the classical logic are proved. The notion of the fuzzy theory in the first-order fuzzy logic is introduced and its canonical model is constructed. Finally, the extensions of Gödel's completeness theorems are proved which confirm that the first-order fuzzy logic is also semantically complete. (shrink)

Here is an account of logical consequence inspired by Bolzano and Tarski. Logical validity is a property of arguments. An argument is a pair of a set of interpreted sentences (the premises) and an interpreted sentence (the conclusion). Whether an argument is logically valid depends only on its logical form. The logical form of an argument is fixed by the syntax of its constituent sentences, the meanings of their logical constituents and the syntactic differences between their non-logical constituents, treated as (...) variables. A constituent of a sentence is logical just if it is formal in meaning, in the sense roughly that its application is invariant under permutations of individuals.1 Thus ‘=’ is a logical constant because no permutation maps two individuals to one or one to two; ‘∈’ is not a logical constant because some permutations interchange the null set and its singleton. Truth functions, the usual quantifiers and bound variables also count as logical constants. An argument is logically valid if and only if the conclusion is true under every assignment of semantic values to variables (including all non-logical expressions) under which all its premises are true. A sentence is logically true if and only if the argument with no premises of which it is the conclusion is logically valid, that is, if and only if the sentence is true under every assignment of semantic values to variables. An interpretation assigns values to all variables. (shrink)

I present a sequent calculus that extends a nonmonotonic reflexive consequence relation as defined over an atomic first-order language without variables to one defined over a logically complex first-order language. The extension preserves reflexivity, is conservative (therefore nonmonotonic) and supraintuitionistic, and is conducted in a way that lets us codify, within the logically extended object language, important features of the base thus extended. In other words, the logical operators in this calculus play what (...) Brandom (2008) calls expressive roles. Expressivist logical systems have already been proposed for propositional logics (see Hlobil, 2016, and Kaplan, 2018) but not for first-order logics. An advantage of this calculus over standard first-order calculi (e.g., those in Gentzen, 1935/1964) is that universally quantified variables behave as they should even in the presence of arbitrary nonlogical axioms. I claim that because of this robust well-behavedness of variables, this calculus also provides logical inferentialists with a way to understand the meanings of variables in terms of the roles those variables play in a wide range of inferences that is not limited to purely logical ones (e.g, mathematical inferences). (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)

In lieu of an abstract, here is a brief excerpt of the content:First Order Relationality and Its Implications:A Response to David ElsteinRoger T. Ames (bio)David Elstein has asked a series of important questions about Human Becomings that provide me with an opportunity to try to bring the argument of the book into clearer focus. Let me begin by thanking David for his always generous and intelligent reflection on not only my new monograph [End Page 181] but also on (...) Henry Rosemont's and my best efforts to expand upon the idea of "role ethics" as a productive way to read Confucian ethics.David asks: Is relationality truly a part of original Confucian thought? Does relationality rule out any notion of essential human nature, and does it necessarily imply or entail role ethics? Is relationality true or merely a useful way of thinking (if these can be distinguished)? Do we know that it's useful?I think the answer to these questions turns on two very different ways of understanding relationality, namely the doctrines of first and second order relationality. The term 'ontology' as "the science of being per se or in itself" gives us a doctrine of external, second order relations. Ontology was introduced into our philosophical vocabulary as a new term for an old way of thinking at the beginning of the seventeenth century by two German philosophers.1 For the classical Greeks, "the science of being per se" (to on he on) was posited as their "first philosophy" with all of its implications for metaphysics, epistemology, logic, ethics, philosophy of religion, and so on. Ontology is that branch of metaphysics that seeks to classify and explain the things that exist, with its underlying assumption that there are unchanging substances or essences internal to things that are available to us to classify them as this and not that. Ontology privileges "being per se" with its categorical language and its "substance" and "attribute" dualism, giving us a grammar of substances as property-bearers and properties that are borne, respectively.Such ontological thinking animates Plato's pursuit of formal, "real" definitions in his quest for certainty (that is, definitions not of words but of what really is), and underlies Aristotle's taxonomical science of knowing "what is what." For these classical Greek philosophers, only what is real and is thus true can be the proper object of knowledge, giving us a logic of the changeless. Corollary to ontology is causal thinking, formal definitions, and, important for David's question, a doctrine of external, second order relationality in which relations conjoin discrete and self-sufficient things, such as human "beings." As the contemporary philosopher Zhao Tingyang 趙汀陽 avers, this kind of substance ontology defining the real things that constitute the content of an orderly and structured cosmosprovides a "dictionary" kind of explanation of the world, seeking to set up an accurate understanding of the limits of all things. In simple terms, it determines "what is what," and all concepts are footnotes to "being" or "is."2In the Book of Changes, we find a vocabulary making explicit cosmological assumptions that stand in stark contrast to this substance ontology and that brings with it a doctrine of first order, constitutive relations. This alternative "first philosophy" has prompted me to create the neologism "zoetology," with the Greek zoe- "life" and -logia "discourse," as my own new term for an old way of thinking that we might translate into modern Chinese as shengshenglun 生生論: "the art of living." The starting point in this zoetological cosmology, then, is that nothing does anything by [End Page 182] itself; association is a fact. Since the very nature of life is associative and transactional, the vocabulary appealed to in defining Confucian cosmology is irreducibly dyadic and collateral: always multiple, never one.And further, it is the nature of life itself that it seeks to optimize the available conditions for its continuing growth, where such growth has a persistent existential and thus intentional aspect. "Life" is the productive correlation between organism and environment that gives rise to correlative, relational, ecological thinking that many of our best sinologists (Marcel Granet, David Keightley, Tang Junyi, K. C. Chang, A. C. Graham, and many others) would ascribe to the earliest semblances of Chinese... (shrink)

This document presents a Gentzen-style deductive calculus and proves that it is complete with respect to a 3-valued semantics for a language with quantifiers. The semantics resembles the strong Kleene semantics with respect to conjunction, disjunction and negation. The completeness proof for the sentential fragment fills in the details of a proof sketched in Arnon Avron (2003). The extension to quantifiers is original but uses standard techniques.

It is shown that there is a formula σ(g) in the first-order language of group theory with the following property: for every finite group G, the largest soluble normal subgroup of G consists precisely of the elements g of G such that σ(g) holds.

This is a companion paper to Braüner where a natural deduction system for propositional hybrid logic is given. In the present paper we generalize the system to the first-order case. Our natural deduction system for first-order hybrid logic can be extended with additional inference rules corresponding to conditions on the accessibility relations and the quantifier domains expressed by so-called geometric theories. We prove soundness and completeness and we prove a normalisation theorem. Moreover, we give an axiom (...) system first-order hybrid logic. (shrink)

This text/courseware package presents a new approach to teaching first-order logic. Taking advantage of Tarski's World 4.0, the text skilfully balances the semantic conception of logic with methods of proof. The book contains eleven chapters, in four parts. Part I is about propositional logic, Part II about quantifier logic. Part III contains chapters on set theory and inductive definitions. Part IV contains advanced topics in logic, including topics of importance in applications of logic in computer science. The (...) class='Hi'>Language of First-order Logic contains hundreds of problems and exercises for the user to work through. (shrink)

In this note we study a counterpart in predicate logic of the notion of logical friendliness, introduced into propositional logic in [15]. The result is a new consequence relation for predicate languages with equality using first-order models. While compactness, interpolation and axiomatizability fail dramatically, several other properties are preserved from the propositional case. Divergence is diminished when the language does not contain equality with its standard interpretation.

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.

In this paper, some basic properties of automorphisms of first order languages and some examples are presented. In particular, an omitting types theorem is proved.

We consider the problem of constructing first-order definitions in the language of rings of holomorphy rings of one-variable function fields of characteristic 0 in their integral closures in finite extensions of their fraction fields and in bigger holomorphy subrings of their fraction fields. This line of questions is motivated by similar existential definability results over global fields and related questions of Diophantine decidability.

The paper presents Property Theory with Curry Typing where the language of terms and well-formed formulæ are joined by a language of types. In addition to supporting fine-grained intensionality, the basic theory is essentially first-order, so that implementations using the theory can apply standard first-order theorem proving techniques. The paper sketches a system of tableau rules that implement the theory. Some extensions to the type theory are discussed, including type polymorphism, which provides a useful (...) analysis of conjunctive terms. Such terms can be given a single polymorphic type that expresses the fact that they can conjoin phrases of any one type, yielding an expression of the same type. (shrink)

We study the class of Sperner spaces, a generalized version of affine spaces, as defined in the language of pointline incidence and line parallelity. We show that, although the class of Sperner spaces is a pseudo-elementary class, it is not elementary nor even ℒ∞ω-axiomatizable. We also axiomatize the first-order theory of this class.

The paper presents Property Theory with Curry Typing (PTCT) where the language of terms and well-formed formulæ are joined by a language of types. In addition to supporting fine-grained intensionality, the basic theory is essentially first-order, so that implementations using the theory can apply standard first-order theorem proving techniques. Some extensions to the type theory are discussed, type polymorphism, and enriching the system with sufficient number theory to account for quantifiers of proportion, such as (...) “most.”. (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)

One is often said to be reasoning well when they are reasoning logically. Many attempts to say what logical reasoning is have been proposed, but one commonly proposed system is first-order classical logic. This Element will examine the basics of first-order classical logic and discuss some surrounding philosophical issues. The first half of the Element develops a language for the system, as well as a proof theory and model theory. The authors provide theorems about (...) the system they developed, such as unique readability and the Lindenbaum lemma. They also discuss the meta-theory for the system, and provide several results there, including proving soundness and completeness theorems. The second half of the Element compares first-order classical logic to other systems: classical higher order logic, intuitionistic logic, and several paraconsistent logics which reject the law of ex falso quodlibet. (shrink)

First, we describe a psychological experiment in which the participants were asked to determine whether sentences of first-order logic were true or false in finite graphs. Second, we define two proof systems for reasoning about truth and falsity in first-order logic. These proof systems feature explicit models of cognitive resources such as declarative memory, procedural memory, working memory, and sensory memory. Third, we describe a computer program that is used to find the smallest proofs in (...) the aforementioned proof systems when capacity limits are put on the cognitive resources. Finally, we investigate the correlation between a number of mathematical complexity measures defined on graphs and sentences and some psychological complexity measures that were recorded in the experiment. (shrink)