Logic Workshop

The model theory of fields with automorphisms began with ACFA, where the field has one named automorphism or, equivalently, a named action by the group $(\mathbb{Z}, +)$. Some other groups acting on fields also produce nice theories: free groups, finite groups, subgroups of $(\mathbb{Q}, +)$. Some, such as free abelian groups on two or more generators, do not. This talk will survey these results.

Abstract

Definition: A collection $\mathcal F$ of forbidden subgraphs is a Rado family if the class of countable $\mathcal F$-free graphs contains a universal structure with respect to embeddings as induced subgraphs. (By 'forbidden' I mean forbidden as subgraphs; usage varies in the literature.)

We consider the following decision problem for Rado families.

Problem: Given a finite set $\mathcal F$ of finite, connected graphs, determine whether or not it is a Rado family.

Question: Is this a decidable problem?

If we specialize to the sake of a single constraint then we speak instead of a Rado constraint. Much is known, and much more conjectured, about the case of a single constraint.

Conjecture: The decision problem for the case of a single constraint is decidable.

Discussion

From the model theoretic side, a finite collection of forbidden subgraphs specifies a universal theory with some special properties: notably, there is a model companion. When we restrict to families of connected constraints, the theory has joint embedding and the model companion is complete. In model theoretic terms the question becomes whether the model companion has a countable universal model with respect to elementary embedding, for which a purely type theoretic criterion is known.

Decision problems for other model theoretic properties of the model companion are natural. We have focused on this one because the question came to us from graph theory. However, even in that form, two variants are relevant.

• Can we decide whether the model companion is $\aleph_0$-categorical?
• Dropping the connectedness hypothesis on the constraints, can we decide whether the model companion is complete?

The main source of positive answers to the universality problem appears to be the $\aleph_0$-categorical case, and this has some theoretical justification. The most direct route to understanding the original graph theoretical problem appears to take the detour through $\aleph_0$-categoricity.

As time allows, I would like to discuss the following three points.

• What we know, and what we expect, in the case of a single constraint;
• Methods of proof (algebraic closure; induction by pruning);
• The status of the decision problem for j.e.p. and its analog in the theory of permutation pattern classes (work of Braunfeld).

This is joint work with Shelah, e.g. [Sh689].

A Turing computable embedding is a Turing operator that maps one class of structures to another so as to preserve isomorphism. The embedding codes the input structure in the output structure. It is interesting when there is an effective decoding. It is also interesting when the decoding is very difficult. Recently, Harrison-Trainor, Melnikov, R. Miller, and Montalbán have defined very general notions of interpretation, in which the interpreting formulas have no fixed arity. Uniformly defined interpretations give us decoding. I will discuss some known Turing computable embeddings, looking for uniform interpretations that yield effective, or Borel, decoding.

1. Marker's embedding of directed graphs in undirected graphs,
2. Mal'tsev's embedding of fields in groups,
3. Friedman and Stanley's embedding of graphs in linear orderings.

The first two embeddings come with uniform 'effective' interpretations, which give uniform effective decoding. For the third, we do not even have uniform interpretation via $L_{\omega_1\omega}$ formulas.

Ramsey's Theorem for pairs and 2 colors says that for every 2-coloring, $C$, of pairs of natural numbers, there is an infinite set $H$, such that all pairs from $H$ have the same constant color. $H$ is called a homogeneous set for $C$. We will also consider Ramsey's Theorem in other settings. For example, we can be given countably many $1$-colorings of natural numbers, $\{c_i\}$, and ask for a set $C$ such that, for each $i$, all but finitely many elements of $C$ have the same color with respect to $c_i$. Call $C$ a cohesive set for $\{c_i\}$. Among the questions we will explore here is what can be computed from homogeneous sets. For example, given countably many $1$-colorings $\{c_i\}$, is there a 2-coloring $C$, such that every homogeneous set for $C$ computes a cohesive set for $\{c_i\}$?

We will introduce the notions of virtual conditions and balanced conditions in definable partial orders, and apply these ideas to forcing extensions of the Solovay model. We will present a variety of independence results, and some ZF implications, for weak forms of the Axiom of Choice, and discuss related issues concerning the preservation of cardinals and chromatic numbers. Some of these results can be stated more generally using a natural classification of definable partial orders in terms of amalgamation properties.

We consider three variations of the Löwenheim-Skolem Theorem type statements on stationary logics. These statements imply respectively that the size of the continuum is $\aleph_1$, $\aleph_2$ or very big (e.g. hyper, hyper, ... weakly Mahlo).

We also consider reflection principles in terms of games and strengthenings of generic supercompactness which are related to these three Löwenheim-Skolem Theorems for stationary logics.

We consider effective Mathias forcing over a countable Turing ideal. In particular, we show that a Mathias generic constructed with conditions from a countable ideal $\mathcal{I}$ need not compute a Mathias generic over every smaller ideal $\mathcal{J} \subseteq \mathcal{I}$, answering a question of Cholak, Dzhafarov, and Soskova. This is joint work with Henry Towsner and Dan Turetsky.

Generic elementary embeddings have many applications throughout set theory. For example, Solovay's original proof that every stationary subset of a regular uncountable cardinal $\kappa$ can be partitioned into $\kappa$ disjoint stationary sets involves the use of a generic ultrapower embedding obtained by forcing with the nonstationary ideal. The generic ultrapower construction leads naturally to a characterization of the nonstationary ideal on a regular uncountable cardinal $\textrm{NS}_\kappa$ in terms of generic elementary embeddings. We will show that this characterization can be generalized to various ideals associated to large cardinals. Specifically, we will discuss characterizations of the $\Pi^m_n$-indescribability ideals, the subtle ideal and the ineffability ideal in terms of generic elementary embeddings as well as potential applications.

Given a countable transitive model of set theory and a notion of forcing in it, there is a natural countable Borel equivalence relation on generic objects over the model; two generics are equivalent if they yield the same generic extension. We study generic reals arising from familiar notions of forcing, e.g., Cohen and random forcing, under this equivalence relation and describe their relative complexity using the techniques of invariant descriptive set theory.

A sequence of random variables is exchangeable when its distribution is invariant to reorderings of the sequence. This notion of symmetry and its generalizations to arrays, graphs, and other structures, arise in many statistical contexts. Representation theorems due to de Finetti, Aldous-Hoover, and others, describe how exchangeable structures can be written in a way that exposes conditional independence, which is often important for computational purposes. However, these results are not obviously computable. We will present several positive and negative results examining the computable content of these theorems, and will also describe several implications for the design of probabilistic programming languages. Joint work with Nathanael Ackerman, Jeremy Avigad, Daniel Roy, and Jason Rute.​

In 1959, MacDowell and Specker proved that every model of Peano Arithmetic has an elementary end extension. Since then, the theorem has been a constant source of new results, as well as a subject of extensions and generalizations. I will give a quick survey of those developments, including some very recent results.

In this talk, I will discuss the relative complexity of the isomorphism and bi-embeddability relations for various classes of countable abelian groups from the point of view of descriptive set theory. This is joint work with Filippo Calderoni.