Well partial orderings and better partial orderings,

with applications to algebra

Stephen G. Simpson

Pennsylvania State University http://www.math.psu.edu/simpson/

simpson@math.psu.edu

Vanderbilt University stephen.g.simpson@vanderbilt.edu

Shanks Workshop

Ordered Algebraic Structures and Logic Vanderbilt University February 6–7, 2016 Well partial orderings. Definition. A well partial ordering is a partially ordered set P with any of the following properties. (By Ramsey’s Theorem, these properties are pairwise equivalent.)

1. P has no infinite descending sequences and no infinite antichains.

2. Any upwardly closed subset of P is finitely generated.

3. For any sequence a_{i}, i = 0, 1, 2, … of elements of P, there exist i and j such that i < j and a_{i} ≤ a_{j}. A sequence for which this conclusion fails is called a bad sequence . Property 3 says that P has no bad sequences.

4. For any sequence a_{i}, i = 0, 1, 2, … of elements of P, there exists a subsequence a_{i_{n}}, n = 0, 1, 2, …, i_{0} < i_{1} < i_{2} < ⋯, such that a_{i_{0}} ≤ a_{i_{1}} ≤ a_{i_{2}} ≤ · · ·.

5. Any linearization of P is a well ordering.

Examples of well partial orderings.

1. Any well ordering is a well partial ordering.

2. The union of any finite sequence of well partial orderings is a well partial ordering.

3. The product of any finite sequence of well partial orderings is a well partial ordering.

4. (Higman’s Lemma) If P is a well partial ordering, then P ∗ = {finite sequences of elements of P } is a well partial ordering.

Here P ∗ is partially ordered as follows: ⟨a_{1}, …, a_{m}⟩ ≤ ⟨b_{1}, …, b_{n}⟩ if and only if a_{1} ≤ b_{j_{1}}, …, a_{m} ≤ b_{j_{m}} for some j_{1}, …, j_{m} such that 1 ≤ j_{1} < ⋯ < j_{m} ≤ n.

Summary. The class of well partial orderings is closed under certain finitary operations.

An application to algebra: the Hilbert Basis Theorem.

Let K be a field. The Hilbert Basis Theorem says: for any positive integer k, every ideal in the polynomial ring K[x_{1}, …, x_{k}] is finitely generated.

A standard proof of the Hilbert Basis Theorem uses Dickson’s Lemma: The monomials x_{1}^{e_{1}} ⋯ x_{k}^{e_{k}}, e_{1}, …, e_{k} ∈ ℕ, are well partially ordered under divisibility. In other words, ℕ^{k} is well partially ordered under the product ordering. This is a special case of item 3 above.

Another application to algebra: Formanek/Lawrence.

Let S be the infinite symmetric group, i.e., the group of permutations of ℕ which move only finitely many elements of ℕ.

Theorem (Formanek/Lawrence, 1978). For any field K of characteristic 0, the group ring K[S] is Noetherian , i.e., it has no infinite ascending sequence of two-sided ideals. Equivalently, any two-sided ideal in K[S] is finitely generated.

Proof of the Formanek/Lawrence Theorem.

Let S be the infinite symmetric group.

Theorem (Formanek/Lawrence, 1978). For any field K of characteristic 0, the group ring K[S] is Noetherian.

Proof. A diagram is a finite, downwardly closed subset of ℕ^{2}. By Higman’s Lemma, the diagrams form a well partial ordering under inclusion. A set U of diagrams is said to be closed if ∀D (D ∈ U ⟺ ∀E (E ⫌ D ⇒ E ∈ U)). Note that any closed set of diagrams is upwardly closed under inclusion. Hence, any closed set of diagrams is finitely generated. Formanek and Lawrence exhibit a one-to-one, order-preserving correspondence between two-sided ideals in K[S] and closed sets of diagrams. Hence, any two-sided ideal in K[S] is finitely generated, Q.E.D.

Remark. It is unknown whether the Formanek/Lawrence Theorem can be generalized from the specific group S to some large family of locally finite groups. The proof for S relies on detailed information about the representation theory of the finite symmetric groups S_{n}, n = 2, 3, 4, …, information which is not available for other finite groups.

A generalization of Ramsey’s Theorem.

Given an infinite set X ⊆ ℕ, let [X]^{k} = {Y ⊂ X | Y is of cardinality k}, and let [X]^{∞} = {Y ⊆ X | Y is infinite}. There is a generalization of Ramsey’s Theorem due to Fred Galvin and Karel Prikry.

Ramsey’s Theorem. If [ℕ]^{k} = C_{1} ∪ ⋯ ∪ C_{l} then there exists X ∈ [ℕ]^{∞} such that [X]^{k} ⊆ C_{i} for some i.

Galvin/Prikry Theorem. We endow [ℕ]^{∞} with the product topology. If [ℕ]^{∞} = C_{1} ∪ ⋯ ∪ C_{l} where each C_{i} is a Borel set, then there exists X ∈ [ℕ]^{∞} such that [X]^{∞} ⊆ C_{i} for some i.

As a consequence of the Galvin/Prikry Theorem, we have:

Lemma. Let a be a Borel function from [ℕ]^{∞} into a discrete topological space. Then, there exists X ∈ [ℕ]^{∞} such that the restriction of a to [X]^{∞} is continuous.

The idea behind better partial orderings. Definition. A sequence is a function a such that dom (a) = ℕ. A subsequence of a is the restriction of a to some X ∈ [ℕ]^{∞}. Definition. An array is a function a such that dom (a) = [ℕ]^{∞}. A subarray of a is the restriction of a to [X]^{∞} for some X ∈ [ℕ]^{∞}. We may identify a sequence a with the array X ↦ a(min (X)). From this point of view, an array is a kind of generalized sequence. The idea behind better partial ordering theory is to imitate well partial ordering theory, replacing sequences by Borel arrays.

Better partial orderings.

Definition (essentially due to Crispin St. J. A. Nash-Williams). A better partial ordering is a partial ordering P with any of the following pairwise equivalent properties.

We endow P with the discrete topology.

1. For any Borel array a : [ℕ]^{∞} → P, there exists X ∈ [ℕ]^{∞} such that a(X) ≤ a(X \ {min (X)}).

A Borel array for which this conclusion fails is called a bad array . Property 1 says that P has no bad array.

2. For any Borel array a : [ℕ]^{∞} → P, there exists X ∈ [ℕ]^{∞} such that a(Y) ≤ a(Y \ {min (Y)}) for all Y ∈ [X]^{∞}.

3. For any continuous array a : [ℕ]^{∞} → P, there exists X ∈ [ℕ]^{∞} such that a(X) ≤ a(X \ {min (X)}).

4. For any continuous array a : [ℕ]^{∞} → P, there exists X ∈ [ℕ]^{∞} such that a(Y) ≤ a(Y \ {min (Y)}) for all Y ∈ [X]^{∞}.

A theorem of Nash-Williams. We have seen that the class of well partial orderings has some finitary closure properties. Nash-Williams proved that the class of better partial orderings has analogous infinitary closure properties. The infinitary analog of Higman’s Lemma reads as follows: Theorem (Nash-Williams). If P is a better partial ordering, then P ∗∗ = {transfinite sequences of elements of P } is a better partial ordering. Here P ∗∗ is partially ordered as follows: ⟨a_{i} | i < α⟩ ≤ ⟨b_{j} | j < β⟩ if and only if there exists a function f : {i | i < α} → {j | j < β} such that f(i) < f(i′) for all i < i′ < α, and a_{i} ≤ b_{f(i)} for all i < α.

As a corollary of the Nash-Williams Transfinite Sequence Theorem, we have: Corollary 1. If P is a better partial ordering, then the downwardly closed subsets of P form a better partial ordering under inclusion. Taking complements, we also have: Corollary 2. If P is a better partial ordering, then the upwardly closed subsets of P form a better partial ordering under reverse inclusion. On the next slide we present an application to algebra.

An application to algebra.

Applying Corollary 1 to the better partial ordering ℕ^{2}, we see that the diagrams are better partially ordered under inclusion. And then, applying Corollary 2 to the diagrams, we see that the upwardly closed sets of diagrams are better partially ordered under reverse inclusion. But then, as in the proof of the Formanek/Lawrence Theorem, it follows that the two-sided ideals of K[S] are better partially ordered under reverse inclusion. In particular we have:

Theorem (Hatzikiriakou/Simpson, 2015). The group ring K[S] satisfies the antichain condition , i.e., it has no infinite family of two-sided ideals which are pairwise incomparable under inclusion.

.

Thank you for your attention!