COMPUTING MAXIMAL CHAINS

ALBERTO MARCONE, ANTONIO MONTALBÁN, AND RICHARD A. SHORE

Abstract. In [Wol67], Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that such maximal chain cannot be found computably, not even hyperarithmetically: No hyperarithmetic set can compute maximal chains in all computable wpos. However, we prove that almost every set, in the sense of category, can compute maximal chains in all computable wpos.

Wolk’s original result actually shows that every wpo has a strongly maximal chain, which we define below. We show that a set computes strongly maximal chains in all computable wpo if and only if it computes all hyperarithmetic sets.

1. Introduction

In this paper we study well partial orders (from now on wpos), that is well-founded partial orders with no infinite antichains. In [Wol67], Wolk proved that every wpo has a maximal chain, that is a chain of maximal order type. We are interested in two related problems. One is determining the computational complexity of such chains and the other is the complexity of the process that takes one from the wpo to such a chain.

If P is partially ordered by ≤_{P}, C ⊆ P is a chain in P if the restriction of ≤_{P} to C is linear. If P is a well-founded partial order then every chain in P is a well-order and we define the height of P, ht(P), to be the supremum of all ordinals which are order types of chains in P. For x ∈ P, let ht_{P} (x) be the supremum of all ordinals which are order types of chains in P_{(−∞,x)} = { y ∈ P | y <_{P} x }. It is easy to see that ht(P) = sup{ ht_{P} (x) + 1 | x ∈ P } and that ht_{P} (x) = sup{ ht_{P} (y) + 1 | y <_{P} x }.

Definition 1.1. Let C be a chain in P:

• C is maximal if it has order type ht(P);

• C is strongly maximal if, for every α < ht(P), there exists a (necessarily unique) x ∈ C with ht_{P} (x) = α.

Of course, strongly maximal chains are maximal. While maximal chains are maximal with respect to order type, strongly maximal chains are maximal with respect to inclusion as well (although there exist wpos with chains which are maximal with respect to inclusion but neither strongly maximal nor maximal).

Date: Saved: January 12, 2012. Compiled: January 16, 2012.

The question answered in this paper was asked by Thierry Coquand upon attending a talk of the first author about the results of [MS11] and [Mon07].

Montalbán was partially supported by NSF grant DMS-0901169. Shore was partially supported by NSF Grant DMS-0852811.

Wolk ([Wol67, Theorem 9]) actually proved the following theorem:

Theorem 1.2. Every wpo has a strongly maximal chain.

Wolk’s result appears also in Harzheim’s book ([Har05, Theorem 8.1.7]). The result was extended to a wider class of well founded partial orders by Schmidt ([Sch81]) in the countable case, and by Milner and Sauer ([MS81]) in general.

We can now state precisely the questions we are interested in:

Question 1.3. If P is a computable wpo, how complicated must maximal and strongly maximal chains in P be?

Question 1.4. How complicated must any function taking the wpo P to such a maximal chain be?

As usual, the computability of P means that both P ⊆ ℕ and ≤_{P} ⊆ ℕ × ℕ are (Turing) computable sets. In our answers to these questions, we will also measure complexity in terms of Turing computability as well as the hyperarithmetic hierarchy which is built by iterating the Turing jump (halting problem) along computable well orderings. (Definitions and basic facts can be found, for example, in [Sac90].)

We answer Question 1.3 for strongly maximal chains by showing (Theorem 3.2) that, for every hyperarithmetic set X, there is a computable wpo P such that any strongly maximal chain in P computes X. Thus any set computing strongly maximal chains in every computable wpo must lie above all the hyperarithmetic sets. For maximal chains we show that is far from true. Indeed, almost every set, in the sense of category, can compute maximal chains in every computable wpo (Theorem 4.1) while such “generic” sets do not compute any noncomputable hyperarithmetic set. On the other hand, we also show (Theorem 3.3) that the chains must be highly noncomputable in the sense that for every hyperarithmetic set X there is a computable wpo P with no maximal chain computable from X.

We answer Question 1.4 by showing that there is no computable or even hyperarithmetical procedure for constructing even maximal chains in computable wpos. To be more precise, any function f(e, n) such that, for every computable wpo P with index e, the function of n determined by f and e (λnf(e, n)) is (the characteristic function of) a maximal chain in P must itself compute every hyperarithmetic set X (Theorem 5.1). Other information about this question is also provided in §5.

Theorem 1.2 is somewhat similar to the better known result of de Jongh and Parikh ([dJP77]):

Theorem 1.5. Every wpo P has a maximal linear extension, i.e. there exists a linear extension of P such that every linear extension of P embeds into it. We call such a linear extension a maximal linear extension.

In [Mon07] the second author answered the analogues of Questions 1.3 and 1.4 for maximal linear extensions. His answer for the first question is very different than ours for maximal and strongly maximal chains but essentially the same for the second. Theorem 1.6. Every computable wpo has a computable maximal linear extension, yet there is no hyperarithmetic way of computing (an index for) a computable maximal linear extension from (an index for) the computable wpo.

These results illustrate several interesting differences between the analysis of complexity in terms of computability strength as done here and axiomatic strength in the sense of reverse mathematics as is done in [MS11]. (See [Sim09] for basic background in reverse mathematics whose general goal is to determine precisely which axiomatic systems are both necessary and sufficient to prove each theorem of classical mathematics.) From the viewpoint of reverse mathematics, all of the theorems analyzed computationally here and in [Mon07] are equivalent. Indeed, in [MS11] the first and third author showed that Theorem 1.5 and Theorem 1.2 (indeed even the version for maximal chains) for countable wpos are each equivalent (over RCA_{0}) to the same standard axiom system, ATR_{0}. As we have explained, however, the computational analysis of these three theorems in the sense of Question 1.3 are quite different.

Computable partial orders all have computable maximal linear extensions [Mon07]. Computable wpos all have hyperarithmetic maximal and even strongly maximal chains as is shown by the proof in ATR_{0} of Theorem 1.2 in [MS11]. However, strongly maximal chains for computable wpos must be of arbitrarily high complexity relative to the hyperarithmetic sets while maximal chains can be computably incomparable with all noncomputable hyperarithmetic sets. Yet another level of computational complexity within the theorems axiomatically equivalent to ATR_{0}, is provided by König’s duality theorem (every bipartite graph G has a matching M such that there is a cover of G consisting of one vertex from each edge in M). (See [AMS92] for definitions.) Here [AMS92] and [Sim94] show that this theorem for countable graphs is equivalent to ATR_{0}. On the other hand, [AMS92, Theorem 4.12] shows that there is a single computable graph G such that any cover as required by the theorem already computes every hyperarithmetic set and so this G certainly has no such hyperarithmetic cover.

Another, less natural phrasing of our theorems produces a yet different phenomena. If one asks, for every partial order, for either a witness that it is not a wpo or a (strongly) maximal chain then one adds on the well known possibilities inherent in producing descending sequences in nonwellfounded partial orderings. A more natural (or at least seemingly so) example of a similar behavior is determinacy for open (Σ_{1}^{0}) or clopen (Δ_{1}^{0}) sets. Both versions of determinacy are reverse mathematically equivalent to ATR_{0} [Sim09, Theorem V.8.7]. Computationally, the second always has hyperarithmetic solutions (strategies) for computable games and they are cofinal in the hyperarithmetic degrees while the former has computable instances with no hyperarithmetic solutions (again computing a path through a nonwellfounded tree) [Bla72]. Thus, we have at least four or five different levels of computational complexity for theorems all axiomatically equivalent to ATR_{0}. The phenomena exhibited by our analysis of the existence of maximal chains seems to be new.

2. Notation, terminology and basic observations

In this section we fix our notation about partial orders, make a simple but crucial observation about downward closed sets in computable wpos, and recall the notion of hyperarithmetically generic set.

If P is partially ordered by ≤_{P} and x, y ∈ P we write x <_{P} y for x ≤_{P} y and x ≠ y, and x |_{P} y for x ≰_{P} y ≰_{P} x.

We denote by P_{[x,y)} the partial order obtained by restricting ≤_{P} to the set { z ∈ P | x ≤_{P} z <_{P} y }. The notations P_{[x,y]} and P_{(x,y)} are defined similarly, while P_{[x,∞)} and P_{(−∞,x)} are obtained by restricting the order relation respectively to { z ∈ P | x ≤_{P} z } and { z ∈ P | z <_{P} x }. Notice that if P is computable so are all these partial orders.

Definition 2.1. A set C ⊆ P is cofinal in P if for every x ∈ P there exists y ∈ C such that x ≤_{P} y.

Definition 2.2. A set I ⊆ P is an ideal in P if it is downward closed (i.e. x ∈ I and y ≤_{P} x imply y ∈ I) and for every x, y ∈ I there exists z ∈ I such that x ≤_{P} z and y ≤_{P} z.

Definition 2.3. Given x_{0}, ..., x_{k} ∈ P we let

P_{x_{0},...,x_{k}} = { x ∈ P | x_{0} ≰_{P} x ∧ ⋯ ∧ x_{k} ≰_{P} x }.

Notice that if P is computable, so is P_{x_{0},...,x_{k}}.

Observation 2.4. If P is a computable wpo then every downward closed subset D ⊆ P is computable. In fact P wpo clearly implies the existence of a finite set of minimal elements {x_{0}, …, x_{k}} in P \ D while then D = P_{x_{0},...,x_{k}} which is computable.

We will use α-generic and hyperarithmetically generic for Cohen forcing (i.e. conditions are finite binary strings), as defined in detail in [Sac90, §IV.3].

Definition 2.5. For α < ω_{1}^{CK} (i.e. α a computable ordinal), a set G is α-generic if the conditions which are initial segments of G suffice to decide all Σ_{α}-questions. G is hyperarithmetically generic if it is α-generic for every α < ω_{1}^{CK}.

We associate to an infinite set a function in the usual way, described by the next definition. We will use this function when G is generic.

Definition 2.6. If G ⊆ ℕ is infinite let f_{G} : ω → ω be defined by letting f_{G}(n) be the number of 0’s between the nth 1 and the (n + 1)st 1 in (the characteristic function of) G.

3. Highly noncomputable maximal and strongly maximal chains

We will use the following result of Ash and Knight ([AK90, Example 2]):

Theorem 3.1. Let α < ω_{1}^{CK}. If A is a Π_{2α+1}^{0} set then there exists a uniformly computable sequence of linear orders L_{n}^{A} such that L_{n}^{A} ≅ ω^{α} for all n ∈ A and L_{n}^{A} ≅ ω^{α+1} for all n ∉ A. Indeed, this sequence of linear orderings can be computed uniformly in indices for α as a computable ordinal and A as a Π_{2α+1}^{0} set.

Our first results concerns strongly maximal chains in computable wpos and shows that they indeed must be of arbitrarily high complexity in the hyperarithmetical hierarchy.

Theorem 3.2. Let α < ω_{1}^{CK}. There exists a computable wpo P such that any strongly maximal chain in P computes 0^{(α)}.

Proof. Let P include elements { a_{n} | n ∈ ℕ } and { b_{n}^{i} | n ∈ ℕ, i < 2 }. The partial order on these elements is given by a_{n} <_{P} b_{n}^{i} <_{P} a_{n+1} and b_{n}^{0} |_{P} b_{n}^{1}.

Let A = 0^{(α)}: since A is Σ_{α}^{0} it is also Δ_{2α+1}^{0} and we can apply Theorem 3.1 both to A and to its complement Ā. The order P_{(b_{n}^{0},a_{n+1})} consists of L_{n}^{A}, while P_{(b_{n}^{1},a_{n+1})} consists of LĀ ; n. (Therefore all elements of one chain are incomparable with the elements of the other chain.) This completes the definition of P.

Notice that for every n there are exactly two disjoint chains maximal with respect to inclusion in P_{(a_{n},a_{n+1})}: one of them has length ω^{α+1}, whiled the other has length ω^{α}. Hence ht_{P} (a_{n}) = ω^{α+1} · n for every n and ht(P) = ω^{α+2}. Therefore there exists only one strongly maximal chain in P: the one that goes through all chains of length ω^{α+1}.

Thus if C is a strongly maximal chain in P we have 0^{(α)} = { n | b_{n}^{1} ∈ C }. □

Our second result shows that maximal chains can also be highly noncomputable. In contrast to Theorem 3.2, however, we do not show that they must lie arbitrarily high up in the hyperarithmetic hierarchy. Indeed, Theorem 4.1 shows that this is not the case.

Theorem 3.3. Let α < ω_{1}^{CK}. There exists a computable wpo P such that 0^{(α)} does not compute any maximal chain in P.

Proof. We can assume α is a successor ordinal, so that α + 1 ≤ 2α.

Let P include elements { a_{n} | n ∈ ℕ } and { b_{n}^{i} | n ∈ ℕ, i ≤ n }. The partial order on these elements is given by a_{n} <_{P} b_{n}^{i} <_{P} a_{n+1} and b_{n}^{i} |_{P} b_{n}^{j} for i ≠ j.

For every i let A_{i} = { n | ∃e < n Φ_{e}^{0^{(α)}}(n) = i } which is Σ_{α+1}^{0} and hence Π_{2α+1}^{0}: we can thus apply Theorem 3.1 to A_{i}. The order P_{(b_{n}^{i},a_{n+1})} consists of L_{n}^{A_{i}}. (Therefore again all elements of one chain are incomparable with the elements of the other chains.) This completes the definition of P.

Notice that for every n there are exactly n+1 chains maximal with respect to inclusion in P_{(a_{n},a_{n+1})}, and these are pairwise disjoint. Since n belongs to A_{i} for at most n different i’s, at least one of these chains has length ω^{α+1}, while the shorter chains have length ω^{α}. Hence ht_{P} (a_{n}) = ω^{α+1} · n for every n and ht(P) = ω^{α+2}. Therefore every maximal chain in P goes through infinitely many chains of length ω^{α+1}.

If C is a maximal chain in P define a partial function ψ ≤_{T} C by setting

ψ(n) = \begin{cases}i & if ∃x ∈ C b_{n}^{i} ≤_{P} x <_{P} a_{n+1}; \\ ↑ & otherwise. \end{cases}

Notice that ψ is well defined because if x, x′ ∈ C are such that b_{n}^{i} ≤_{P} x <_{P} a_{n+1} and b_{n}^{j} ≤_{P} x′ <_{P} a_{n+1} the comparability of x and x′ implies i = j.

We now show that ψ ≠ Φ_{e}^{0^{(α)}} for every e, thereby establishing that C ≰_{T} 0^{(α)}. Fix e. There exists n > e such that C intersects P_{(a_{n},a_{n+1})} in a chain of length ω^{α+1}. Thus ψ(n) is defined and n ∉ A_{ψ(n)}. In particular Φ_{e}^{0^{(α)}}(n) ≠ ψ(n) and thus ψ ≠ Φ_{e}^{0^{(α)}}. □

4. Maximal chains do not code

In this section we prove that maximal chains in wpos can be computed from generic sets. Here is the precise statement of our result.

Theorem 4.1. If P is a computable wpo and G a hyperarithmetically generic set then C ≤_{T} G for some maximal chain C in P. Furthermore, if P has a maximal chain of length < ω^{α+1}, then 2 · α-genericity of G suffices.

Theorem 4.1 is proved in several steps. First we make some observations that allow us to restrict our attention to computable wpos P such that for some α, ht(P) = ω^{α} and P has a cofinal chain of order type ω^{α}. Then, under these hypothesis, we first deal with the cases α = 1 and α = 2. Eventually, generalizing the ideas used in the simplest cases, we prove the theorem for every α.

4.1. Reducing to wpos with special properties. Let P be a computable wpo with ht(P) = γ = ω^{α_{0}} + ⋯ + ω^{α_{k}} with α_{0} ≥ α_{1} ≥ ⋯ ≥ α_{k}. By Theorem 1.2 let { x_{β} | β < γ } be a strongly maximal chain in P with ht_{P} (x_{β}) = β for every β < γ. For every i ≤ k let γ_{i} = ∑_{j<i} ω^{α_{j}} and a_{i} = x_{γ_{i}}, while a_{k+1} = ∞. Then for all i ≤ k we have that P_{[a_{i},a_{i+1})} is a computable wpo and ht(P_{[a_{i},a_{i+1})}) = ω^{α_{i}}. Moreover if C_{i} is a maximal chain in P_{[a_{i},a_{i+1})} for every i ≤ k then ⋃_{i≤k} C_{i} is a maximal chain in P. Obviously, if C_{i} ≤_{T} G for every i then ⋃_{i≤k} C_{i} ≤_{T} G.

This shows that to prove Theorem 4.1 it is enough to compute from a hyperarithmetically generic set maximal chains for computable wpos with height of the form ω^{α}.

If P is such a computable wpo let C be a maximal chain in P. Then the set I = { x ∈ P | ∃y ∈ C x ≤_{P} y } is downward closed and hence, by Observation 2.4, computable. Moreover ht(I) = ω^{α} and I has a cofinal chain of length ω^{α}.

Thus, to prove Theorem 4.1 it suffices to compute from a hyperarithmetically generic set maximal chains for computable wpos with height of the form ω^{α} which have cofinal chains of length ω^{α}.

We define for each 0 < α < ω_{1}^{CK} a computable operator Φ_{α} such that if P is a partial order and G is generic enough we have:

• Φ_{α}(P, G) is a chain in P of order type at most ω^{α};

• if P has a cofinal chain of length ω^{α}, then Φ_{α}(P, G) has order type ω^{α}.

It is then clear that if P is a wpo with ht(P) = ω^{α} and a cofinal chain of length ω^{α}, then Φ_{α}(P, G) is a maximal chain in P. If moreover P is computable then Φ_{α}(P, G) is G-computable, as desired.

The Φ_{α}s are defined by induction on α.

4.2. The case α = 1. For α = 1 we do not use the generic set at all, and thus we write Φ_{1}(P). Given an enumeration { x_{n} | n ∈ ℕ } of P, define Φ_{1}(P) recursively as follows: let x_{n} ∈ Φ_{1}(P) if and only if for all m < n with x_{m} ∈ Φ_{1}(P) we have x_{m} ≤_{P} x_{n}. It is clear that Φ_{1}(P) is a chain of order type ≤ ω and if P has a cofinal chain of length ω (so that it has no maximal element), then Φ_{1}(P) has order type ω.

4.3. The case α = 2. We now consider explicitly the case α = 2, which is the blueprint for the general case. We need to define the computable operator Φ_{2}.

Using G, we define sequences ⟨a_{i} : i ∈ ℕ⟩, ⟨b̄_{i} : i ∈ ℕ⟩, ⟨k_{i} : i ∈ ℕ⟩ with a_{i} ∈ P, b̄_{i} ∈ P^{<ω}, k_{i} ∈ ℕ and a_{i} <_{P} a_{i+1} as follows. Let k_{0} be the first k such that f_{G}(k) is a code for a tuple ⟨a, b̄⟩ with a ∈ P and b̄ ∈ P^{<ω}. Let a_{0} = a and b̄_{0} = b̄. Now, given k_{i}, a_{i}, b̄_{i}, let k_{i+1} be the first k > k_{i} such that f_{G}(k) is a code for a tuple a ∈ P, b̄ ∈ P^{<ω} and a_{i} <_{P} a. (If a_{i} happens to be maximal in P, we will wait forever for k_{i+1}, i.e. the sequence is finite.) Let a_{i+1} = a and b̄_{i+1} = b̄.

For each i, let

P_{i} = Pb̄_{i} ∩ P_{[a_{i},a_{i+1})}.

Then let

Φ_{2}(P, G) = ⋃_{i∈ℕ}Φ_{1}(P_{i}).

We claim that Φ_{2} is the computable operator we need.

First, Φ_{2}(P, G) is a chain, because each Φ_{1}(P_{i}) is a chain and if i < j then every element of P_{i} is below every element of P_{j}. Since every Φ_{1}(P_{i}) has order type at most ω, the order type of Φ_{2}(P, G) is at most ω^{2}.

Second, we need to show that Φ_{2}(P, G) is computable uniformly in P and G. Take x ∈ P. If x <_{P} a_{0}, then x ∉ Φ_{2}(P, G). Otherwise, we go through the definition of a_{0}, b̄_{0}, a_{1}, b̄_{1}, … until we find and i such that either x ∈ P_{[a_{i},a_{i+1})} or x |_{P} a_{i}. By the 1-genericity of G, we will eventually find such an i. If x |_{P} a_{i}, then x ∉ Φ_{2}(P, G). If x ∈ P_{[a_{i},a_{i+1})} then x ∈ Φ_{2}(P, G) if and only if x ∈ Φ_{1}(P_{i}).

Third, we need to prove that if P has a cofinal chain of length ω^{2}, then Φ_{2}(P, G) has order type ω^{2}. We claim that with this hypothesis, there are infinitely many i’s such that P_{i} has a cofinal ω-chain. The reason is that every x ∈ P is bounded by an element of the cofinal ω^{2}-chain, and hence it is bounded by a whole ω-piece of this chain. That is, for each x ∈ P, there exists a, a′, b̄ such that x ≤_{P} a <_{P} a′ and Pb̄ ∩ P_{[a,a′)} has a cofinal ω-chain. So, by genericity, we will be choosing such a, a′, b̄ infinitely often. Therefore, for all such i, we have that Φ_{1}(P_{i}) is an ω-chain. Hence Φ_{2}(P, G) has order type ω^{2}.

4.4. The general case. Let α > 0 be a computable ordinal. We can fix a sequence { α_{i} | i ∈ ℕ } with α_{i} ≤ α_{i+1} < α such that ω^{α} = ∑_{i∈ℕ} ω^{α_{i}} (if α = β + 1 we can take α_{i} = β for every i, while if α is limit it suffices to take an increasing cofinal sequence in α). Notice that ω^{α} = ∑_{i∈A} ω^{α_{i}} whenever A ⊆ ℕ is infinite.

We now define Φ_{α}(P, G) as follows. Using G, define sequences ⟨a_{i} : i ∈ ℕ⟩ and ⟨b̄_{i} : i ∈ ℕ⟩ with a_{i} <_{P} a_{i+1} exactly as in the case α = 2. We again let P_{i} = Pb̄_{i} ∩ P_{[a_{i},a_{i+1})} and, using effective transfinite recursion, let

Φ_{α}(P, G) = ⋃_{i∈ℕ}Φ_{α_{i}}(G, P_{i}).

We prove by transfinite induction on α that Φ_{α} is a computable operator with the desired properties.

The proof that, Φ_{α}(P, G) is a chain and is computable uniformly in P and G is exactly as in the case α = 2. Inductively it is clear that if P is a partial order and G is generic enough Φ_{α}(P, G) is a chain in P of order type ≤ ω^{α}.

Now we need to prove that if P has a cofinal chain of length ω^{α}, then Φ_{α}(P, G) has order type exactly ω^{α}. To this end we claim that in this case, there are infinitely many i’s such that P_{i} has a cofinal chain of length ω^{α_{i}}. The reason is that every element x ∈ P is below an element of the ω^{α}-chain, and hence it is below a whole ω^{α_{i}}-piece of this chain, for all i. That is, for each x ∈ P and each i, there exists a, a′, b̄ such that x ≤_{P} a <_{P} a′ and Pb̄ ∩ P_{[a,a′)} has a cofinal ω^{α_{i}}-chain. So, by genericity, we will be choosing a, a′, b̄ with this property infinitely often. Therefore, by our induction hypothesis, for each i for which we make such a choice, we have that Φ(P_{i}) is an ω^{α_{i}}-chain. Therefore Φ_{α}(P, G) has order type ω^{α}.

4.5. On the amount of genericity. The only place where we need G to meet complex dense sets is when we require infinitely many i’s such that P_{i} = Pb̄_{i} ∩ P_{[a_{i},a_{i+1})} has a cofinal chain of length ω^{α_{i}}. Deciding if a wpo has a cofinal chain of order type ω^{α} is a Π_{2·α} question:

• P has a cofinal chain of order type ω iff it is an ideal and has no maximal elements, which is the conjunction of two Π_{2}^{0} conditions;

• P has a cofinal chain of order type ω^{α} iff for all i ∈ ℕ and x ∈ P, there exists a, a′, b̄ ∈ P such that x <_{P} a <_{P} a′ and Pb̄ ∩ P_{[a,a′)} has a cofinal chain of order type ω^{α_{i}}.

5. Nonuniformity

Our proof of Theorem 4.1 is nonuniform. In §4.1 we first need to know ht(P) and its Cantor normal form, then we need to find the a_{i}, and eventually to compute I. Later in the proof, the choice of the appropriate Φ_{α}(P, G) is also nonuniform. The proofs in ATR_{0} that there are hyperarithmetic maximal and strongly maximal chains in every countable wpo in [MS11] also show that there are hyperarithmetic such chains for every computable wpo but are similarly nonuniform (as are the ones for computable maximal linear extensions in [Mon07]). This nonuniformity cannot be avoided. We consider our results in this paper.

If L_{0} and L_{1} are computable well-orders (of different length) we can consider the wpo L_{0} ⊕L_{1}, the disjoint union of the two well-orders. A maximal chain in L_{0} ⊕L_{1} is included in some L_{i} for some i < 2 and which one it is in is, of course, uniformly computable from the maximal chain and the wpo. Then L_{1−i} embeds in L_{i} and so L_{i} is the longer chain. By Theorem 3.1, with proper choice of the L_{j} as prescribed there, this decision can uniformly code membership in any hyperarithmetic set. Thus we have the following nonuniformity result:

Theorem 5.1. There is no hyperarithmetic procedure which calculates a maximal chain in every computable wpo. In fact, any function f(e, n) such that, for every computable wpo P with index e, λnf(e, n) is (the characteristic function of) a maximal chain in P must compute every hyperarithmetic set X

As for Theorem 4.1, if G is hyperarithmetically generic and α > β then G^{(β)} does not compute 0^{(α)}. (Looking toward the next theorem, one might also point out, that the ordinals computable from such a G are just the computable ordinals.) Combining this fact with the previous arguments shows that the procedure of computing a maximal chain in a computable wpo from a hyperarithmetically generic G cannot be uniform either.

Theorem 5.2. There is no recursive ordinal β, number i and hyperarithmetically generic G such that for every index e for a computable wpo P, λn.Φ_{i}^{G^{(β)}}(e, n) is (the characteristic function of) a maximal chain in P.

References

[AK90] C. J. Ash and J. F. Knight. Pairs of recursive structures. Ann. Pure Appl. Logic, 46(3):211–234, 1990.

[AMS92] Ron Aharoni, Menachem Magidor, and Richard A. Shore. On the strength of König’s duality theorem for infinite bipartite graphs. J. Combin. Theory Ser. B, 54(2):257–290, 1992.

[Bla72] Andreas Blass. Complexity of winning strategies. Discrete Math., 3:295–300, 1972.

[dJP77] D. H. J. de Jongh and Rohit Parikh. Well-partial orderings and hierarchies. Nederl. Akad. Wetensch. Proc. Ser. A 80=Indag. Math., 39(3):195–207, 1977.

[Har05] Egbert Harzheim. Ordered sets, volume 7 of Advances in Mathematics (Springer). Springer, New York, 2005.

[Mon07] Antonio Montalbán. Computable linearizations of well-partial-orderings. Order, 24(1):39–48, 2007.

[MS81] E. C. Milner and N. Sauer. On chains and antichains in well-founded partially ordered sets. J. London Math. Soc. (2), 24(1):15–33, 1981.

[MS11] Alberto Marcone and Richard Shore. The maximal linear extension theorem in second order arithmetic. Archive for Mathematical Logic, 50:543–564, 2011.

[Sac90] Gerald E. Sacks. Higher recursion theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1990.

[Sch81] Diana Schmidt. The relation between the height of a well-founded partial ordering and the order types of its chains and antichains. J. Combin. Theory Ser. B, 31(2):183–189, 1981.

[Sim94] Stephen G. Simpson. On the strength of König’s duality theorem for countable bipartite graphs. J. Symbolic Logic, 59(1):113–123, 1994.

[Sim09] Stephen G. Simpson. Subsystems of second order arithmetic. Perspectives in Logic. Cambridge University Press, Cambridge, second edition, 2009.

[Wol67] E. S. Wolk. Partially well ordered sets and partial ordinals. Fund. Math., 60:175–186, 1967.

  E-mail address: alberto.marcone@dimi.uniud.it
  E-mail address: antonio@math.uchicago.edu
  E-mail address: shore@math.cornell.edu

10 ALBERTO MARCONE, ANTONIO MONTALBÁN, AND RICHARD A. SHORE

Dipartimento di Matematica e Informatica, Università di Udine, 33100 Udine, Italy Department of Mathematics, University of Chicago, Chicago, IL 60637, USA Department of Mathematics, Cornell University, Ithaca, NY 14853, USA