# Harvard/MIT Logic Seminar

### Spring 2013 Monday 4:30 – 5:30 pm Science Center Room 507 Harvard University (unless otherwise noted)

Organizers: Nate Ackerman, Rachel Epstein, Cameron Freer, and Rehana Patel.

### Schedule

Algebraic Dynamics, Number Theory, and Model Theory

Model Theory, a branch of mathematical logic, is a new and useful way to approach number-theoretic conjectures about "special points" and "special subvarieties", such as the Manin-Mumford Conjecture. Algebraic Dynamics, the study of discrete dynamical systems in the category of algebraic geometry, supplies natural generalizations of these conjectures. We use model-theoretic ideas to settle some cases of these dynamical generalizations of number-theoretic conjectures.

Our key result is a complete characterization of invariant subvarieties for coordinate-wise polynomial dynamical systems on affine space, in characteristic zero. That is, we work over a field $K$ of characteristic zero (such as the complex numbers) and study the iteration of a function
$F(x_1, x_2, ... x_n) = ( f_1(x_1), f_2(x_2), ... f_n(x_n) )$
for some univariate polynomials $f_i$ over $K$. Model-theoretic ideas reduce the question of invariant subvarieties in cartesian powers of $K$ to the question of invariant curves in $K\times K$. Refining Ritt's Theorem about composition of polynomials allows us to classify these invariant plane curves.

Our classification implies that, barring obvious obstructions from linear $f_i$, such dynamical systems always have $K$-rational points with Zariski-dense forward orbits, a generalization of a case of Zhang's Conjecture. We also prove the dynamical analog of the Manin-Mumford conjecture for the very special case when all $f_i$ are defined over the integers, and for some prime $p$ all $f_i$ are congruent to $x^p$ modulo $p$.

Extensions of Levy-Shoenfield Absoluteness

0-1 Laws for Fragments of Second-Order Logic

FITTMs, $\Sigma^0_3$ Determinacy, and nested $\Sigma_2$ Reflection

Infinite Time Turing Machines are a generalization of classical computability into the transfinite. They are so powerful that the tools of admissible set theory are needed to analyze their strength. Feedback ITTMs are a further extension, which demand for their analysis notions of determinacy, reflection, and non-standard models. I will sketch the theory involved, leading up to the big open conjecture of this topic.

A Random Walk Through Some First Order 0-1 Laws [Patel]

A class of finite structures has a 'first order zero-one law' if any first order property holds asymptotically almost surely, or almost never, in that class. In this talk we will focus on first order zero-one laws for classes of graphs that have a fixed finite forbidden subgraph. We will provide a partial catalog, outline some conjectures, and describe approaches to resolving them.

Computability of 0-1 Laws [Ackerman]

In this talk we will consider the abstract operator which takes a complete first order theory $T$ and returns the collection of sentences which are asymptotically almost surely true of all finite substructures of models of $T$.

In particular we will consider the question of how computable the result of this operation can be if we start with a theory with a computable collection of $\Sigma_1$-sentences.

• Monday March 18: No talk (Spring break)

Tranferring model-theoretic results about $\mathcal{L}_{\infty, \omega}$ to a Grothendieck topos

One of the most significant discoveries of categorical logic is that for a first order language $L$ the operations of $\mathcal{L}_{\infty, \omega}(L)$ can be described categorically. This observation allows us to study models of sentences of $\mathcal{L}_{\infty, \omega}(L)$ in categories other than the category of sets and functions. One class of categories which are especially well suited to interpret sentences of $\mathcal{L}_{\infty, \omega}(L)$ are Grothendieck toposes, i.e. categories which are equivalent to the category of sheaves on some site.

However, while it makes sense to study the model theory of $\mathcal{L}_{\infty, \omega}(L)$ in a Grothendieck topos, this model theory can behave very differently than model theory in the category of sets and functions. (For example, in general it will be intuitionistic and need not satisfy the law of excluded middle). A natural question to ask is: "If we fix a Grothendieck topos, which results about the model theory of $\mathcal{L}_{\infty, \omega}(L)$ in the category of sets and functions have analogs for the model theory of $\mathcal{L}_{\infty, \omega}(L)$ in our fixed Grothendieck topos?"

In this talk we will discuss a method of encoding models of a sentence of $\mathcal{L}_{\infty, \omega}(L)$ in a (fixed) Grothendieck topos by models of a sentence of $\mathcal{L}_{\infty, \omega}(L')$ in the category of sets and functions, (where $L'$ is a language related to $L$). We will then discuss how to use this encoding to prove analogs in a fixed Grothendieck topos of the downward Löwenheim-Skolem theorem, the completeness theorem as well as Barwise compactness.

One of the most significant difficulties we will have to overcome is the fact that sheaves are fundamentally second order objects. We will discuss how our encoding deals with this fact and the tradeoffs which must be made in the final theorems to accommodate the non-first order nature of sheaves and the corresponding models in a Grothendieck topos.

Constructing Atomic Models in the Continuum

I will discuss several applications of a method of Shelah to build a model in the continuum from a countable model satisfying certain geometric conditions. We baptize the notion of Asymptotic Similarity which appeared almost 40 years ago in Shelah's Classification Theory. We present a template for building atomic Borel structures in the continuum based on this notion. We then survey a wide range of applications of this template.

In particular, this provides a streamlined argument for the first part of the Ackerman, Freer, and Patel paper:

Theorem 0.0.1    Let $B$ be a countable model with a totally trivial closure operation. Then there is an uncountable Borel model of the Scott sentence of $B$ which 'strongly witnesses' $\text{Th}(M)$.

Another application is to the notion recently introduced by Shelah, which I will call pseudoclosure, $\text{pcl}$.

Theorem 0.0.2    If there is a pseudo-minimal $M \in \mathbf{K}_T$, where $\text{pcl}$ satisfies exchange, with cardinality $\aleph_1$, then there is an $N \in \mathbf{K}_T$ with cardinality $2^{\aleph_0}$.

The underlying ideas are from Shelah; this explicitly unified approach is recent work with Chris Laskowski.

A key prerequisite for the results is the reduction from a complete sentence of $L_{\omega_1,\omega}$ to the class of atomic models of an associated first order theory. The details are in section 6.1 of my monograph, summarized in Theorem 6.1.8.

How hard is proving hardness? Logic approach to barriers in Complexity theory

In spite of much work over the years, the main questions in complexity theory such as P vs. NP remain unresolved. Is this question solvable at all? Is P vs. NP independent of some logical theory? Indeed, on a meta-level, there are several results that state that certain classes of techniques, including Turing's celebrated diagonalization, cannot be used to resolve these questions. Such results we call the "barriers" of complexity theory.

In this talk, we will survey some of the most well-known such barriers (Relativization, Algebrization, Natural Proofs), and talk about how knowledge of such barriers helps evaluate (and, so far, discard) proposed proofs of P vs. NP. The main emphasis will be on using logic-based approaches to pinpoint and formalize these barriers.

Strongly prompt sets and weak Demuth randomness

Randomness notions stronger than Martin-Löf randomness can often be described in terms of computational strength. For instance, Downey, Nies, Weber, and Yu showed that the weakly 2-random sequences are precisely the Martin-Löf random sequences that cannot compute any nonrecursive r.e. set, and Ng and I showed that the difference random sequences are precisely the Turing incomplete Martin-Löf random sequences. More recently, Ng and I have characterized the weakly Demuth random sequences as the Martin-Löf random sequences that cannot compute a strongly prompt r.e. set. I'll discuss this result and its consequences and present some open questions in this area.

Fraïssé's construction from a topos-theoretic perspective

We present a topos-theoretic interpretation of (a categorical generalization of) Fraïssé's construction in Model Theory, with applications to countably categorical theories. The proof of our main theorem represents an illustration of the role of Grothendieck toposes as 'bridges' for translating properties and results across different mathematical theories; specifically, the three concepts involved in the classical Fraïssé's construction (i.e., amalgamation and joint embedding properties, homogeneousness, atomicity) are seen to correspond precisely to three different ways (resp. of geometric, semantic and syntactic nature) of looking at the same classifying topos.

• Tuesday April 30: Haim Gaifman (Columbia University)

4:15 pm sharp (i.e., 4:08 pm Harvard time), Fong Auditorium, Harvard University

Epistemic and Ontological Problems Concerning Mathematics

Philosophy of mathematics is confronted with two major questions:

(i) How do we come to know mathematical propositions?
(ii) What is the nature of mathematical truth?

Attempts to give satisfactory answers to one of the questions have resulted in unsatisfactory accounts regarding the other. I shall outline an approach intended to do justice to both questions. This is an ongoing work.

Completeness for differential algebraic varieties

We will discuss the completeness problem for differential algebraic varieties and the partial answers which are known. We will show how the notion can be used to generalize and relate various problems regarding linear independence and generalized Wronskians in differential fields.