Search

We present a cut-free sequent calculus for a class of first-order theories in negation normal form which include coherent and co-coherent theories alike. All structural rules, including cut, are admissible. [ABSTRACT FROM AUTHOR]

The ε -elimination method of Hilbert's ε -calculus yields the up-to-date most direct algorithm for computing the Herbrand disjunction of an extensional formula. A central advantage is that the upper bound on the Herbrand complexity obtained is independent of the propositional structure of the proof. Prior (modern) work on Hilbert's ε -calculus focused mainly on the pure calculus, without equality. We clarify that this independence also holds for first-order logic with equality. Further, we provide upper bounds analyses of the extended first ε -theorem, even if the formalisation incorporates so-called ε -equality axioms. [ABSTRACT FROM AUTHOR]

This paper concerns product constructions within the continuous-logic framework of Ben Yaacov, Berenstein, Henson, and Usvyatsov. Continuous-logic analogues are presented for the direct product, direct sum, and almost everywhere direct product analyzed in the work of Feferman and Vaught. These constructions are shown to possess a number of preservation properties analogous to those enjoyed by their classical counterparts in ordinary first-order logic: for example, each product preserves elementary equivalence in an appropriate sense; and if for i ∈ N M i is a metric structure and the sentence θ is true in ∏ i = 0 k M i for every k ∈ N , then θ is true in ∏ i ∈ N M i . [ABSTRACT FROM AUTHOR]

In Schwichtenberg (Studies in logic and the foundations of mathematics, vol 90, Elsevier, pp 867–895, 1977), Schwichtenberg fine-tuned Tait's technique (Tait in The syntax and semantics of infinitary languages, Springer, pp 204–236, 1968) so as to provide a simplified version of Gentzen's original cut-elimination procedure for first-order classical logic (Gallier in Logic for computer science: foundations of automatic theorem proving, Courier Dover Publications, London, 2015). In this note we show that, limited to the case of classical propositional logic, the Tait–Schwichtenberg algorithm allows for a further simplification. The procedure offered here is implemented on Kleene's sequent system G4 (Kleene in Mathematical logic, Wiley, New York, 1967; Smullyan in First-order logic, Courier corporation, London, 1995). The specific formulation of the logical rules for G4 allows us to provide bounds on the height of cut-free proofs just in terms of the logical complexity of their end-sequent. [ABSTRACT FROM AUTHOR]

This paper establishes model-theoretic properties of M E ∞ , a variation of monadic first-order logic that features the generalised quantifier ∃ ∞ ('there are infinitely many'). We will also prove analogous versions of these results in the simpler setting of monadic first-order logic with and without equality ( M E and M , respectively). For each logic L ∈ { M , M E , M E ∞ } we will show the following. We provide syntactically defined fragments of L characterising four different semantic properties of L -sentences: (1) being monotone and (2) (Scott) continuous in a given set of monadic predicates; (3) having truth preserved under taking submodels or (4) being truth invariant under taking quotients. In each case, we produce an effectively defined map that translates an arbitrary sentence φ to a sentence φ p belonging to the corresponding syntactic fragment, with the property that φ is equivalent to φ p precisely when it has the associated semantic property. As a corollary of our developments, we obtain that the four semantic properties above are decidable for L -sentences. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This note concerns the model theoretic properties of logics extending the first-order logic with monadic (weak) second-order variables equipped with the stationarity quantifier. The eight variations of the strong downward Löwenheim–Skolem Theorem (SDLS) down to < ℵ 2 for this logic with the interpretation of second-order variables as countable subsets of the structures are classified into four principles. The strongest of these four is shown to be equivalent to the conjunction of CH and the Diagonal Reflection Principle for internally clubness of S. Cox. We show that a further strengthening of this SDLS and its variations follow from the Game Reflection Principle of B. König and its generalizations. [ABSTRACT FROM AUTHOR]

We propose the notion of a quasiminimal abstract elementary class (AEC). This is an AEC satisfying four semantic conditions: countable Löwenheim-Skolem-Tarski number, existence of a prime model, closure under intersections, and uniqueness of the generic orbital type over every countable model. We exhibit a correspondence between Zilber’s quasiminimal pregeometry classes and quasiminimal AECs: any quasiminimal pregeometry class induces a quasiminimal AEC (this was known), and for any quasiminimal AEC there is a natural functorial expansion that induces a quasiminimal pregeometry class. We show in particular that the exchange axiom is redundant in Zilber’s definition of a quasiminimal pregeometry class. [ABSTRACT FROM AUTHOR]

We use sets of assignments, a.k.a. teams, and measures on them to define probabilities of first-order formulas in given data. We then axiomatise first-order properties of such probabilities and prove a completeness theorem for our axiomatisation. We use the Hardy-Weinberg Principle of biology and the Bell's Inequalities of quantum physics as examples. [ABSTRACT FROM AUTHOR]

We introduce a new typed combinatory calculus with a type constructor that, to each type $$\sigma $$ , associates the star type $$\sigma ^*$$ of the nonempty finite subsets of elements of type $$\sigma $$ . We prove that this calculus enjoys the properties of strong normalization and confluence. With the aid of this star combinatory calculus, we define a functional interpretation of first-order predicate logic and prove a corresponding soundness theorem. It is seen that each theorem of classical first-order logic is connected with certain formulas which are tautological in character. As a corollary, we reprove Herbrand's theorem on the extraction of terms from classically provable existential statements. [ABSTRACT FROM AUTHOR]

We introduce and study the first-order Generic Vopěnka's Principle, which states that for every definable proper class of structures $$\mathcal {C}$$ of the same type, there exist $$B\ne A$$ in $$\mathcal {C}$$ such that B elementarily embeds into A in some set-forcing extension. We show that, for $$n\ge 1$$ , the Generic Vopěnka's Principle fragment for $$\Pi _n$$ -definable classes is equiconsistent with a proper class of n-remarkable cardinals. The n-remarkable cardinals hierarchy for $$n\in \omega $$ , which we introduce here, is a natural generic analogue for the $$C^{(n)}$$ -extendible cardinals that Bagaria used to calibrate the strength of the first-order Vopěnka's Principle in Bagaria (Arch Math Logic 51(3-4):213-240, 2012). Expanding on the theme of studying set theoretic properties which assert the existence of elementary embeddings in some set-forcing extension, we introduce and study the weak Proper Forcing Axiom, $$\mathrm{wPFA}$$ . The axiom $$\mathrm{wPFA}$$ states that for every transitive model $$\mathcal M$$ in the language of set theory with some $$\omega _1$$ -many additional relations, if it is forced by a proper forcing $$\mathbb P$$ that $$\mathcal M$$ satisfies some $$\Sigma _1$$ -property, then V has a transitive model $$\bar{\mathcal M}$$ , satisfying the same $$\Sigma _1$$ -property, and in some set-forcing extension there is an elementary embedding from $$\bar{\mathcal M}$$ into $$\mathcal M$$ . This is a weakening of a formulation of $$\mathrm{PFA}$$ due to Claverie and Schindler (J Symb Logic 77(2):475-498, 2012), which asserts that the embedding from $$\bar{\mathcal M}$$ to $$\mathcal M$$ exists in V. We show that $$\mathrm{wPFA}$$ is equiconsistent with a remarkable cardinal. Furthermore, the axiom $$\mathrm{wPFA}$$ implies $$\mathrm{PFA}_{\aleph _2}$$ , the Proper Forcing Axiom for antichains of size at most $$\omega _2$$ , but it is consistent with $$\square _\kappa $$ for all $$\kappa \ge \omega _2$$ , and therefore does not imply $$\mathrm{PFA}_{\aleph _3}$$ . [ABSTRACT FROM AUTHOR]

Inspired by the work done by Baaz et al. (Ann Pure Appl Log 147(1-2): 23-47, ; Lecture Notes in Computer Science, vol 4790/2007, pp 77-91, ) for first-order Gödel logics, we investigate Nilpotent Minimum logic NM. We study decidability and reciprocal inclusion of various sets of first-order tautologies of some subalgebras of the standard Nilpotent Minimum algebra, establishing also a connection between the validity in an NM-chain of certain first-order formulas and its order type. Furthermore, we analyze axiomatizability, undecidability and the monadic fragments. [ABSTRACT FROM AUTHOR]

This work presents a model-theoretic approach to the study of the amalgamation property for varieties of semilinear commutative residuated lattices. It is well-known that if a first-order theory T enjoys quantifier elimination in some language L, the class of models of the set of its universal consequences $${\rm T_\forall}$$ has the amalgamation property. Let $${{\rm Th}(\mathbb{K})}$$ be the theory of an elementary subclass $${\mathbb{K}}$$ of the linearly ordered members of a variety $${\mathbb{V}}$$ of semilinear commutative residuated lattices. We show that whenever $${{\rm Th}(\mathbb{K})}$$ has elimination of quantifiers, and every linearly ordered structure in $${\mathbb{V}}$$ is a model of $${{\rm Th}_\forall(\mathbb{K})}$$, then $${\mathbb{V}}$$ has the amalgamation property. We exploit this fact to provide a purely model-theoretic proof of amalgamation for particular varieties of semilinear commutative residuated lattices. [ABSTRACT FROM AUTHOR]

A probability distribution can be given to the set of isomorphism classes of models with universe {1, ..., n} of a sentence in first-order logic. We study the entropy of this distribution and derive a result from the 0–1 law for first-order sentences. [ABSTRACT FROM AUTHOR]

We introduce a new approach to the model theory of metric structures by defining the notion of a metric abstract elementary class (MAEC) closely resembling the notion of an abstract elementary class. Further we define the framework of a homogeneous MAEC were we additionally assume the existence of arbitrarily large models, joint embedding, amalgamation, homogeneity and a property which we call the perturbation property. We also assume that the Löwenheim-Skolem number, which in this setting refers to the density character of the set instead of the cardinality, is $${\aleph_0}$$. In these settings we prove an analogue of Morley’s categoricity transfer theorem. We also give concrete examples of homogeneous MAECs. [ABSTRACT FROM AUTHOR]

In this paper we study the idea of theories with containers, like sets, pairs, sequences. We provide a modest framework to study such theories. We prove two concrete results. First, we show that first-order theories of finite signature that have functional non-surjective ordered pairing are definitionally equivalent to extensions in the same language of the basic theory of non-surjective ordered pairing. Second, we show that a first-order theory of finite signature is sequential (is a theory of sequences) iff it is definitionally equivalent to an extension in the same language of a system of weak set theory called WS. [ABSTRACT FROM AUTHOR]

We study the formal first order system TIND in the standard language of Gentzen's LK . TIND extends LK by the purely logical rule of term-induction, that is a restricted induction principle, deriving numerals instead of arbitrary terms. This rule may be conceived as the logical image of full induction. [ABSTRACT FROM AUTHOR]

Let T be a complete, countable, first-order theory with a finite number of countable models. Assuming that dcl(∅) is infinite we show that T has the strict order property. [ABSTRACT FROM AUTHOR]

Carrying out a suggestion by Kreisel, we adapt Gödel’s functional interpretation to ordinary first-order predicate logic(PL) and thus devise an algorithm to extract Herbrand terms from PL-proofs. The extraction is carried out in an extension of PL to higher types. The algorithm consists of two main steps: first we extract a functional realizer, next we compute the β-normal-form of the realizer from which the Herbrand terms can be read off. Even though the extraction is carried out in the extended language, the terms are ordinary PL-terms. In contrast to approaches to Herbrand’s theorem based on cut elimination or ɛ-elimination this extraction technique is, except for the normalization step, of low polynomial complexity, fully modular and furthermore allows an analysis of the structure of the Herbrand terms, in the spirit of Kreisel ([13]), already prior to the normalization step. It is expected that the implementation of functional interpretation in Schwichtenberg’s MINLOG system can be adapted to yield an efficient Herbrand-term extraction tool. [ABSTRACT FROM AUTHOR]

We formulate a restricted version of the Tukey-Teichmüller Theorem that we denote by (rTT). We then prove that (rTT) and (BPI) are equivalent in ZF and that (rTT) applies rather naturally to several equivalent forms of (BPI): Alexander Subbase Theorem, Stone Representation Theorem, Model Existence and Compactness Theorems for propositional and first-order logic. We also give two variations of (rTT) that we denote by (rTT)+ and (rTT)++; each is equivalent to (rTT) in ZF. The variation (rTT)++ applies rather naturally to various Selection Lemmas due to Cowen, Engeler, and Rado. [ABSTRACT FROM AUTHOR]

An algebraization of multi-signature first-order logic without terms is presented. Rather than following the traditional method of choosing a type of algebras and constructing an appropriate variety, as is done in the case of cylindric and polyadic algebras, a new categorical algebraization method is used: The substitutions of formulas of one signature for relation symbols in another are treated in the object language. This enables the automatic generation via an adjunction of an algebraic theory. The algebras of this theory are then used to algebraize first-order logic. [ABSTRACT FROM AUTHOR]

We show that a strong form of the so called Lindström’s Theorem [4] fails to generalize to extensions ofL ? ? andL ? ?: For weakly compact?there is no strongest extension ofL ? ? with the (?,?)-compactness property and the Löwenheim-Skolem theorem down to?. With an additional set-theoretic assumption, there is no strongest extension ofL ? ? with the (?,?)-compactness property and the Löwenheim-Skolem theorem down to

For a complete first order theory of Boolean algebras T which has nonisomorphic countable models, we determine the first limit ordinal α = α(T) such that We show that for some and for all other T‘s, A nonprincipal ideal I of B is almost principal, if a is a principal ideal of B} is a maximal ideal of B. We show that the theory of Boolean algebras with an almost principal ideal has complete extensions and characterize them by invariants similar to the Tarski’s invariants. [ABSTRACT FROM AUTHOR]

Abstract. We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line). [ABSTRACT FROM AUTHOR]

Abstract. It is a classical result of Mortimer that L[sup 2], first-order logic with two variables, is decidable for satisfiability. We show that going beyond L[sup 2] by adding any one of the following leads to an undecidable logic: -- very weak forms of recursion, viz. (i) transitive closure operations (ii) (restricted) monadic fixed-point operations -- weak access to cardinalities, through the Hartig (or equicardinality) quantifier -- a choice construct known as Hilbert's epsilon-operator. In fact all these extensions of L[sup 2] prove to be undecidable both for satisfiability, and for satisfiability in finite structures. Moreover most of them are hard for SIGMA[sup 1, sub 1], the first level of the analytical hierachy, and thus have a much higher degree of undecidability than first-order logic. [ABSTRACT FROM AUTHOR]