Reverse mathematics, Young diagrams, and the ascending chain condition

Kostas Hatzikiriakou Department of Primary Education University of Thessaly Argonafton & Filellinon Volos 38221, GREECE kxatzkyr@uth.gr

Stephen G. Simpson Department of Mathematics Pennsylvania State University State College, PA 16802, USA http://www.math.psu.edu/simpson simpson@math.psu.edu

First draft: January 27, 2014 This draft: March 25, 2016

Abstract

Let S be the group of finitely supported permutations of a countably infinite set. Let K[S] be the group algebra of S over a field K of characteristic 0. According to a theorem of Formanek and Lawrence, K[S] satisfies the ascending chain condition for two-sided ideals. We study the reverse mathematics of this theorem, proving its equivalence over RCA_{0} (or even over RCA∗_{0}) to the statement that ω^{ω} is well ordered. Our equivalence proof proceeds via the statement that the Young diagrams form a well partial ordering.

Keywords: reverse mathematics, ascending chain condition, group rings, Young diagrams, partition theory, well partial orderings.

2010 MSC: Primary 03B30; Secondary 16P40, 16S34, 05A17, 03F15.

Simpson’s research was partially supported by the Eberly College of Science at the Pennsylvania State University, and by Simons Foundation Collaboration Grant 276282. A version of this paper will be published in the Journal of Symbolic Logic.

Contents

1 Introduction  2
2 Well partial ordering of diagrams  4
3 Closed sets of diagrams  6
4 Two-sided ideals in K[S]  9
5 Weakening the base theory  10
6 A question for future research  12
References  13

1 Introduction

Reverse mathematics is a research program in the foundations of mathematics. The purpose of reverse mathematics is to discover which axioms are needed to prove specific core-mathematical theorems of analysis, algebra, geometry, combinatorics, etc. Reverse mathematics takes place in the context of subsystems of second-order arithmetic. The standard reference for reverse mathematics is [28, Part A].

This paper is a contribution to the reverse mathematics of algebra. Let ℚ be the field of rational numbers. The Hilbert Basis Theorem [11] says that, for each positive integer n, there is no infinite ascending sequence of ideals in the polynomial ring ℚ[x_{1}, …, x_{n}]. This is one of the most famous theorems of abstract algebra. In a previous paper [26, Theorem 2.7] we have shown that the Hilbert Basis Theorem^{1} is reverse-mathematically equivalent to WO(ω^{ω}). Here WO(ω^{ω}) is the assertion that (the standard system of Cantor normal form notations for the ordinal numbers less than the ordinal number) ω^{ω} is well ordered. The place of WO(ω^{ω}) within the usual hierarchy of subsystems of second-order arithmetic [28] is discussed in our expository paper [32].

Our reverse-mathematical result in [26, Theorem 2.7] implies that the Hilbert Basis Theorem is not finitistically reducible. (See [26, Proposition 2.6].) This foundational outcome is significant with respect to Hilbert’s foundational program of finitistic reductionism [12, 27, 35]. In a certain fairly precise philosophical sense [30, 31], our result in [26, Theorem 2.7] justifies Gordan’s famous remark (see [19]) to the effect that the Hilbert Basis Theorem is not mathematics but rather theology.

On the other hand, in analyzing the significance of [26, Theorem 2.7], it is important to note that the Hilbert Basis Theorem refers not to a single ring but to a sequence of rings ℚ[x_{1}, …, x_{n}] where n = 1, 2, 3, . . .. Moreover, for each specific positive integer n, the special case ℚ[x_{1}, …, x_{n}] of the Hilbert Basis Theorem is finitistically reducible, in fact provable in RCA_{0} [26, Lemmas 3.4 and 3.6]. Therefore, from the foundational viewpoint of [26, §1], it would be interesting to find a specific commutative ring which has no infinite ascending sequence of ideals and to prove that the corresponding basis theorem is not finitistically reducible.

1A related theorem of Hilbert says that for each n there is no infinite ascending sequence of ideals in the power series ring ℚ[[x_{1}, …, x_{n}]]. We have shown in [10] that this theorem, like the Hilbert Basis Theorem, is reverse-mathematically equivalent to WO(ω^{ω}).

At the moment we are unable to provide such a commutative ring, but in this paper we achieve something similar in the noncommutative case. Specifically, we perform a reverse-mathematical analysis of a theorem of Formanek and Lawrence [6]. The Formanek/Lawrence Theorem says that there is no infinite ascending sequence of twosided ideals in the group algebra ℚ[S] of the infinite symmetric group S over the field ℚ. The purpose of this paper is to show that the Formanek/Lawrence Theorem, like the Hilbert Basis Theorem, is reverse-mathematically equivalent to WO(ω^{ω}). From this result it follows, just as in [26], that the Formanek/Lawrence Theorem is not finitistically reducible.

Our work in this paper involves partitions. A partition is a finite sequence of integers m_{1}, …, m_{k} such that m_{1} ≥ ⋯ ≥ m_{k} > 0 and k > 0. It is well known (see for instance [4, §28]) that there is a close relationship between two-sided ideals in ℚ[S] and partitions. A partition m_{1}, …, m_{k} is usually visualized as a Young diagram, i.e., a planar array of boxes with k left-justified rows of lengths m_{1}, …, m_{k} respectively. For example, the partition 5, 2, 2, 1 is visualized as the Young diagram in Figure 1 consisting of 10 = 5 + 2 + 2 + 1 boxes. Note that there is another partition 4, 3, 1, 1, 1 consisting of the lengths of the columns of this same Young diagram. A standard reference for partition theory is [1].

Figure 1: The Young diagram corresponding to the partition 5, 2, 2, 1.

Our notation and terminology in this paper is as follows. We use ℕ to denote the set of positive integers. We use i, j, k, l, m, n as variables ranging over ℕ. We use D to denote the set of diagrams, i.e., Young diagrams. We use D, E, F, G, H as variables ranging over D. Given D ∈ D, the number of boxes in D is denoted |D|. We write r_{i}(D) = the length of the ith row of D, or 0 if i > the number of rows. Similarly, we write c_{i}(D) = the length of the ith column of D, or 0 if i > the number of columns. Note that |D| = r_{1}(D) + ⋯ + r_{k}(D) = c_{1}(D) + ⋯ + c_{l}(D) where k = c_{1}(D) = max({i | r_{i}(D) > 0}) = the number of rows, and l = r_{1}(D) = max({i | c_{i}(D) > 0}) = the number of columns. Note also that |D| ≤ r_{1}(D) · c_{1}(D). For D, E ∈ D we write D ≤ E to mean that r_{i}(D) ≤ r_{i}(E) for all i, or equivalently c_{i}(D) ≤ c_{i}(E) for all i. Thus D, ≤ is a partial ordering. We write D < E to mean that D ≤ E and D ≠ E. We write sup(D, E) = the unique diagram F such that r_{i}(F) = max(r_{i}(D), r_{i}(E)) for all i, or equivalently c_{i}(F) = max(c_{i}(D), c_{i}(E)) for all i.

As in [26] some of our results in this paper involve well partial ordering theory.

A well partial ordering is a partial ordering P, ≤ such that for all infinite sequences ⟨P_{i}⟩_{i∈ℕ} of elements of P there exist i, j ∈ ℕ such that i < j and P_{i} ≤ P_{j}. For example, any well ordering is a well partial ordering, and the product of any two well partial orderings is a well partial ordering. For background on well partial ordering theory, see [5, 17, 21, 24, 25, 36]. A key fact for us in this paper is that D, ≤ is a well partial ordering. We denote this fact as WPO(D). In Theorem 2.6 we show that the statement WPO(D) is robust with respect to equivalence over RCA_{0}.

The plan of this paper is as follows. In §2 we prove that the statements WO(ω^{ω}) and WPO(D) are equivalent over RCA_{0}. In §3 we define what it means for a subset of D to be closed, and we prove that WPO(D) is equivalent over RCA_{0} to the statement that there is no infinite ascending sequence of closed subsets of D. In §4 we show that the latter statement is equivalent over RCA_{0} to the statement that there is no infinite ascending sequence of two-sided ideals in ℚ[S]. Combining this with the results of §2 and §3, we obtain our main result. In §5 we show how the base theory RCA_{0} can be weakened to RCA∗_{0}. In §6 we raise a question for future research.

2 Well partial ordering of diagrams

In this section we use a result from [26] to prove in RCA_{0} that the set D of all diagrams is well partially ordered if and only if the ordinal number ω^{ω} is well ordered.

Lemma 2.1. RCA_{0} proves WO(ω^{ω}) ⇒ WPO(D).

Proof. Reasoning in RCA_{0}, assume that WPO(D) fails, i.e., D is not well partially ordered. Let ⟨D_{i}⟩_{i∈ℕ} be a bad sequence of diagrams, i.e., ∀i ∀j (i < j ⇒ D_{i} ≰ D_{j}). Let m = r_{1}(D_{1}) and n = c_{1}(D_{1}). For all j > 1 we have D_{1} ≰ D_{j}, hence m > r_{n}(D_{j}) and n > c_{m}(D_{j}). To each diagram D such that m > r_{n}(D) and n > c_{m}(D), we associate a sequence s(D) ∈ ℕ^{m+n−2} given by

s(D) = ⟨r_{1}(D) + 1, …, r_{n−1}(D) + 1, c_{1}(D) + 1, …, c_{m−1}(D) + 1⟩.

The point is that for any two such diagrams D and E, we have D ≤ E if and only if s(D) ≤ s(E) with respect to the coordinatewise partial ordering of ℕ^{m+n−2}. Since ⟨D_{j}⟩_{j>1} is a bad sequence of such diagrams, it follows that ⟨s(D_{j})⟩_{j>1} is a bad sequence in ℕ^{m+n−2}, hence ℕ^{m+n−2} is not well partially ordered. It then follows by [26, Lemma 3.6] that ω^{ω} is not well ordered, i.e., WO(ω^{ω}) fails.

Lemma 2.2. RCA_{0} proves WPO(D) ⇒ WO(ω^{ω}).

Proof. We reason in RCA_{0}. Given a nonzero ordinal α < ω^{ω}, write α in Cantor normal form as α = ω^{n_{1}} + ⋯ + ω^{n_{k}} where n_{1} ≥ ⋯ ≥ n_{k} ≥ 0 and k > 0. Let D(α) be the unique diagram D with r_{1}(D) = n_{1} +1, …, r_{k}(D) = n_{k} +1 and r_{k+1}(D) = 0. Clearly D(α) ≤ D(β) implies α ≤ β. Assume now that WO(ω^{ω}) fails. Let ⟨α_{i}⟩_{i∈ℕ} be an infinite descending sequence of ordinals < ω^{ω}, i.e., ω^{ω} > α_{i} > α_{j} for all i, j ∈ ℕ such that i < j. Then D(α_{i}) ≰ D(α_{j}) for all i, j ∈ ℕ such that i < j, hence ⟨D(α_{i})⟩_{i∈ℕ} is a bad sequence in D, so WPO(D) fails.

Theorem 2.3. RCA_{0} proves WPO(D) ⇔ WO(ω^{ω}).

Proof. This is immediate from Lemmas 2.1 and 2.2.

As a technical supplement to Theorem 2.3, we now prove a theorem to the effect that the statement WPO(D) is robust up to equivalence over RCA_{0}.

Definition 2.4. Within RCA_{0} we make the following definitions.

1. A set U of diagrams is said to be upwardly closed if ∀D ∀E ((D ∈ U and D ≤ E) ⇒ E ∈ U). For each finite set S of diagrams, there exists a set ucl(S) = {E | ∃D (D ∈ S and D ≤ E)} = the upward closure of S, i.e., the smallest upwardly closed set which includes S. An upwardly closed set of diagrams is finitely generated if it is of the form ucl(S) for some finite set S.

2. Consider a sequence of diagrams ⟨D_{i}⟩_{i∈ℕ}. The sequence is said to be upwardly closed if ∀i ∀E (D_{i} ≤ E ⇒ ∃j (D_{j} = E)). The sequence is said to be finitely generated if there is a finite set S such that ∀E (E ∈ ucl(S) ⇔ ∃j (D_{j} = E)), i.e., there is a finitely generated, upwardly closed set which is the range of the sequence.

Lemma 2.5. RCA_{0} proves the following. If all upwardly closed sets of diagrams are finitely generated, then all upwardly closed sequences of diagrams are finitely generated.

Proof. We reason in RCA_{0}. Let ⟨D_{i}⟩_{i∈ℕ} be an upwardly closed sequence of diagrams which is not finitely generated. Define a subsequence ⟨D_{i_{n}}⟩_{i∈ℕ} recursively as follows. Let i_{1} = 1. Given i_{1} < ⋯ < i_{n} let i_{n+1} = the least i > i_{n} such that D_{i} ∉ ucl({D_{i_{1}}, …, D_{i_{n}}}) and |D_{i}| > max(|D_{i_{1}}|, …, |D_{i_{n}}|). Thus i_{n} < i_{n+1} and |D_{i_{n}}| < |D_{i_{n+1}}| for all n. By Δ_{1}^{0} comprehension let U be the set of diagrams D such that D ∈ ucl({D_{i_{1}}, …, D_{i_{n}}}) where n = the least n such that |D_{i_{n}}| > |D|. Clearly U = ⋃_{n∈ℕ} ucl({D_{i_{1}} …, D_{i_{n}}}), hence U is upwardly closed, and U ≠ ucl({D_{i_{1}}, …, D_{i_{n}}}) for all n, hence U is not finitely generated.

Theorem 2.6. Over RCA_{0} each of the following statements implies the others.

1. WPO(D).

2. There is no infinite ascending sequence of upwardly closed sets of diagrams.

3. There is no infinite ascending sequence of finitely generated, upwardly closed sets of diagrams.

4. Every upwardly closed set of diagrams is finitely generated.

5. Every upwardly closed sequence of diagrams is finitely generated.

Proof. We reason in RCA_{0}. To prove 1 ⇒ 2, assume that 2 fails. Let ⟨U_{i}⟩_{i∈ℕ} be an infinite ascending sequence of upwardly closed sets of diagrams. For each i let D_{i} be the least element of U_{i+1} \ U_{i}. Then ⟨D_{i}⟩_{i∈ℕ} is a bad sequence of diagrams, so 1 fails.

Trivially 2 ⇒ 3. To prove 3 ⇒ 4, assume that 4 fails. Let U be an upwardly closed set of diagrams which is not finitely generated. Let D_{1} be the least element of U. Given D_{1}, …, D_{n} ∈ U, let D_{n+1} = the least element of U \U_{n} where U_{n} = ucl({D_{1}, …, D_{n}}). Then ⟨U_{n}⟩_{n∈ℕ} is an infinite ascending sequence of upwardly closed sets, so 3 fails.

By Lemma 2.5 we have 4 ⇒ 5. It remains to prove 5 ⇒ 1. Assume that 1 fails. Let ⟨D_{i}⟩_{i∈ℕ} be a bad sequence of diagrams. The formula Φ(E) ≡ ∃i (D_{i} ≤ E) is Σ_{1}^{0}, so by [28, Lemma II.3.7] there is a sequence of diagrams ⟨E_{j}⟩_{j∈ℕ} such that ∀E (Φ(E) ⇔ ∃j (E = E_{j})). Clearly ⟨E_{j}⟩_{j∈ℕ} is an upwardly closed sequence of diagrams, and by Σ_{1}^{0} bounding we have ∀m ∃n (∀j < m) (∃i < n) (D_{i} ≤ E_{j}). Because ⟨D_{i}⟩_{i∈ℕ} is bad, it follows that ⟨E_{j}⟩_{j∈ℕ} is not finitely generated, so 5 fails. This completes the proof.

3 Closed sets of diagrams

Definition 3.1. A set U of diagrams is said to be closed if

∀D (D ∈ U ⇔ ∀E (E > D ⇒ E ∈ U)).

Remark 3.2. Obviously all closed sets of diagrams are upwardly closed. However, not all upwardly closed sets of diagrams are closed. For example, letting D_{1} and D_{2} be the diagrams corresponding to the partitions 4, 2 and 2, 2, 1, 1 respectively, the upwardly closed set ucl({D_{1}, D_{2}}) is not closed.^{2} In this section we clarify the structure of closed sets of diagrams. Definition 3.3 and Lemmas 3.4–3.6 and Theorem 3.8 appear to be new, in the sense that we have not found their counterparts in the partition theory literature such as [1, 4, 6, 7].

Definition 3.3. Given a diagram D, let (D)_{r} = the diagram obtained by shortening the first row to the length of the second row, or 1 if there is no second row. Thus r_{1}((D)_{r}) = max(r_{2}(D), 1) and r_{i}((D)_{r}) = r_{i}(D) for all i > 1. Similarly, let (D)_{c} = the diagram obtained by shortening the first column to the length of the second column, or 1 if there is no second column. Thus c_{1}((D)_{c}) = max(c_{2}(D), 1) and c_{i}((D)_{c}) = c_{i}(D) for all i > 1.

The next three lemmas are proved in RCA_{0}.

Lemma 3.4. For all diagrams D we have D = sup((D)_{r}, (D)_{c}). For all diagrams D and E, if (D)_{r} = (E)_{r} or (D)_{c} = (E)_{c}, then D ≤ E or E ≤ D.

Proof. These statements are obvious from Definition 3.3.

Lemma 3.5. Let D, E, F be diagrams such that |F | > (r_{1}(D) − 1)(c_{1}(E) − 1) and F ≥ sup((D)_{r}, (E)_{c}). Then F ≥ D or F ≥ E.

Proof. Since |F | > (r_{1}(D) − 1)(c_{1}(E) − 1), we must have r_{1}(F) ≥ r_{1}(D) or c_{1}(F) ≥ c_{1}(E). In the first case we have F ≥ (first row of D) and F ≥ (D)_{r}, hence F ≥ D. In the second case we have F ≥ (first column of E) and F ≥ (E)_{c}, hence F ≥ E.

Lemma 3.6. Let S be a finite set of diagrams. Suppose F is a diagram such that ∃n ∀G ((|G| > n and G > F) ⇒ G ∈ ucl(S)). Then F ≥ sup((D)_{r}, (E)_{c}) for some D, E ∈ S.

Proof. Let S and F and n be as in the hypothesis. Since S is finite, we may safely assume that n > max(|F |, max({r_{1}(D), c_{1}(E) | D, E ∈ S})). Let G be the unique diagram with r_{1}(G) = n+1 and r_{i}(G) = r_{i}(F) for all i > 1. Then G > F and |G| > n, hence G ∈ ucl(S), i.e., G ≥ D for some D ∈ S. It then follows that F ≥ (D)_{r}. Similarly, let H be the unique diagram with c_{1}(H) = n + 1 and c_{i}(H) = c_{i}(F) for all i > 1, then H ≥ E for some E ∈ S, hence F ≥ (E)_{c}. Thus F ≥ sup((D)_{r}, (E)_{c}).

Definition 3.7. Given a finite set S of diagrams, let

Ŝ = {sup((D)_{r}, (E)_{c}) | D, E ∈ S},

2To see that ucl({D_{1}, D_{2}}) is not closed, let D be the diagram corresponding to the partition 3,3,3. This D does not belong to ucl({D_{1}, D_{2}}), but any diagram > D belongs to ucl({D_{1}, D_{2}}). And in fact, Theorem 3.8 will tell us that the smallest closed set of diagrams containing D_{1} and D_{2} is ucl({E}) where E is the diagram corresponding to the partition 2,2.

and let

\overline{S} = \{F ∈ ucl(Ŝ) | |F | ≤ ∥S∥\}

where

∥S∥ = max({(r_{1}(D) − 1)(c_{1}(E) − 1) | D, E ∈ S}).

Note that Ŝ and \overline{S} are finite sets of diagrams, and they can be found effectively given the finite set S. Note also that S ⊆ Ŝ, hence ucl(S) ⊆ ucl(Ŝ).

Theorem 3.8. RCA_{0} proves the following. For any finite set S of diagrams, we have ucl(Ŝ) = \overline{S} ∪ ucl(S). Moreover, ucl(Ŝ) is closed and includes S and is included in all closed sets that include S.

Proof. Trivially \overline{S} ∪ ucl(S) ⊆ ucl(Ŝ), and by Lemma 3.5 we have ucl(Ŝ) ⊆ \overline{S} ∪ ucl(S), so ucl(Ŝ) = \overline{S} ∪ ucl(S). Let U be a closed set of diagrams which includes S. Then ucl(S) ⊆ U, so by Lemma 3.5 we have F ∈ U for all F ∈ ucl(Ŝ) such that |F | > ∥S∥. But then, by induction on ∥S∥ − |F |, it follows that F ∈ U for all F ∈ ucl(Ŝ) such that |F | ≤ ∥S∥. Thus ucl(Ŝ) ⊆ U. It remains to prove that ucl(Ŝ) is closed. Let F be a diagram such that ∀G (G > F ⇒ G ∈ ucl(Ŝ)), i.e., ∀G (G > F ⇒ G ∈ \overline{S} ∪ ucl(S)). From the definition of \overline{S} it follows that ∀G ((|G| > ∥S∥ and G > F) ⇒ G ∈ ucl(S)). But then by Lemma 3.6 we have F ∈ ucl(Ŝ). Thus ucl(Ŝ) is closed, Q.E.D.

We shall now use Theorem 3.8 to prove a result about closed sets of diagrams which is analogous to Theorem 2.6 about upwardly closed sets of diagrams. Our result here will be needed in §4.

Definition 3.9. Within RCA_{0} we make the following definitions.

1. The closure of a finite set S of diagrams is the set

cl(S) = ucl(Ŝ) = \overline{S} ∪ ucl(S).

This definition is appropriate in view of Theorem 3.8.

2. A sequence of diagrams ⟨D_{i}⟩_{i∈ℕ} is said to be closed if ∀D ((∃i (D = D_{i})) ⇔ ∀E (E > D ⇒ ∃j (E = D_{j}))).

Remark 3.10. Theorem 3.8 implies that, provably in RCA_{0}, a closed set of diagrams is finitely generated qua closed set if and only if it is finitely generated qua upwardly closed set, i.e., finitely generated in the sense of Definition 2.4. And similarly, a closed sequence of diagrams is finitely generated qua closed sequence if and only if it is finitely generated qua upwardly closed sequence.

Lemma 3.11. RCA_{0} proves the following. Given a closed sequence of diagrams ⟨D_{i}⟩_{i∈ℕ} which is not finitely generated, we can find a subsequence ⟨D_{i_{n}}⟩_{n∈ℕ} such that ∀n (D_{i_{n}} ∉ cl({D_{i_{1}}, …, D_{i_{n−1}}})) and ∀m ∀n (m < n ⇒ D_{i_{n}} ≰ D_{i_{m}}).

Proof. We reason in RCA_{0}. Using the results of [28, §II.3], define i_{n} recursively as follows. Let i_{1} = 1. Assume inductively that i_{1} < ⋯ < i_{n} have been defined. By bounded Σ_{1}^{0} comprehension [28, Theorem II.3.9] there is a finite set T_{n} = {D | ∃j (D = D_{j} and D ≤ sup(D_{i_{1}}, …, D_{i_{n}}))}. Since ⟨D_{i}⟩_{i∈ℕ} is not finitely generated, we have D_{i} ∉ cl(T_{n}) for infinitely many i. A fortiori we also have D_{i} ∉ cl({D_{i_{1}}, …, D_{i_{n}}}) and D_{i} ≰ sup(D_{i_{1}}, …, D_{i_{n}}) for infinitely many i, so let i_{n+1} = the least such i which is > i_{n}. Clearly the subsequence ⟨D_{i_{n}}⟩_{n∈ℕ} has the desired properties.

Lemma 3.12. RCA_{0} proves the following. If all closed sets of diagrams are finitely generated, then all closed sequences of diagrams are finitely generated.

Proof. We reason in RCA_{0}. Suppose there is a closed sequence of diagrams which is not finitely generated. By Lemma 3.11 let ⟨D_{n}⟩_{n∈ℕ} be a sequence of diagrams such that ∀n (D_{n} ∉ cl({D_{1}, …, D_{n−1}})) and ∀m ∀n (m < n ⇒ D_{n} ≰ D_{m}). In particular we have ∀m ∀n (D_{m} ≤ D_{n} ⇒ m = n). It follows by Lemma 3.4 that for all D, there is at most one n such that (D_{n})_{r} = D and there is at most one n such that (D_{n})_{c} = D.

Using the results of [28, §II.3] define a subsequence ⟨D_{n_{k}}⟩_{k∈ℕ} recursively as follows. Assume inductively that n_{1} < ⋯ < n_{k−1} have been defined. Let S_{k} = {D_{n_{1}}, …, D_{n_{k−1}}}. The set of diagrams D such that |D| ≤ ∥S_{k}∥ is finite, so by bounded Σ_{1}^{0} comprehension and Σ_{1}^{0} bounding we have |(D_{n})_{r}| > ∥S_{k}∥ and |(D_{n})_{c}| > ∥S_{k}∥ for all sufficiently large n. Let n_{k} = the least such n which is also > n_{k−1}. This completes the construction. The construction insures that ∀k ∀l ∀D (if k < l and D ∈ cl(S_{l}) and |D| ≤ ∥S_{k}∥ then D ∈ cl(S_{k})).

By Δ_{1}^{0} comprehension let U be the set of diagrams D such that D ∈ cl(S_{k}) where k = the least k such that |D| ≤ ∥S_{k}∥. Then U = ⋃_{k∈ℕ} cl(S_{k}) is a closed set of diagrams which not finitely generated. This proves our lemma.

Theorem 3.13. Over RCA_{0} each of the following statements implies the others.

1. WPO(D).

2. There is no infinite ascending sequence of closed sets of diagrams.

3. There is no infinite ascending sequence of finitely generated closed sets of diagrams.

4. Every closed set of diagrams is finitely generated.

5. Every closed sequence of diagrams is finitely generated.

Proof. We reason in RCA_{0}. Let D be a diagram, and let S be a finite set of diagrams. By Theorem 3.8 and Definition 3.9, the relation D ∈ cl(S) is Δ_{1}^{0}. With this remark in mind, the proofs of 1 ⇒ 2 and 2 ⇒ 3 and 3 ⇒ 4 are similar to the proofs of the corresponding implications in Theorem 2.6.

By Lemma 3.12 we have 4 ⇒ 5. It remains to prove 5 ⇒ 1. Assume that 1 fails. Let ⟨D_{i}⟩_{i∈ℕ} be a bad sequence of diagrams. The formula Φ(E) ≡ ∃i (E ∈ cl({D_{1}, …, D_{i}})) is Σ_{1}^{0}, so by [28, Lemma II.3.7] there is a sequence of diagrams ⟨E_{j}⟩_{j∈ℕ} such that ∀E (Φ(E) ⇔ ∃j (E = E_{j})). Clearly ⟨E_{j}⟩_{j∈ℕ} is closed. We claim that ⟨E_{j}⟩_{j∈ℕ} is not finitely generated. Otherwise, by Σ_{1}^{0} bounding there would be an n such that {D_{1}, …, D_{n}} is a set of generators. Let S = {D_{1}, …, D_{n}}. By Theorem 3.8 and Definition 3.9 we have cl(S) = \overline{S} ∪ ucl(S). Since \overline{S} is finite we have D_{i} ∉ \overline{S} for all sufficiently large i, and since ⟨D_{i}⟩_{i∈ℕ} is bad we have D_{i} ∉ ucl(S) for all i > n. It is now clear that D_{i} ∉ cl(S) for all sufficiently large i, contradicting our assumption that S is a set of generators. Thus ⟨E_{j}⟩_{j∈ℕ} is a counterexample to 5, so 5 fails, Q.E.D.

Remark 3.14. For each n ∈ ℕ let D_{n} be the set of nonempty finite subsets of ℕ^{n} which are downwardly closed with respect to the coordinatewise partial ordering of ℕ^{n}. It is known that D_{n} is well partially ordered under inclusion. Recall that Figure 1 is the diagram corresponding to the partition 5, 2, 2, 1. If we rotate Figure 1 counterclockwise by 3π/4 radians, we obtain a picture of an element of D_{2}, namely, the downwardly closed subset of ℕ^{2} consisting of 10 elements:

(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 2), (3, 1), (3, 2), (4, 1).

In this way we obtain a one-to-one order-preserving correspondence between D_{2} and D. Similarly, there is a one-to-one order-preserving correspondence between D_{n+1} and the so-called n-dimensional partitions which are discussed in [1, Chapter 11]. Our results in this section may be interpreted as results about D_{2}, and it is straightforward to generalize them to D_{n+1}. It would be interesting to find appropriate similar generalizations of our results in §2, from D_{2} to D_{n+1}.

4 Two-sided ideals in K[S]

In this section we review the known one-to-one correspondence [6, Theorem 2] between closed sets of diagrams and two-sided ideals of K[S]. We observe that this correspondence is provable in RCA_{0}. We use this observation plus our Theorems 2.3 and 3.13 to obtain a reverse-mathematical classification of the known theorem [6, Theorem 10] that K[S] satisfies the ascending chain condition for two-sided ideals.

Definition 4.1. The following definitions are made in RCA_{0}.

1. Let S be the infinite symmetric group, i.e., the group of finitely supported permutations of ℕ. Let K be a countable field of characteristic 0. For instance, we could take K = ℚ. The group algebra K[S] is the set of formal finite linear combinations ∑_{g} a_{g}g where g ∈ S, a_{g} ∈ K, and a_{g} = 0 for all but finitely many g ∈ S. The algebraic operations on K[S] are given by

c ∑_{g} a_{g}g = ∑_{g}(ca_{g})g,
∑_{g} a_{g}g + ∑_{g} b_{g}g = ∑_{g}(a_{g} + b_{g})g,
∑_{g} a_{g}g · ∑_{g} b_{g}g = ∑_{g} ∑_{h}(a_{g}b_{h})(gh)

where c ∈ K.

2. A two-sided ideal of K[S] is a nonempty set I ⊆ K[S] such that (∀p ∈ I) (∀q ∈ I) (p + q ∈ I) and (∀p ∈ I) (∀r ∈ K[S]) (p · r ∈ I and r · p ∈ I).

3. For each n ∈ ℕ let S_{n} be the group of permutations of {1, …, n}. The group algebra K[S_{n}] and the two-sided ideals of K[S_{n}] are defined as above, replacing S by S_{n}. Identifying permutations of {1, …, n} with permutations of ℕ having support included in {1, …, n}, we have S = ⋃_{n∈ℕ} S_{n} and K[S] = ⋃_{n∈ℕ} K[S_{n}].

The next lemma summarizes some known facts from the representation theory of S_{n}.

Lemma 4.2. RCA_{0} proves the following. There is an explicit one-to-one mapping e : D → K[S] with the following properties.

1. The irreducible central idempotents of K[S_{n}] are e(D), |D| = n.

2. Consequently, there is a one-to-one correspondence between two-sided ideals of K[S_{n}] and sets of diagrams of size n. The two-sided ideal of K[S_{n}] corresponding to S ⊆ {D | |D| = n} is generated by {e(D) | D ∈ S}.

3. Let E be a diagram of size ≤ n. Then e(E) and {e(D) | |D| = n, E ≤ D} generate the same two-sided ideal of K[S_{n}].

Proof. As noted in [6, Theorem 1], these facts are proved in [13, 4.27, 4.51, 4.52]. Their formalization within RCA_{0} is routine. Some other helpful sources are [4, §§23–28] for facts 1 and 2, and [7, Chapter 7] for fact 3.

Lemma 4.3. RCA_{0} proves the following. There is a one-to-one order-preserving correspondence between two-sided ideals of K[S] and closed sets of diagrams. The two-sided ideal of K[S] corresponding to a closed set U of diagrams is generated by {e(D) | D ∈ U}. A two-sided ideal of K[S] is finitely generated if and only if the corresponding closed set of diagrams is finitely generated.

Proof. We reason in RCA_{0}. Define T ⊆ {E | |E| ≤ n} to be n-closed if

T = {E | |E| ≤ n, ∀D ((|D| = n, E ≤ D) ⇒ D ∈ S)}

for some S ⊆ {D | |D| = n}. Lemma 4.2 implies a one-to-one correspondence between n-closed subsets of {E | |E| ≤ n} and two-sided ideals I of K[S_{n}], where the n-closed set corresponding to I is {E | |E| ≤ n, e(E) ∈ I}. Our lemma then follows upon noting that (1) a set U of diagrams is closed if and only if ∀n (U ∩ {E | |E| ≤ n} is nclosed), and (2) a set I ⊆ K[S] is a two-sided ideal of K[S] if and only if ∀n (I ∩K[S_{n}] is a two-sided ideal of K[S_{n}]).

We now present the main theorem of this paper.

Theorem 4.4. Over RCA_{0} each of the following statements implies the others.

1. WO(ω^{ω}).

2. There is no infinite ascending sequence of two-sided ideals of K[S].

3. There is no infinite ascending sequence of finitely generated, two-sided ideals of K[S].

4. Every two-sided ideal of K[S] is finitely generated.

Proof. We reason in RCA_{0}. The one-to-one correspondence in Lemma 4.3 is such that each two-sided ideal of K[S] is uniformly Δ_{1}^{0} definable from its corresponding closed set of diagrams and vice versa. Therefore, by Δ_{1}^{0} comprehension, the one-to-one correspondence between two-sided ideals I ⊆ K[S] and closed sets U ⊆ D extends to a one-to-one correspondence between sequences ⟨I_{i}⟩_{i∈ℕ} of two-sided ideals of K[S] and sequences ⟨U_{i}⟩_{i∈ℕ} of closed sets of diagrams. We now see that Theorem 4.4 follows from Theorems 2.3 and 3.13.

5 Weakening the base theory

The usual base theory for reverse mathematics [28, Part A] is RCA_{0}. However, there is an alternative base theory RCA∗_{0} consisting of RCA_{0} with Σ_{1}^{0} induction replaced by exponentiation plus Σ_{0}^{0} induction [28, §IX.4]. Many of the known reversals over RCA_{0} can be proved over the weaker base theory RCA∗_{0}, and in this way one strengthens the reversals [28, Remark X.4.3]. There are also some reversals over RCA∗_{0} which have no counterpart over RCA_{0}, because the theorems in question are provable in RCA_{0} and in fact equivalent to RCA_{0} over RCA∗_{0}. The alternative base theory RCA∗_{0} was introduced and used in [33] and has been used in several subsequent publications including [8, 9, 14, 29, 34, 37].

The purpose of this section is to strengthen some of our reversals in Theorems 2.6 and 3.13 and 4.4 by weakening the base theory from RCA_{0} to RCA∗_{0}. In order to do so, we exercise care in defining the concept “infinite ascending sequence” within RCA∗_{0}. The following definition of “infinite ascending sequence” is equivalent over RCA_{0} to the usual definition with I = ℕ, but the equivalence does not hold over RCA∗_{0}.

Definition 5.1. Within RCA∗_{0} we define (a code for) an infinite sequence of ideals of K[S] to consist of an infinite set I ⊆ ℕ together with a set I ⊆ K[S] × I such that for each i ∈ I the set I_{i} = {p | (p, i) ∈ I} is an ideal of K[S]. Such a sequence is denoted ⟨I_{i}⟩_{i∈I}. The sequence is said to be ascending if (∀i ∈ I) (∀j ∈ I) (i < j ⇒ I_{i} ⫋ I_{j}). Similarly within RCA∗_{0} we define (codes for) infinite (ascending) sequences ⟨U_{i}⟩_{i∈I} of (closed or upwardly closed) sets of diagrams.

Lemma 5.2. Over RCA∗_{0} each of the following statements implies the others.

1. RCA_{0}.

2. Σ_{1}^{0} induction.

3. There is no infinite descending sequence in ℕ. In other words, there is no function f : I → ℕ such that I ⊆ ℕ is infinite and (∀i ∈ I) (∀j ∈ I) (i < j ⇒ f(i) > f(j)).

Proof. We reason in RCA∗_{0}. For 1 ⇔ 2 see [33] or [28, §X.4]. Clearly we have 2 ⇒ 3, so it remains to prove 3 ⇒ 2. Suppose 2 fails. Let Φ(m) be a Σ_{1}^{0} formula such that Φ(1) and ∀m (Φ(m) ⇒ Φ(m + 1)) and ∃n ¬ Φ(n). Fix an n such that Φ(n) fails, and write Φ(m) ≡ ∃j Θ(m, j) where Θ(m, j) is Σ_{0}^{0}. By Σ_{0}^{0} comprehension there is a function g : ℕ → {1, …, n} defined by g(i) = the least m such that ¬ (∃j < i) Θ(m, j). Clearly we have ∀i ∀j (i > j ⇒ g(i) ≥ g(j)). By Δ_{1}^{0} comprehension let I = {i + 1 | g(i + 1) > g(i)}. If the set I were finite, then letting m_{0} + 1 = g(i_{0} + 1) where i_{0} + 1 = the largest element of I, we would have Φ(m_{0}) and ¬ Φ(m_{0} + 1), a contradiction. Thus I is infinite, so f : I → ℕ defined by f(i) = n − g(i) is an infinite descending sequence, so 3 fails, Q.E.D.

Lemma 5.3. Lemmas 4.2 and 4.3 and Theorem 3.8 hold over RCA∗_{0}.

Proof. The proofs in RCA_{0} remain valid in RCA∗_{0}. The proof of Lemma 4.2 involves Gaussian elimination for finite systems of linear equations over K, but this works perfectly well in RCA∗_{0} despite the use of Σ_{1}^{0} induction in [28, Exercise II.4.11]. The difference here is that K, unlike the real field ℝ, is a countable discrete field.

The main result of this section is as follows.

Theorem 5.4. Over RCA∗_{0} each of the following statements implies the others.

1. RCA_{0} + WO(ω^{ω}).

2. There is no infinite ascending sequence of upwardly closed sets of diagrams.

3. There is no infinite ascending sequence of closed sets of diagrams.

4. There is no infinite ascending sequence of two-sided ideals of K[S].

Proof. We reason in RCA∗_{0}. By Theorems 2.6 and 3.13 and 4.4, it will suffice to prove that the disjunction 2 ∨ 3 ∨ 4 implies RCA_{0}. Suppose RCA_{0} fails. By Lemma 5.2 there is an infinite descending sequence f : I → ℕ. For each i ∈ I let F_{i} be the diagram such that r_{1}(F_{i}) = f(i) and r_{2}(F_{i}) = 0. By Lemma 5.3 let I_{i} be the two-sided ideal of K[S] corresponding to the closed set U_{i} = cl({F_{i}}) = ucl({F_{i}}). Then ⟨U_{i}⟩_{i∈I} is an infinite ascending sequence of (upwardly) closed sets of diagrams, and ⟨I_{i}⟩_{i∈I} is an infinite ascending sequence of two-sided ideals in K[S]. Thus 2∨3∨4 fails, Q.E.D.

In a similar fashion, we can strengthen [26, Theorem 2.7] by weakening the base theory from RCA_{0} to RCA∗_{0}. As in [26] let K[x_{1}, …, x_{n}] be the ring of polynomials over K in n indeterminates.

Theorem 5.5. Over RCA∗_{0} each of the following statements implies the other. 1. RCA_{0} + WO(ω^{ω}).

2. For each n ∈ ℕ there is no infinite ascending sequence of ideals in K[x_{1}, …, x_{n}].

Proof. We reason in RCA∗_{0}. By [26, Theorem 2.7] we have 1 ⇒ 2. Assume that 2 holds and 1 fails. Then by [26, Theorem 2.7] RCA_{0} must fail, so by Lemma 5.2 let f : I → ℕ be an infinite descending sequence. Let K[x] be the ring of polynomials over K in one indeterminate. For each i ∈ I let I_{i} be the ideal in K[x] generated by the monomial x^{m_{i}} where m_{i} = 2^{f(i)}. Then ⟨I_{i}⟩_{i∈I} is an infinite ascending sequence of ideals in K[x], so 2 fails for n = 1. This contradiction completes the proof.

6 A question for future research

In this section we raise a question for future research.

Maclagan [15]^{3} has shown that monomial ideals in the polynomial ring K[x_{1}, …, x_{n}] satisfy the antichain condition, i.e., there is no infinite sequence of such ideals which are pairwise incomparable under inclusion. Maclagan’s argument also gives the same result for the power series ring K[[x_{1}, …, x_{n}]]. And in a similar vein we have the following result, which is apparently new.

Theorem 6.1. Let K[S] be as in §4. Then, the two-sided ideals in K[S] satisfy the antichain condition. In other words, there is no infinite sequence of two-sided ideals in K[S] which are pairwise incomparable under inclusion.

Proof. The better partial orderings [18]^{4} are a subclass of the well partial orderings. Many of the well partial orderings which arise in practice are in fact better partial orderings. However, the class of better partial orderings enjoys many infinitary closure properties which are not shared by the class of well partial orderings. A key result of this kind due to Nash-Williams [18] implies the following:

If P is a better partial ordering, then the downwardly closed subsets of P form a better partial ordering under inclusion.

(1)

Taking complements, we also have:

If P is a better partial ordering, then the upwardly closed subsets of P form a better partial ordering under reverse inclusion.

(2)

Applying (1) to the better partial ordering ℕ^{n}, we see that D_{n} (see Remark 3.14) is a better partial ordering. And then, applying (2) to D_{n}, we see that the upwardly closed subsets of D_{n} are better partially ordered under reverse inclusion. Letting n = 2, it follows by Lemma 4.3 that the two-sided ideals of K[S] are better partially ordered under reverse inclusion, so in particular they satisfy the antichain condition.

Remark 6.2. The calculations of Aschenbrenner and Pong [2] can be used to show that Maclagan’s result is reverse-mathematically equivalent to WO(ω^{ω^{ω}}). It is also known [26, Theorem 2.9] that the Robson Basis Theorem [20, Theorem 3.15] is reversemathematically equivalent to WO(ω^{ω^{ω}}), and we conjecture that ∀n WPO(D_{n}) has the same reverse-mathematical status. In view of Theorem 4.4, it would be interesting to determine the reverse-mathematical status of Theorem 6.1.

3We thank Florian Pelupessy for calling our attention to [2, 15].

4See also our exposition in [24] and the further simplification in [36].

References

[1] George E. Andrews. The Theory of Partitions. Cambridge University Press, 2014. XVI + 273 pages. 3, 6, 9

[2] Matthias Aschenbrenner and Wai Yan Pong. Orderings of monomial ideals. Fundamenta Mathematicae, 181(1):27–74, 2004. 12

[3] C.-T. Chong, Q. Feng, T. A. Slaman, and W. H. Woodin, editors. Infinity and Truth. Number 25 in IMS Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific, 2014. IX + 234 pages. 14

[4] Charles W. Curtis and Irving Reiner. Representation Theory of Finite Groups and Associative Algebras. Interscience, John Wiley and Sons, 1962. XIV + 689 pages. 3, 6, 9

[5] D. H. J. de Jongh and Rohit Parikh. Well-partial orderings and hierarchies. Indagationes Mathematicae, 80(3):195–207, 1977. 4

[6] Edward Formanek and John Lawrence. The group algebra of the infinite symmetric group. Israel Journal of Mathematics, 23(3–4):325–331, 1976. 3, 6, 9

[7] William Fulton. Young Tableaux With Applications to Representation Theory and Geometry. Number 35 in London Mathematical Society Student Texts. Cambridge University Press, 1997. IX + 260 pages. 6, 9

[8] Kostas Hatzikiriakou. Algebraic disguises of Σ_{1}^{0} induction. Archive for Mathematical Logic, 29(1):47–51, 1989. 10

[9] Kostas Hatzikiriakou. Commutative Algebra in Subsystems of Second Order Arithmetic. PhD thesis, Pennsylvania State University, 1989. VII + 43 pages. 10

[10] Kostas Hatzikiriakou. A note on ordinal numbers and rings of formal power series. Archive for Mathematical Logic, 33(4):261–263, 1994. 2

[11] David Hilbert. Ueber die Theorie der algebraischen Formen. Mathematische Annalen, 36(4):473–534, 1890. http://dx.doi.org/10.1007/BF01208503. 2

[12] David Hilbert. Über das Unendliche. Mathematische Annalen, 95(1):161–190, 1926. 2

[13] Adalbert Kerber. Representations of Permutation Groups I. Number 240 in Lecture Notes in Mathematics. Springer-Verlag, 1971. V + 192 pages. 9

[14] Leszek Aleksander Kołodziejczyk and Keita Yokoyama. Categorical characterizations of the natural numbers require primitive recursion. Annals of Pure and Applied Logic, 166(2):219–231, 2015. 10

[15] Diane Maclagan. Antichains of monomial ideals are finite. Proceedings of the American Mathematical Society, 129(6):1609–1615, 2000. 12

[16] Richard Mansfield and Galen Weitkamp. Recursive Aspects of Descriptive Set Theory. Oxford Logic Guides. Oxford University Press, 1985. VI + 144 pages. 14

[17] Alberto Marcone. WQO and BQO theory in subsystems of second order arithmetic. In [23], pages 303–330, 2005. 4

[18] Crispin St. J. A. Nash-Williams. On better-quasi-ordering transfinite sequences. Mathematical Proceedings of the Cambridge Philosophical Society, 64(2):273–290, 1968. 12 [19] Max Noether. Paul Gordan. Mathematische Annalen, 75(1):1–41, 1914. 2

[20] J. C. Robson. Well quasi-ordered sets and ideals in free semigroups and algebras. Journal of Algebra, 55(2):521–535, 1978. 12

[21] Diana Schmidt. Well-Partial Orderings and Their Maximal Order Types. Habilitationsschrift, University of Heidelberg, 1979, IV + 77 pages. 4

[22] S. G. Simpson, editor. Logic and Combinatorics. Contemporary Mathematics. American Mathematical Society, 1987. XI + 394 pages. 14

[23] S. G. Simpson, editor. Reverse Mathematics 2001. Number 21 in Lecture Notes in Logic. Association for Symbolic Logic, 2005. X + 401 pages. 13

[24] Stephen G. Simpson. BQO theory and Fraïssé’s conjecture. In [16], pages 124– 138, 1985. 4, 12

[25] Stephen G. Simpson. Nichtbeweisbarkeit von gewissen kombinatorischen Eigenschaften endlicher Bäume. Archiv für mathematische Logik und Grundlagenforschung, 25(1):45–65, 1985. 4

[26] Stephen G. Simpson. Ordinal numbers and the Hilbert basis theorem. Journal of Symbolic Logic, 53(3):961–974, 1988. 2, 3, 4, 11, 12

[27] Stephen G. Simpson. Partial realizations of Hilbert’s program. Journal of Symbolic Logic, 53(2):349–363, 1988. 2

[28] Stephen G. Simpson. Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, 1999. XIV + 445 pages; Second Edition, Perspectives in Logic, Association for Symbolic Logic, Cambridge University Press, 2009, XVI + 444 pages. 2, 5, 7, 8, 10, 11

[29] Stephen G. Simpson. Baire categoricity and Σ_{1}^{0} induction. Notre Dame Journal of Formal Logic, 55(1):75–78, 2014. 10

[30] Stephen G. Simpson. An objective justification for actual infinity? In [3], pages 225–228, 2014. 2

[31] Stephen G. Simpson. Toward objectivity in mathematics. In [3], pages 157–169, 2014. 2

[32] Stephen G. Simpson. Comparing WO(ω^{ω}) with Σ_{2}^{0} induction. arXiv:1508.02655, 11 August 2015. 6 pages. 2

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

[34] Stephen G. Simpson and Keita Yokoyama. Reverse mathematics and Peano categoricity. Annals of Pure and Applied Logic, 164(3):284–293, 2013. 10

[35] William W. Tait. Finitism. Journal of Philosophy, 78(9):524–546, 1981. 2

[36] Fons van Engelen, Arnold W. Miller, and John Steel. Rigid Borel sets and better quasi-order theory. In [22], pages 199–222, 1987. 4, 12

[37] Keita Yokoyama. On the strength of Ramsey’s Theorem without Σ_{1}-induction. Mathematical Logic Quarterly, 59(1–2):108–111, 2013. 10