Simpson, S. G. [2009], Subsystems of Second Order Arithmetic 2nd
ed., Perspectives in Logic, Association for Symbolic Logic and
Cambridge University Press, New York.
Expected primary topics and papers:
Ramsey's Theorem: Cholak, P. A., Jockusch, Jr., C. G. and Slaman, T. A.
[2001], On the strength of Ramsey's Theorem for pairs, Journal of
Symbolic Logic 66, 1--55.
New unpublished results: Liu, Ramsey's Theorem for pairs does not imply
WKL$_{0}$ (forcing) and if the proof works and gets written up soon: Chong,
Slaman and Yang, Stable Ramsey's Theorem for pairs does not imply Ramsey's
Theorem for pairs (nonstandard models).
Weak consequences of Ramsey's theorem: Hirschfeldt, D. R. and Shore, R. A.
[2007], Combinatorial principles weaker than Ramsey's theorem for pairs.
Journal of Symbolic Logic 72, 171--206.
Some Strong Ramsey type theorems depending on interest and time:
Hindman's Theorem: Blass, A., Hirst, J., Simpson, S., Logical analysis of some
theorems of combinatorics and topological dynamics, in S. Simpson ed., Logic
and Combinatorics, Contemporary Mathematics , AMS, 1987.
Infinite exponent Ramsey's Theorem: open ($\Sigma_{1}^{0}$), arithmetical
($\Sigma_{\omega}^{0}$), Borel ($\Delta_{1}^{1}$) (Galvin-Prikry) and
analytic ($\Sigma_{1}^{1}$):
Some in Simpson's book V.9, VI.6; others in
Tanaka, K. [1989], The Galvin-Prikry theorem and set existence axioms,
Annals of Pure and Applied Logic 42, 81-104 and others.
Dual Ramsey Theorem: Carlson, T. and Simpson. S. [1984] A dual form of
Ramsey's theorem, Advances in Mathematics 53, 265-290.
Miller, J. and Solomon, R. [2004], Effectiveness for infinite variable words and the
dual Ramsey theorem, Archive for Mathematical Logic 43, 543-555.
We meet in Malott 206. Tuesday 2:55-4:10 and Wednesday 4:00-5:15.
The Topic day will be Wednesday unless some scheduling issues arise for some specific week.
Schedule of Seminars:
Tuesday, 1/24: Organizational meeting.
Wednesday, 1/25: Reverse Mathematics and Recursion Theory
Richard A.
Shore, Cornell University
Tuesday, 1/31: Biinterpretability up to double jump:
The Turing degrees below 0'
Richard A. Shore, Cornell University
Wednesday, 2/1: WKL_0, RT^n_k and ACA_0: Some relations
Richard A. Shore , Cornell University
Tuesday, 2/7: TBA
Justin Moore, Cornell University
Wednesday, 2/8: Ramsey's Theorem for pairs I
David Belanger, Cornell University
Tuesday, 2/14: On the reverse mathematics of Peano categoricity
Keita Yokayama, Tokyo Institute of Technology and Penn. State
University
Abstract:
It is important in the foundations of mathematics that the natural
number system is characterizable as a system of 0 and a successor
function by second-order logic. In other words, the following Peano
categoricity theorem holds: every Peano system (P,e,F) is isomorphic
to the natural number system (N,0,S). In this talk, we will
investigate the Peano categoricity theorem and other similar
statements. We will first do reverse mathematics over RCA0, and then
weaken the base theory. This is a joint work with Stephen G. Simpson.
There will be a dinner with the speaker after the talk.
Wednesday, 2/15: Ramsey's Theorem for pairs II
David Belanger, Cornell University
Tuesday, 2/21: Bases, non-hyperfiniteness, and rigidity
Ben Miller, University of Munster
Abstract: By the Glimm-Effros dichotomy, every non-smooth countable Borel
equivalence relation contains a copy of the non-smooth hyperfinite Borel
equivalence relation. We will discuss how local rigidity properties of the
usual action of SL_2(Z) on R^2 can be used to rule out analogous results
for the class of non-measure-hyperfinite Borel equivalence relations. I
hope to make the talk accessible to a broad audience.
Wednesday, 2/22: Proving that Artinian implies Noetherian without proving that
Artinian implies finite length
Chris Conidis, Waterloo University
Abstract: Let $R$ be a commutative ring with identity. Recall from basic
graduate algebra that:
1. $R$ is Noetherian if it satisfies the ascending chain condition on its
ideals;
2. $R$ is Artinian if it satisfies the descending chain condition on its
ideals; and
3. $R$ is of finite length if there is a uniform bound on the length of any
(strictly increasing/decreasing) chain of ideals in $R$.
It is well-known that 2. implies 1., but the proofs given in most standard
algebra texts prove this by showing the stronger statement that 2. implies
3. This begs the question: "Can one prove that 2. implies 1. without
showing that 2. implies 3? We will show that this is indeed the case by
showing that, in the context of reverse mathematics, the former (weaker)
statement is equivalent to weak K\"onig's lemma, while the latter
(stronger) statement is equivalent to arithmetic comprehension in the
context of $\omega$-models. Another way to view our main result is that it
proves that there is a model of computable mathematics in which 2. implies
1., but 2. does not imply 3.
There will be a dinner for both Ben Miller and Chris Conidis on Wedensday.
Tuesday, 2/28: Weak irregular principles
Damir Dzhafarov, Notre Dame University
Abstract: The investigation of the logical content of mathematical theorems
in the framework of reverse mathematics is today an active and
well-developed area. Its originators saw the subject as the classification
of mathematical principles into one of several natural categories according
to the set-existence assumptions required for their proof. While this view
was affirmed by the strengths of the vast majority of mathematical
statements, the last ten years have seen a growing number of principles fall
outside its scope. The most notable example is Ramsey's theorem for pairs,
but at last count, it is now joined by over thirty principles from a variety
of mathematical areas, including combinatorics, model theory, set theory,
and measure theory. I shall present an introduction to principles of this
``irregular'' type, focusing on those lying below below the subsystem
$ACA_0$, and include a survey of recent results and open questions.
There will be a dinner with the speaker after the seminar.
Wednesday, 2/29: Ramsey's Theorem for pairs III
David Belanger Cornell University
Tuesday, 3/6: Situated Games
Adam Bjorndahl Cornell University
Abstract:
We propose a generalization of classical game theory in which utility is
defined not on strategy profiles ("outcomes"), but on "situations", which
are, loosely speaking, descriptions in some fixed, formal language. The
classical setting is recovered as the special case in which the language
only has terms that express the strategies chosen by the players. Recent
work in "psychological game theory" can be captured in our framework by
fixing a formal language that is equipped with belief modalities.
Epistemic logic comes in many flavors, so there are several such languages
one might consider for this purpose. In this talk, I will focus on the
language associated with the qualitative logic of belief captured by the
KD45 axiom system. I will show that the analogue of Nash's theorem fails:
there do not, in general, exist mixed strategy Nash equilibria. However,
under mild assumptions, rationalizable strategies can be shown to exist in
general.
Wednesday, 3/7: Principles weaker than Ramsey's theorem for pairs I
Tom Kern
Cornell University
Tuesday, 3/13: The jump of a structure
Antonio Montalban, University of Chicago
Abstract:
In the last few years there has been various definitions of what the
Turing jump of an algebraic structure should be. We will discuss the
different definitions of the jump of a structure and talk about recent
results in the area.
There will be dinner with the speaker after the talk.
Wednesday, 3/14: Principles weaker than Ramsey's theorem for pairs II
Tom Kern Cornell University
Tuesday 3/20 and Wednesday 3/21, Spring Break, no seminar.
Tuesday, 3/27: Counterexamples in Reverse Mathematics Using Iterated Forcing
Henry Towsner, University of Connecticut
Abstract:
One of the main concerns of reverse mathematics is with theorems of
the form "given a instance X of a specified problem, there is a
solution Y". For instance, the principle ADS says that given any
linear ordering of the natural numbers, there is either an infinite
descending sequence or an infinite ascending sequence, while the
principle CAC says that given any partial ordering there is either an
infinite chain or an infinite antichain. A natural question in
reverse mathematics is what implications hold between these
principles. We describe an approach using a method similar to
iterated forcing: we simultaneously construct an instance X of CAC
together with solutions to all instances of ADS computable from X, as
well as all instances of ADS computable from those solutions, and so
on, with the property that none of these solutions to instances of ADS
compute a solution to X. It follows that ADS does not imply CAC. We
similarly construct an instance of a stable 2-coloring of the integers
(the principle SRT22) together with transitive subsets of every
tournament (the principle EM), showing that EM does not imply SRT22.
(Joint work with Manny Lerman and Reed Solomon.)
There will be a dinner with the speaker after the talk.
Wednesday, 3/28: The dual Ramsey theorem
Adam Bjorndhal, Cornell University
Tuesday, 4/3: Strict Reverse Mathamatics
Scott Messick, Cornell University
Wednesday, 4/4: The dual Ramsey theorem II
Adam Bjorndhal, Cornell University
Tuesday, 4/10: New
Dexter Kozen, Cornell University
Abstract:
There are many situations in computing in which we want to create
something new. We often do not care exactly what is created, as long
as it has the right properties. For example, when allocating a new
heap cell, we do not care exactly what its address in memory is, but
only that we can store and retrieve data there; for that purpose, any
heap cell is as good as any other. In object-oriented programming,
when we create a new object, we only care that it has the right fields
and methods and is different from every other object previously created.
In the lambda-calculus, when we rename a bound variable, we do
not care what the new variable is as long as it is fresh.
As common as it is, the intuitive act of creating a new object out of
nothing does not fit well with set-theoretic foundations. Such situations
are commonly modeled as an allocation of one of a previously existing
collection of equivalent candidates.
There are two difficulties with this view: the candidates for allocation
should be indiscernible, but they cannot be if one must be chosen
deterministically; and cardinality restrictions on the set of candidates
often interfere with closure conditions on the language.
In this talk I will describe a theoretical device for modeling the creation of
new indiscernible semantic objects during program execution. Simply put,
a semantic object is created by allocating a name for it. The object itself
is defined to be the congruence class of all its names. I will describe
an operational semantics for a higher-order functional language with
imperative and object-oriented features implementing this idea.
Wednesday, 4/11: Hindman's Theorem
Diana Ojeda, Cornell University
Tuesday, 4/17: Truth-table minimal pairs of Turing complete sets
Rachel Epstein, Harvard University
Abstract:
We will show that there is a pair of Turing complete sets that form a minimal
pair in the truth-table degrees. This question arose when studying the sets of
random strings with respect to a universal prefix-free machine, which Muchnik
has shown are Turing complete but not necessarily tt-complete. We show that
there is in fact no tt-minimal pair of such sets of random strings. This talk
is based on joint work with Cai, Downey, Lempp, and Miller.
There will be a dinner with the speaker after the talk.
Wednesday, 4/18: Hindman's Theorem II
Diana Ojeda, Cornell University
Tuesday, 4/24: Degrees of orderings on torsion-free abelian groups
Karen Lange, Wellesley College
Abstract
It is well known that an abelian group admits an ordering if and only if it
is torsion-free. This classical statement is false, however, from a
computable perspective. Downey and Kurtz (1986) showed that there is a
computable torsion-free abelian group that admits no computable ordering. We
look at generalizations of this result by examining the collection of
orderings X(G) on a given computable torsion-free group G. Specifically, we
are interested in the degree spectrum of X(G), i.e., the set of degrees of
orderings in X(G). One way to construct orderings is to use a basis for G,
and this relationship between bases and orderings has consequences for the
degree spectrum of X(G). Given these consequences, it is natural to ask
whether the degree spectra of orderings on computable torsion-free abelian
groups are closed upward. In joint work with Kach and Solomon, we show the
answer is no.
There will be a dinner with the speaker after the talk.
Wednesday, 4/25: The Atomic Model Theorem I
Richard A. Shore, Cornell University
Tuesday, 5/1: An abstract approach to Ramsey theory with applications to Ramsey
theorems for finite trees
Slawek Solecki, University of Illinois at Urbana-Champaign
Abstract: I will show how certain Ramsey results for finite trees (some old,
some new) are obtained
by applying an abstract approach to Ramsey theory. A streamlined version of
this abstract approach
will be explained in the talk.
Wednesday, 5/2: The Atomic Model Theorem II
Richard A. Shore, Cornell University