We first ask how hard it is to say of a countable well-ordered set A that it has order type at least some given ordinal <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation>. We measure complexity in the Borel and effective Borel hierarchies. The class of well orderings is not Borel, so our results use Calvert’s notions of complexity and completeness within. We then turn to subsets of ordered Abelian groups. We ask how hard it is to say of well-ordered subsets A, B of such a group G that the set <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$ A+B = \{a+b:a\in A\ \& \ b\in B\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo>+</mo> <mi>B</mi> <mo>=</mo> <mo stretchy="false">{</mo> <mi>a</mi> <mo>+</mo> <mi>b</mi> <mo>:</mo> <mi>a</mi> <mo>∈</mo> <mi>A</mi> <mspace width="4pt" /> <mo>&</mo> <mspace width="4pt" /> <mi>b</mi> <mo>∈</mo> <mi>B</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> has type at least <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation>. The question is more interesting if we require that A and B have type strictly less than <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation>. If <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> is multiplicatively indecomposable, so of the form <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\omega ^{\omega ^\gamma }$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>ω</mi> <msup> <mi>ω</mi> <mi>γ</mi> </msup> </msup> </math></EquationSource> </InlineEquation>, the answer is trivial—if <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$tp(A),tp(B) < \alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mi>p</mi> <mo stretchy="false">(</mo> <mi>A</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>t</mi> <mi>p</mi> <mo stretchy="false">(</mo> <mi>B</mi> <mo stretchy="false">)</mo> <mo><</mo> <mi>α</mi> </mrow> </math></EquationSource> </InlineEquation>, then <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$tp(A+B) < \alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mi>p</mi> <mo stretchy="false">(</mo> <mi>A</mi> <mo>+</mo> <mi>B</mi> <mo stretchy="false">)</mo> <mo><</mo> <mi>α</mi> </mrow> </math></EquationSource> </InlineEquation>. Assuming that G is Archimedean, we have a precise result for <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> the <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$n^{th}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>n</mi> <mrow> <mi mathvariant="italic">th</mi> </mrow> </msup> </math></EquationSource> </InlineEquation> power of a multiplicatively indecomposable ordinal, for finite <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$n\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. Finally, we ask how hard it is to say of a well-ordered set A of non-negative elements in an ordered Abelian group G that the set [A], consisting of finite sums of elements of A, has type at least <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation>. Assuming that G is Archimedean, we have complete results.

Complexity of well-ordered sets in an ordered Abelian group

期刊论文
发表日期：

2025年6月11日

查看全文

Chris Hall,
Julia Knight,
Karen Lange

摘要

We first ask how hard it is to say of a countable well-ordered set A that it has order type at least some given ordinal $\alpha $ $α$ . We measure complexity in the Borel and effective Borel hierarchies. The class of well orderings is not Borel, so our results use Calvert’s notions of complexity and completeness within. We then turn to subsets of ordered Abelian groups. We ask how hard it is to say of well-ordered subsets A, B of such a group G that the set $ A+B = \{a+b:a\in A\ \& \ b\in B\}$ $A + B = {a + b : a \in A & b \in B}$ has type at least $\alpha $ $α$ . The question is more interesting if we require that A and B have type strictly less than $\alpha $ $α$ . If $\alpha $ $α$ is multiplicatively indecomposable, so of the form $\omega ^{\omega ^\gamma }$ $ω^{ω^{γ}}$ , the answer is trivial—if $tp(A),tp(B) < \alpha $ $t p (A), t p (B) < α$ , then $tp(A+B) < \alpha $ $t p (A + B) < α$ . Assuming that G is Archimedean, we have a precise result for $\alpha $ $α$ the $n^{th}$ $n^{th}$ power of a multiplicatively indecomposable ordinal, for finite $n\ge 2$ $n \geq 2$ . Finally, we ask how hard it is to say of a well-ordered set A of non-negative elements in an ordered Abelian group G that the set [A], consisting of finite sums of elements of A, has type at least $\alpha $ $α$ . Assuming that G is Archimedean, we have complete results.