
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 wellbehaved) 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.
« Back... 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
« Back... 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 secondorder 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 computabilitytheoretic 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 screducible 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.
« Back... Brown's lemma is equivalent to Sigma02induction 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.
« Back... 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.
« Back... 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 "nonuniformly computable" choice principles.
« Back... 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 proofmining in the areas of convex optimization and nonlinear semigroup theory. The proofs analyzed are based on ACA or WKL to which then prooftheoretic elimination procedures are applied resulting in explicit and low complexity (polynomial or simple exponential) bounds.
« Back... 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.
« Back... Ramsey's theorem and compactness Ludovic Patey, Université Paris Diderot Paris 7, France
Ramsey's theorem (RT^n_k) asserts that every kcoloring of the ntuples 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 Ramseytype 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 Ramseytype theorems and various notions of compactness.
« Back... 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 Kruskallike principles, presenting lower and upper bounds.
« Back... The unreasonable effectiveness of Nonstandard Analysis and Reverse Mathematics Sam Sanders, LudwigMaximiliansUniversität München, Germany
We show that equivalences between theorems from Nonstandard Analysis (NSA) give rise to effective equivalences in Kohlenbach's higherorder 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 twoway street between NSA and RM.
« Back... 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 higherorder 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.
« Back... Reverse mathematics and the strong Tietze extension theorem Paul Shafer, Ghent University, Belgium
We survey versions of the Tietze extension theorem formulated in secondorder 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.
« Back... 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 reversemathematically equivalent to wellorderedness of $\omega^\omega$, hence not finitistically reducible in the sense of Hilbert's Program in the foundations of mathematics. This reversemathematical 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 reversemathematically equivalent to wellorderedness 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 2sided 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 reversemathematically equivalent to wellorderedness of $\omega^\omega$, but the reversemathematical status of the antichain condition remains as an open question.
« Back... 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 positionfaithful onetape 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.
« Back... Determinacy strength of infinite games in omegalanguages recognized by variations of automata Kazuyuki Tanaka, Tohoku University, Japan
Continuing my talk at the 2014 IMSJSPS workshop in Singapore, I will report on the progress of our study on determinacy strength of infinite games in omegalanguages recognized by variations of automata. For example, we downscale O. Finkel?s result on analytic determinacy in contextfree omegalanguages to the Borel hierarchy, so that we obtain some reversemathematical results on determinacy. This is a joint work with Wenjuan Li.
« Back... 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
« Back... A survey on Qdegrees Guohua Wu, Nanyang Technological University
In the talk, I will give a survey on recent research on Qdegrees, with the focus on the isolation phenomenon involved.
« Back... The prooftheoretic strength of Ramsey's theorem for pairs Keita Yokoyama, Japan Advanced Institute of Science and Technology, Japan
In this talk, we study the prooftheoretic strength of Ramsey's theorem for pairs and two colors. Bovykin and Weiermann pointed out that the prooftheoretic strength of RT^2_2 can be can be approximated by Paris's density notion. Here, a finite set is said to be ndense if one can apply Ramsey's theorem for pairs ntimes repeatedly and the result set is still relatively large. Then, the Pi^0_3part of RT^2_2+WKL_0 is the same as that of RCA_0+"any infinite set contains an ndense 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_3part 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.
« Back...

