# Blog Archives

# Topic Archive: Models of PA

# Some abstract versions of Goedel’s Second Incompleteness Theorem based on non-classical logics

We study abstract versions of Goedel’s second incompleteness theorem and formulate generalizations of Loeb’s derivability conditions that work for logics weaker than the classical one. We isolate the role of the contraction and weakening rules in Goedel’s theorem and give a (toy) example of a system based on modal logic without contraction invalidating Goedel’s argument. On the other hand, Goedel’s theorem is established for a version of Peano arithmetic without contraction. (Joint work with Daniyar Shamkanov)

# Lattices of Elementary Substructures

The set of elementary substructures of a model of PA, under the inclusion relation, form a lattice. The lattice problem for models of PA asks which lattices can be represented as substructure lattices of some model of PA. This question dates back to Gaifman’s work on minimal types, which showed that the two element chain can be represented as a substructure lattice. Since then, there have been many important contributions to this problem, including by Paris, Wilkie, Mills, and Schmerl, though no complete picture has yet emerged. Studying this question involves knowledge of models of PA as well as some nontrivial lattice theory and combinatorics. In my talk, I will survey some of the major results and, if there’s time, give an idea of the techniques used to study this question.

Slides from this talk.

# 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.

# Definability in linear fragments of Peano arithmetic

In this talk, I will give an overview of recent results on linear arithmetics with main focus on definability in their models. 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). The hierarchy of linear arithmetics lies between Presburger and Peano arithmetics and stretches from tame to wild.

I will present a quantifier elimination result 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*(or any

_{2}*LA*with

_{k}*k*at least

*2*) where multiplication is definable on a non-standard initial segment (and thus no similar quantifier elimination is possible).

There is a close connection between models of linear arithmetics and certain discretely ordered modules (as each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars) which allows to construct wild (e.g. non-NIP) ordered modules. On the other hand, the quantifier elimination result for *LA _{1}* implies interesting properties of the structure of saturated models of Peano arithmetic.

Slides from this talk.

# Representing Scott sets in algebraic settings

The longstanding problem of representing Scott sets as standard systems of models of Peano Arithmetic is one of the most vexing in the subject. We show that the analogous question has a positive solution for real closed fields and Presburger arithmetic. This is joint work with Alf Dolich, Julia Knight and Karen Lange.

# 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.

# The lattice problem

Ordered by inclusion, the set of elementary substructures of a model of PA is a lattice.

It is an ℵ_{1}-compactly generated lattice, meaning that every element of the lattice is a supremum of its compact elements, and for every compact element, there are at most countably many compact elements below it. The lattice problem for models of PA is to determine which lattices can be represented as lattices of elementary substructures of a model of PA. The condition above puts a restriction on the types of lattices that can be represented this way. As far as we know, this can be the only restriction. Much work on the problem has been done in the 1970s by Gaifman, Knight, Mills, Paris, Schmerl, and Wilkie, and has been continued by Schmerl. It involves some specialized knowledge of models of PA, highly nontrivial lattice representation theory, combinatorics, and sometimes number theory. There are many positive results, but we still do not know if there is a finite lattice which cannot be represented as a substructure lattice of a model of PA. My talk will be an introduction to the lattice problem. I’ll introduce basic definitions and I’ll prove a couple of introductory negative results.

# 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.

# 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.

# Automorphism Groups of Countable, Recursively Saturated Models of Peano Arithmetic

It is still unknown whether there are nonisomorphic countable recursively saturated models M and N whose automorphism groups Aut(M) and Aut(N) are isomorphic. I will discuss what has happened over the last 20 years towards showing that such models do not exist, including some very recent results.

# 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

# Satisfaction is not absolute

I will discuss a number of theorems showing that the satisfaction relation of first-order logic is less absolute than might have been supposed. Two models of set theory $M_1$ and $M_2$, for example, can agree on their natural numbers $langlemathbb{N},{+},{cdot},0,1,{lt}rangle^{M_1}=langlemathbb{N},{+},{cdot},0,1,{lt}rangle^{M_2}$, yet disagree on arithmetic truth: they have a sentence $sigma$ in the language of arithmetic that $M_1$ thinks is true in the natural numbers, yet $M_2$ thinks $negsigma$ there. Two models of set theory can agree on the natural numbers $mathbb{N}$ and on the reals $mathbb{R}$, yet disagree on projective truth. Two models of set theory can have the same natural numbers and have a computable linear order in common, yet disagree about whether this order is well-ordered. Two models of set theory can have a transitive rank initial segment $V_delta$ in common, yet disagree about whether this $V_delta$ is a model of ZFC. The theorems are proved with elementary classical methods.

This is joint work with Ruizhi Yang (Fudan University, Shanghai). We argue, on the basis of these mathematical results, that the definiteness of truth in a structure, such as with arithmetic truth in the standard model of arithmetic, cannot arise solely from the definiteness of the structure itself in which that truth resides; rather, it must be seen as a separate, higher-order ontological commitment.

# Real closures of $omega_1$-like models of PA

In an earlier seminar I showed that assuming diamond we can build many $omega_1$-like models of PA with the same standard system but non-isomorphic real closures. In this lecture I will show how to do this without diamond. This is joint work with Jim Schmerl and Charlie Steinhorn.

# Transplendent models of rich theories

Following up on a talk by Roman Kossak earlier this semester, I will discuss work by Engstrom and Kaye which address the question of existence of transplendent models (models with expansions omitting a type). If there is time, I will talk about transplendent models of PA.

# 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.

# Generalizing the notion of interstices

I will present a generalization of the notion of interstices that

originated from the study of generic cuts.