The Guarded Negation Fragment (GNFO) is a fragment of first-order logic that contains all positive existential formulas, can express the first-order translations of basic modal logic and of many description logics, along with many sentences that arise in databases. It has been shown that the syntax of GNFO is restrictive enough so that computational problems such as validity and satisfiability are still decidable. This suggests that, in spite of its expressive power, GNFO formulas are amenable to novel optimizations. In this article we study the model theory of GNFO formulas. Our results include effective preservation theorems for GNFO, effective Craig Interpolation and Beth Definability results, and the ability to express the certain answers of queries with respect to a large class of GNFO sentences within very restricted logics.

A set $G \subseteq \omega$ is n-generic for a positive integer n if and only if every ${\rm{\Sigma }}_n^0$ formula of G is decided by a finite initial segment of G in the sense of Cohen forcing. It is shown here that every n-generic set G is properly ${\rm{\Sigma }}_n^0$ in some G-recursive X. As a corollary, we also prove that for every $n > 1$ and every n-generic set G there exists a G-recursive X which is generalized ${\rm{lo}}{{\rm{w}}_n}$ but not generalized ${\rm{lo}}{{\rm{w}}_{n - 1}}$. Thus we confirm two conjectures of Jockusch [4].

In the framework of Bishop’s constructive mathematics we introduce co-convexity as a property of subsets B of ${\left\{ {0,1} \right\}^{\rm{*}}}$, the set of finite binary sequences, and prove that co-convex bars are uniform. Moreover, we establish a canonical correspondence between detachable subsets B of ${\left\{ {0,1} \right\}^{\rm{*}}}$ and uniformly continuous functions f defined on the unit interval such that B is a bar if and only if the corresponding function f is positive-valued, B is a uniform bar if and only if f has positive infimum, and B is co-convex if and only if f satisfies a weak convexity condition.

We consider definable topological dynamics for NIP groups admitting certain decompositions in terms of specific classes of definably amenable groups. For such a group, we find a description of the Ellis group of its universal definable flow. This description shows that the Ellis group is of bounded size. Under additional assumptions, it is shown to be independent of the model, proving a conjecture proposed by Newelski. Finally we apply the results to new classes of groups definable in o-minimal structures, generalizing all of the previous results for this setting.

We provide algebraic conditions ensuring the decidability of the theory of modules over effectively given Prüfer (in particular Bézout) domains with infinite residue fields in terms of a suitable generalization of the prime radical relation. For Bézout domains these conditions are also necessary.

Analysability of finite U-rank types are explored both in general and in the theory ${\rm{DC}}{{\rm{F}}_0}$. The well-known fact that the equation $\delta \left( {{\rm{log}}\,\delta x} \right) = 0$ is analysable in but not almost internal to the constants is generalized to show that $\underbrace {{\rm{log}}\,\delta \cdots {\rm{log}}\,\delta }_nx = 0$ is not analysable in the constants in $\left( {n - 1} \right)$-steps. The notion of a canonical analysis is introduced–-namely an analysis that is of minimal length and interalgebraic with every other analysis of that length. Not every analysable type admits a canonical analysis. Using properties of reductions and coreductions in theories with the canonical base property, it is constructed, for any sequence of positive integers $\left( {{n_1}, \ldots ,{n_\ell }} \right)$, a type in ${\rm{DC}}{{\rm{F}}_0}$ that admits a canonical analysis with the property that the ith step has U-rank ${n_i}$.

We introduce the notion of infinitary interpretation of structures. In general, an interpretation between structures induces a continuous homomorphism between their automorphism groups, and furthermore, it induces a functor between the categories of copies of each structure. We show that for the case of infinitary interpretation the reversals are also true: every Baire-measurable homomorphism between the automorphism groups of two countable structures is induced by an infinitary interpretation, and every Baire-measurable functor between the set of copies of two countable structures is induced by an infinitary interpretation. Furthermore, we show that the complexities are maintained in the sense that if the functor is ${\bf{\Delta }}_\alpha ^0$, then the interpretation that induces it is ${\rm{\Delta }}_\alpha ^{in}$ up to ${\bf{\Delta }}_\alpha ^0$ equivalence.

We explore the structural properties of the inner model L(Vδ+1) under the assumption that δ is a singular limit of Berkeley cardinals each of which is itself limit of extendible cardinals, lifting some of the main results of the theory of the axiom I0 to the level of Berkeley cardinals, the strongest known large cardinal axioms. Berkeley cardinals have been recently introduced in [1] and contradict the Axiom of Choice.1 In fact, our background theory will be ZF.

We give an example of a dense o-minimal structure in which there is a definable quotient that cannot be eliminated, even after naming parameters. Equivalently, there is an interpretable set which cannot be put in parametrically definable bijection with any definable set. This gives a negative answer to a question of Eleftheriou, Peterzil, and Ramakrishnan. Additionally, we show that interpretable sets in dense o-minimal structures admit definable topologies which are “tame” in several ways: (a) they are Hausdorff, (b) every point has a neighborhood which is definably homeomorphic to a definable set, (c) definable functions are piecewise continuous, (d) definable subsets have finitely many definably connected components, and (e) the frontier of a definable subset has lower dimension than the subset itself.

Simpson [6] showed that every countable model ${\cal M} \models PA$ has an expansion $\left( {{\cal M},X} \right) \models P{A^{\rm{*}}}$ that is pointwise definable. A natural question is whether, in general, one can obtain expansions of a nonprime model in which the definable elements coincide with those of the underlying model. Enayat [1] showed that this is impossible by proving that there is ${\cal M} \models PA$ such that for each undefinable class X of ${\cal M}$, the expansion $\left( {{\cal M},X} \right)$ is pointwise definable. We call models with this property Enayat models. In this article, we study Enayat models and show that a model of $PA$ is Enayat if it is countable, has no proper cofinal submodels and is a conservative extension of all of its elementary cuts. We then show that, for any countable linear order γ, if there is a model ${\cal M}$ such that $Lt\left( {\cal M} \right) \cong \gamma$, then there is an Enayat model ${\cal M}$ such that $Lt\left( {\cal M} \right) \cong \gamma$.

With the help of various square principles, we obtain results concerning the consistency strength of several statements about trees containing ascent paths, special trees, and strong chain conditions. Building on a result that shows that Todorčević’s principle $\square \left( {\kappa ,\lambda } \right)$ implies an indexed version of $\square \left( {\kappa ,\lambda } \right)$, we show that for all infinite, regular cardinals $\lambda < \kappa$, the principle $\square \left( \kappa \right)$ implies the existence of a κ-Aronszajn tree containing a λ-ascent path. We then provide a complete picture of the consistency strengths of statements relating the interactions of trees with ascent paths and special trees. As a part of this analysis, we construct a model of set theory in which ${\aleph _2}$-Aronszajn trees exist and all such trees contain ${\aleph _0}$-ascent paths. Finally, we use our techniques to show that the assumption that the κ-Knaster property is countably productive and the assumption that every κ-Knaster partial order is κ-stationarily layered both imply the failure of $\square \left( \kappa \right)$.

We prove a variation of Easton’s lemma for strongly proper forcings, and use it to prove that, unlike the stronger principle IGMP, GMP together with 2ω ≤ ω2 is consistent with the existence of an ω1-distributive nowhere c.c.c. forcing poset of size ω1. We introduce the idea of a weakly guessing model, and prove that many of the strong consequences of the principle GMP follow from the existence of stationarily many weakly guessing models. Using Namba forcing, we construct a model in which there are stationarily many indestructibly weakly guessing models which have a bounded countable subset not covered by any countable set in the model.

Profinite algebras are exactly those that are isomorphic to inverse limits of finite algebras. Such algebras are naturally equipped with Boolean topologies. A variety ${\cal V}$ is standard if every Boolean topological algebra with the algebraic reduct in ${\cal V}$ is profinite.

We show that there is no algorithm which takes as input a finite algebra A of a finite type and decide whether the variety $V\left( {\bf{A}} \right)$ generated by A is standard. We also show the undecidability of some related properties. In particular, we solve a problem posed by Clark, Davey, Freese, and Jackson.

We accomplish this by combining two results. The first one is Moore’s theorem saying that there is no algorithm which takes as input a finite algebra A of a finite type and decides whether $V\left( {\bf{A}} \right)$ has definable principal subcongruences. The second is our result saying that possessing definable principal subcongruences yields possessing finitely determined syntactic congruences for varieties. The latter property is known to yield standardness.

I construct, in ZFC, a forcing notion that collapses $\aleph _3 $ and preserves all other cardinals. The existence of such a forcing answers a question of Uri Abraham from 1983.

Givant [6] generalized the notion of an atomic pair-dense relation algebra from Maddux [13] by defining the notion of a measurable relation algebra, that is to say, a relation algebra in which the identity element is a sum of atoms that can be measured in the sense that the “size” of each such atom can be defined in an intuitive and reasonable way (within the framework of the first-order theory of relation algebras). In Andréka--Givant [2], a large class of examples of such algebras is constructed from systems of groups, coordinated systems of isomorphisms between quotients of the groups, and systems of cosets that are used to “shift” the operation of relative multiplication. In Givant--Andréka [8], it is shown that the class of these full coset relation algebras is adequate to the task of describing all measurable relation algebras in the sense that every atomic and complete measurable relation algebra is isomorphic to a full coset relation algebra.

Call an algebra $\mathfrak{A}$ a coset relation algebra if $\mathfrak{A}$ is embeddable into some full coset relation algebra. In the present article, it is shown that the class of coset relation algebras is equationally axiomatizable (that is to say, it is a variety), but that no finite set of sentences suffices to axiomatize the class (that is to say, the class is not finitely axiomatizable).

In this article, we will show that ${\rm{R}}{{\rm{T}}^2} + WK{L_0}$ is a ${\rm{\Pi }}_1^1$-conservative extension of ${\rm{B\Sigma }}_3^0$.

We study universal minimal flows of the homeomorphism groups of generalized Ważewski dendrites WP, $P \subseteq \left\{ {3,4, \ldots ,\omega } \right\}$. If P is finite, we prove that the universal minimal flow of the homeomorphism group H (WP) is metrizable and we compute it explicitly. This answers a question of Duchesne. If P is infinite, we show that the universal minimal flow of H (WP) is not metrizable. This provides examples of topological groups which are Roelcke precompact and have a nonmetrizable universal minimal flow with a comeager orbit.

Shelah has provided sufficient conditions for an ${\Bbb L}_{\omega _1 ,\omega } $-sentence ψ to have arbitrarily large models and for a Morley-like theorem to hold of ψ. These conditions involve structural and set-theoretic assumptions on all the ${\aleph _n}$’s. Using tools of Boney, Shelah, and the second author, we give assumptions on ${\aleph _0}$ and ${\aleph _1}$ which suffice when ψ is restricted to be universal:

Theorem.Assume${2^{{\aleph _0}}} < {2^{{\aleph _1}}}$. Let ψ be a universal ${\Bbb L}_{\omega _1 ,\omega } $-sentence.

1. (1) If ψ is categorical in${\aleph _0}$and$1 \leqslant {\Bbb L}\left( {\psi ,\aleph _1 } \right) < 2^{\aleph _1 } $, then ψ has arbitrarily large models and categoricity of ψ in some uncountable cardinal implies categoricity of ψ in all uncountable cardinals.

2. (2) If ψ is categorical in${\aleph _1}$, then ψ is categorical in all uncountable cardinals.

The theorem generalizes to the framework of ${\Bbb L}_{\omega _1 ,\omega } $-definable tame abstract elementary classes with primes.

Previous results about n-grids with acceptable colorings are extended here to n-indexed hyperspaces, which are structures ${\cal A} = \left( {A;{E_0},{E_1}, \ldots ,{E_{n - 1}}} \right)$, where each ${E_i}$ is an equivalence relation on A.

Let ${\cal E}$ be a topos, ${\rm{Dec}}\left( {\cal E} \right) \to {\cal E}$ be the full subcategory of decidable objects, and ${{\cal E}_{\neg \,\,\neg }} \to {\cal E}$ be the full subcategory of double-negation sheaves. We give sufficient conditions for the existence of a Unity and Identity ${\cal E} \to {\cal S}$ for the two subcategories of ${\cal E}$ above, making them Adjointly Opposite. Typical examples of such ${\cal E}$ include many ‘gros’ toposes in Algebraic Geometry, simplicial sets and other toposes of ‘combinatorial’ spaces in Algebraic Topology, and certain models of Synthetic Differential Geometry.