Reverse mathematics, ordinal numbers, and the ACC

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/ simpson@math.psu.edu

August 8, 2014

This is my abstract for Proof Theory, Modal Logic, Reflection Principles (Second International Wormshop), ITAM, Mexico City, September 29 – October 2, 2014.

In abstract algebra, a ring is said to satisfy the ACC (ascending chain condition) if it has no infinite ascending sequence of ideals. According to a famous and controversial theorem of Hilbert, 1890, polynomial rings with finitely many indeterminates satisfy the ACC. There is a similar theorem for noncommuting indeterminates, due to J. C. Robson, 1978. In 1988 I performed a reversemathematical analysis of the theorems of Hilbert and Robson, proving that they are equivalent over RCA_{0} to the well-orderedness of (the standard notation systems for) the ordinal numbers ω^{ω} and ω^{ω^{ω}} respectively. Now I perform a similar analysis of a theorem of Formanek and Lawrence, 1976. Let S be the group of finitely supported permutations of the natural numbers. Let K[S] be the group ring of S over a countable field K of characteristic 0. Formanek and Lawrence proved that K[S] satisfies the ACC. All of these results concerning the ACC involve well partial ordering theory. I now prove that the Formanek/Lawrence theorem is equivalent over RCA_{0} to the well-orderedness of ω^{ω}. The proof involves an apparently new, combinatorial lemma concerning Young diagrams. I also show that, in all of these reverse-mathematical results, RCA_{0} can be weakened to RCA_{0}^{∗}. This recent work was done jointly with Kostas Hatzikiriakou.

In addition, I make some remarks concerning reverse mathematics as it applies to Hilbert’s foundational program of finitistic reductionism. It is significant that RCA_{0} and WKL_{0} and even WKL_{0} + Σ_{2}^{0}-bounding are Π_{2}^{0}-conservative over PRA, while Σ_{2}-induction and the well-orderedness of ω^{ω} are not even Π_{1}^{0}-conservative over PRA. The proof-theoretic strength of RCA_{0} + Ramsey’s Theorem for exponent 2 is an open question which has attracted much recent attention.