# Models of PA

# Ultrafilters and nonstandard methods in combinatorics of numbers

In certain areas of Ramsey theory and combinatorics of numbers, diverse non-elementary methods are successfully applied, including ergodic theory, Fourier analysis, (discrete) topological dynamics, algebra in the space of ultrafilters. In this talk I will survey some recent results that have been obtained by using tools from mathematical logic, namely ultrafilters and nonstandard models of the integers.

On the side of Ramsey theory, I will show how the hypernatural numbers of nonstandard analysis can play the role of ultrafilters, and provide a convenient setting for the study of partition regularity problems of diophantine equations. About additive number theory, I will show how the methods of nonstandard analysis can be used to prove density-dependent properties of sets of integers. A recent example is the following theorem: If a set $A$ of natural numbers has positive upper asymptotic density then there exists infinite sets $B$, $C$ such that their sumset $C+B$ is contained in the union of $A$ and a shift of $A$. (This gives a partial answer to an old question by Erdős.)

# Linear fragments of PA – beyond LA_1

I will continue my series of talks on linear fragments of PA. Nevertheless, this talk will be mostly self contained.

In my previous talks, I paid attention almost exclusively to the case of the linear arithmetic LA_1 – a reduct of PA containing only unary multiplication by one distinguished element (scalar) instead of the complete binary multiplication. It was shown that LA_1 is a rather tame theory with most of the properties similar to those of Presburger arithmetic (model completeness, decidability, existence of non-standard recursive models, NIP, …).

In this talk, I will start to examine linear arithmetics with more then one scalar. Starting with LA_2 (two scalars) already, the picture changes dramatically – I will construct a model of LA_2 where a “Peano multiplication” is definable on an infinite initial segment. On the other hand, the quantifier elimination does not fail completely in linear arithmetics with more than one scalar – I will show that all linear arithmetics satisfy bounded QE.

I will summarize the results of this and previous talks in an almost complete characterization of linear fragments of PA which are/aren’t model complete.

If time permits, I will show some applications (in particular a result on (in)dependence of values of multiplication in different points in a saturated model of PA).

# Order Type vs. Isomorphism Type for Models of PA II

I will continue to discuss work of Shelah on the problem of under what conditions can the underlying order

type of a model of PA determine its isomorphism type. In particular I will outline a proof of a theorem roughly

stating that a model, M, of PA whose underlying order exhibits a week form of rigidity has the property that any

other model of PA which is order isomorphic to M is in fact isomorphic (as models of PA) to M.

# A perfectly generic talk

We will look at perfect generics for countable models of PA. Our goal will be to prove the following theorems: 1. Any countable collection of inductive subsets of a countable model are definable from a single generic. 2. Any countable model has minimally undefinable generics.

# Order type vs. Isomorphism type for models of PA

I will discuss recent work of Shelah around the general problem of how the underlying order type of a model of PA may determine influence its isomorphism type as a full model of PA.

# The undecidability of lattice-ordered groups II

In this talk I will discuss conjugacy in the automorphism group of the rationals as a linearly ordered set, and then show that the integers, together with addition and multiplication, can be interpreted in Aut(Q), and thus that the theory of Aut(Q) is undecidable.

# Generic I0 at $\aleph_\omega$

It is common practice to consider the generic version of large cardinals defined with an elementary embedding, but what happens when such cardinals are really large? The talk will concern a form of generic I0 and the consequences of this over-the-top hypothesis on the “largeness” of the powerset of $\aleph_\omega$. This research is a result of discussions with Hugh Woodin.

# Countable Arithmetically Saturated Models and the Small Index Property.

In 1994 Lascar proved that countable arithmetically saturated models of PA have the Small Index Property. In this talk we outline the proof and discuss related results and open problems.

# The undecidability of lattice-ordered groups

In this talk I will discuss conjugacy in the automorphism group of the rationals as a linearly ordered set, and then show that the integers, together with addition and multiplication, can be interpreted in Aut(Q), and thus that the theory of Aut(Q) is undecidable.

# Definability in linear fragments of Peano arithmetic III

In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the k-linear arithmetic (LA_k) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). Note that each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars.

I will prove a quantifier elimination result (QE up to disjunctions of bounded pp-formulas) for LA_1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA_2 (or any LA_k with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no pp-elimination is possible). Finally, I will show that all the theories LA_k satisfy quantifier elimination (at least) up to bounded formulas.

I will mention several applications and corollaries of these results including a construction of a non-NIP ordered module, or a result on automorphisms in saturated models of PA.

# Definability in linear fragments of Peano arithmetic II

In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the k-linear arithmetic (LA_k) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). Note that each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars.

I will prove a quantifier elimination result (QE up to disjunctions of bounded pp-formulas) for LA_1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA_2 (or any LA_k with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no pp-elimination is possible). Finally, I will show that all the theories LA_k satisfy quantifier elimination (at least) up to bounded formulas.

I will mention several applications and corollaries of these results including a construction of a non-NIP ordered module, or a result on automorphisms in saturated models of PA.

# Definability in linear fragments of Peano arithmetic I

In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the k-linear arithmetic (LA_k) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). Note that each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars.

I will prove a quantifier elimination result (QE up to disjunctions of bounded pp-formulas) for LA_1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA_2 (or any LA_k with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no pp-elimination is possible). Finally, I will show that all the theories LA_k satisfy quantifier elimination (at least) up to bounded formulas.

I will mention several applications and corollaries of these results including a construction of a non-NIP ordered module, or a result on automorphisms in saturated models of PA.

# Models with the omega-property

A model M of PA has the omega-property if it has an elementary end extension coding a subset

of M of order type omega. The countable short recursively saturated models are a proper subclass

of the countable models with the omega-property, and both classes share many common

model theoretic properties. For example, they all have automorphism groups of size continuum. I will give a brief survey of what is known about models with the omega-property and I will discuss some open problems.

# Bounded Second-Order Arithmetic I

We will discuss axiom systems for weak second order arithmetic. In the study of bounded arithmetic, the base theory is called V^0; we will discuss coding and counting in V^0 and in an extension of it. We will give at least one example of a sentence that is not provable in V^0 but is provable in the extension.

# Forcing over models of arithmetic

I will talk about forcing over models of arithmetic. Our primary application will be the following theorem, due to Simpson: if a model M of PA is countable, then M has a subset U such that that (M,U) is a pointwise definable model of PA*. Time permitting, we will see that the MacDowell–Specker theorem fails for uncountable languages: for M countable and nonstandard, there are U_alpha for alpha < omega_1 such that (M, U_alpha)_{alpha < omega_1} is a model of PA* and has no elementary end extensions.

# Decoding in the automorphism group of a model of arithmetic.

In the talk I will discuss results on recovering a countable recursively saturated model of Peano Arithmetic from its automorphism group.

# The pentagon lattice II

# The pentagon lattice

In this talk, I will discuss the proof that for every countable model M of PA, there is an end extension N such that Lt(N /M) is isomorphic to N5. I will begin by constructing an infinite representation of N5 and then discuss Theorem 4.5.21 in TSOMOPA which shows how to construct an extension from such a representation.

# The Hales-Jewett Theorem and Applications II

# The Hales-Jewett Theorem and Applications

The Hales-Jewett Theorem has applications in Ramsey Theory, and is also used to prove properties about lattices of elementary substructures. We will prove the Hales-Jewett Theorem and discuss applications.

# Elementary end extensions and the pentagon lattice

By a theorem of Wilkie, every countable model M of PA has an elementary end extension N such that interstructure lattice Lt(N/N) is isomorphic to the pentagon lattice. I will explain why the theorem does not generalize to uncountable models.

# Ranked lattices and elementary end extensions

Every countable model M of PA has and elementary end extension N such that the lattice Lt(N/M) is

isomorphic to the pentagon lattice N_5. I will go over the proof why none of such extensions can be conservative.

# Lattices of elementary substructures of arithmetically saturated models of PA

# An introduction to arithmetically saturated models of PA

# Submodel Lattices of Nerode Semirings

Let TA be True Arithmetic, and let TA_2 be the set of Pi_2 sentences in TA.

If N is a model of TA_2, then the set Lt(N) of substructures of N that are also models of TA_2

forms a complete lattice. A Nerode semiring is a finitely generated model of TA_2.

I will be talking about some joint work with Volodya Shavrukov in which we investigate the possible lattices that are isomorphic to some Lt(N), where N is a Nerode semiring. Existentially closed models of TA_2 were studied long ago. The possible Lt(N) will also be considered for e.c. Nerode semirings.

# Lattices with congruence representations as interstructure lattices

In this talk I will discuss arguably the most general result on which finite lattices may

arise as substructure lattices of models of Peano arithmetic. The focus will be on lattices with

congruence representations.

Let A be an algebra (a structure in a purely functional signature). We may consider the set of all congruence relations on A, which naturally forms a lattice Cg(A). A lattice L is said to have a congruence representation if there is an algebra A so that L is isomorphic to Cg(A)*. (Cg(A)* is the lattice obtained from Cg(A) be interchanging the roles of join and meet.) The main theorem is that if L is a finite lattice with a congruence representation and M is a non-standard model of PA then there is a cofinal elementary extension N of M so that the interstructure lattice Lt(N/M) is isomorphic to L.

This talk is intended as an overview. I do not plan on going into any details of the proofs but rather will survey the necessary tools that go into proving the theorem.

# Finite Distributive Lattices II

I will continue the proof (in TSOMOPA 4.3) that if D is a finite distributive lattice, there is a model M such that Lt(M) is isomorphic to D.

# Finite Distributive Lattices

In this talk, I will present the proof (in TSOMOPA 4.3) that if D is a finite distributive lattice, there is a model M such that Lt(M) is isomorphic to D.

# Boolean algebras of elementary substructures II

This is a continuation of the talk from last week. I will show how to use minimal types to construct elementary end extensions with large interstructure lattices.

# Boolean algebras of elementary substructures

In his 1976 paper Haim Gaifman proved that for every set I, every model M of PA has an elementary end extension N such that Lt(N/M) is isomorphic to P(I). I will present a proof.

# Blass-Gaifman and Ehrenfeucht lemmas

Proofs of the lemmas will be given and some consequences related to substructure lattices will be explained.

# Introduction to Lattices and Substructure Lattices II

We will continue an introduction to Substructure Lattices, a theme for this semester’s seminar. It will still be completely elementary.

# Introduction to Lattices and Substructure Lattices

This talk with be completely elementary. We will provide an introduction to Substructure Lattices, a theme for this semester’s seminar. Given a model M of Peano Arithmetic, its Substructure Lattice is the lattice of elementary substructures of M. We will discuss the basics of lattice theory relevant to understanding this topic and present some of the big questions in this area.

# Equivalence relations in models of Peano arithmetic

The talk will be about the correspondence between definable equivalence relations on countable recursively saturated models of PA and the closed normal subgroups of their automorphism groups.

# When are subsets of a model “coded”? II

# When are subsets of a model “coded”?

I will present a result by J. Schmerl that characterizes when a collection of subsets of a given model, M, will appear as the coded sets in some elementary end extension of M. This is an analogue to Scott’s theorem, which characterizes when a collection of sets of natural numbers can be the standard system of some model of PA. If there is time, I will also present some extensions of the result.

# How to make a full satisfaction class

# Tanaka’s embedding theorem

# Schmerl’s Lemma and Boundedly Saturated Models II

# Schmerl’s Lemma and Boundedly Saturated Models

We prove a slight modification of Schmerl’s Lemma for saturated models, and show how it can be applied to prove Kaye’s Theorem for boundedly saturated models of PA.

# Cofinal extensions of recursively saturated ordered structures

# More on fullness

Continuing with the discussion from last week, I will state a few conditions that imply fullness and use that to show a few basic examples of full models. I will also show one direction of Kaye’s theorem that a model M is full if and only if its standard system is a model of full second order comprehension (CA_0).

# Fullness

A model $M$ of PA is full if for every definable in $(M,omega)$ set $X$, $Xcap omega$ is coded in $M$. In a recent paper, Richard Kaye proved that $M$ is full if and only if its standard system is a model of full second order comprehension. Later in the semester we will examine Kaye’s proof. In this talk I will discuss some preliminary results and I will show an example of a model that is not full, using an argument that does not depend on Kaye’s theorem

# The automorphism group of a model of arithmetic: recognizing standard system

Let M be countable recursively saturated model of Peano Arithmetic. In the talk I will discuss ongoing research on recognizing standard system of M in the automorphism group of M.

# Regular Interstices

We define the notion of a regular interstice and show that every regular interstice has elements realizing selective types.

# Pseudostandard cuts

A cut I in a model M of PA is *pseudostandrd* if there is an N such that (M,I) is elementary

equivalent to (N,omega). I will discuss some preliminary results in model theory of pseudostandard cuts.

# Fast Growing Functions and Arithmetical Independence Results

We explore the role of the function $a+2^x$ and its generalisations to higher number classes, in supplying complexity bounds for the provably computable functions across a broad spectrum of (arithmetically based) theories. We show how the resulting “fast growing” subrecursive hierarchy forges direct links between proof theory and various combinatorial independence results – e.g. Goodstein’s Theorem (for Peano Arithmetic) and Friedman’s Miniaturised Kruskal Theorem for Labelled Trees (for $Pi^1_1$-CA$_0$).

Ref: Schwichtenberg and Wainer, “Proofs and Computations”, Persp. in Logic, CUP 2012.

# Generalizing the notion of interstices

I will present a generalization of the notion of interstices that

originated from the study of generic cuts.

# Several versions of self-embedding theorem

In this talk, I will give several versions of Friedman’s self-embedding theorem which can characterize subsystems of Peano arithmetic. Similarly, I will also give several variations of Tanaka’s self-embedding theorem to characterize subsystems of second-order arithmetic.

# Introduction to interstices and intersticial gaps II

# Introduction to interstices and intersticial gaps

Let M be a model of PA for which Th(M) is not Th(N) (N is the standard model). Then M has nonstandard definable elements. Let c be a non-definable element. The largest convex set which contains c and no definable elements is called the interstice around c. In this talk we discuss various properties of interstices. We also define intersticial gaps which are special subsets of interstices. We show that the set of the intersticial gaps which are contained in any given interstice of a countable arithmetically saturated model of PA is a dense linear order.