Journal of Mathematical Logic

This paper is about omitting types in logic of metric structures introduced by Ben Yaacov, Berenstein, Henson and Usvyatsov. While a complete type is omissible in some model of a countable complete theory if and only if it is not principal, this is not true for the incomplete types by a result of Ben Yaacov. We prove that there is no simple test for determining whether a type is omissible in a model of a theory $T$ in a countable language. More precisely, we find a theory in a countable language such that the set of types omissible in some of its models is a complete ${\mathrm{\Sigma }}_2^1$ set and a complete theory in a countable language such that the set of types omissible in some of its models is a complete ${\mathrm{\Pi }}_1^1$ set. Two more unexpected examples are given: (i) a complete theory $T$ and a countable set of types such that each of its finite sets is jointly omissible in a model of $T$, but the whole set is not and (ii) a complete theory and two types that are separately omissible, but not jointly omissible, in its models.

We construct a nontrivial definable type V field topology on any dp-minimal field $K$ that is not strongly minimal, and prove that definable subsets of $K^n$ have small boundary. Using this topology and its properties, we show that in any dp-minimal field $K$, dp-rank of definable sets varies definably in families, dp-rank of complete types is characterized in terms of algebraic closure, and $|K^{\times }/{(K^{\times })}^n|$ is finite for all $n\ge 0$. Additionally, by combining the existence of the topology with results of Jahnke, Simon and Walsberg [Dp-minimal valued fields, J. Symbolic Logic 82(1) (2017) 151–165], it follows that dp-minimal fields that are neither algebraically closed nor real closed admit nontrivial definable Henselian valuations. These results are a key stepping stone toward the classification of dp-minimal fields in [Fun with fields, Ph.D. thesis, University of California, Berkeley (2016)].

We construct a model $M$ of $\mathrm{\text{ZF}}$ which lies between $L$ and $L[c]$ for a Cohen real $c$ and does not have the form $L(x)$ for any set $x$. This is loosely based on the unwritten work done in a Bristol workshop about Woodin’s HOD Conjecture in 2011. The construction given here allows for a finer analysis of the needed assumptions on the ground models, thus taking us one step closer to understanding models of $\mathrm{\text{ZF}}$, and the HOD Conjecture and its relatives. This model also provides a positive answer to a question of Grigorieff about intermediate models of $\mathrm{\text{ZF}}$, and we use it to show the failure of Kinna–Wagner Principles in $\mathrm{\text{ZF}}$.

We initiate a systematic investigation of the abstract elementary classes that have amalgamation, satisfy tameness (a locality property for orbital types), and are stable (in terms of the number of orbital types) in some cardinal. Assuming the singular cardinal hypothesis (SCH), we prove a full characterization of the (high-enough) stability cardinals, and connect the stability spectrum with the behavior of saturated models.

We deduce (in ZFC) that if a class is stable on a tail of cardinals, then it has no long splitting chains (the converse is known). This indicates that there is a clear notion of superstability in this framework.

We also present an application to homogeneous model theory: for $D$ a homogeneous diagram in a first-order theory $T$, if $D$ is both stable in $\left|T\right|$ and categorical in $\left|T\right|$ then $D$ is stable in all $\lambda \ge \left|T\right|$.

A computable structure ${𝒜}$ is decidable if, given a formula $\phi (\bar{x})$ of elementary first-order logic, and a tuple $ā\in {𝒜}$, we have a decision procedure to decide whether $\phi$ holds of $ā$. We show that there is no reasonable classification of the decidably presentable structures. Formally, we show that the index set of the computable structures with decidable presentations is ${\mathrm{\Sigma }}_1^1$-complete. We also show that for each $n$ the index set of the computable structures with $n$-decidable presentations is ${\mathrm{\Sigma }}_1^1$-complete.

We prove that consistently the Lebesgue null ideal is not Tukey reducible to the Silver null ideal. This contrasts with the situation for the meager ideal which, by a recent result of the author, Spinas [Silver trees and Cohen reals, Israel J. Math. 211 (2016) 473–480] is Tukey reducible to the Silver ideal.

The feasible interpolation theorem for semantic derivations from [J. Krajíček, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic 62(2) (1997) 457–486] allows to derive from some short semantic derivations (e.g. in resolution) of the disjointness of two $\mathrm{\text{NP}}$ sets $U$ and $V$ a small communication protocol (a general dag-like protocol in the sense of Krajíček (1997) computing the Karchmer–Wigderson multi-function $KW[U,V]$ associated with the sets, and such a protocol further yields a small circuit separating $U$ from $V$. When $U$ is closed upwards, the protocol computes the monotone Karchmer–Wigderson multi-function $K{W}^m[U,V]$ and the resulting circuit is monotone. Krajíček [Interpolation by a game, Math. Logic Quart. 44(4) (1998) 450–458] extended the feasible interpolation theorem to a larger class of semantic derivations using the notion of a real communication complexity (e.g. to the cutting planes proof system CP). In this paper, we generalize the method to a still larger class of semantic derivations by allowing randomized protocols. We also introduce an extension of the monotone circuit model, monotone circuits with a local oracle (CLOs), that does correspond to communication protocols for $K{W}^m[U,V]$ making errors. The new randomized feasible interpolation thus shows that a short semantic derivation (from a certain class of derivations larger than in the original method) of the disjointness of $U,V$, $U$ closed upwards, yields a small randomized protocol for $K{W}^m[U,V]$ and hence a small monotone CLO separating the two sets. This research is motivated by the open problem to establish a lower bound for proof system $\mathrm{\text{R(LIN}}/{\mathrm{\text{F}}}_2)$ operating with clauses formed by linear Boolean functions over ${\mathrm{\text{F}}}_2$. The new randomized feasible interpolation applies to this proof system and also to (the semantic versions of) cutting planes CP, to small width resolution over CP of Krajíček [Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic 63(4) (1998) 1582–1596] (system R(CP)) and to random resolution RR of Buss, Kolodziejczyk and Thapen [Fragments of approximate counting, J. Symbolic Logic 79(2) (2014) 496–525]. The method does not yield yet lengths-of-proofs lower bounds; for this it is necessary to establish lower bounds for randomized protocols or for monotone CLOs.