Lexicographic Exponentiation of chains^{∗}

by Salma Kuhlmann^{†} In memory of Felix Hausdorff.

August 16, 2004

Prof. Dr. habil. Salma Kuhlmann, Research Unit Algebra and Logic, University of Saskatchewan, McLean Hall, 106 Wiggins Road, Saskatoon, SK S7N 5E6, Canada email: skuhlman@math.usask.ca homepage: http://math.usask.ca/˜ skuhlman/index.html

The slides of this talk are available at: http://math.usask.ca/˜ skuhlman/slidesle.pdf

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

†Partially supported by an NSERC research grant.

References

[Gr] Green, T. : Properties of chain products and Ehrenfeucht– Fraïssé Games on Chains, M.Sc. thesis, University of Saskatchewan, (August 2002)

[H1] Hausdorff, F. : Grundzüge einer Theorie der geordneten Mengen, Math. Annalen 65 (1908)

[H2] Hausdorff, F. : Grundzüge der Mengenlehre, Verlag Von Veit, Leipzig (1914)

[HKM] Holland, W. C. – Kuhlmann, S. – McCleary, S. : Lexicographic Exponentiation of chains, to appear in Journal of Symbolic Logic

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

[K–K–S1] Kuhlmann, F.-V. – Kuhlmann, S. – Shelah, S. : Exponentiation in power series fields, Proc. Amer. Math. Soc. 125, No. 11 (1997)

[K–K–S2] Kuhlmann, F.-V. – Kuhlmann, S. – Shelah, S. : Functorial equations for lexicographic products, Proc. Amer. Math. Soc. 131 (2003)

[K–S] Kuhlmann, S. – Shelah, S. : κ-bounded Exponential-Logarithmic power series fields, submitted (2004)

[W] Warton, P. : Lexicographic Powers of the real line, Ph.D. thesis, Bowling Green State University (1998)

PLAN OF THE TALK:

Part I: Historical. Hausdorff’s 1908 paper.

Part II: Introductory.

• Arithmetic operations: finite sums and products. General lexicographic products and powers.

• Anti-lexicographic products. Proposition. Warning.

• Relation to Ordinal Arithmetic.

• Dependence on the chosen base points. Brief discussion. See [Gr] for more.

• Examples.

Part III: Focus on Results of [HKM] and [K].

(a) 2-transitivity: when is Aut (Δ^{Γ}) 2-transitive ?

• Hausdorff’s interest. Definitions and field example. 2-transitive implies n-transitive.

• General Proposition. Hausdorff’s theorem proved in [W]. Converse proved today.

• State main result of [HKM].

(b) Isomorphism Invariants: Does ℝ^{Γ} ≃ ℝ^{Γ′} imply Γ ≃ Γ′ ?

• State main result of [K]. State main result of [HKM]. Converse to Hausdorff’s theorem [W].

• Two powerful tools: C_{00} chains and Arithmetic Rules.

• Proofs and examples.

Part IV: Algebraic motivation and applications in [K-K-S1], [K-K-S2] and [K–S]. (if time permits).

PART I.^{1}

In [H1]^{2} Hausdorff:

• Introduces operations on chains: sums, products, lexicographic products, lexicographic exponentiation of chains.

• Develops the basic arithmetic of these operations.

• Generalizes Cantor’s ordinal arithmetic.

• Uses lexicographic chain constructions for constructing models with given species and genera.

• Formulates the GCH and defines inaccessible cardinals. He resumes this study in [H2] and investigates (among other problems):

• 2-transitivity of lexicographic products.

The theory offers a variety of open problems that I have been studying in the last decade. Some have been solved, many are still open.

******* PART II. Arithmetic operations on chains. Let Γ and Γ′ be chains. The sum Γ + Γ′ is the chain formed by concatenation, with Γ < Γ′.

1Througout this talk, chain means totally ordered set.

2A translation into English of this paper appears as an appendix in [Gr].

• Note that our definition coincides with ordinal addition in case Γ and Γ′ are ordinals.

More generally, if {Γ_{i}; i ∈ I} is a collection of chains indexed by a chain I, we define the sum ∑_{i∈I} Γ_{i} analogously.

We denote by Γ ⨿ Γ′ the lexicographic product of Γ and Γ′. That is, Γ ⨿ Γ′ is the chain obtained by ordering the Cartesian product Γ×Γ′ lexicographically from the left. Note that

• Γ ⨿ Γ′ ≃ ∑_{γ∈Γ} Γ′ (see figure)

• if α and β are ordinals then α ⨿ β is the ordinal product βα (!)

Lexicographic exponentiation of chains: Now let {Δ_{γ} ; γ ∈ Γ} be chains, with index chain Γ, and for each γ ∈ Γ, fix a base point 0_{γ} ∈ Δ_{γ}. We define a chain in the Cartesian product ∏_{γ∈Γ} Δ_{γ}: the lexicographic product is the subset

H_{γ∈Γ} Δ_{γ} := {s ∈ _{γ∈Γ}^{∏} Δ_{γ} ; support (s) is wellordered},

totally ordered lexicographically from the left (also known as “order by first differences”). Here, support (s) := {γ ∈ Γ ; s(γ) ≠ 0_{γ}}.

If all Δ_{γ}’s are the same chain Δ, and all base points 0_{γ} are the same element 0 ∈ Δ, then H_{γ∈Γ} Δ_{γ} is the lexicographic power Δ^{Γ}:

Δ^{Γ} := {s : Γ → Δ ; support (s) is wellordered}
= {s ∈ _{γ∈Γ}^{∏} Δ ; support (s) is wellordered}.

Dual Theory: Anti-lexicographic exponentiation of chains.

• In the literature, many authors prefer to work with the anti-lexicographic ordering.

The anti-lexicographic power ^{Γ}Δ is the set

ΓΔ := {s : Γ → Δ ; support(s) is anti-wellordered in Γ},

ordered anti-lexicographically from the right (also known as “ordered by last differences”).

How to translate from lex to anti-lex ?

Let Γ^{∗} denote Γ with its order reversed. We note: Proposition 1 Let Γ be a chain, and Δ a chain with a base point 0. Then the antilexicographic power ^{Γ}Δ coincides with the lexicographic power Δ^{Γ^{∗}}.

• But note that in general Δ^{Γ} ≃ Δ^{Γ′} does not imply ^{Γ}Δ ≃ ^{Γ′}Δ. Example later.

Relation to Ordinal Arithmetic. When α and β are ordinals, our lexicographic power α^{β^{∗}}, with chosen base point the least element 0 ∈ α, is the ordinal α^{β}. That is, our anti-lexicographic power ^{β}α, with chosen base point the least element 0 ∈ α, is the ordinal α^{β}.

• In order to recover Cantor’s notation, Hausdorff writes Δ^{Γ} whenever he actually works with the lexicographic power Δ^{Γ^{∗}}.

• It is important that here, the chosen base point is the least element 0 ∈ α. For example, if α is the ordinal 2 = {0, 1}, then the lexicographic power 2^{β^{∗}}, if computed with base point 1 ∈ {0, 1} instead of 0, is the reverse of the ordinal 2^{β}.

Dependence on the chosen base points. The lexicographic chain Δ^{Γ} depends in general on the choice of the base point 0 of Δ.^{3} Below is a brief discussion of this issue. A uniform way of defining lexicographic products: In [H1] Hausdorff introduces lexicographic products as follows. Given {Δ_{γ} ; γ ∈ Γ} with index chain Γ, define a partial order on the Cartesian product ∏_{γ∈Γ} Δ_{γ} by comparing two sequences s and t lexicographically from the left just in case

dif(s, t) := {γ ∈ Γ ; s(γ) ≠ t(γ)}

has a least element. Now define an equivalence relation on the Cartesian product ∏_{γ∈Γ} Δ_{γ}:

s ∼ t if dif(s, t) is wellordered.

• The equivalence classes are maximal chains in this partial order.

• Furthermore, if [s] denotes the equivalence class of s ∈ ∏_{γ∈Γ} Δ_{γ}, then each [s] is a lexicographic product defined by s, that is, with base points 0_{γ} = s(γ) ∈ Δ_{γ}.

• So if t ∼ s then the lexicographic product with base points 0_{γ} = t(γ) coincides with the lexicographic product defined by s, and conversely.

Each equivalence class is possibly a new chain ....

3In [Gr], α^{ω^{∗}} is computed, for every possible choice of the base point!

Cases where it does not matter:

• If Γ is wellordered, then there is a single equivalence class, and the lexicographic product of {Δ_{γ} ; γ ∈ Γ} with index chain Γ is uniquely determined (independently from the chosen base points). It is just ∏_{γ∈Γ} Δ_{γ} totally ordered lexicographically.

• If t ≁ s, s and t may still define isomorphic lexicographic products. This is the case, for example, if each of the Δ_{γ} ’s is a transitive chain.^{4} • In particular, if Δ is a totally ordered Abelian group, then the lexicographic chain Δ^{Γ} is uniquely determined, up to isomorphism, independently of the chosen base point.

4for each γ ∈ Γ fix an automorphism π_{γ} of Δ_{γ} satisfying π_{γ}(s(γ)) = t(γ); the π_{γ}’s induce the required isomorphism in the obvious way. Moreover, this induced isomorphism maps base points to base points.

Examples.

• ℤ^{ℕ} is the order type of the irrationals.

• ℕ^{ℕ} (with any base point) is the order type of the non-negative reals.

• 2^{ℕ} (with any base point) is the order type of Cantor’s ternary set.

• The underlying order of Hahn groups is a lexicographic product.

• The underlying order of a field of power series k((G)) (with coefficients in an ordered field k and exponents in an ordered Abelian group G) is the lexicographic power k^{G}. Similarly for the rings of power series k((G^{≥0})) and k((G^{<0})).

• The underlying order of Conway’s “field of surreal numbers” No is a lexicographic power.

Lexicographic orderings appear naturally in: Descriptive Set Theory, Real Algebra, Valuation Theory, Gröbner Bases (monomial orders), ...

******* PART III.

(a) 2-transitivity. Let A be a chain containing more than 2 elements. A is 2-transitive if given a_{1}, a_{2}, b_{1}, b_{2} ∈ A such that a_{1} < b_{1} and a_{2} < b_{2}, there exists an automorphism σ of A such that σ(a_{1}) = a_{2} and σ(b_{1}) = b_{2}.

• Example: the underlying chain of a totally ordered field F is always 2-transitive.^{5}

• If A is 2-transitive then it is n-transitive for all natural numbers n ≥ 2 (defined analogously).

• In [H2] Hausdorff’s major interest in lexicographic powers is in their 2-transitivity:

when is Aut (Δ^{Γ}) 2-transitive?

Proposition 2 A lexicographic power Δ^{Γ} is 2-transitive if Γ is transitive and Δ is 2-transitive.

5Given a_{1}, a_{2}, b_{1}, b_{2} as above, define σ(a) = (a − a_{1})\frac{(b_{2}−a_{2})}{(b_{1}−a_{1})} + a_{2}.

However, this proposition does not cover the interesting cases, for example, the case of an ordinal exponent or base.

Theorem [H2], [W] Let α be an additive principal ordinal. Then ℝ^{α} is 2-transitive. (α is additive principal^{6} if it is an ordinal power of ω, or equivalently, if α is isomorphic to any of its nonempty final segments, i.e., α is self-final).

Today, we shall prove the converse: Theorem 1 [HKM] Let α be an ordinal. If ℝ^{α} is 2-transitive, then α is additive principal.

The other main result concerning 2-transitivity is: Theorem 2 [HKM] Let Δ be a countable ordinal ≥ 2, with its least element 0 as base point. Then Δ^{ℝ} (with its least element deleted) is 2-transitive. The proof is quite involved, we shall omit it in today’s talk.

6That is, α is a monomial in the Cantor normal form.

(b) Isomorphism Invariants. We studied the question

Does ℝ^{Γ} ≃ ℝ^{Γ′} imply Γ ≃ Γ′ ?

Theorem [K] Let α be an ordinal, and J a chain in which the chain ℝ does not embed. Assume that ℝ^{α} embeds in ℝ^{J}. Then α embeds in J. In particular, if α and β are distinct ordinals, then ℝ^{α} ≄ ℝ^{β} . What about non-wellordered exponents? Sometimes, Theorem [K] provides a test: Example 1 ℝ^{ℕ} ≄ ℝ^{ℚ}. (Indeed, every countable ordinal embeds in ℚ ...) At other times, the test is not informative, and we have to work harder: Theorem 4 [HKM] ^{7} ℝ^{ℝ} ≄ ℝ^{ℚ}. Theorem 3 [HKM] ^{8} Let α be any countably infinite ordinal. Then ℝ^{α^{∗}+α} ≃ ℝ^{α}.

We now want to provide the main ideas in the proofs of Theorem 1 and Theorem 3 of [HKM]. For this we need ...

7The proof is quite involved, we shall omit it in today’s talk.

8We prove a more general result: Let α and β be ordinals, with α countable and β infinite. Then ℝ^{α^{∗}+β} ≃ ℝ^{β}.

ARITHMETIC RULES:

(1) The operations + and ⨿ are both associative, but in general not commutative.

(2) (Γ + Γ′) ⨿ Γ′′ ≃ (Γ ⨿ Γ′′) + (Γ′ ⨿ Γ′′).

(3) (Γ_{1} + Γ_{2})^{∗} ≃ Γ_{2}^{∗} + Γ_{1}^{∗} and (Γ_{1} ⨿ Γ_{2})^{∗} ≃ Γ_{1}^{∗} ⨿ Γ_{2}^{∗}.

(4) (Δ^{Γ})^{∗} ≃ (Δ^{∗})^{Γ}.

(5) Δ^{Γ+Γ′} ≃ Δ^{Γ} ⨿ Δ^{Γ′}.

(6) If {Γ_{i}; i ∈ I} is a collection of chains indexed by a chain I, then

Δ^{∑_{i∈I} Γ_{i}} ≃ H_{i∈I} Δ^{Γ_{i}},

(where the base point of Δ^{Γ_{i}} is 0, the sequence with empty support).

(7) In particular Δ^{Γ ⨿ Γ′} ≃ (Δ^{Γ′})^{Γ}. (Recall that Γ ⨿ Γ′ ≃ ∑_{γ∈Γ} Γ′).

(8) Δ^{Γ_{1}} ≃ Δ^{Γ_{2}} and Δ^{Γ′_{1}} ≃ Δ^{Γ′_{2}} ⇒ Δ^{Γ_{1}+Γ′_{1}} ≃ Δ^{Γ_{2}+Γ′_{2}}.

(9) Δ^{Γ_{1}} ≃ Δ^{Γ_{2}} ⇒ Δ^{Γ′ ⨿ Γ_{1}} ≃ Δ^{Γ′ ⨿ Γ_{2}}.

We also need ...

A powerful tool. A chain A is C_{00} or has countable coterminalities if both the cofinality and the coinitiality of A are equal to ℵ_{0}. That is, there is a coterminal (both coinitial and cofinal) subset of A isomorphic to ℤ.

Our main tool is the following: Proposition 3 Let A be a 2-transitive C_{00} chain. Then A is isomorphic to any of its convex C_{00} subsets.

To apply this proposition to 2-transitive C_{00} lexicographic powers and their convex subsets, the following easy observations are very useful:

Remark Let Γ be a chain and F ≠ ∅ a final segment of Γ. Then Δ^{F} is (isomorphic to) a convex subset of Δ^{Γ}.

Proposition 4 Let Γ be a chain, and Δ a chain with base point 0 ∈ Δ. Then the lexicographic power Δ^{Γ} is C_{00} if either Γ has a least element and Δ is C_{00}, or Γ has countable coinitiality and 0 is not an endpoint of Δ.

We can now work with these facts to establish ...

Proposition 5 ℝ^{ω^{∗}+ω} and ℝ^{ω} are isomorphic and these chains are 2-transitive. Proof ℝ^{ω} is convex in ℝ^{ω^{∗}+ω} by the Remark. Both are C_{00} chains by Proposition 4. ℝ^{ω^{∗}+ω} admits an ordered field structure; in fact, it is the underlying chain of the Laurent series field ℝ((ℤ)). Therefore, ℝ^{ω^{∗}+ω} is a 2-transitive chain. Now apply Proposition 3.

Example 2 ℝ^{ω^{∗}+ω} ≃ ℝ^{ω}. However, the corresponding anti-lexicographic powers are not. If they were, then we would have by Proposition 1 that ℝ^{ω^{∗}+ω} ≃ ℝ^{ω^{∗}}. So ℝ^{ω} ≃ ℝ^{ω^{∗}}. But this is impossible by Theorem [K] since ω does not embed in ω^{∗}.

The proof of Theorem 3 now basically follows by an induction argument. This theorem is not true without the assumption of countability:

Example 3 Let κ be an uncountable regular cardinal. Then ℝ^{κ^{∗}+κ} and ℝ^{κ} are not isomorphic. Indeed, ℝ^{κ} is C_{00} by Proposition 4, whereas ℝ^{κ^{∗}+κ} has cofinality κ.

We can now also establish Theorem 1: Proof: Assume that α ≠ 1. Let φ be a nonempty final segment of α. Both ℝ^{α} and ℝ^{φ} are C_{00} by Proposition 4, and ℝ^{φ} is convex by the Remark. So by Proposition 3, ℝ^{α} ≃ ℝ^{φ}. So α ≃ φ by Theorem [K]. This shows that α is self-final, as required. □

An example of a slightly different flavour: Example 4 ℝ^{ℝ} and ℝ^{ℝ+ℝ} are isomorphic and these chains are 2-transitive. Proof: ℝ^{ℝ+ℝ} ≃ ℝ^{ℝ} ⨿ ℝ^{ℝ} (by AR(6)). Also, ℝ^{ℝ} ≃ ℝ^{ℝ^{<0}} (since the exponents are isomorphic). Further, ℝ^{ℝ} ≃ ℝ^{ℝ^{≥0}}: ℝ^{ℝ^{≥0}} is convex in ℝ^{ℝ} by the Remark. Both are C_{00} chains by Prop. 4. ℝ^{ℝ} is 2-transitive (since it is the underlying chain of the power series field ℝ((ℝ))). Now apply Proposition 3. Thus ℝ^{ℝ+ℝ} ≃ ℝ^{ℝ^{<0}} ⨿ ℝ^{ℝ^{≥0}} ≃ ℝ^{ℝ} (by AR(9)).

******* Part IV. Algebraic motivation and applications in [K-K-S1] and [K-K-S2]. While trying to define an exponential function on a power series field, we encountered the question

When does Γ embed convexly in Δ^{Γ}?

Theorem [K-K-S2] Let Γ and Δ_{γ}, γ ∈ Γ , be nonempty chains. For every γ ∈ Γ , fix a base point 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_{γ∈Γ} Δ_{γ} .

Corollary 1 Let Γ and Δ be nonempty chains without last element, and fix a base point 0 in Δ. Then there is no embedding

ι : Γ → Δ^{Γ}

for which ι(Γ) is convex in Δ^{Γ}.

Corollary 2 Let G be a nontrivial ordered abelian group and K = ℝ((G)). Then (K, <) admits no exponential. Proof If K admits an exponential, then G ≃ ℝ((G^{<0})), as ordered groups. This gives rise to an embedding of G^{<0} in ℝ((G^{<0})) with convex image. Contradiction.

*******