The reverse mathematics of

some finiteness theorems in algebra

Stephen G. Simpson Pennsylvania State University

http://www.math.psu.edu/simpson/ simpson@math.psu.edu

New Challenges in Reverse Mathematics Institute of Mathematical Sciences National University of Singapore

January 3–16, 2016 Basis theorems in algebra. Definition. A ring satisfies the ACC (ascending chain condition ) if every increasing sequence of ideals is finite. Equivalently, every ideal is finitely generated. Theorem (Hilbert 1890). Let K be a field. For all positive integers d, the polynomial ring K[x_{1}, …, x_{d}] satisfies the ACC. This is the Hilbert Basis Theorem . The Hilbert Basis Theorem is very important in invariant theory and in algebraic geometry. It is not to be confused with “basis theorems” in recursion theory!

Basis theorems in algebra (continued).

There are also the following basis theorems.

Theorem (Hilbert). Let K be a field. For all positive integers d, the formal power series ring K[[x_{1}, …, x_{d}]] satisfies the ACC.

Theorem (Formanek/Lawrence 1976). Let K be a field of characteristic 0. Let S be infinite symmetric group, i.e., the group of finitely supported permutations of ℕ. Then, the group ring K[S] satisfies the ACC for 2-sided ideals.

Does this hold for other locally finite groups beside S? In particular, does it hold for the Hall group?

Theorem (Robson 1978). Let K be a field. For all d the polynomial ring K⟨x_{1}, …, x_{d}⟩ in d noncommuting indeterminates satisfies the ACC for insertive ideals.

An insertive ideal is closed under multiplication on the left, multiplication on the right, and multiplication in the middle.

Some related finiteness theorems:

Theorem (Hatzikiriakou/Simpson 2015). K[S] satisfies the antichain condition , i.e., there is no infinite set of 2-sided ideals which are pairwise incomparable under inclusion.

Theorem (Maclagan 2000). For all positive integers d, the polymonial ring K[x_{1}, …, x_{d}] and the power series ring K[[x_{1}, …, x_{d}]] satisfy the antichain condition for monomial ideals , i.e., ideals generated by monomials.

Questions for algebraists: Is the antichain condition of interest to algebraists? What does the antichain condition mean for algebraic geometry, etc.?

Some reverse mathematics. Working in RCA_{0}, we restrict ourselves to countable fields. Theorem (Simpson 1988). Over RCA_{0},

1. Hilbert Basis Theorem ⟺ WO(ω^{ω}).

2. Robson’s Theorem ⟺ WO(ω^{ω^{ω}}). Theorem (Hatzikiriakou 1994). Over RCA_{0}, the Hilbert Basis Theorem for power series rings is equivalent to WO(ω^{ω}). Theorem (Hatzikiriakou/Simpson 2015). Over RCA_{0}, the Formanek/Lawrence Theorem is equivalent to WO(ω^{ω}), and Maclagan’s Theorem is equivalent to WO(ω^{ω^{ω}}). Note: The Hilbert Basis Theorem refers to an infinite sequence of rings, K[x_{1}, …, x_{d}], d ∈ ℕ, while Formanek/Lawrence refers to only one ring, K[S]. We also show that, in all of these reverse-mathematical results, the base theory RCA_{0} can be weakened to RCA∗_{0}.

Foundational significance:

The foundational significance of these results is as follows:

None of these basis theorems is finitistically reducible in the sense of Hilbert’s Program in the foundations of mathematics.)

In particular, our results support Gordan’s famous remark concerning the Hilbert Basis Theorem:

“That is not mathematics. That is theology!”

The point is that finitistic reducibility is equivalent to Π_{2}^{0}-conservativity over PRA (primitive recursive arithmetic). And RCA_{0} + WO(ω^{ω}) is not even Π_{1}^{0}-conservative over PRA, because it proves consistency of PRA and totality of the Ackermann function.

I will say more about Hilbert’s Program in my Public Lecture, Wednesday January 6, 18:30–19:30.

References:

Edward Formanek and John Lawrence, The group algebra of the infinite symmetric group, Israel Journal of Mathematics, 23, 1976, 325–331.

J. C. Robson, Well quasi-ordered sets and ideals in free semigroups and algebras, Journal of Algebra, 55, 1978, 521–535.

Stephen G. Simpson, Ordinal numbers and the Hilbert Basis Theorem, Journal of Symbolic Logic, 53, 1988, 961–974.

Kostas Hatzikiriakou, A note on ordinal numbers and rings of formal power series, Archive for Mathematical Logic, 33, 1994, 261–263.

Kostas Hatzikiriakou and Stephen G. Simpson, Reverse mathematics, Young diagrams, and the ascending chain condition, 2015, 14 pages, submitted for publication.

Stephen G. Simpson and Rick L. Smith, Factorization of polynomials and Σ_{1}^{0} induction, Annals of Pure and Applied Logic, 31, 1986, 289–306.

Diane Maclagan, Antichains of monomial ideals are finite, Proceedings of the

American Mathematical Society, 129, 2000, 1609–1615.

I will now give some details about the proof of both the Formanek/Lawrence Theorem and its reversal.

Partition theory.

As noted by Formanek and Lawrence, 2-sided ideals in K[S] are in 1-to-1 correspondence with certain sets of partitions .

A partition of n is a finite sequence of integers n_{1} ≥ ⋯ ≥ n_{k} > 0 such that n = n_{1} + ⋯ + n_{k}.

Example: (5, 2, 2, 1) is a partition of 10, because 10 = 5 + 2 + 2 + 1 and 5 ≥ 2 ≥ 2 ≥ 1 > 0.

Partitions of n are in 1-to-1 correspondence with conjugacy classes of S_{n}. Here S_{n} is the group of permutations of the set {1, …, n}.

Partition theory is a large branch of mathematics, closely connected to the representation theory of S_{n}.

Note: S = ∞ ; ⋃ ; n=1 S_{n} and K[S] = ∞ ; ⋃ ; n=1 K[S_{n}].

Partitions are often visualized as Young diagrams . For example, the partition 10 = 5 + 2 + 2 + 1 corresponds to the Young diagram

consisting of 10 boxes.

Rotated counterclockwise 135 degrees, this Young diagram becomes a downwardly closed set in (ℕ^{2}, ≤), partially ordered by (m, n) ≤ (p, q) ⟺ (m ≤ p and n ≤ q).

[figure]

A diagram is a finite downwardly closed set in ℕ^{2}. Let D_{2} be the set of diagrams, partially ordered by inclusion.

A poset P is said to be WPO (well partially ordered ) if (∀f : ℕ → P) ∃i ∃j (i < j and f(i) ≤ f(j)).

In my 1988 paper I show that, over RCA_{0},

1. K[x_{1}, …, x_{d}] has ACC ⟺ ℕ^{d} is WPO.

2. K⟨x_{1}, …, x_{d}⟩ ACC for insertive ideals ⟺ {x_{1}, …, x_{d}}∗ WPO.

Since ℕ^{2} is WPO, it follows by Higman’s Lemma that D_{2} is WPO.

A set U ⊆ D_{2} is said to be closed if ∀D (D ∈ U ⟺ ∀E (D ⫋ E ⇒ E ∈ U)). This implies that U is upwardly closed, but not conversely!

Formanek and Lawrence exhibit a 1-to-1 correspondence between 2-sided ideals in K[S] and closed sets in D_{2}. Since D_{2} is WPO, it has the ACC on closed sets, hence K[S] has the ACC on 2-sided ideals.

Reversing Formanek/Lawrence.

Working in RCA_{0}, we formalize the work of Formanek/Lawrence to prove that K[S] has the ACC if and only if D_{2} has the ACC on closed sets. Also working in RCA_{0}, we use methods of Simpson 1988 to prove that WO(ω^{ω}) ⟺ D_{2} is WPO.

Still working in RCA_{0}, it remains to prove: D_{2} is WPO ⟺ D_{2} has the ACC on closed sets. To prove this, we use a new combinatorial lemma. Lemma. Let S be a finite set of diagrams. Then, the closure of S is equal to the upward closure of {D_{r} ∪ E_{c} | D, E ∈ S}. Moreover, there are only finitely many diagrams in the closure of S which are not in the upward closure of S.

D_{r} and D_{c} are the results of truncating the first row and first column of D, respectively. For example, if D = (5, 2, 2, 1) then D_{r} = (2, 2, 2, 1) and D_{c} = (5, 2, 2).

Weakening the base theory.

Recall that RCA∗_{0} = RCA_{0} minus Σ_{1}^{0} induction plus integer exponentiation.

In our ACC reversals, we wish to replace RCA_{0} by RCA∗_{0}. For this, it suffices to prove in RCA∗_{0} that if K[x] has ACC then Σ_{1}^{0} induction holds.

Lemma. Over RCA∗_{0}, if Σ_{1}^{0} induction fails, then there exist an infinite set I ⊆ ℕ and a function f : I → ℕ such that (∀i ∈ I) (∀j ∈ I) (i < j ⇒ f(i) > f(j)).

In this situation, letting n_{i} = 2^{f(i)}, the ideals in K[x] generated by x^{n_{i}} for each i ∈ I are a counterexample to the ACC.

Philosophical aspect.

I have suggested that, in contrast to the concept of potential infinity , the concept of actual infinity appears to lack objective justification. Therefore, in order to promote objectivity in mathematics, it seems desirable to limit the use of actual infinity.

I see a close connection to Hilbert’s program of finitistic reductionism. Let us say that a system T ⊆ Z_{2} is finitistically reducible if all Π_{1}^{0} (or possibly even Π_{2}^{0}) sentences provable in T are provable in PRA, i.e., Primitive Recursive Arithmetic.

Some important systems are finitistically reducible, namely WKL_{0}, and WKL_{0} + Σ_{2}^{0} bounding, and some stronger systems. These systems suffice for the formalization of large parts of mathematics.

On the other hand, RCA_{0} + WO(ω^{ω}) and RCA_{0} + Σ_{2}^{0} induction are not finitistically reducible, because they prove Con(PRA) and totality of the Ackermann function.

Philosophical aspect (continued).

In particular, the Hilbert Basis Theorem and the Formanek/Lawrence Theorem are not finitistically reducible.

(However, for each specific positive integer d, the Hilbert Basis Theorem for K[x_{1}, …, x_{d}] is finitistically reducible, because it is provable in RCA_{0}.)

A remark on RT(2, 2).

Over the past few years, Chong, Slaman, Yang, and Yokoyama have done some important work on the reverse mathematics of RT(2, 2), i.e., Ramsey’s Theorem for exponent 2.

Very recently, Patey and Yokoyama solved an important problem by proving that RCA_{0} + RT(2, 2) is finitistically reducible. In fact, they proved that RCA_{0} + RT(2, 2) is Π_{3}^{0}-conservative over RCA_{0}.

More references:

David Hilbert, Über das Unendliche, Mathematische Annalen, 95, 1926, 161–190. William W. Tait, Finitism, Journal of Philosophy, 78, 1981, 524–546. Stephen G. Simpson, Partial realizations of Hilbert’s program, Journal of Symbolic Logic, 53, 1988, 349–363. Stephen G. Simpson, Subsystems of Second Order Arithmetic, Springer-Verlag, 1999, XIV + 445 pages; 2nd edition, Association for Symbolic Logic, 2009, XVI + 444 pages. Richard Zach, Hilbert’s Program, Stanford Encyclopedia of Philosophy, 2003, http://plato.stanford.edu/entries/hilbert-program/. Stephen G. Simpson, Toward objectivity in mathematics, in: Infinity and Truth, edited by C.-T. Chong, Q. Feng, T. A. Slaman, and W. H. Woodin, World Scientific, 2014, 157–169. Stephen G. Simpson, An objective justification for actual infinity?, same volume, 2014, 225–228.

Thank you for your attention!