Logic Workshop

In the 1980s, Henryk Kotlarski published a number of results about elementary cuts in countable recursively saturated models of arithmetic. I will outline some of Kotlarski's main results that motivated him to ask whether the lattice of elementary substructures of a countable recursively saturated model of PA depends on the model. I will outline the proof of a partial answer that Jim Schmerl and I gave a long time ago and I will follow with some new results related to modified versions of Kotlarski's question.

In my previous talk (Spring 26), I gave a tentative description of non-evil sentences in categories. When sorting out the details, I realized that this can be set within a much more abstract, model-theoretic framework. Given a first-order language $L$, a subset $\Lambda$ of $L$-formulas is a logic, if it is closed under conjunction, negation, quantification and term substitution. It turns out that many of the standard constructions carry over to these fragments: compactness of Stone spaces (although they can now be finite!), completions, and in particular, the analogue of a weak form of the Keisler-Shelah theorem: two structures satisfy the same $\Lambda$-sentences if an only if there is a map from one to an ultrapower of the other that preserves all $\Lambda$-formulas. Assume in addition that $L$ contains a binary predicate $E$ and only consider structures in which $E$ yields a congruence (equivalence) relation. Call two such structures equivalent if there are homomorphisms in either direction whose compositions are congruent (point-wise) to the identity map. Using this, we can now define the logic consisting of the so-called benign formulas. In particular, a sentence is benign if and only if equivalent structures agree on it. To derive some meaningful properties, we also need to assume that the quotient map, i.e., the map sending an element to its congruence class, is split. I'll give some examples, including the case of categories, where this machinery can be applied.

We show that every finite Boolean combination of polynomial equations and inequations over $\mathbb C$ is equivalent both to a $\forall\exists$ quantification of a single equation and to an $\exists\forall$ quantification of a single equation, in each case by an explicit construction using one quantifier of each type. Furthermore, neither a purely universal nor a purely existential prefix suffices, and different tradeoffs apply over $\mathbb R$ and $\mathbb Q$. In the language of complex exponentiation, we show that $\mathbb Q$ can be defined with $\exists$ and the conjunction of two exponential equations, but not by $\exists$ and a single such equation. We use these arguments to strengthen Boxall's special case of Zilber's quasiminimality conjecture. The constructions above also show that the full conjecture is equivalent to its subcase about quantified equations rather than quantified formulas.

Given a noncomputable c.e. set D, we can construct a computable structure $G$ such that any two computable copies of $G$ are computably isomorphic while there are two $D$-computable copies of $G$ that are not $D$-computably isomorphic. In other words, $G$ is computably categorical, but not computably categorical relative to $D$. Conversely, we construct a computable structure that is not computably categorical, but is computably categorical relative to $D$. These results differ from those in the literature regarding computable categoricity and its relativizations because the degree $D$ is given instead of constructed. In this talk, we discuss these results and some aspects of the construction regarding the former result.

We shall discuss the contingently contingent nature of the class $HOD$ of hereditarily ordinal- definable sets. In some models of set theory the axiom $V=HOD$ is contingent by set forcing and in others it is not. After discussing some philosophical and historical puzzles concerning the nature of ordinal definability, I shall introduce and investigate what we call the contingent $HOD$ dichotomy. Namely, it is provable in $ZFC$ that either (1) the set-theoretic universe $V$ is close to $HOD$ in several respects: $HOD$ is a ground model of $V$; the axiom $V=HOD$ is forceable by set forcing; every object is ordinal-definable with a single additional parameter; and furthermore all these things are forcing invariant and hold throughout the generic multiverse; or (2) the universe is far from $HOD$; in particular $V\neq HOD$; more generally, $HOD$ is not a ground; the axiom $V=HOD$ is not forceable; the universe is not ordinal-definable from a parameter; and these things hold invariantly throughout the generic multiverse. We shall explore how the dichotomy engages with large cardinals, with set-theoretic geology, with the maximality principles, and with Woodin's $HOD$ dichotomy. This is new joint work in progress with Bokai Yao (Peking University).