Well partial orderings and better partial orderings,

with applications to algebra

Stephen G. Simpson

Vanderbilt University stephen.g.simpson@vanderbilt.edu

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

Group Theory and Topology Seminar Vanderbilt University November 2, 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 sequence.

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 “divides.” 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 “subset of.” 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 “subset of.” 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 give [ℕ]^{∞} 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 < α.

More precisely, P ∗∗ is quasi-ordered by ≤. In other words, ≤ is a reflexive and transitive relation on P ∗∗, so it becomes a partial ordering when we mod out by the equivalence relation x ≤ y ≤ x.

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 “subset of.” 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 “superset of.” 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 “subset of.” And then, applying Corollary 2 to the diagrams, we see that the upwardly closed sets of diagrams are better partially ordered under “superset of.” 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 “superset of.” 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 “superset of.”

More applications to algebra.

Given a field K, let K⟨x_{1}, …, x_{k}⟩ be the ring of polynomials in k noncommuting indeterminates. A two-sided ideal I in K⟨x_{1}, …, x_{k}⟩ is said to be homogeneous if it is generated by homogeneous polynomials, and insertive if it is closed under “multiplication in the middle,” i.e., a, b ∈ I implies acb ∈ I.

Robson Basis Theorem (1978). In the noncommutative polynomial ring K⟨x_{1}, …, x_{k}⟩, there is no infinite ascending sequence of insertive homogeneous ideals.

A monomial ideal is an ideal generated by monomials.

Maclagan’s Theorem (2000). In the polynomial ring K[x_{1}, …, x_{k}], there is no infinite antichain of monomial ideals.

The ordinal number associated to the Hilbert Basis Theorem and the Formanek/Lawrence Theorem is ω^{ω}. The ordinal number associated to the Robson Basis Theorem and Maclagan’s Theorem is ω^{ω^{ω}}.

Some theorems from better partial ordering theory.

Let A and B be linear orderings. We quasi-order the linear orderings by defining A ≤ B if and only if A is embeddable in B.

Laver’s Theorem (1976). The countable linear orderings form a better quasi-ordering, hence a well quasi-ordering, under embeddability.

A tree is a rooted partial ordering T such that for all t ∈ T the set {s ∈ T | s ≤ t} is finite and linearly ordered. A Friedman tree is a tree T together with a mapping from T into the ordinal numbers. We quasi-order the Friedman trees by defining (T, f) ≤ (U, g) if and only if there exists an inf-preserving function ϕ : T → U such that for all u ∈ U, if ϕ(t) ≥ u for some t ∈ T then g(u) ≥ f(inf{t ∈ T | ϕ(t) ≥ u}).

Kriz’s Theorem (Kříž, 1995). The Friedman trees form a better quasi-ordering, hence a well quasi-ordering, under ≤.

The ordinal numbers associated with better quasi-ordering theory are a subject of much research.

Another theorem from well partial ordering theory.

Let H be a graph. A minor of H is any graph obtained by deleting some edges and vertices and contracting some edges of H. We write G ≤ H if G is isomorphic to a minor of H.

Graph Minor Theorem (Robertson/Seymour, 2001). The finite simple undirected graphs are well quasi-ordered under ≤.

The proof of this theorem has been published in a series of 20 papers, Graph Minors I–XX.

The ordinal number associated to the Graph Minor Theorem is known to be quite large.

Thank you for your attention!