# Topic Archive: Models of PA

Computational Logic SeminarTuesday, May 3, 20162:00 pmGraduate Center, rm. 4422

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

Steklov Mathematical Institute of Russian Academy of Sciences in Moscow

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)

Model theory seminarFriday, February 19, 201612:30 pmGC 6417

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

Models of PAWednesday, March 4, 20154:50 pmGC 6300

# Definability in linear fragments of Peano arithmetic III

Charles University

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 of PAWednesday, February 25, 20154:50 pmGC 6300

# Definability in linear fragments of Peano arithmetic II

Charles University

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 of PAWednesday, February 18, 20154:50 pmGC 6300

# Definability in linear fragments of Peano arithmetic I

Charles University

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 of PAWednesday, February 11, 20154:50 pmGC 6300

# Models with the omega-property

The City University of New York

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.

CUNY Logic WorkshopFriday, February 27, 20152:00 pmGC 6417

# Definability in linear fragments of Peano arithmetic

Charles University

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 (LAk) 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 LA1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA2 (or any LAk with 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 LA1 implies interesting properties of the structure of saturated models of Peano arithmetic.

Slides from this talk.

Model theory seminarFriday, November 7, 201410:45 amGC5382

# Representing Scott sets in algebraic settings

University of Illinois at Chicago

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.

Models of PAWednesday, September 17, 20144:50 pmGC 6300New location

# Ranked lattices and elementary end extensions

The City University of New York

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.

CUNY Logic WorkshopFriday, April 4, 20142:00 pmGC 6417

# The lattice problem

The City University of New York

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.

Models of PAMonday, February 10, 20146:30 pmGC 4214.03

# Introduction to Lattices and Substructure Lattices

Bronx Community College

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.

Models of PAWednesday, October 23, 20136:30 pmGC 4214.03

# Schmerl’s Lemma and Boundedly Saturated Models

St. Francis College

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.

CUNY Logic WorkshopFriday, October 25, 20132:00 pmGC 6417

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

University of Connecticut

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.

Models of PAWednesday, October 2, 20136:30 pmGC 4214.03

# Fullness

The City University of New York

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

CUNY Logic WorkshopFriday, September 27, 20132:00 pmGC 6417

# Satisfaction is not absolute

The City University of New York

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.

Model theory seminarFriday, October 4, 201312:30 pmGC6417

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

University of Illinois at Chicago

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.

Model theory seminarFriday, May 10, 201312:30 pmGC 6417

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

Models of PAWednesday, April 17, 20136:30 pmGC 4214.03

# Pseudostandard cuts

The City University of New York

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.

University of Pennsylvania
Models of PAWednesday, March 13, 20138:00 amGC 4214.03

# Generalizing the notion of interstices

Ghent University

I will present a generalization of the notion of interstices that
originated from the study of generic cuts.