We show that the conceptual distance between any two theories of first-order logic is the same as the generator distance between their Lindenbaum–Tarski algebras of concepts. As a consequence of this, we show that, for any two arbitrary mathematical structures, the generator distance between their meaning algebras (also known as cylindric set algebras) is the same as the conceptual distance between their first-order logic theories. As applications, we give a complete description for the distances between meaning algebras corresponding to structures having at most three elements and show that this small network represents all the possible conceptual distances between complete theories. As a corollary of this, we will see that there are only two non-trivial structures definable on three-element sets up to conceptual equivalence (i.e., up to elementary plus definitional equivalence).

Dialogues are turn-taking games which model debates about the satisfaction of logical formulas. A novel variant played over first-order structures gives rise to a notion of first-order satisfaction. We study the induced notion of validity for classical and intuitionistic first-order logic in the constructive setting of the calculus of inductive constructions. We prove that such material dialogue semantics for classical first-order logic admits constructive soundness and completeness proofs, setting it apart from standard model-theoretic semantics of first-order logic. Furthermore, we prove that completeness with regard to intuitionistic material dialogues fails in both constructive and classical settings. As an alternative, we propose material dialogues played over Kripke structures. These Kripke material dialogues exhibit constructive completeness when restricting to the negative fragment. The results concerning classical material dialogues have been mechanized using the Coq interactive theorem prover.

Two first-order logic theories are definitionally equivalent if and only if there is a bijection between their model classes that preserves isomorphisms and ultraproducts (Theorem 2). This is a variant of a prior theorem of van Benthem and Pearce. In Example 2, uncountably many pairs of definitionally inequivalent theories are given such that their model categories are concretely isomorphic via bijections that preserve ultraproducts in the model categories up to isomorphism. Based on these results, we settle several conjectures of Barrett, Glymour and Halvorson.

We show that the first-order logical theory of the binary overlap-free words (and, more generally, the $\alpha $-free words for rational $\alpha $, $2 < \alpha \leq 7/3$), is decidable. As a consequence, many results previously obtained about this class through tedious case-based proofs can now be proved “automatically,” using a decision procedure, and new claims can be proved or disproved simply by restating them as logical formulas.

In this paper, we introduce a logic based on team semantics, called $\mathbf {FOT} $ , whose expressive power is elementary, i.e., coincides with first-order logic both on the level of sentences and (possibly open) formulas, and we also show that a sublogic of $\mathbf {FOT} $ , called $\mathbf {FOT}^{\downarrow } $ , captures exactly downward closed elementary (or first-order) team properties. We axiomatize completely the logic $\mathbf {FOT} $ , and also extend the known partial axiomatization of dependence logic to dependence logic enriched with the logical constants in $\mathbf {FOT}^{\downarrow } $ .

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.

In 1978, Yu. F. Borisov presented an axiom system using a few basic assumptions and four explicit axioms, the fourth being a formulation of the relativity principle, and he demonstrated that this axiom system had (up to choice of units) only two models: a relativistic one in which worldview transformations are Poincaré transformations and a classical one in which they are Galilean. In this paper, we reformulate Borisov’s original four axioms within an intuitively simple, but strictly formal, first-order logic framework, and convert his basic background assumptions into explicit axioms. Instead of assuming that the structure of physical quantities is the field of real numbers, we assume only that they form an ordered field. This allows us to investigate how Borisov’s theorem depends on the structure of quantities.

We demonstrate (as our main contribution) how to construct Euclidean, Galilean, and Poincaré models of Borisov’s axiom system over every non-Archimedean field. We also demonstrate the existence of an infinite descending chain of models and transformation groups in each of these three cases, something that is not possible over Archimedean fields.

As an application, we note that there is a model of Borisov’s axioms that satisfies the relativity principle, and in which the worldview transformations are Euclidean isometries. Over the field of reals it is easy to eliminate this model using natural axioms concerning time’s arrow and the absence of instantaneous motion. In the case of non-Archimedean fields, however, the Euclidean isometries appear intrinsically as worldview transformations in models of Borisov’s axioms, and neither the assumption of time’s arrow, nor the rejection of instantaneous motion, can eliminate them.

We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$. We show that, for $m \ge 2$, this subfragment forces $\left\lfloor {m/2} \right\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$-NExpTime-hard. We further establish that, for $m \ge 3$, any satisfiable ${\cal F}{{\cal L}^m}$-formula has a model of at most ($m - 2$)-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in ($m - 2$)-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for ${\cal F}{{\cal L}^m}$ for all $m \le 4$.

First-order formalisations are often preferred to propositional ones because they are thought to underwrite the validity of more arguments. We compare and contrast the ability of some well-known logics—these two in particular—to formally capture valid and invalid arguments. We show that there is a precise and important sense in which first-order logic does not improve on propositional logic in this respect. We also prove some generalisations and related results of philosophical interest. The rest of the article investigates the results’ philosophical significance. A first moral is that the correct way to state the oft-cited superiority of first-order logic vis-à-vis propositional logic is more nuanced than often thought. The second moral concerns semantic theory; the third logic’s use as a tool for discovery. A fourth and final moral is that second-order logic’s transcendence of first-order logic is greater than first-order logic’s transcendence of propositional logic.

The article approaches cut elimination from a new angle. On the basis of an arbitrary inference relation among logically atomic formulae, an inference relation on a language possessing logical operators is defined by means of inductive clauses similar to the operator-introducing rules of a cut-free intuitionistic sequent calculus. The logical terminology of the richer language is not uniquely specified, but assumed to satisfy certain conditions of a general nature, allowing for, but not requiring, the existence of infinite conjunctions and disjunctions. We investigate to what extent structural properties of the given atomic relation are preserved through the extension to the full language. While closure under the Cut rule narrowly construed is not in general thus preserved, two properties jointly amounting to closure under the ordinary structural rules, including Cut, are.

Attention is then narrowed down to the special case of a standard first-order language, where a similar result is obtained also for closure under substitution of terms for individual parameters. Taken together, the three preservation results imply the familiar cut-elimination theorem for pure first-order intuitionistic sequent calculus.

In the interest of conceptual economy, all deducibility relations are specified purely inductively, rather than in terms of the existence of formal proofs of any kind.

We present abstract complexity results about Coquand and Hyland–Ong game semantics, that will lead to new bounds on the length of first-order cut-elimination, normalization, interaction between expansion trees and any other dialogical process game semantics can model and apply to. In particular, we provide a novel method to bound the length of interactions between visible strategies and to measure precisely the tower of exponentials defining the worst-case complexity. Our study improves the old estimates on average by several exponentials.

First-order logic has limited existential import: the universalized conditional ∀x [S(x) → P(x)] implies its corresponding existentialized conjunction ∃x [S(x) & P(x)] in some but not all cases. We prove the Existential-Import Equivalence:

∀x [S(x) → P(x)] implies ∃x [S(x) & P(x)] iff ∃x S(x) is logically true.

The antecedent S(x) of the universalized conditional alone determines whether the universalized conditional has existential import: implies its corresponding existentialized conjunction.

A predicate is a formula having only x free. An existential-import predicate Q(x) is one whose existentialization, ∃x Q(x), is logically true; otherwise, Q(x) is existential-import-free or simply import-free. Existential-import predicates are also said to be import-carrying.

How widespread is existential import? How widespread are import-carrying predicates in themselves or in comparison to import-free predicates? To answer, let L be any first-order language with any interpretation INT in any [sc. nonempty] universe U. A subset S of U is definable in L under INT iff for some predicate Q(x) in L, S is the truth-set of Q(x) under INT. S is import-carrying definable iff S is the truth-set of an import-carrying predicate. S is import-free definable iff S is the truth-set of an import-free predicate.

Existential-Importance Theorem: Let L, INT, and U be arbitrary. Every nonempty definable subset of U is both import-carrying definable and import-free definable.

Import-carrying predicates are quite abundant, and no less so than import-free predicates. Existential-import implications hold as widely as they fail.

A particular conclusion cannot be validly drawn from a universal premise, or from any number of universal premises.—Lewis-Langford, 1932, p. 62.

This paper considers Henkin’s proof of completeness of classical first-order logic and extends its scope to the realm of algebraizable logics in the sense of Blok and Pigozzi. Given a propositional logic L (for which we only need to assume that it has an algebraic semantics and a suitable disjunction) we axiomatize two natural first-order extensions L∀m and L∀ and prove that the former is complete with respect to all models over algebras from , while the latter is complete with respect to all models over relatively finitely subdirectly irreducible algebras. While the first completeness result is relatively straightforward, the second requires non-trivial modifications of Henkin’s proof by making use of the disjunction connective. As a byproduct, we also obtain a form of Skolemization provided that the algebraic semantics admits regular completions. The relatively modest assumptions on the propositional side allow for a wide generalization of previous approaches by Rasiowa, Sikorski, Hájek, Horn, and others and help to illuminate the “essentially first-order” steps in the classical Henkin’s proof.

This paper presents the use of first-order logic to improve upon currently employed engineering design knowledge management techniques. Specifically, this work uses description logic in unison with Horn logic, to not only guide the knowledge acquisition process but also to offer much needed support in decision making during the engineering design process in a distributed environment. The knowledge management methods introduced are highlighted by the ability to identify modeling knowledge inconsistencies through the recognition of model characteristic limitations, such as those imposed by model idealizations. The adopted implementation languages include the Semantic Web Rule Language, which enables Horn-like rules to be applied to an ontological knowledge base and the Semantic Web's native Web Ontology Language. As part of this work, an ontological tool, OPTEAM, was developed to capture key aspects of the design process through a set of design-related ontologies and to serve as an application platform for facilitating the engineering design process. The design, analysis, and optimization of a classical I-beam problem are presented as a test-bed case study to illustrate the capabilities of these ontologies in OPTEAM. A second, more extensive test-bed example based on an industry-supplied medical device design problem is also introduced. Results indicate that well-defined, networked relationships within an ontological knowledge base can ultimately lead to a refined design process, with guidance provided by the identification of infeasible solutions and the introduction of “best-case” alternatives. These case studies also show how the application of first-order logic to engineering design improves the knowledge acquisition, knowledge management, and knowledge validation processes.