Logic Workshop

“What can one describe by first-order formulas in a given algebraic structure A?” - is an old and interesting question. Of course, this depends on the structure A. For example, in a free group only cyclic subgroups (and the group itself) are definable in the first-order logic, but in a free monoid of finite rank any finitely generated submonoid is definable. An algebraic structure A is called rich if the first-order logic in A is equivalent to the weak second order logic. Surprisingly, there are a lot of interesting groups, rings, semigroups, etc., which are rich. I will discuss some of them and then describe various algebraic, geometric, and algorithmic properties that are first-order definable in rich structures and apply these to some open problems. Weak second order logic can be introduced into algebraic structures in different ways: via HF-logic, or list superstructures over A, or computably enumerable infinite disjunctions and conjunctions, or via finite binary predicates, etc. I will describe a particular form of this logic which is especially convenient to use in algebra and show how to effectively translate such weak second order formulas into the equivalent first-order ones in the case of a rich structure A.

Video

​

Stationary logic was introduced in the 1970’s. It allows the quantifier 'for almost all countable subsets s…'. Although it is undoubtedly a kind of second order logic, it is completely axiomatizable, countably compact and satisfies a kind of Downward Lowenheim-Skolem theorem. In this talk I give first a general introduction to the extension of first order logic by this 'almost all'-quantifier. As 'almost all' is interpreted as 'for a club of', the theory of this logic is entangled with properties of stationary sets. I will give some examples of this. The main reason to focus on this logic in my talk is to use it to build an inner model of set theory. I will give a general introduction to this inner model, called C(aa), or the aa-model, and sketch a proof of CH in the model. My work on the aa-model is joint work with Juliette Kennedy and Menachem Magidor.

​

I shall introduce and consider the natural infinitary variations of Wordle, Absurdle, and Mastermind. Infinite Wordle extends the familiar finite game to infinite words and transfinite play—the code-breaker aims to discover a hidden codeword selected from a dictionary $\Delta\subseteq\Sigma^\omega$ of infinite words over a countable alphabet $\Sigma$ by making a sequence of successive guesswords, receiving feedback after each guess concerning its accuracy. For any dictionary using the usual 26-letter alphabet, for example, the code-breaker can win in at most 26 guesses, and more generally in $n$ guesses for alphabets of finite size $n$. Meanwhile, for some dictionaries on an infinite alphabet, infinite play is required, but the code-breaker can always win by stage $\omega$ on a countable alphabet, for any fixed dictionary. Infinite Mastermind, in contrast, is a subtler game than Wordle because only the number and not the position of correct bits is given. When duplication of colors is allowed, nevertheless, then the code-breaker can still always win by stage $\omega$, but in the no-duplication variation, no countable number of guesses (even transfinite) is sufficient for the code-breaker to win. I therefore introduce the mastermind number, denoted $\frak{mm}$, to be the size of the smallest winning no-duplication Mastermind guessing set, a new cardinal characteristic of the continuum, which I prove is bounded below by the additivity number $\text{add}(\mathcal{M})$ of the meager ideal and bounded above by the covering number $\text{cov}(\mathcal{M})$. In particular, the precise value of the mastermind number is independent of ZFC and can consistently be strictly between $\aleph_1$ and the continuum $2^{\aleph_0}$. In simplified Mastermind, where the feedback given at each stage includes only the numbers of correct and incorrect bits (omitting information about rearrangements), then the corresponding simplified mastermind number is exactly the eventually different number $\frak{d}(\neq^*)$. http://jdh.hamkins.org/infinite-wordle-and-the-mastermind-numbers-cuny-logic-workshop-march-2022/

​

A Hardy field is a differential field of germs at infinity of one-variable differentiable real-valued functions defined on half-lines. Hardy fields appear naturally in model theory and its applications to real analytic geometry and dynamical systems, and also have found uses in computer algebra, ergodic theory, and various other fields of mathematics. I will discuss some optimal extension results for Hardy fields obtained in the last few years, which lead to a description of the theory of maximal Hardy fields and applications to ordinary differential equations. (This is joint work with Lou van den Dries and Joris van der Hoeven.)

Video

​

We present two different elementary algebraic constructions that are as complicated as possible and whose complexity vastly exceeds those typically found in the elementary algebra literature. The first is the prime radical of a noncommutative ring, while the second is the radical of a module. These constructions contrast similar constructions in more familiar contexts that we will also mention along the way. We will spend most of our time describing how to construct radicals that are as complicated as possible from a computability point of view.

A Turing degree is low for isomorphism if whenever it can compute an isomorphism between two countably presented structures, there is already a computable isomorphism between them and thus there is no need to use the degree as an oracle at all. I will discuss the types of degrees that are low for isomorphism and the extent to which this class of degrees has the same properties as other lowness classes.

This work is joint with Reed Solomon.

In this talk we revisit the problem of describing the 'finer' structure of geometrically trivial strongly minimal sets in $DCF_0$. In particular, I will explain how recent work joint with Guy Casale and James Freitag on automorphic functions, has lead to intriguing questions around the $\omega$-categoricity conjecture. This conjecture was disproved in its full generality by James Freitag and Tom Scanlon using the modular $j$-function. I will explain how their counter-example fits into the larger context of arithmetic automorphic functions and has allowed us to 'propose' refinements to the original conjecture.

We prove that $\omega_1$ cannot be embedded into any preordering $\Sigma$-definable with parameters in the hereditarily finite superstructure over the ordered field of real numbers, HF(R). As corollaries, we obtain characterizations of $\Sigma$-presentable ordinals and Gödel constructive sets of kind $L_\alpha$. It also follows that there are no $\Sigma$-presentations for structures of $T$-, $m$-, $1$-, and $tt$-degrees over HF(R).

Our talk concerns axiomatic theories of truth predicates. They are theories obtained by adding to Peano Arithmetic (${\rm PA}$) a fresh predicate $T(x)$ with the intended reading '$x$ is (a code of) a true sentence in the language of arithmetic' together with some axioms governing newly added predicate.

The canonical example of such a theory is ${\rm CT}^-$ (Compositional Truth). Its axioms state that the truth predicate is compositional. For instance, a conjunction is true iff both conjuncts are. If we add to ${\rm CT}^-$ full induction in the extended language, we call the resulting theory ${\rm CT}$.

It is easy to check that ${\rm CT}$ is not conservative over ${\rm PA}$, i.e., it proves new arithmetical sentences. On the other hand, by a nontrivial theorem of Kotlarski, Krajewski, and Lachlan, ${\rm CT}^-$ extends ${\rm PA}$ conservatively.

In our talk, we will discuss results on the strength of theories between ${\rm CT}^-$ and ${\rm CT}$. It turns out that the natural axioms concerning purely truth theoretic properties of the newly added predicate (as opposed to axiom schemes which are consequences of induction in more general context) are typically either conservative or exactly equal to ${\rm CT}_0$, the theory of compositional truth with $\Delta_0$-induction. Thus ${\rm CT}_0$ turns out to be a surprisingly robust theory and, arguably, the minimal 'natural' non-conservative theory of truth.

The Wadge hierarchy was originally defined and studied only in the Baire space (and some other zero-dimensional spaces). We extend it to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces, which implies, e.g., several Hausdorff-Kuratowski-type theorems in quasi-Polish spaces. In fact, many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q.