New Challenges in Reverse Mathematics - IMS

New Challenges in Reverse Mathematics
(3 - 16 Jan 2016)

~ Abstracts ~

Recursion theory over a model
David Belanger, National University of Singapore

Let $(M,S)$ be a model of $RCA_0$. Viewing the elements of $S$ as recursive, it is sensible to compare the (sufficiently well-behaved) sets $ X \subseteq M$ in terms of Turing reducibility. We develop the theory of these Turing degrees to a point, and receive several conservation theorems for our trouble.

A tutorial on Weihrauch complexity
Vasco Brattka, UniBW Munich, Germany

We present a tutorial on Weihrauch complexity. This theory aims to use the concept of Weihrauch reducibility in order to develop a uniform computational version of reverse mathematics, which is closely linked to computable analysis. In this tutorial we plan to present a survey on the theory as it has been developed so far. Roughly, the tutorial will be subdivided into three parts:

1. The Weihrauch lattice, its algebraic structure and choice
2. Jumps and higher levels
3. Probabilistic choice and algorithmic randomness

The strength of RT^1_k
Damir Dzhafarov, University of Connecticut, USA

The principle RT^1_k states that given any partition of \omega into k parts, at least one part must be infinite. Of course, this is a very weak statement, and for every (standard) k it is probable in the fragment RCA_0 of second-order arithmetic. In this sense, it is provable from every other principle one considers in reverse mathematics. If we move from proof theory to computability, and compare principles under computability-theoretic reducibilities rather than under provability over RCA_0, things become more interesting. I will give several examples along these lines, and outline a recent result (jointly with Patey, Solomon, and Westrick) that for k > l, RT^1_k is not sc-reducible to SRT^2_l. This answers a question of Hirschfeldt and Jockusch. The proof is a forcing argument using the tree labeling method, a new technique of building homogeneous sets for stable colorings, which I will describe. I will also talk about several related results (jointly with Hirschfeldt and Patey) concerning the strength of RT^1_k under Weihrauch reducibility.

Brown's lemma is equivalent to Sigma02-induction
Emanuele Frittaion, Tohoku University, Japan

We discuss a partion lemma in combinatorial number theory due to Brown (1969) and closely related to van der Waerden's theorem. We show that, over RCA0, Brown's lemma is equivalent to ISigma02. Brown's lemma. Every finite partition of the natural numbers has a piecewise syndetic cell. An infinite set X is piecewise syndetic if there is a natural number d such that X contains arbitrarily large sets with gaps bounded by d.

Ramsey properties of partial orderings
Marcia Groszek, Dartmouth College, USA

We discuss open problems in reverse mathematics and Ramsey properties of partial orderings. Very little analysis of partial orderings with infinite levels has been done so far.

Weak choice principles in the Weihrauch degrees
Takayuki Kihara, The University of California, Berkeley, USA

Various problems on the Weihrauch degrees have been proposed in the Dagstuhl seminar on "Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis". We give solutions to some of the Dagstuhl problems, e.g., those on the strengths of sequential compositions and parallel products of several "non-uniformly computable" choice principles.

Logical analysis of proofs in convex optimization and nonlinear semigroup theory that are based on WKL or ACA
Ulrich Kohlenbach, Technische Universitaet Darmstadt, Germany

We present some recent uses of proof-mining in the areas of convex optimization and nonlinear semigroup theory. The proofs analyzed are based on ACA or WKL to which then proof-theoretic elimination procedures are applied resulting in explicit and low complexity (polynomial or simple exponential) bounds.

On cone avoid result under certain combinatorial condition
Lu Liu, Central South University, China

In this talk, we present a method used to prove $\mathsf{RT}_2^2$ does not imply $\mathsf{WWKL}$. We also discuss other applications and generalizations about it. We also propose some further questions.

Ramsey's theorem and compactness
Ludovic Patey, Université Paris Diderot Paris 7, France

Ramsey's theorem (RT^n_k) asserts that every k-coloring of the n-tuples of integers admits an infinite monochromatic set. The standard proof of Ramsey's theorem for pairs involves weak König's lemma (WKL). Recently, Liu proved that RT^2_2 does not imply WKL, and therefore that WKL is not needed in the proof of RT^2_2. Later, Flood introduced a Ramsey-type weak König's lemma which happens to be the exact amount of compactness needed by RT^2_2. In this talk, we present an extensive analysis of the links between Ramsey-type theorems and various notions of compactness.

Bounds for the strength of the graph minor theorem
Michael Rathjen, University of Leeds, UK

The graph minor theorem, GM, is arguably the most important theorem of graph theory. The strength of GM exceeds that of the standard classification systems of RM known as the "big five". The plan is to survey the current knowledge about the strength of GM and other Kruskal-like principles, presenting lower and upper bounds.

The unreasonable effectiveness of Nonstandard Analysis and Reverse Mathematics
Sam Sanders, Ludwig-Maximilians-Universität München, Germany

We show that equivalences between theorems from Nonstandard Analysis (NSA) give rise to effective equivalences in Kohlenbach's higher-order Reverse Mathematics (RM) (where the latter does not involve NSA). We study examples of such equivalences for nonstandard versions of the Big Five of RM, as well as particularly elegant notions, like nonstandard compactness, and the nonstandard notion of partial computable function. Furthermore, we show that carefully crafted effective equivalences *not involving NSA*, called Herbrandisations, in turn give rise to the original ?nonstandard? equivalences from NSA. Thus, we establish a two-way street between NSA and RM.

Higher reverse mathematics and determinacy principles
Noah Schweber, The University of California, Berkeley, USA

In this talk I will give an introduction to higher reverse mathematics. I will present a base theory, $RCA_0^3$, which is a conservative subtheory of the usual base theory $RCA_0^\omega$ of higher reverse mathematics that is more similar to $RCA_0$. I will then discuss the reverse mathematics of higher-order versions of $ATR_0$; the main result is the separation of clopen and open determinacy for reals. Time permitting, I will also present related results on versions of the axiom of choice.

Reverse mathematics and the strong Tietze extension theorem
Paul Shafer, Ghent University, Belgium

We survey versions of the Tietze extension theorem formulated in second-order arithmetic and show that a certain uniformly continuous version is equivalent to WKL_0 over RCA_0, which confirms a conjecture of Giusto and Simpson.

The reverse mathematics of some finiteness theorems in algebra
Stephen Simpson, Pennsylvania State University, USA

In this talk I discuss the reverse mathematics of some finiteness theorems in algebra. A long time ago I showed that the Hilbert Basis Theorem (``every ideal in a polynomial ring is finitely generated'') is reverse-mathematically equivalent to well-orderedness of $\omega^\omega$, hence not finitistically reducible in the sense of Hilbert's Program in the foundations of mathematics. This reverse-mathematical result supports Gordan's famous remark to the effect that the Hilbert Basis Theorem is not mathematics but rather theology. Some similar finiteness theorems due to Robson and MacLagan are even more theological, in that they are reverse-mathematically equivalent to well-orderedness of $\omega^{\omega^\omega}$. Let $K[S]$ denote the group ring of the infinite symmetric group $S$. A 1976 theorem of Formanek and Lawrence says that every 2-sided ideal in $K[S]$ is finitely generated, i.e., every ascending chain of such ideals is finite. The proof uses w.q.o.\ theory plus detailed information concerning Young diagrams and the representation theory of the finite symmetric groups. Recently Kostas Hatzikiriakou and I used b.q.o.\ theory to show that these same ideals satisfy the antichain condition, i.e., every antichain of such ideals is finite. For these ideals we prove that the ascending chain condition is reverse-mathematically equivalent to well-orderedness of $\omega^\omega$, but the reverse-mathematical status of the antichain condition remains as an open question.

An overview on recent results on semiautomatic groups and semigroups
Frank Stephan, National University of Singapore

An automatic function is a function where a deterministic finite automaton verifies that the output belongs to the input, that is, it reads the input and output with the same speed (one symbol per cycle) and accepts iff the output is correct for the given input. Automatic functions can also be characterised as those which are computed by position-faithful one-tape Turing machines in linear time. A group is automatic iff its domain is regular and both, equality and the group operation, are automatic functions with two inputs (read at the same speed). A group is Cayley automatic iff the domain is regular and equality is automatic and multiplication with a fixed group element is an automatic function; furthermore, one might postulate that the group is finitely generated. A group is semiautomatic, iff the domain is regular, for each fixed group element the set of all representatives is regular and for each fixed group element the multiplication from either side is automatic. Note that Cayley automatic does not require that multiplication with constants from both sides is automatic but only from one side. The talk will give an overview on recent results on these three types of groups and automaticity.

Determinacy strength of infinite games in omega-languages recognized by variations of automata
Kazuyuki Tanaka, Tohoku University, Japan

Continuing my talk at the 2014 IMS-JSPS workshop in Singapore, I will report on the progress of our study on determinacy strength of infinite games in omega-languages recognized by variations of automata. For example, we downscale O. Finkel?s result on analytic determinacy in context-free omega-languages to the Borel hierarchy, so that we obtain some reverse-mathematical results on determinacy. This is a joint work with Wenjuan Li.

Generalized Goodstein sequences
Andreas Weiermann, Ghent University, Belgium

A by know famous independence result for $ACA_0$ concerns the unprovability of the termination of the Goodstein sequences. The classical Goodstein sequences are defined relative to complete base $k$-representations of natural numbers.

Instead of working with base $k$-representations we now consider natural representations of natural numbers in terms of plus, times, exponetiations, and the branches of the Ackermann function where the start function is $A_0(k,b):=k^b$.

We analyze the termination behavior of the resulting Goodstein sequences and among other things we obtain a natural independence result for $ATR_0$.

This is joint work with Tosi Arai and Stan Wainer

A survey on Q-degrees
Guohua Wu, Nanyang Technological University

In the talk, I will give a survey on recent research on Q-degrees, with the focus on the isolation phenomenon involved.

The proof-theoretic strength of Ramsey's theorem for pairs
Keita Yokoyama, Japan Advanced Institute of Science and Technology, Japan

In this talk, we study the proof-theoretic strength of Ramsey's theorem for pairs and two colors. Bovykin and Weiermann pointed out that the proof-theoretic strength of RT^2_2 can be can be approximated by Paris's density notion. Here, a finite set is said to be n-dense if one can apply Ramsey's theorem for pairs n-times repeatedly and the result set is still relatively large. Then, the Pi^0_3-part of RT^2_2+WKL_0 is the same as that of RCA_0+"any infinite set contains an n-dense subset" for any standard n. In this talk, we introduce a new combinatorial principle called grouping principle, and with this, calculate the size of dense sets for RT^2_2. By this we will show that the Pi^0_3-part of RT^2_2+WKL_0 is the same as that of RCA_0, and thus RT^2_2 does not imply the totality of the Ackermann function, which answers the question posed by Cholak, Jockusch and Slaman. This is a joint work with Ludovic Patey.

Best viewed with IE 7 and above