Reverse mathematics and the ACC

Stephen G. Simpson Pennsylvania State University

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

Computability Theory and Foundations of Mathematics Tokyo Institute of Technology

February 17–20, 2014 Basis theorems in algebra.

Definition. A ring satisfies the ACC (ascending chain condition ) if every nondecreasing sequence of ideals is finite.

Equivalently, every ideal is finitely generated.

Theorem (Hilbert 1890). Let K be a field. For all 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 theorems.

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

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.

Theorem (Formanek/Lawrence 1976). Let K be a field of characteristic 0. Let S be the group of finitely supported permutations of ℕ. Then, the group ring K[S] satisfies the ACC.

Some reverse mathematics.

Working in RCA_{0}, we restrict ourselves to countable fields.

Theorem (Simpson 1988). Over RCA_{0}, 1. Hilbert’s Theorem ⟺ WO (ω^{ω}).

2. Robson’s Theorem ⟺ WO (ω^{ω^{ω}}).

Theorem (Hatzikiriakou 1994). Over RCA_{0}, Hilbert’s Theorem for power series rings is equivalent to WO (ω^{ω}).

Theorem (Hatzikiriakou/Simpson 2014). Over RCA_{0} the Formanek/Lawrence Theorem is equivalent to WO (ω^{ω}).

Note: Hilbert’s Theorem refers to an infinite sequence of rings, while Formanek/Lawrence refers to only one ring, K[S].

We also show that, in all of these reverse mathematics results, the base theory RCA_{0} can be weakened to RCA∗_{0}.

References:

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

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

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

J. C. Robson, Polynomials satisfied by matrices, Journal of Algebra, 55, 1978, 509–520.

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

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

Kostas Hatzikiriakou and Stephen G. Simpson, Reverse mathematics and partition theory, 2014, in preparation.

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

Partition theory.

As noted by Formanek and Lawrence, 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 diagram

consisting of 10 boxes.

Rotated counterclockwise 135 degrees, it becomes a downwardly closed set in (ℕ^{2}, ≤) where (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 ⟺ {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 ideals in K[S] and closed sets in D_{2}. Since D_{2} is WPO, it follows that D_{2} 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 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 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_{0} ∪ E_{1} | 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_{0} and D_{1} are the results of truncating the first row and first column of D, respectively. For example, if D = (5, 2, 2, 1) then D_{0} = (2, 2, 2, 1) and D_{1} = (5, 2, 2).

Weakening the base theory.

Recall that RCA∗_{0} is 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 exists f : ℕ → ℕ such that

(1) f(i) ≥ f(i + 1) for all i ∈ ℕ, and

(2) f(i) > f(i + 1) for infinitely many i ∈ ℕ.

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

Philosophical aspect.

Recently I 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. 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, since provable in RCA_{0}.)

Recently 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.

An important open question remains:

Is RCA_{0} + RT (2, 2) finitistically reducible?

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, Kazuyuki Tanaka, and Takeshi Yamazaki, Some conservation results on weak König’s lemma, Annals of Pure and Applied Logic, 118, 2002, 87–114.

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!