Functorial Equations for Lexicographic Products ^{∗}

Franz-Viktor, Salma Kuhlmann and Saharon Shelah

16. 4. 2002

Abstract We generalize the main result of [K–K–S] concerning the convex embeddings of a chain Γ in a lexicographic power Δ^{Γ}. For a fixed non-empty chain Δ, we derive necessary and sufficient conditions for the existence of non-empty solutions Γ to each of the lexicographic functorial equations

(Δ^{Γ})^{≤0} ≃ Γ , (Δ^{Γ}) ≃ Γ and (Δ^{Γ})^{<0} ≃ Γ .

1 Introduction

Let us recall the definition of lexicographic products of ordered sets. Let Γ and Δ_{γ}, γ ∈ Γ be non-empty totally ordered sets. For every γ ∈ Γ, we fix a distinguished element 0_{γ} ∈ Δ_{γ}. The support of a family a = (δ_{γ})_{γ∈Γ} ∈ ∏_{γ∈Γ} Δ_{γ} is the set of all γ ∈ Γ for which δ_{γ} ≠ 0_{γ}. We denote it by supp(a). As a set, we define H_{γ∈Γ}(Δ_{γ}, 0_{γ}) to be the set of all families (δ_{γ})_{γ∈Γ} with well-ordered support (with respect to fixed distinguished elements 0_{γ}). To relax the notation, we shall write H_{γ∈Γ} Δ_{γ} instead of H_{γ∈Γ}(Δ_{γ}, 0_{γ}) once the distinguished elements 0_{γ} have been fixed. Then the lexicographic order on H_{γ∈Γ} Δ_{γ} is defined as follows. Given a = (δ_{γ})_{γ∈Γ} and b = (δ′_{γ})_{γ∈Γ} ∈ H_{γ∈Γ} Δ_{γ}, observe that supp(a) ∪ supp(b) is wellordered. Let γ_{0} be the least of all elements γ ∈ supp(a) ∪ supp(b) for which δ_{γ} ≠ δ′_{γ}. We set a < b :⇔ δ_{γ_{0}} < δ′_{γ_{0}} . Then (H_{γ∈Γ} Δ_{γ}, <) is a totally ordered set, the lexicographic product (or Hahn product) of the ordered sets Δ_{γ}. We shall always denote by 0 the sequence with empty support in H_{γ∈Γ} Δ_{γ}.

Note that if all Δ_{γ} are totally ordered abelian groups, then we can take the distinguished elements 0_{γ} to be the neutral elements of the groups Δ_{γ}. Defining addition on H_{γ∈Γ} Δ_{γ} componentwise, we obtain a totally ordered abelian group (H_{γ∈Γ} Δ_{γ}, +, 0 <).

∗2000Mathematics Subject Classification: Primary 06A05, Secondary 03C60.

First and second authors partially supported by an NSERC research grant, third author partially supported by the Edmund Landau Center for research in Mathematical Analysis, supported by the Minerva Foundation (Germany). Publication number 615

Lexicographic exponentiation of chains: If Δ = Δ_{γ} for every γ ∈ Γ, we fix a distinguished element in Δ (the same distinguished element for every γ ∈ Γ), and denote it by 0_{Δ}. In this case we denote H_{γ∈Γ} Δ_{γ} by Δ^{Γ}, and call it the lexicographic power Δ^{Γ} (with respect to 0_{Δ}). In other words, Δ^{Γ} is the set

{s; s : Γ → Δ such that supp(s) is well-ordered in Γ},

ordered lexicographically.

This exponentiation of chains has its own arithmetic. In this paper we study some of its aspects (cf. also [K] and [H–K–M]). Note that if Γ and Δ are infinite ordinals, then lexicographic exponentiation does not coincide with ordinal exponentiation (cf. [H]).

Lexicographic powers appear naturally in many contexts. For example, ℕ^{ℕ} is the order type of the nonnegative reals, and ℤ^{ℕ} that of the irrationals (cf. [R]). Also, 2^{Γ} is (isomorphic to) the chain of all well-ordered subsets of Γ, ordered by inclusion. The chain 2^{ℕ} has been studied in [H].

However, the main motivating example for us was that of generalized power series fields. If k is a real closed field and G a totally ordered divisible abelian group, then the field k((G)) of power series with exponents in G and coefficients in k is again real closed. The unique order of k((G)) is precisely the chain k^{G}. It was while studying such fields that our interest in the present problems arose. In [K-K-S], we considered the problem of defining an exponential function on K = k((G)), that is, an isomorphism f of ordered groups f : (K, +, 0, <) → (K^{>0}, ·, 1, <). We showed that the existence of f would imply that of a convex embedding (that is, an embedding with convex image) of the chain G^{<0} into the chain k^{G^{<0}}. On the other hand, we proved:

Theorem 1 Let Γ and Δ be non-empty totally ordered sets without greatest element, and fix an element 0_{Δ} ∈ Δ. Suppose that Γ′ is a cofinal subset of Γ and that ι: Γ′ → Δ^{Γ} is an order preserving embedding. Then the image ιΓ′ is not convex in Δ^{Γ}.

Now for any ordered field k, the chain k has no last element. Similarly, G^{<0} has no last element if G is nontrivial and divisible. So, using Theorem 1 one establishes that no exponentiation is possible on generalized power series fields.

If we omit the conditions on Γ and Δ in Theorem 1, the situation changes drastically. In this paper, we study conditions on the chains Γ and Δ under which a convex embedding of Γ in Δ^{Γ} exists. In particular, we seek for non-empty solutions Γ to the functorial equations:

(Δ^{Γ})^{≤0} ≃ Γ , (Δ^{Γ}) ≃ Γ , and (Δ^{Γ})^{<0} ≃ Γ .

(if T is any totally ordered set and 0 ∈ T is any element, we denote by T^{≤0} the initial segment (including 0), and by T^{<0} the strict initial segment (excluding 0) determined by 0 in T). None of the three equations hold if both Δ and Γ have no last element (for the first, this is trivial, and for the second and third it follows from Theorem 1). In Section 2 we start by proving a strong generalization of Theorem 1 (cf. Theorem 2). In Section 3, for each of the three functorial equations, we give simple characterizations of those chains Δ for which non-empty solutions Γ exist. In Section 4 we study simultaneous solutions to all three equations.

2 Nonexistence of convex embeddings

In this section, we shall prove that Theorem 1 remains true in the case where Δ is arbitrary, but 0_{Δ} is not the last element of Δ. This will follow from the following more general result:

Theorem 2 Let Γ and Δ_{γ}, γ ∈ Γ , be non-empty totally ordered sets. For every γ ∈ Γ , fix an element 0_{γ} which is not the last element in Δ_{γ}. Suppose that Γ has no last element and that Γ′ is a cofinal subset of Γ. Then there is no convex embedding

ι : Γ′ → H_{γ∈Γ} Δ_{γ} .

Proof: For every γ ∈ Γ′, we choose an element 1_{γ} ∈ Δ_{γ} such that 1_{γ} > 0_{γ}. Take d = (d_{γ})_{γ∈Γ} . If S is a well-ordered subset of Γ′ such that d_{γ} = 0_{γ} for all γ ∈ S, then we set

d ⊕ S := (d′_{γ})_{γ∈Γ} with d′_{γ} = \{ \begin{matrix}d_{γ} & for γ ∉ S \\ 1_{γ} & for γ ∈ S . \end{matrix}

Observe that the support of d ⊕ S is contained in supp(d) ∪ S and thus, it is again well-ordered. Note also that

S′ ⊂_{≠} S ⇒ d ⊕ S′ < d ⊕ S .  (1)

Indeed, let γ_{0} be the least element in S \S′. Then (d⊕S′)_{γ_{0}} = 0_{γ} < 1_{γ} = (d⊕S)_{γ_{0}}. On the other hand, if γ ∈ Γ and γ < γ_{0} then (d ⊕ S′)_{γ} = (d ⊕ S)_{γ}: if γ ∈ S then γ ∈ S′ (by minimality of γ_{0}) and (d ⊕ S′)_{γ} = 1_{γ} = (d ⊕ S)_{γ}; if γ ∉ S then γ ∉ S′ and (d ⊕ S′)_{γ} = d_{γ} = (d ⊕ S)_{γ}.

Now suppose that ι : Γ′ → H_{γ∈Γ} Δ_{γ} is an order preserving embedding such that the image ιΓ′ is convex in H_{γ∈Γ} Δ_{γ}. We wish to deduce a contradiction. The idea of the proof is the following. Let ON denote the class of ordinal numbers. We shall define an infinite ON×ℕ matrix with coefficients in Γ′, such that each column (γ_{ν}^{(n)})_{ν∈ON} is a strictly increasing sequence in Γ′. Since Γ′ is a set, every column of this matrix will provide a contradiction at the end of the construction (cf. figure).

( γ_{0}^{(1)} … γ_{0}^{(n)} γ_{0}^{(n+1)} …; ⋮  ⋮  ⋮ ; ⋮  ⋮  ⋮ ; γ_{ν}^{(1)} … γ_{ν}^{(n)} γ_{ν}^{(n+1)} …; ⋮  ⋮  ⋮ ; γ_{μ}^{(1)} … γ_{μ}^{(n)} = ? . . . . . . ; ⋮ ; . . . . . . . . .  . . . . . . )

To get started, we have to define the first row of the matrix. We construct sequences β^{(n)}, n ∈ ℕ ∪ {0}, and γ_{0}^{(n)}, n ∈ ℕ, in Γ′. We take an arbitrary β^{(0)} ∈ Γ′. Having constructed β^{(n)}, we choose γ_{0}^{(n+1)} and β^{(n+1)} as follows. Since Γ′ has no last element, we can choose μ^{(n)}, ν^{(n)} ∈ Γ′ such that β^{(n)} < μ^{(n)} < ν^{(n)}. Hence,

ιβ^{(n)} < ιμ^{(n)} < ιν^{(n)} .

Let σ^{(n)} ∈ Γ be the least element in supp ιβ^{(n)} ∪ supp ιμ^{(n)} for which

(ιβ^{(n)})_{σ^{(n)}} < (ιμ^{(n)})_{σ^{(n)}} ,  (2)

and τ^{(n)} ∈ Γ the least element in supp ιμ^{(n)} ∪ supp ιν^{(n)} for which

(ιμ^{(n)})_{τ^{(n)}} < (ιν^{(n)})_{τ^{(n)}} .  (3)

Since Γ′ is cofinal in Γ, we can choose β^{(n+1)} ∈ Γ′ such that

β^{(n+1)} ≥ max{σ^{(n)}, τ^{(n)}} .

Further, we set

d^{(n+1)} := (d_{γ}^{(n+1)})_{γ∈Γ} with d_{γ}^{(n+1)} = \{ \begin{matrix}(ιμ^{(n)})_{γ} & for γ ≤ β^{(n+1)} \\ 0_{γ} & for γ > β^{(n+1)} . \end{matrix}

Then by (2) and (3),

ιβ^{(n)} < d^{(n+1)} < ιν^{(n)} .

Thus, d^{(n+1)} ∈ ιΓ′ by convexity, and we can set

γ_{0}^{(n+1)} := ι^{−1}d^{(n+1)} .

Now for every n ∈ ℕ we have that β^{(n)} < γ_{0}^{(n+1)} , hence every well-ordered set S ⊂ Γ′ with smallest element γ_{0}^{(n+1)} has the property that (ιγ_{0}^{(n)})_{γ} = d_{γ}^{(n)} = 0_{γ} for all γ ∈ S; and moreover,

ιγ_{0}^{(n)} < ιγ_{0}^{(n)} ⊕ S < ιν^{(n−1)} .

Thus, ιγ_{0}^{(n)} ⊕ S ∈ ιΓ′ by convexity. Suppose now that for some ordinal number μ ≥ 1 we have chosen elements γ_{ν}^{(n)} ∈ Γ′, ν < μ, n ∈ ℕ, such that for every fixed n, the sequence (γ_{ν}^{(n)})_{ν<μ} is strictly increasing. Then we set

γ_{μ}^{(n)} := ι^{−1}(ιγ_{0}^{(n)} ⊕ {γ_{ν}^{(n+1)} | ν < μ}) ∈ Γ′

for every n ∈ ℕ. If λ < μ, then {γ_{ν}^{(n+1)} | ν < λ} ⊂_{≠} {γ_{ν}^{(n+1)} | ν < μ} and thus,

γ_{λ}^{(n)} < γ_{μ}^{(n)} by (1). So for every ordinal number μ, the sequences (γ_{ν}^{(n)})_{ν<μ} can be extended. We obtain strictly increasing sequences of arbitrary length, contradicting the fact that their length is bounded by the cardinality of Γ. □

Corollary 3 Assume that 0_{Δ} is not the last element of Δ. If there is an embedding of Γ in Δ^{Γ} with convex image, then Γ has a last element.

3 Solutions to the Functorial equations

We start with a few easy remarks and lemmas. Throughout, fix a chain Δ with distinguished element 0_{Δ}.

Remark 4 1) If 0_{Δ} is last in Δ (respectively, least), then 0 is last in Δ^{Γ} (respectively, least), for any non-empty chain Γ.

2) Let I be any chain, and C a non-empty convex subset of I. Let c ∈ C. Then the initial segment determined by c in C is a final segment of the initial segment determined by c in I.

Remark 5 If Δ^{<0_{Δ}} has no last element, then also (Δ^{Γ})^{<0} has no last element, for any chain Γ: If not, let s be last in (Δ^{Γ})^{<0} and set γ = min supp(s). Then s(γ) = δ < 0_{Δ}. Take δ < δ′ < 0_{Δ}. Consider s′ defined by s′(γ) = δ′ and s′(γ′) = 0_{Δ} if γ′ ≠ γ. Then s′ ∈ (Δ^{Γ})^{<0}, but s′ > s, contradiction.

Lemma 6 Let Γ and Γ′ be chains, and suppose that ϕ : Γ → Γ′ is a chain embedding. Then ϕ lifts to a chain embedding

ϕ̂: Δ^{Γ} → Δ^{Γ′} .

Proof: For s ∈ Δ^{Γ} and x ∈ Γ′, set

ϕ̂(s)(x) = \{ \begin{matrix}0_{Δ} & if x ∉ Im ϕ \\ s(ϕ^{−1}(x)) & if x ∈ Im ϕ . \end{matrix}

(here, Im ϕ denotes the image of ϕ). Now, it is straightforward to check the assertion of the lemma. □

In view of this lemma, if F is a subchain of a chain Γ, then there is a natural identification of Δ^{F} as a subchain of Δ^{Γ}.

Lemma 7 Let Γ be a chain and F a non-empty final segment of Γ. Then Δ^{F} is convex in Δ^{Γ} (and 0 ∈ Δ^{F}).

Proof: Let s_{i} ∈ Δ^{F}, and set γ_{i} = min supp(s_{i}) ∈ F, for i = 1, 2. Let s ∈ Δ^{Γ} be such that s_{1} < s < s_{2}. If s = 0, then s ∈ Δ^{F}. So assume s ≠ 0 and set γ = min supp(s). Suppose that γ ∉ F. If s > 0, then s(γ) > 0_{Δ}. On the other hand, γ < γ_{2} (otherwise, γ ∈ F). Thus, s > s_{2} , a contradiction. Similarly, we argue that if s < 0, then s < s_{1} , a contradiction. Hence, min supp(s). Since F is a final segment of Γ, this implies that s ∈ Δ^{F}, which proves our assertion. □

Corollary 8 Assume that Γ has a last element. Then Δ embeds convexly in Δ^{Γ}, such that 0_{Δ} is mapped to 0 ∈ Δ^{Γ}. If moreover 0_{Δ} is last in Δ, then Δ^{F} embeds as a final segment in Δ^{Γ}, for any non-empty final segment F of Γ. Consequently, if Γ has a last element, and 0_{Δ} is last in Δ, then Δ embeds as a final segment in Δ^{Γ}.

Proof: The first assertion follows from Lemma 7, applied to the final segment consisting of the single last element of Γ. For the second assertion use Remark 4, parts 1) and 2). □

We now give a complete solution to the first functorial equation, and a sufficient condition for the existence of solutions Γ to the third functorial equation:

Theorem 9 There is always a non-empty solution Γ for the functorial equation (Δ^{Γ})^{≤0} ≃ Γ. If Δ^{<0_{Δ}} has a last element, then there is also a non-empty solution Γ for (Δ^{Γ})^{<0} ≃ Γ.

Proof: Set Γ_{0} := Δ^{≤0_{Δ}}. Since Γ_{0} has a last element, Δ embeds convexly in Δ^{Γ_{0}}. Consequently, Γ_{0} embeds as a final segment in Γ_{1} := (Δ^{Γ_{0}})^{≤0}. By induction on n ∈ ℕ we define Γ_{n} := (Δ^{Γ_{n−1}})^{≤0}, and obtain an embedding of Γ_{n−1} as a final segment in Γ_{n}. We set Γ := ∪_{n∈ℕ}Γ_{n}.

Since every Γ_{n} is a final segment of Γ, every well-ordered subset S of Γ is already contained in some Γ_{n} (just take n such that the first element of S lies in Γ_{n}). Hence, an element of (Δ^{Γ})^{≤0} with support S is actually an element of Γ_{n+1} = (Δ^{Γ_{n}})^{≤0}, for some n. This fact gives rise to an order isomorphism of (Δ^{Γ})^{≤0} onto Γ.

To prove the second assertion, we set Γ_{0} := Δ^{<0_{Δ}}. Since Γ_{0} has a last element by assumption, Δ embeds convexly in Δ^{Γ_{0}}, and the same arguments as above work if we define Γ_{n} := (Δ^{Γ_{n−1}})^{<0}. □

Remark 10 Note that Γ_{0} has a last element and embeds as a final segment in the constructed solution Γ (in both cases considered in the proof). Thus, Γ has a last element, and there is no contradiction to Theorem 2.

Note that if 0_{Δ} is least in Δ, then the first equation has the trivial solution Γ = {0_{Δ}}.

We next turn to the second functorial equation.

Remark 11 Suppose that 0_{Δ} is last in Δ. Then the solution to the first equation given in Theorem 9 also solves the second equation. Indeed, in this case, 0 is last in Δ^{Γ}, so (Δ^{Γ})^{≤0} = Δ^{Γ}.

We also have the converse:

Corollary 12 Assume Δ is a chain such that the functorial equation Δ^{Γ} ≃ Γ has a non-empty solution Γ. Then 0_{Δ} is last in Δ. Thus, the functorial equation Δ^{Γ} ≃ Γ has a non-empty solution if and only if 0_{Δ} is last in Δ.

Proof: Assume 0_{Δ} is not last, and choose some element 1_{Δ} > 0_{Δ}. This provides us with characteristic functions. If S ⊂ Γ is well-ordered, then let χ_{S} ∈ Δ^{Γ} denote the characteristic function on S defined by:

χ_{S}(γ) = \{ \begin{matrix}1_{Δ} & if γ ∈ S \\ 0_{Δ} & if γ ∉ S . \end{matrix}

Note that these characteristic functions reflect inclusion: if S is a proper wellordered subset of S′, then χ_{S} < χ_{S′}. Now assume for a contradiction that i : Γ ≃ Δ^{Γ}, and let κ = card(Γ). We shall construct a strictly increasing sequence {γ_{μ}; μ < κ^{+}} in Γ.

Set γ_{0} = i^{−1}(0), and assume by induction that {γ_{ν}; ν < μ} is defined, and strictly increasing in Γ. Then define

γ_{μ} = i^{−1}(χ_{{γ_{ν};ν<μ}}).

It follows that χ_{{γ_{λ};λ<ν}} < χ_{{γ_{λ};λ<μ}}, whenever ν < μ. Since i^{−1} is order preserving, it follows that γ_{ν} < γ_{μ} as required. □

We now turn to the third functorial equation. We deduce a simple criterion for the existence of solutions:

Corollary 13 Assume that 0_{Δ} is not the last element of Δ. Then the functorial equation (Δ^{Γ})^{<0} ≃ Γ has a non-empty solution Γ if and only if Δ^{<0_{Δ}} has a last element.

Proof: The “if” direction is just the second assertion of Theorem 9. So assume now that Γ is a non-empty solution. Assume for a contradiction that Δ^{<0_{Δ}} has no last element. Then by Remark 5 (Δ^{Γ})^{<0} has no last element as well. Thus, the same holds for the solution Γ. This contradicts Theorem 2. □

4 Simultaneous Solutions

Recall that by Remark 11, the chain Γ given in Theorem 9 solves the first and the second functorial equations, if 0_{Δ} is last in Δ. By ω^{∗} we denote the ordinal ω with the reverse ordering.

Theorem 14 Assume that 0_{Δ} is last in Δ and that ω^{∗} embeds as a final segment in Δ. Then the solution Γ given in Theorem 9 to the first and second functorial equations solves (Δ^{Γ})^{<0} ≃ Γ as well.

Proof: Recall that Δ embeds as a final segment in the given solution Γ. Thus, ω^{∗} embeds as a final segment in Γ as well. In particular, Γ has a last element 0. Since Δ^{Γ} = (Δ^{Γ})^{<0} ∪ {0} and Δ^{Γ} ≃ Γ, we find that (Δ^{Γ})^{<0} ≃ Γ \ {0}. But Γ ≃ Γ \ {0}, since ω^{∗} is a final segment of Γ. □

We now turn to the question of whether the sufficient conditions given in this last theorem is also necessary. We need to introduce a definition: Say that a solution Γ (to any of the three equations) is special if Δ embeds as a final segment in Γ. Note that special solutions are necessarily non-empty.

Proposition 15 Every non-empty solution to Γ ≃ Δ^{Γ} is special.

Proof: Necessarily, 0_{Δ} is last in Δ (by Corollary 12). Thus, Γ has a last element, so by Corollary 8, Δ embeds as a final segment in Δ^{Γ}, and thus in Γ. □

Corollary 16 Assume that Δ is infinite and Γ is any non-empty chain which solves simultaneously

(Δ^{Γ})^{<0} ≃ Γ ≃ Δ^{Γ}.

Then 0_{Δ} is last in Δ and ω^{∗} embeds as a final segment in Δ.

Proof: Since Γ ≃ Δ^{Γ}, 0_{Δ} is last in Δ (Corollary 12). Therefore, 0 is last in Δ^{Γ} by Remark 4, and so also Γ has a last element 0. The assumptions imply that Γ \ {0} ≃ Γ. This is equivalent to the assertion that ω^{∗} embeds as a final segment in Γ. Now note that Γ is a special solution by Proposition 15, i.e., Δ embeds as a final segment of Γ. Since Δ is infinite this implies that ω^{∗} embeds as a final segment in Δ, as required. □

Corollary 17 Assume that Δ is infinite. Then the following are equivalent:

(a) 0_{Δ} is last in Δ and ω^{∗} embeds as a final segment in Δ.

(b) There exists a (special) simultaneous solution to all three equations.

(c) There exists a (special) simultaneous solution to the second and third equations.

Proof: (a) implies (b) by Theorem 14. (b) implies (c) trivially. Finally, (c) implies (a) by Corollary 16. □

We conclude with the following question: Are special solutions unique up to isomorphism? We can give a partial answer to this last question:

Proposition 18 Assume that 0_{Δ} is last in Δ. Let Γ = ∪Γ_{n} be the solution to the second equation given in Theorem 9. Then Γ embeds as a final segment in any other solution.

Proof: Let Γ′ be another solution. Then it is a special solution, by Proposition 15. So Δ = Γ_{0} embeds as a final segment in Γ′. Since 0_{Δ} is last in Δ, Γ_{1} = Δ^{Γ_{0}} embeds as a final segment in Δ^{Γ′}. By induction, Γ_{n} is a final segment of Γ′ for every n ∈ ℕ. Thus. Γ embeds as a final segment in Γ′ as well. □

References

[H] Hausdorff, F. : Grundzüge der Mengenlehre, Verlag von Veit, Leipzig (1914) [H–K–M] Holland, W. C. – Kuhlmann, S. – McCleary, S. : The Arithmetic of Lexico-

graphic Exponentiation, preprint

[K] Kuhlmann, S. : Isomorphisms of Lexicographic Powers of the Reals, Proc. Amer. Math. Soc. 123 (1995), 2657-2662

[K–K–S] Kuhlmann, F.-V. – Kuhlmann, S. – Shelah, S. : Exponentiation in power

series fields, Proc. Amer. Math. Soc. 125 (1997), 3177-3183

[R] Rosenstein, J. G. : Linear orderings, Academic Press, New York - London (1982)

Department of Mathematics and Statistics University of Saskatchewan 106 Wiggins Road Saskatoon, SK S7N 5E6 Department of Mathematics The Hebrew University of Jerusalem Jerusalem, Israel