Model Theory

In this article we explore some properties of H-structures which are introduced in [2]. We describe a construction of H-structures based on one-dimensional asymptotic classes which preserves pseudofiniteness. That is, the H-structures we construct are ultraproducts of finite structures. We also prove that under the assumption that the base theory is supersimple of SU-rank one, there are no new definable groups in H-structures. This improves the corresponding result in [2].

We study the two model-theoretic concepts of weak saturation and weak amalgamation property in the context of accessible categories. We relate these two concepts providing sufficient conditions for existence and uniqueness of weakly saturated objects of an accessible category ${\cal K}$. We discuss the implications of this fact in classical model theory.

In this article, we prove that if a countable non-${\aleph _0}$-categorical NSOP1 theory with nonforking existence has finitely many countable models, then there is a finite tuple whose own preweight is ω. This result is an extension of a theorem of the author on any supersimple theory.

We show that for any uncountable cardinal λ, the category of sets of cardinality at least λ and monomorphisms between them cannot appear as the category of points of a topos, in particular is not the category of models of a ${L_{\infty,\omega }}$-theory. More generally we show that for any regular cardinal $\kappa < \lambda$ it is neither the category of κ-points of a κ-topos, in particular, nor the category of models of a ${L_{\infty,\kappa }}$-theory.The proof relies on the construction (...) of a categorified version of the Scott topology, which constitute a left adjoint to the functor sending any topos to its category of points and the computation of this left adjoint evaluated on the category of sets of cardinality at least λ and monomorphisms between them. The same techniques also apply to a few other categories. At least to the category of vector spaces of with bounded below dimension and the category of algebraic closed fields of fixed characteristic with bounded below transcendence degree. (shrink)

We continue the study of the theories of Baldwin–Shi hypergraphs from [5]. Restricting our attention to when the rank δ is rational valued, we show that each countable model of the theory of a given Baldwin–Shi hypergraph is isomorphic to a generic structure built from some suitable subclass of the original class used in the construction. We introduce a notion of dimension for a model and show that there is a an elementary chain $\left\{ {\mathfrak{M}_\beta :\beta \leqslant \omega } \right\}$ (...) of countable models of the theory of a fixed Baldwin–Shi hypergraph with $\mathfrak{M}_\beta \preccurlyeq \mathfrak{M}_\gamma $ if and only if the dimension of $\mathfrak{M}_\beta $ is at most the dimension of $\mathfrak{M}_\gamma $ and that each countable model is isomorphic to some $\mathfrak{M}_\beta $. We also study the regular types that appear in these theories and show that the dimension of a model is determined by a particular regular type. Further, drawing on a large body of work, we use these structures to give an example of a pseudofinite, ω-stable theory with a nonlocally modular regular type, answering a question of Pillay in [11]. (shrink)

Fix a weakly minimal (i.e. superstable U-rank 1) structure M. Let M∗ be an expansion by constants for an elementary substructure, and let A be an arbitrary subset of the universe M. We show that all formulas in the expansion (M∗,A) are equivalent to bounded formulas, and so (M,A) is stable (or NIP) if and only if the M-induced structure AM on A is stable (or NIP). We then restrict to the case that M is a pure abelian group with (...) a weakly minimal theory, and AM is mutually algebraic (equivalently, weakly minimal with trivial forking). This setting encompasses most of the recent research on stable expansions of (Z,+). Using various characterizations of mutual algebraicity, we give new examples of stable structures of the form (M,A). Most notably, we show that if (G,+) is a weakly minimal additive subgroup of the algebraic numbers, A⊆G is enumerated by a homogeneous linear recurrence relation with algebraic coefficients, and no repeated root of the characteristic polynomial of A is a root of unity, then (G,+,B) is superstable for any B⊆A. (shrink)

A Steiner triple system (STS) is a set S together with a collection B of subsets of S of size 3 such that any two elements of S belong to exactly one element of B. It is well known that the class of finite STS has a Fraïssé limit M_F. Here, we show that the theory T of M_F is the model completion of the theory of STSs. We also prove that T is not small and it has quantifier elimination, (...) TP2, NSOP1, elimination of hyperimaginaries and weak elimination of imaginaries. (shrink)

Takeuti introduced an infinitary proof system for determinate logic and showed that for transitive models of Zermelo-Fraenkel set theory with the Axiom of Dependent Choice that contain all reals, the cut-elimination theorem is equivalent to the Axiom of Determinacy, and in particular contradicts the Axiom of Choice. We consider variants of Takeuti's theorem without assuming the failure of the Axiom of Choice. For instance, we show that if one removes atomic formulae of infinite arity from the language of Takeuti's proof (...) system, then cut elimination is equivalent to a determinacy hypothesis provable, e.g., in ZFC + “there are infinitely many Woodin cardinals.” A slight extension of the proof system admits cut elimination for countable sequents under the same assumptions. A simple modification of the proof system yields analogs of the results above for the Axiom of Real Determinacy and uncountably many Woodin cardinals. (shrink)

We define and investigate a uniformly locally o-minimal structure of the second kind in this paper. All uniformly locally o-minimal structures of the second kind have local monotonicity, which is a local version of monotonicity theorem of o-minimal structures. We also demonstrate a local definable cell decomposition theorem for definably complete uniformly locally o-minimal structures of the second kind. We define dimension of a definable set and investigate its basic properties when the given structure is a locally o-minimal structure which (...) admits local definable cell decomposition. (shrink)

About 25 years ago, it came to light that a single combinatorial property determines both an important dividing line in model theory and machine learning. The following years saw a fruitful exchange of ideas between PAC-learning and the model theory of NIP structures. In this article, we point out a new and similar connection between model theory and machine learning, this time developing a correspondence between stability and learnability in various settings of online learning. In particular, this gives many new (...) examples of mathematically interesting classes which are learnable in the online setting. (shrink)

This article builds on Humberstone’s idea of defining models of propositional modal logic where total possible worlds are replaced by partial possibilities. We follow a suggestion of Humberstone by introducing possibility models for quantified modal logic. We show that a simple quantified modal logic is sound and complete for our semantics. Although Holliday showed that for many propositional modal logics, it is possible to give a completeness proof using a canonical model construction where every possibility consists of finitely many formulas, (...) we show that this is impossible to do in the first-order case. However, one can still construct a canonical model where every possibility consists of a computable set of formulas and thus still of finitely much information. (shrink)

The fundamental principle of the theory of possible worlds is that a proposition p is possible if and only if there is a possible world at which p is true. In this paper we present a valid derivation of this principle from a more general theory in which possible worlds are defined rather than taken as primitive. The general theory uses a primitive modality and axiomatizes abstract objects, properties, and propositions. We then show that this general theory has very small (...) models and hence that its ontological commitments—and, therefore, those of the fundamental principle of world theory—are minimal. (shrink)

We establish completeness and the finite model property for logics featuring the pooling modalities that were introduced in Van De Putte and Klein. The definition of our canonical models combines standard techniques with a so-called “puzzle piece construction”, which we first illustrate informally. After that, we apply it to the weakest classical logics with pooling modalities and investigate the technique’s potential for the axiomatization of stronger logics, obtained by imposing well-known frame conditions on the models.

Extender-based Prikry–Magidor forcing for overlapping extenders is introduced. As an application, models with strong forms of negations of the Shelah Weak Hypothesis for various cofinalities are constructed.

A fundamental result from Boolean modal logic states that a first-order definable class of Kripke frames defines a logic that is validated by all of its canonical frames. We generalise this to the level of non-distributive logics that have a relational semantics provided by structures based on polarities. Such structures have associated complete lattices of stable subsets, and these have been used to construct canonical extensions of lattice-based algebras. We study classes of structures that are closed under ultraproducts and whose (...) stable set lattices have additional operators that are first-order definable in the underlying structure. We show that such classes generate varieties of algebras that are closed under canonical extensions. The proof makes use of a relationship between canonical extensions and MacNeille completions. (shrink)

I build a canonical model for constant domain basic first-order logic (BQLCD), the constant domain first-order extension of Visser’s basic propositional logic, and use the canonical model to verify that BQLCD satisfies the disjunction and existence properties.

We characterize, in syntactic terms, the ranges of epimorphisms in an arbitrary class of similar first-order structures. This allows us to strengthen a result of Bacsich, as follows: in any prevariety having at most \ non-logical symbols and an axiomatization requiring at most \ variables, if the epimorphisms into structures with at most \ elements are surjective, then so are all of the epimorphisms. Using these facts, we formulate and prove manageable ‘bridge theorems’, matching the surjectivity of all epimorphisms in (...) the algebraic counterpart of a logic \ with suitable infinitary definability properties of \, while not making the standard but awkward assumption that \ comes furnished with a proper class of variables. (shrink)

The notion of contact algebra is one of the main tools in the region-based theory of space. It is an extension of Boolean algebra with an additional relation C, called contact. Standard models of contact algebras are topological and are the contact algebras of regular closed sets in a given topological space. In such a contact algebra we add the predicate of internal connectedness with the following meaning—a regular closed set is internally connected if and only if its interior is (...) a connected topological space in the subspace topology. We add also a ternary relation \ meaning that the intersection of the first two arguments is included in the third. In this paper the extension of a Boolean algebra with \, contact and internal connectedness, satisfying certain axioms, is called an extended contact algebra. We prove a representation theorem for extended contact algebras and thus obtain an axiomatization of the theory, consisting of the universal formulas, true in all topological contact algebras with added relations of internal connectedness and \. (shrink)

Motivated by the goal of constructing a model in which there are no κ-Aronszajn trees for any regular $k>\aleph_1$, we produce a model with many singular cardinals where both the singular cardinals hypothesis and weak square fail.

In this article we present a technique for selecting models of set theory that are complete in a model-theoretic sense. Specifically, we will apply Robinson infinite forcing to the collections of models of ZFC obtained by Cohen forcing. This technique will be used to suggest a unified perspective on generic absoluteness principles.

Every Berman’s variety \ which is the subvariety of Ockham algebras defined by the equation \ and \) determines a finitary substitution invariant consequence relation \. A sequent system \ is introduced as an axiomatization of the consequence relation \. The system \ is characterized by a single finite frame \ under the frame semantics given for the formal language. By the duality between frames and algebras, \ can be viewed as a \-valued logic as it is characterized by a (...) distributive lattice of \ elements with a unary operator. Moreover, a structural-rule-free, cut-free and terminating sequent system \ is established for \. The Craig interpolation property of \ is shown proof-theoretically utilizing \. (shrink)

We define a family of intuitionistic non-normal modal logics; they can be seen as intuitionistic counterparts of classical ones. We first consider monomodal logics, which contain only Necessity or Possibility. We then consider the more important case of bimodal logics, which contain both modal operators. In this case we define several interactions between Necessity and Possibility of increasing strength, although weaker than duality. We thereby obtain a lattice of 24 distinct bimodal logics. For all logics we provide both a Hilbert (...) axiomatisation and a cut-free sequent calculus, on its basis we also prove their decidability. We then define a semantic characterisation of our logics in terms of neighbourhood models containing two distinct neighbourhood functions corresponding to the two modalities. Our semantic framework captures modularly not only our systems but also already known intuitionistic non-normal modal logics such as Constructive K and the propositional fragment of Wijesekera’s Constructive Concurrent Dynamic Logic. (shrink)

We show that Martin Hyland's effective topos can be exhibited as the homotopy category of a path category EFF. Path categories are categories of fibrant objects in the sense of Brown satisfying two additional properties and as such provide a context in which one can interpret many notions from homotopy theory and Homotopy Type Theory. Within the path category EFF one can identify a class of discrete fibrations which is closed under push forward along arbitrary fibrations (in other words, this (...) class is polymorphic or closed under impredicative quantification) and satisfies propositional resizing. This class does not have a univalent representation, but if one restricts to those discrete fibrations whose fibres are propositions in the sense of Homotopy Type Theory, then it does. This means that, modulo the usual coherence problems, it can be seen as a model of the Calculus of Constructions with a univalent type of propositions. We will also build a more complicated path category in which the class of discrete fibrations whose fibres are sets in the sense of Homotopy Type Theory has a univalent representation, which means that this will be a model of the Calculus of Constructions with a univalent type of sets. (shrink)

It was shown recently that epimorphisms need not be surjective in a variety K of Heyting algebras, but only one counter-example was exhibited in the literature until now. Here, a continuum of such examples is identified, viz. the variety generated by the Rieger-Nishimura lattice, and all of its (locally finite) subvarieties that contain the original counter-example K . It is known that, whenever a variety of Heyting algebras has finite depth, then it has surjective epimorphisms. In contrast, we show that (...) for every integer $n \geq 2$ , the variety of all Heyting algebras of width at most n has a non-surjective epimorphism. Within the so-called Kuznetsov-Gerčiu variety (i.e., the variety generated by finite linear sums of one-generated Heyting algebras), we describe exactly the subvarieties that have surjective epimorphisms. This yields new positive examples, and an alternative proof of epimorphism surjectivity for all varieties of Gödel algebras. The results settle natural questions about Beth-style definability for a range of intermediate logics. (shrink)

In the first part of the article, we show that if $\omega \le \kappa < \lambda$ are cardinals, ${\kappa ^{ < \kappa }} = \kappa$, and λ is weakly compact, then in $V\left[M {\left} \right]$ the tree property at $$\lambda = \left^{V\left[ {\left} \right]} $$ is indestructible under all ${\kappa ^ + }$-cc forcing notions which live in $V\left[ {{\rm{Add}}\left} \right]$, where ${\rm{Add}}\left$ is the Cohen forcing for adding λ-many subsets of κ and $\left$ is the standard Mitchell forcing for (...) obtaining the tree property at $\lambda = \left^{V\left[ {\left} \right]} $. This result has direct applications to Prikry-type forcing notions and generalized cardinal invariants. In the second part, we assume that λ is supercompact and generalize the construction and obtain a model ${V^{\rm{*}}}$, a generic extension of V, in which the tree property at ${\left^{{V^{\rm{*}}}}}$ is indestructible under all ${\kappa ^ + }$-cc forcing notions living in $V\left[ {{\rm{Add}}\left} \right]$, and in addition under all forcing notions living in ${V^{\rm{*}}}$ which are ${\kappa ^ + }$-closed and “liftable” in a prescribed sense. (shrink)

Let κ be a cardinal of cofinality \omega_1 witnessed by a club of cardinals (κ_\alpha | \alpha < \omega_1) . We study Silver's type effects of collapsing of κ^+_\alphas 's on κ^+ . A model in which κ^+_\alphas 's (and also κ^+) are collapsed on a stationary co-stationary set is constructed.

This paper proposes a generalization of the Kripke semantics of intuitionistic logic IL appropriate for intuitionistic Łukasiewicz logic IŁL — a logic in the intersection between IL and (classical) Łukasiewicz logic. This generalised Kripke semantics is based on the poset sum construction, used in Bova and Montagna (Theoret Comput Sci 410(12):1143–1158, 2009) to show the decidability (and PSPACE completeness) of the quasiequational theory of commutative, integral and bounded GBL algebras. The main idea is that w \Vdash \sigma—which for IL is (...) a relation between worlds w and formulas \sigma, and can be seen as a function taking values in the booleans w \Vdash \sigma \in {B}—becomes a function taking values in the unit interval w \Vdash \sigma \in [0,1]. An appropriate monotonicity restriction (which we call sloping functions) needs to be put on such functions in order to ensure soundness and completeness of the semantics. (shrink)

We show that the theory Tlog of the asymptotic couple of the field of logarithmic transseries is distal. As distal theories are NIP, this provides a new proof that Tlog is NIP.

We define an easily verifiable notion of an atomic formula having uniformly bounded arrays in a structure M. We prove that if T is a complete L-theory, then T is mutually algebraic if and only if there is some model M of T for which every atomic formula has uniformly bounded arrays. Moreover, an incomplete theory T is mutually algebraic if and only if every atomic formula has uniformly bounded arrays in every model M of T.

In a recent article, Barrett & Halvorson define a notion of equivalence for first-order theories, which they call “Morita equivalence.” To argue that Morita equivalence is a reasonable measure of “theoretical equivalence,” they make use of the claim that Morita extensions “say no more” than the theories they are extending. The goal of this article is to challenge this central claim by raising objections to their argument for it and by showing why there is good reason to think that the (...) claim itself is false. In light of these criticisms, this article develops a natural way for the advocate of Morita equivalence to respond. I prove that this response makes her criterion a special case of bi-interpretability, an already well-established barometer of theoretical equivalence. I conclude by providing reasons why the advocate of Morita equivalence should opt for a notion of theoretical equivalence that is defined in terms of interpretability rather than Morita extensions. (shrink)

The variety DMM of De Morgan monoids has just four minimal subvarieties. The join-irreducible covers of these atoms in the subvariety lattice of DMM are investigated. One of the two atoms consisting of idempotent algebras has no such cover; the other has just one. The remaining two atoms lack nontrivial idempotent members. They are generated, respectively, by 4-element De Morgan monoids C4 and D4, where C4 is the only nontrivial 0-generated algebra onto which finitely subdirectly irreducible De Morgan monoids may (...) be mapped by noninjective homomorphisms. The homomorphic preimages of C4 within DMM constitute a proper quasivariety, which is shown to have a largest subvariety U. The covers of the variety within U are revealed here. There are just ten of them. In exactly six of these ten varieties, all nontrivial members have C4 as a retract. In the varietal join of those six classes, every subquasivariety is a variety—in fact, every finite subdirectly irreducible algebra is projective. Beyond U, all covers of [or of ] within DMM are discriminator varieties. Of these, we identify infinitely many that are finitely generated, and some that are not. We also prove that there are just 68 minimal quasivarieties of De Morgan monoids. (shrink)

In this study, we prove the completeness and cut-elimination theorems for a first-order extension F4CC of Arieli, Avron, and Zamansky’s ideal paraconsistent four-valued logic known as 4CC. These theorems are proved using Schütte’s method, which can simultaneously prove completeness and cut-elimination.

Pietruszczak :163–171, 2009. https://doi.org/10.12775/LLP.2009.013) proved that the normal logics \, \ ), \ are determined by suitable classes of simplified Kripke frames of the form \, where \. In this paper, we extend this result. Firstly, we show that a modal logic is determined by a class composed of simplified frames if and only if it is a normal extension of \. Furthermore, a modal logic is a normal extension of \ ; \; \) if and only if it is (...) determined by a set consisting of finite simplified frames ; such frames with \ or \; such frames with \). Secondly, for all normal extensions of \, \, \ and \, in particular for extensions obtained by adding the so-called “verum” axiom, Segerberg’s formulas and/or their T-versions, we prove certain versions of Nagle’s Fact :319–328, 1981. https://doi.org/10.2307/2273624) ). Thirdly, we show that these extensions are determined by certain classes of finite simplified frames generated by finite subsets of the set \ of natural numbers. In the case of extensions with Segerberg’s formulas and/or their T-versions these classes are generated by certain finite subsets of \. (shrink)

The purpose of this paper is to clarify the relationship between various conditions implying essential undecidability: our main result is that there exists a theory T in which all partially recursive functions are representable, yet T does not interpret Robinson’s theory R. To this end, we borrow tools from model theory — specifically, we investigate model-theoretic properties of the model completion of the empty theory in a language with function symbols. We obtain a certain characterization of ∃∀ theories interpretable in (...) existential theories in the process. (shrink)