Logic Workshop

'Classifying' a natural collection of structures is a common goal in mathematics. Providing a classification can mean different things, e.g., identifying a set of invariants that settle the isomorphism problem or creating a list of all structures of a given kind without repetition of isomorphism type. Here we discuss recent work on classifications of the latter kind from the perspective of computable structure theory. We’ll consider natural classes of computable structures such as vector spaces, equivalence relations, algebraic fields, and trees to better understand the nuances of classification via effective lists and its relationship to other forms of classification in this setting.

Video

​

Video

​

Cardinal invariants of the continuum are cardinal numbers which, roughly, measure how 'badly' CH fails in various mathematical contexts such as analysis and topology. For instance the cardinal ${\rm add}(\mathcal N)$ is the least $\kappa$ for which there are $\kappa$ many Lebesgue measure zero sets of reals whose union is not measure zero. Classical facts imply $\aleph_1 \leq {\rm add}(\mathcal N) \leq 2^{\aleph_0}$ but the precise value is undetermined in ZFC and depends heavily on the axioms of set theory. Other numbers follow a similar pattern of 'the least size of a set of reals (Borel sets, etc) lacking a classical smallness property'.

The Cichoń diagram displays cardinal invariants related to Lebesgue measure (the null ideal), Baire category (the meager ideal) as well as the bounding and dominating numbers which concern growth rates of functions. Many surprising ZFC-inequalities exist between these cardinals suggesting a rich world living on the reals in various models of set theory. At the combinatorial heart of every proof of a ZFC inequality derives from a Galois-Tukey reduction: the (ZFC-provable) existence of a pair of continuous maps with simple properties that make sense outside of the context of logic and indeed would be sensible to any analyst or topologist.

In this talk we will discuss some recent work in progress on the descriptive complexity of maps witnessing consistent but non-provable implications. We will show using largely computability theoretic methods that in Gödel's constructible universe there are low level projective reductions between any two cardinal invariants - thus CH holds in a very 'definable' way, while in Solovay's model of 'all sets of reals are Lebesgue measurable' (and therefore the axiom of choice fails) there are no non-ZFC provable implications thus these cardinals are all as different as possible.

Video

​

Second-order arithmetic has two types of objects: numbers and sets of numbers, which we think of as the reals. The second-order arithmetic framework has been used successfully to investigate what kinds of real numbers need to exist to prove various significant results in analysis. One of the strongest second-order arithmetic axiomatizations is the theory ${\rm Z}_2$ consisting of the axioms ${\rm PA}$ (for numbers), the set induction axiom, and comprehension for all second-order formulas with set parameters. How significant is the inclusion of set parameters in the comprehension scheme? Let ${\rm Z}_2^{-p}$ be like ${\rm Z}_2$, but where set parameters are not allowed in the comprehension scheme. Harvey Friedman showed that ${\rm Z}_2$ and ${\rm Z}_2^{-p}$ are equiconsistent because parameter-free comprehension suffices to build a model's version of the constructible universe $L$ inside the model and the 'constructible' reals satisfy ${\rm Z}_2$. Kanovei recently showed that models of ${\rm Z}_2^{-p}$ can be very badly behaved, for example, their sets may not even be closed under complement. Kanovei also showed that there can be nicely behaved models of ${\rm Z}_2^{-p}$ in which $\Sigma^1_2$-comprehension (with set parameters) holds. He constructed his model in a forcing extension by a tree iteration of Sacks forcing. In Kanovei's model, $\Sigma^1_4$-comprehension (with set parameters) fails and he asked whether this can be improved to $\Sigma^1_3$-comprehension. In this talk, I will show how to construct a model of $\Sigma^1_2$-comprehension and ${\rm Z}_2^{-p}$ in which $\Sigma^1_3$-comprehension fails. The model will be constructed in a forcing extension by a tree iteration of Jensen's forcing. Jensen's forcing is a sub-poset of Sacks forcing constructed by Jensen to show that it is consistent to have a non-constructible $\Pi^1_2$-definable singleton real (every $\Sigma^1_2$-definable set of reals is constructible by Shoenfield's Absoluteness).

Video

​

The theory of countable Borel equivalence relations analyzes the actions of countable groups on Polish spaces. The main question studied is how much information is encoded by the corresponding orbit space. The amount of encoded information reflects the extent to which the action is rigid.

In this talk we will discuss rigidity results for the action of the group of rational rotations. In particular we will analyze the rotation equivalence on spheres in higher dimension. This is connected to superrigidity results of Margulis and to Zimmer’s program about the actions of discrete subgroups of Lie groups on manifolds.

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.

Video

​

When Gromov asked 'What is a typical group?', he was thinking of finitely presented groups, and he proposed an approach involving limiting density. Here, we reframe this question in the context of universal algebra and discuss some examples illustrating the behaviors of some of these algebraic varieties and then general conditions that imply some of these behaviors. Our primary general result states that for a commutative generalized bijective variety and presentations with a single generator and single identity, the zero-one law holds and, furthermore, that the sentences with density 1 are those true in the free structure. The proof of this result requires a specialized version of Gaifman's Locality Theorem that enables us to get a better bound on the complexity of the formulas of interest to us.

This work is joint with Meng-Che 'Turbo' Ho and Julia Knight.

Video

​

Fix a computable presentation $\overline{\mathbb Q}$ of the algebraic closure of the rational numbers. The absolute Galois group of the rational numbers, which is precisely the automorphism group of the field $\overline{\mathbb Q}$, may then be viewed as a collection of paths through a finite-branching tree. Each individual automorphism has a Turing degree. We will use known results in computability to try to build natural countable elementary subgroups of the absolute Galois group. Several intriguing questions in number theory will appear as we measure the extent to which we succeed in doing so.

Video

​

It is well known that a countable model of PA has a truth predicate if and only if it is recursively saturated. It is also well known that not all countable recursively saturated models of PA have *inductive* or even $\Delta_0$-inductive truth predicates: indeed, such models must satisfy Con(PA), for example. Recent work by Enayat-Pakhomov and Cieśliński-Łełyk-Wcisło explored the principle of 'disjunctive correctness', asserting that every disjunction is true if and only if it has a true disjunct. In particular, one can show that every countable model of PA has a 'disjunctively trivial' elementary extension: that is, an elementary extension with a truth predicate in which all nonstandard length disjunctions are evaluated as true. In this talk, we will see that such 'disjunctively trivial' models are necessarily arithmetically saturated; indeed, we will see that a countable model of PA is arithmetically saturated if and only if it has a disjunctively trivial truth predicate. We will explore related pathologies in truth predicates, and classify the sets which can be defined using such pathologies. We find other surprising connections between arithmetic saturation and these questions of definability. This is joint work with Mateusz Łełyk, based heavily on unpublished work by Jim Schmerl.

Video

​

I call a subset of the domain of a countable model absolutely undefinable if the set of its images under automorphisms of the model is uncountable. By the Kueker-Reyes theorem, all sets that are not absolutely undefinable are parametrically definable in $L_{\omega_1 \omega}$. I will survey classical results about first-order undefinability in the standard model of arithmetic, and I will contrast them with some old and some new results about absolute undefinability in nonstandard models of PA.​

Video

​