Models of PA seminar

Models of PA

The Models of PA seminar meets regularly at the CUNY Graduate Center, holding talks on models of the Peano Axioms and related theories. It meets on (most) Mondays 6:30 - 8 PM at the CUNY Graduate Center in room 4214.03. It is organized by Roman Kossak and Erez Shochat.
(93 items)

No posts found

Models of PAWednesday, February 15, 20176:30 pmThesis Rom

Alf Dolich

Recursive Reducts of PA III

The City University of New York

I will continue my overview of Schmerl’s work on generalizations of Tennenbaum’s theorm to general reducts of Peano Arithmetic.

Models of PAWednesday, December 7, 20166:30 pmGC 4214-03

Alf Dolich

Recursive Reducts of PA II

The City University of New York

I will continue discussing work of Schmerl addressing the question of under what conditions a given reduct of PA has the property that for any non-standard model M of PA the restriction of M to the reduct must be non-computable.

Models of PAWednesday, November 30, 20166:15 pmGC 4214-03

Michał Tomasz Godziszewski

Satisfaction Classes and Recursive Saturation IV

The study of possible semantics for arithmetized languages in nonstandard models has been a lively research field since the seminal paper of A. Robinson “On languages based on non-standard arithmetic”. Our primary inspiration for examining mathematical features of such structures, and recursively saturated in particular, is that every countable recursively saturated model of Peano Arithmetic supports a great variety of nonstandard satisfaction classes that can serve as models for formal theories of truth – those models allow to investigate the role of arithmetic induction in semantic considerations. On the other hand, nonstandard satisfaction classes are used as a tool in model theoretic constructions providing answers to questions in the model theory of formal arithmetic and often make it possible to solve problems that do not explicitly involve nonstandard semantics. In the series of talks, I will present proofs of classical results concerning satisfaction classes and recursive saturation in models of PA.

Models of PAWednesday, November 16, 20166:30 pm

Alf Dolich

Recursive Reducts — An Introduction

The City University of New York

I will begin talking about work of Schmerl on generalizations of Tennenbaum’s theorem on the non-exsistence of computable nonstandard models of PA to reducts of PA.

Models of PAWednesday, November 9, 20166:30 pmGC 4214-03

Michał Tomasz Godziszewski

Satisfaction Classes and Recursive Saturation III

The study of possible semantics for arithmetized languages in nonstandard models has been a lively research field since the seminal paper of A. Robinson “On languages based on non-standard arithmetic”. Our primary inspiration for examining mathematical features of such structures, and recursively saturated in particular, is that every countable recursively saturated model of Peano Arithmetic supports a great variety of nonstandard satisfaction classes that can serve as models for formal theories of truth – those models allow to investigate the role of arithmetic induction in semantic considerations. On the other hand, nonstandard satisfaction classes are used as a tool in model theoretic constructions providing answers to questions in the model theory of formal arithmetic and often make it possible to solve problems that do not explicitly involve nonstandard semantics. In the series of talks, I will present proofs of classical results concerning satisfaction classes and recursive saturation in models of PA.

Models of PAWednesday, November 2, 20166:30 pmGC 4214-03

Michał Tomasz Godziszewski

Satisfaction Classes and Recursive Saturation II

The study of possible semantics for arithmetized languages in nonstandard models has been a lively research field since the seminal paper of A. Robinson “On languages based on non-standard arithmetic”. Our primary inspiration for examining mathematical features of such structures, and recursively saturated in particular, is that every countable recursively saturated model of Peano Arithmetic supports a great variety of nonstandard satisfaction classes that can serve as models for formal theories of truth – those models allow to investigate the role of arithmetic induction in semantic considerations. On the other hand, nonstandard satisfaction classes are used as a tool in model theoretic constructions providing answers to questions in the model theory of formal arithmetic and often make it possible to solve problems that do not explicitly involve nonstandard semantics. In the series of talks, I will present proofs of classical results concerning satisfaction classes and recursive saturation in models of PA.

Models of PAWednesday, October 26, 20166:30 pmGC 4214-03

Kameryn Williams

Models of arithmetic with two expansions to $ACA_0$, Part 2

The CUNY Graduate Center

In this talk and its prequel I construct models of arithmetic with exactly two expansions to a model of $ACA_0$. Last time, we saw how to build models of arithmetic which are A-rather classless for some class A of the model. In this talk, I will use a kind of forcing argument to show how to pick this A so that the resulting model has exactly two expansions to $ACA_0$. Time permitting, I will explain the difficulties in moving from two to three.

Models of PAWednesday, October 19, 20166:30 pmGC 4214-03

Michał Tomasz Godziszewski

Satisfaction Classes and Recursive Saturation

The study of possible semantics for arithmetized languages in nonstandard models has been a lively research field since the seminal paper of A. Robinson “On languages based on non-standard arithmetic”. Our primary inspiration for examining mathematical features of such structures, and recursively saturated in particular, is that every countable recursively saturated model of Peano Arithmetic supports a great variety of nonstandard satisfaction classes that can serve as models for formal theories of truth – those models allow to investigate the role of arithmetic induction in semantic considerations. On the other hand, nonstandard satisfaction classes are used as a tool in model theoretic constructions providing answers to questions in the model theory of formal arithmetic and often make it possible to solve problems that do not explicitly involve nonstandard semantics. In the series of talks, I will present proofs of classical results concerning satisfaction classes and recursive saturation in models of PA.

Models of PAWednesday, October 5, 20166:30 pmGC 4214-03

Kameryn Williams

Models of arithmetic with two expansions to $ACA_0$, Part 1

The CUNY Graduate Center

In this talk and its sequel I will construct models of arithmetic with exactly two expansions to a model of $ACA_0$. To do so, I will use a modified version of Keisler’s construction of a rather-classless model. This talk will focus on this construction, while in Part 2 I will show how to use this construction to get the result.

Models of PAWednesday, September 28, 20166:30 pmGC 4214-03

Athar Abdul-Quader

Ramsey Quantifiers and PA$(Q^2)$, part II

The CUNY Graduate Center

In this talk, I will discuss the relationship between “strong” models of PA($Q^2$) and $kappa$-like models. Namely, if $kappa$ is a regular uncountable cardinal, then every countable “weak” model has a $kappa$-like ($Q^2$)-elementary end extension that is a kappa like strong model, and if M is a strong model it is $kappa$ like for some $kappa$.

Models of PAWednesday, September 21, 20166:30 pmGC 4214-03

Athar Abdul-Quader

Ramsey Quantifiers and PA($Q^2$)

The CUNY Graduate Center

We can extend the language of first order logic to add in a new quantifier, $Q^2$, which binds two free variables. The intended interpretation of $Q^2 x,y\phi(x, y)$ is “There is an infinite (unbounded) set $X$ such that $\phi(x, y)$ holds for each $x \neq y \in X.$” The theory PA($Q^2$) is the theory of Peano Arithmetic in this augmented language (asserting that induction holds for all formulas, including with Ramsey quantifier) and can be thought of as a second order theory whose models are of the form $(M, \mathfrak{X})$ where $\mathfrak{X} \subseteq P(M)$. In this talk, I will present a few results due to Macintyre (1980) and Schmerl & Simpson (1982), namely that models of PA($Q^2$) correspond to models of the second order system $\Pi_1^1-CA_0$. If there is time, I will present Macintyre’s proof that so-called “strong” models of this theory correspond to $\kappa$-like models for some regular $\kappa$.

Models of PAWednesday, September 14, 20166:30 pmGC 4214-03

Kameryn Williams

Yet more forcing in arithmetic: life in a second-order world

The CUNY Graduate Center

In previous semesters of this seminar, I have talked about how the technique of forcing, originally developed by Cohen for building models of set theory, can be used to produce models of arithmetic with various properties. In this talk, I will present a forcing proof of Harrington’s theorem on the conservativity of $\mathsf{WKL}_0$ over $\mathsf{RCA}_0$. More formally, any countable model of $\mathsf{RCA}_0$ can be extended to a model of $\mathsf{WKL}_0$ with the same first-order part. As an immediate corollary, we get that any $\Pi^1_1$ sentence provable by $\mathsf{WKL}_0$ is already provable by $\mathsf{RCA}_0$.

Models of PAWednesday, May 11, 20166:15 pmGC 4214-03

Simon Heller

Automorphisms of models of Presuburger arithmetic V

GC CUNY

I will present a characterization of the closed normal subgroups of the automorphism group of pseudo-recursively saturated models of Presburger arithmetic using the machinery developed in the prior three talks.

Models of PAWednesday, May 4, 20166:15 pmGC 4214-03

Simon Heller

Automorphisms of models of Presburger arithmetic IV

GC CUNY

I will present a characterization of the closed normal subgroups of the automorphism group of pseudo-recursively saturated models of Presburger arithmetic using the machinery developed in the prior three talks.

Models of PAWednesday, April 20, 20166:15 pmGC 4214-03

Victoria Gitman

Computable processes can produce arbitrary outputs in nonstandard models: part II

The City University of New York

This is a continuation of last week’s talk. I will continue with a proof of Woodin’s theorem, recently generalized by Blanck and Enayat, showing that for every computably enumerable theory $T$ extending ${\rm PA}$, there is a corresponding index $e$ such that ${\rm PA}\vdash “W_e$ is finite” and whenever a model $M\models T$ satisfies that $W_e$ is contained in some $M$-finite set $s$, then $M$ has an end-extension $N\models T$ in which $W_e=s$. Indeed, the hypotheses can be relaxed to say that $T$ extends ${\rm I}\Sigma_1$, but I will not discuss this in the talk.

An extended abstract can be found here on my blog.

Models of PAWednesday, April 13, 20166:15 pmGC 4214-03

Victoria Gitman

Computable processes can produce arbitrary outputs in nonstandard models

The City University of New York

The focus of this talk is the question of what a computable process can output by passing to a nonstandard model of arithmetic. It is not difficult to see that a computable process can change its output by passing to a nonstandard model, but in fact, for some processes, we can thus affect any arbitrary desired change. I will discuss and prove a theorem of Woodin, recently generalized by Blanck and Enayat, showing that for every computably enumerable theory $T$ extending ${\rm PA}$, there is a corresponding index $e$ such that ${\rm PA}\vdash “W_e$ is finite” and whenever a model $M\models T$ satisfies that $W_e$ is contained in some $M$-finite set $s$, then $M$ has an end-extension $N\models T$ in which $W_e=s$. Indeed, the hypotheses can be relaxed to say that $T$ extends ${\rm I}\Sigma_1$, but I will not discuss this in the talk.

An extended abstract can be found here on my blog.

Models of PAWednesday, April 6, 20166:15 pmGC 4214-03

Erez Shochat

Automorphism Groups of Models of Different Theories (Part II)

St. Francis College

Jim Schmerl recently proved that there are continuum many theories extending PA, for which whenever M and N are countable arithmetically saturated models of two different such theories, their automorphism groups are non isomorphic. In part I, we give a survey of results concerning automorphism groups of countable arithmetically saturated models of PA, and introduce notions and prove results which will be used in part II to prove Schmerl’s Theorem.

Models of PAWednesday, March 30, 20166:15 pmGC 4214-03

Erez Shochat

Automorphism Groups of Models of Different Theories (Part I)

St. Francis College

Jim Schmerl recently proved that there are continuum many theories extending PA, for which whenever M and N are countable arithmetically saturated models of two different such theories, their automorphism groups are non isomorphic. In part I, we give a survey of results concerning automorphism groups of countable arithmetically saturated models of PA, and introduce notions and prove results which will be used in part II to prove Schmerl’s Theorem.

Models of PAWednesday, March 16, 20166:15 pmGC 4214-03

Alf Dolich

Structures Between (Z,+) and (Z,+,<)

The City University of New York

I will discuss a recent result of Gabe Conant that there is no structure lying properly between (Z,+) and (Z,+,<).

Models of PAWednesday, March 9, 20166:15 pmGC 4214-03

Simon Heller

Automorphisms of models of Presburger arithmetic III

GC CUNY

This talk will focus on some results on the automorphism groups of countable, pseudo-recursively saturated models of Presburger arithmetic and on the characterization of their closed normal subgroups.

Models of PAWednesday, March 2, 20166:15 pmGC 4214-03

Simon Heller

Automorphisms of models of Presburger arithmetic II

GC CUNY
Models of PAWednesday, February 24, 20166:15 pmGC 4214-03

Simon Heller

Automorphisms of models of Presburger arithmetic I

GC CUNY

I will present an algebraic construction of end extensions of models of Presburger arithmetic, as well as key definitions and examples that are needed for studying the automorphism group of certain countable models of Pr.

Models of PAWednesday, December 2, 20156:30 pmGC 4214-03

Roman Kossak

Loftiness V

The City University of New York

A class C of countable models of PA is countably PC*_δ if there is a theory T in a countable language extending PA* such that for every countable model M of PA, M is in C if and only M is expandable to a model of T. The class of countable recursively saturated models of PA is countably PC*_δ, and Kaufman and Schmerl showed that many other natural classes, including the class uniformly ω-lofty models, are not. I will go over the proof of the Kaufman-Schmerl result, and I will discuss other potential approaches to characterizing classes of models of PA via expandability.

Models of PAWednesday, November 18, 20156:30 pmGC 4214-03

Athar Abdul-Quader

Substructure Lattices of Recursively Saturated Models

The CUNY Graduate Center

Previously, it was known (Kossak-Schmerl 1995) that given two arithmetically saturated models with isomorphic substructure lattices, their standard systems must be the same. In Schmerl’s new paper (2015?), he analyzes this proof a little more carefully: in particular, if M is recursively saturated, and X subset omega, then there is an ideal in the substructure lattice of M corresponding to X if and only if X is Turing computable from the jump of some Y in SSy(M). We will go over this proof and, time permitting, how this is used in the proof of the main theorem: if M and N are countable arithmetically saturated models with isomorphic automorphism groups, then the jumps of their theories are Turing equivalent.

Models of PAWednesday, November 11, 20156:30 pmGC 4214-03

Whan Ki Lee

Cofinal elementary extensions II

Queensborough Community College, CUNY

We will also discuss K-tallness and tallness in relation to the existence of κ-pseudosaturated cofinal elementary extensions. Here, κ-pseudosaturated structures are the structures all of whose infinite definable sets have a cardinality ≥ κ.

Models of PAWednesday, November 4, 20156:30 pmGC 4214-03

Whan Ki Lee

Cofinal elementary extensions

Queensborough Community College, CUNY

We will discuss two weak versions of recursive saturation: K-tallness and tallness. K-tallness characterizes the countable models of 0 + exp that have cofinal elementary extensions enlarging any infinite definable set, and tallness characterizes such models of linear ordering without the last element. I will present the proof of the latter. If time permits, we will also discuss the two properties in relation to the existence of κ-pseudosaturated cofinal elementary extensions. Here, κ-pseudosaturated structures are the structures all of whose infinite definable sets have a cardinality ≥κ.

Models of PAWednesday, October 28, 20156:15 pmGC 4214-03

Kameryn Williams

Recursive definability of the standard cut

The CUNY Graduate Center

Say that the standard cut in a model of arithmetic is recursively definable if there is a recursive sequence coinitial in the nonstandard elements. We will construct minimal models in which the standard cut is recursively definable and minimal models in which the standard cut is not recursively definable.

Models of PAWednesday, October 21, 20156:15 pm

Alf Dolich

Loftiness IV

The City University of New York

I will discuss more work of Kaufmann and Schmerl around loftiness. In particular I will discuss how in the definition of e-loftiness we may restrict our attention to only those types that define cuts. These consideration lead to a simple proof of a theorem of Pabion’s that for kappa an uncountable cardinal a model M of PA is kappa-saturated if and only if its underlying ordering is kappa-saturated. Time permitting I will also discuss how for countable models M, being lofty is equivalent to having a recursively saturated simple extension.

Models of PAWednesday, October 14, 20156:15 pmGC 4214-03

Roman Kossak

Loftiness III

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$. Tall models with the $omega$-property are uniformly $omega$-lofty. I will present several results on models with the $omega$-property, including Jim Schmerl’s construction of a model with the $omega$-property that is not recursively saturated.

Models of PAWednesday, October 7, 20156:15 pmGC 4214-03

Roman Kossak

Loftiness II

The City University of New York

I will introduce uniformly omega-lofty models and I will discuss some results about them due to Matt Kaufmann and Jim Schmerl.

Models of PAWednesday, September 30, 20156:15 pmGC 4214-03

Roman Kossak

Loftiness

The City University of New York

Loftiness is a weak version of recursive saturation. It was introduced and studied by Kaufmann and Schmerl in two papers published in 1984 and 1987. I will present basic definitions and results leading to constructions of lofty models of PA that are not recursively saturated.

Models of PAWednesday, September 16, 20156:15 pmGC 4214-03

Athar Abdul-Quader

Enayat models II

The CUNY Graduate Center

Simpson proved that every countable model of PA has an expansion (to PA*) that is pointwise definable. The natural question, then, is if every countable model has an expansion to PA* in which no new elements are defined. Enayat proved this is false by showing the existence of many models that are not pointwise definable, but become so upon addition of any undefinable class. Inspired by this, I have begun thinking about which models have this property. I will describe some models with this property (and some without) and talk about my search for a non-trivial such model (I will also explain what I mean by “non-trivial” here).

Models of PAWednesday, September 2, 20156:15 pmGC 4214-03

Athar Abdul-Quader

Enayat Models

The CUNY Graduate Center

Simpson proved that every countable model of PA has an expansion (to PA*) that is pointwise definable. The natural question, then, is if every countable model has an expansion to PA* in which no new elements are defined. Enayat proved this is false by showing the existence of many models that are not pointwise definable, but become so upon addition of any undefinable class. Inspired by this, I have begun thinking about which models have this property. I will describe some models with this property (and some without) and talk about my search for a non-trivial such model (I will also explain what I mean by “non-trivial” here).

Set theory seminarModels of PAThursday, June 18, 20155:00 pm4214-03Math Thesis room

Mauro Di Nasso

Ultrafilters and nonstandard methods in combinatorics of numbers

Universita di Pisa

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

The slides are here.

Models of PAWednesday, May 6, 20154:50 pmGC 6300

Petr Glivický

Linear fragments of PA – beyond LA_1

Charles University

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

Models of PAWednesday, April 29, 20154:50 amGC 6300

Alf Dolich

Order Type vs. Isomorphism Type for Models of PA II

The City University of New York

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.

Models of PAWednesday, April 22, 20154:50 pmGC 6300

Kameryn Williams

A perfectly generic talk

The CUNY Graduate Center

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.

Models of PAWednesday, April 15, 20154:50 pmGC 6300

Alf Dolich

Order type vs. Isomorphism type for models of PA

The City University of New York

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.

Models of PAWednesday, April 1, 20154:50 pmGC 6300

Simon Heller

The undecidability of lattice-ordered groups II

GC CUNY

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.

Set theory seminarModels of PAWednesday, March 25, 20155:00 pmGC 7314

Vincenzo Dimonte

Generic I0 at $\aleph_\omega$

Technische Universität Wien

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.

Slides

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

Erez Shochat

Countable Arithmetically Saturated Models and the Small Index Property.

St. Francis College

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.

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

Simon Heller

The undecidability of lattice-ordered groups

GC CUNY

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.

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

Petr Glivický

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

Petr Glivický

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

Petr Glivický

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

Roman Kossak

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.

Models of PAWednesday, December 10, 20144:50 pmGC 6300

Shlomo Ben-Har

Bounded Second-Order Arithmetic II

GC CUNY
Models of PAWednesday, December 3, 20144:50 pmGC 6300

Shlomo Ben-Har

Bounded Second-Order Arithmetic I

GC CUNY

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.

Models of PAWednesday, November 19, 20144:50 pmGC 6300

Kameryn Williams

Forcing over models of arithmetic

The CUNY Graduate Center

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.

Models of PAWednesday, November 12, 20144:50 pmGC 6300

Ermek Nurkhaidarov

Decoding in the automorphism group of a model of arithmetic.

Penn State Mont Alto

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

Models of PAWednesday, November 5, 20144:50 pm

Athar Abdul-Quader

The pentagon lattice III

The CUNY Graduate Center
Models of PAWednesday, October 29, 20144:50 pmGC 6300

Athar Abdul-Quader

The pentagon lattice II

The CUNY Graduate Center
Models of PAWednesday, October 22, 20144:50 pmGC 6300

Athar Abdul-Quader

The pentagon lattice

The CUNY Graduate Center

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.

Models of PAWednesday, October 15, 20144:50 pmGC 6300

Kerry Ojakian

The Hales-Jewett Theorem and Applications II

Bronx Community College
Models of PAWednesday, October 8, 20144:50 pmGC 6300

Kerry Ojakian

The Hales-Jewett Theorem and Applications

Bronx Community College

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.

Models of PAWednesday, October 1, 20144:50 pmGC 6300

Roman Kossak

Elementary end extensions and the pentagon lattice

The City University of New York

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.

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

Roman Kossak

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.

Models of PAMonday, May 12, 20147:00 pmGC 4214.03

Simon Heller

Lattices of elementary substructures of arithmetically saturated models of PA

GC CUNY
Models of PAMonday, May 12, 20146:00 pmGC 4214.03

Erez Shochat

An introduction to arithmetically saturated models of PA

St. Francis College
Models of PAMonday, May 5, 20146:30 pmGC 4214.03

Jim Schmerl

Submodel Lattices of Nerode Semirings

University of Connecticut

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.

Models of PAMonday, April 7, 20146:30 pm

Alf Dolich

Lattices with congruence representations as interstructure lattices

The City University of New York

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.

Models of PAMonday, March 31, 20146:30 pmGC 4214.03

Athar Abdul-Quader

Finite Distributive Lattices II

The CUNY Graduate Center

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.

Models of PAMonday, March 24, 20146:30 pmGC 4214.03

Athar Abdul-Quader

Finite Distributive Lattices

The CUNY Graduate Center

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.

Models of PAMonday, March 17, 20146:30 pmGC 4214.03

Roman Kossak

Boolean algebras of elementary substructures II

The City University of New York

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.

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

Roman Kossak

Boolean algebras of elementary substructures

The City University of New York

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.

Models of PAMonday, March 3, 20146:30 pmGC 4214.03

Shlomo Ben-Har

Blass-Gaifman and Ehrenfeucht lemmas

GC CUNY

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

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

Kerry Ojakian

Introduction to Lattices and Substructure Lattices II

Bronx Community College

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

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

Kerry Ojakian

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, December 11, 20136:30 pmGC 4214.03

Simon Heller

Equivalence relations in models of Peano arithmetic

GC CUNY

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.

Models of PAWednesday, December 4, 20136:30 pmGC 4214.03

Athar Abdul-Quader

When are subsets of a model “coded”? II

The CUNY Graduate Center
Models of PAWednesday, November 20, 20136:30 pmGC 4214.03

Athar Abdul-Quader

When are subsets of a model “coded”?

The CUNY Graduate Center

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.

Models of PAWednesday, November 13, 20136:30 pmGC 4214.03

Alf Dolich

How to make a full satisfaction class

The City University of New York
Models of PAWednesday, November 6, 20136:30 pmGC 4214.03

Kerry Ojakian

Tanaka’s embedding theorem

Bronx Community College
Models of PAWednesday, October 30, 20136:30 pmGC 4214.03

Erez Shochat

Schmerl’s Lemma and Boundedly Saturated Models II

St. Francis College
Models of PAWednesday, October 23, 20136:30 pmGC 4214.03

Erez Shochat

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.

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

Whan Ki Lee

Cofinal extensions of recursively saturated ordered structures

Queensborough Community College, CUNY
Models of PAWednesday, October 9, 20136:30 pmGC 4214.03

Athar Abdul-Quader

More on fullness

The CUNY Graduate Center

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

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

Roman Kossak

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

Models of PAWednesday, May 8, 20135:00 pmGC 4214.03

Ermek Nurkhaidarov

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

Penn State Mont Alto

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.

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

Erez Shochat

Regular Interstices

St. Francis College

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

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

Roman Kossak

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.

Models of PAWednesday, March 20, 20136:45 pmGC 4214.03

Stan Wainer

Fast Growing Functions and Arithmetical Independence Results

The Leeds Logic Group, University of Leeds

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.

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

Tin Lok Wong

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.

Models of PAWednesday, March 6, 20136:30 pmGC 4214.03

Keita Yokoyama

Several versions of self-embedding theorem

Mathematical Institute, Tohoku University

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.

Models of PAWednesday, February 27, 20136:30 pmGC 4214.03

Erez Shochat

Introduction to interstices and intersticial gaps II

St. Francis College
Models of PAWednesday, February 20, 20136:30 pmCUNY Graduate Center in room 4214.03.

Erez Shochat

Introduction to interstices and intersticial gaps

St. Francis College

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.