CUNY Graduate Center
Virtual
Organized by Athar Abdul-Quader and Roman Kossak
Fall 2020
December 9
The seminar will take place virtually at 3pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Konrad Zdanowski
Cardinal Stefan Wyszynski University in Warsaw
Truth predicate for $\Delta_0$ formulas and PSPACE computations
Abstract
We consider a bounded arithmetic in Buss's language enriched with a predicate Tr which is assumed to be a truth definition for bounded sentences. Among other things we assume polynomial induction for $\Sigma^b_1(\text{Tr})$ formulas. We show that such an arithmetic captures PSPACE. We prove a witnessing theorem for such an arithmetic by an interpretation of free-cuts free proofs of strict $\Sigma^{1,b}_1$ in $U^{1,*}_2$, a canonical second order arithmetic capturing PSPACE. It follows that the problem of the existence of a truth definition for $\Delta_0$ sentences without the totality of $\exp$ might be more about separating subexponential time alternation hierarchies from PSPACE.
The presentation is based on the following article: Konrad Zdanowski, Truth definition for $\Delta_0$ formulas and PSPACE computations, Fundamenta Mathematicae 252(2021) , 1-38.
Video
November 11
The seminar will take place virtually at 12pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Joel David Hamkins
Oxford University
Continuous models of arithmetic
Abstract
Ali Enayat had asked whether there is a model of Peano arithmetic (PA) that can be represented as $\langle\mathbb Q,\oplus,\otimes\rangle$, where $\oplus$ and $\otimes$ are continuous functions on the rationals $\mathbb Q$. We prove, affirmatively, that indeed every countable model of PA has such a continuous presentation on the rationals. More generally, we investigate the topological spaces that arise as such topological models of arithmetic. The reals $\mathbb{R}$, the reals in any finite dimension $\mathbb{R}^n$, the long line and the Cantor space do not, and neither does any Suslin line; many other spaces do; the status of the Baire space is open.
This is joint work with Ali Enayat, myself and Bartosz Wcisło.
Video
November 4
The seminar will take place virtually at 3pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Victoria Gitman
CUNY
A model of second-order arithmetic satisfying AC but not DC: Part II
Abstract
One of the strongest second-order arithmetic systems is full second-order arithmetic ${\rm Z}_2$ which asserts that every second-order formula (with any number of set quantifiers) defines a set. We can augment ${\rm Z}_2$ with choice principles such as the choice scheme and the dependent choice scheme. The $\Sigma^1_n$-choice scheme asserts for every $\Sigma^1_n$-formula $\varphi(n,X)$ that if for every $n$, there is a set $X$ witnessing $\varphi(n,X)$, then there is a single set $Z$ whose $n$-th slice $Z_n$ is a witness for $\varphi(n,X)$. The $\Sigma^1_n$-dependent choice scheme asserts that every $\Sigma^1_n$-relation $\varphi(X,Y)$ without terminal nodes has an infinite branch: there is a set $Z$ such that $\varphi(Z_n,Z_{n+1})$ holds for all $n$. The system ${\rm Z}_2$ proves the $\Sigma^1_2$-choice scheme and the $\Sigma^1_2$-dependent choice scheme. The independence of $\Pi^1_2$-choice scheme from ${\rm Z}_2$ follows by taking a model of ${\rm Z}_2$ whose sets are the reals of the Feferman-Levy model of ${\rm ZF}$ in which every $\aleph_n^L$ is countable and $\aleph_\omega^L$ is the first uncountable cardinal.
We construct a model of ${\rm ZF}+{\rm AC}_\omega$ whose reals give a model of ${\rm Z}_2$ together with the full choice scheme in which $\Pi^1_2$-dependent choice fails. This result was first proved by Kanovei in 1979 and published in Russian. It was rediscovered by Sy Friedman and myself with a slightly simplified proof.
Video
October 28
The seminar will take place virtually at 3pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Victoria Gitman
CUNY
A model of second-order arithmetic satisfying AC but not DC
Abstract
One of the strongest second-order arithmetic systems is full second-order arithmetic ${\rm Z}_2$ which asserts that every second-order formula (with any number of set quantifiers) defines a set. We can augment ${\rm Z}_2$ with choice principles such as the choice scheme and the dependent choice scheme. The $\Sigma^1_n$-choice scheme asserts for every $\Sigma^1_n$-formula $\varphi(n,X)$ that if for every $n$, there is a set $X$ witnessing $\varphi(n,X)$, then there is a single set $Z$ whose $n$-th slice $Z_n$ is a witness for $\varphi(n,X)$. The $\Sigma^1_n$-dependent choice scheme asserts that every $\Sigma^1_n$-relation $\varphi(X,Y)$ without terminal nodes has an infinite branch: there is a set $Z$ such that $\varphi(Z_n,Z_{n+1})$ holds for all $n$. The system ${\rm Z}_2$ proves the $\Sigma^1_2$-choice scheme and the $\Sigma^1_2$-dependent choice scheme. The independence of $\Pi^1_2$-choice scheme from ${\rm Z}_2$ follows by taking a model of ${\rm Z}_2$ whose sets are the reals of the Feferman-Levy model of ${\rm ZF}$ in which every $\aleph_n^L$ is countable and $\aleph_\omega^L$ is the first uncountable cardinal.
We construct a model of ${\rm ZF}+{\rm AC}_\omega$ whose reals give a model of ${\rm Z}_2$ together with the full choice scheme in which $\Pi^1_2$-dependent choice fails. This result was first proved by Kanovei in 1979 and published in Russian. It was rediscovered by Sy Friedman and myself with a slightly simplified proof.
Video
October 21
The seminar will take place virtually at 7pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Roman Kossak
CUNY
Types, gaps, and pairs of models of PA: Part III
Abstract
The talk will be a survey of results on first-order theories of pairs (N,M), where M is a model of PA and N is its elementary extension, under various assumptions on the models and on the type of extension. In particular, I will discuss in detail the results on countable recursively saturated models and their cofinal submodels from a joint paper with Jim Schmerl.
Video
October 14
The seminar will take place virtually at 7pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Roman Kossak
CUNY
Types, gaps, and pairs of models of PA: Part II
Abstract
The talk will be a survey of results on first-order theories of pairs (N,M), where M is a model of PA and N is its elementary extension, under various assumptions on the models and on the type of extension. In particular, I will discuss in detail the results on countable recursively saturated models and their cofinal submodels from a joint paper with Jim Schmerl.
Video
October 7
The seminar will take place virtually at 7pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Roman Kossak
CUNY
Types, gaps, and pairs of models of PA
Abstract
The talk will be a survey of results on first-order theories of pairs (N,M), where M is a model of PA and N is its elementary extension, under various assumptions on the models and on the type of extension. In particular, I will discuss in detail the results on countable recursively saturated models and their cofinal submodels from a joint paper with Jim Schmerl.
Video
September 30
The seminar will take place virtually at 3pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Leszek Kołodziejczyk
University of Warsaw
Ramsey's Theorem over $\mathrm{RCA}^*_0$: Part II
Abstract
The usual base theory used in reverse mathematics, $\mathrm{RCA}_0$, is the fragment of second-order arithmetic axiomatized by $\Delta^0_1$ comprehension and $\Sigma^0_1$ induction. The weaker base theory $\mathrm{RCA}^*_0$ is obtained by replacing $\Sigma^0_1$ induction with $\Delta^0_1$ induction (and adding the well-known axiom $\exp$ in order to ensure totality of the exponential function). In first-order terms, $\mathrm{RCA}_0$ is conservative over $\mathrm{I}\Sigma_1$ and $\mathrm{RCA}^*_0$ is conservative over $\mathrm{B}\Sigma_1 + \exp$.
Some of the most interesting open problems in reverse mathematics concern the first-order strength of statements from Ramsey Theory, in particular Ramsey's Theorem for pairs and two colours. In this talk, I will discuss joint work with Kasia Kowalik, Tin Lok Wong, and Keita Yokoyama concerning the strength of Ramsey's Theorem over $\mathrm{RCA}^*_0$.
Given standard natural numbers $n,k \ge 2$, let $\mathrm{RT}^n_k$ stand for Ramsey's Theorem for $k$-colourings of $n$-tuples. We first show that assuming the failure of $\Sigma^0_1$ induction, $\mathrm{RT}^n_k$ is equivalent to its own relativization to an arbitrary $\Sigma^0_1$-definable cut. Using this, we give a complete axiomatization of the first-order consequences of $\mathrm{RCA}^*_0 + \mathrm{RT}^n_k$ for $n \ge 3$ (this turns out to be a rather peculiar fragment of PA) and obtain some nontrivial information about the first-order consequences of $\mathrm{RT}^2_k$. Time permitting, we will also discuss the question whether our results have any relevance for the well-known open problem of characterizing the first-order consequences of $\mathrm{RT}^2_2$ over the traditional base theory $\mathrm{RCA}_0$.
In the first part of the talk, we concentrated on Ramsey's Theorem for $n$-tuples where $n \ge 3$. In this second part, the focus will be on $\mathrm{RT}^2_2$.
Video
September 16
The seminar will take place virtually at 5pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Sam Coskey
Boise State University
Classification of countable models of ZFC
Abstract
In 2009 Roman Kossak and I showed that the classification of countable models of PA is Borel complete, which means it is as complex as possible. The proof is a straightforward application of Gaifman’s canonical I-models. In 2017 Sam Dworetzky, John Clemens, and I showed that the argument may also be used to show the classification of countable models of ZFC is Borel complete too. In this talk I'll outline the original argument for models of PA, the adaptation for models of ZFC, and briefly consider several subclasses of countable models of ZFC.
Video
September 9
The seminar will take place virtually at 3pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Saeideh Bahrami
Institute for Research in Fundamental Sciences, Tehran
Fixed Points of Initial Self-Embeddings of Models of Arithmetic
Abstract
In 1973, Harvey Friedman proved his striking result on initial self-embeddings of countable nonstandard models of set theory and Peano arithmetic. In this talk, I will discuss my joint work with Ali Enayat focused on the fixed point set of initial self-embeddings of countable nonstandard models of arithmetic. Especially, I will survey the proof of some generalizations of well-known results on the fixed point set of automorphisms of countable recursively saturated models of $ \mathrm{PA} $, to results about the fixed point set of initial self-embeddings of countable nonstandard models of $ \mathrm{I}\Sigma_{1} $.
Video
September 2
The seminar will take place virtually at 3pm US Eastern Standard Time. Please email Victoria Gitman for meeting id.
Petr Glivický
Universität Salzburg
The $\omega$-iterated nonstandard extension of $\mathbb{N}$ and Ramsey combinatorics
Abstract
In the theory of nonstandard methods (traditionally known as nonstandard analysis), each mathematical object (a set) $x$ has a uniquely determined so called nonstandard extension ${}^*x$. In general, ${}^*x \supsetneq \{{}^*y; y\in x\}$ - that is, besides the original 'standard' elements ${}^*y$ for $y\in x$, the set ${}^*x$ contains some new 'nonstandard' elements.
For instance, some of the nonstandard elements of ${}^*\mathbb{R}$ can be interpreted as infinitesimals (there is $\varepsilon\in {}^*\mathbb{R}$ such that $0<\varepsilon<1/n$ for all $n\in\mathbb{N}$) allowing for nonstandard analysis to be developed in ${}^*\mathbb{R}$, while ${}^*\mathbb{N}$ turns out to be an (at least $\aleph_1$-saturated) nonstandard elementary extension of $\mathbb{N}$ (in the language of arithmetic).
While the whole nonstandard real analysis is most naturally developed in ${}^*\mathbb{R}$ (with just a few advanced topics where using the second extension ${}^{**}\mathbb{R}$ is convenient, though far from necessary), recent successful applications of nonstandard methods in combinatorics on $\mathbb{N}$ have utilized also higher order extensions ${}^{(n)*}\mathbb{N} = {}^{***\cdots *}\mathbb{N}$ with the chain $***\cdots *$ of length $n>2$.
In this talk we are going to study the structure of the $\omega$-iterated nonstandard extension ${}^{\cdot}\mathbb{N} = \bigcup_{n\in\omega} {}^{(n)*}\mathbb{N}$ of $\mathbb{N}$ and show how the obtained results shed new light on the complexities of Ramsey combinatorics on $\mathbb{N}$ and allow us to drastically simplify proofs of many advanced Ramsey type theorems such as Hindmann's or Milliken's and Taylor's.
Slides
Video