Computable shuffle sums of ordinals (Q938232): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Normalize DOI.
 
(2 intermediate revisions by 2 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s00153-008-0077-3 / rank
Normal rank
 
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00153-008-0077-3 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1971838439 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Jumps of Orderings / rank
 
Normal rank
Property / cites work
 
Property / cites work: On initial segments of computable linear orders / rank
 
Normal rank
Property / cites work
 
Property / cites work: Effective categoricity of equivalence structures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4249724 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Prime models of theories of computable linear orderings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computable models of theories with few models / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S00153-008-0077-3 / rank
 
Normal rank

Latest revision as of 08:59, 10 December 2024

scientific article
Language Label Description Also known as
English
Computable shuffle sums of ordinals
scientific article

    Statements

    Computable shuffle sums of ordinals (English)
    0 references
    0 references
    18 August 2008
    0 references
    The shuffle sum \(\sigma (S)\) of a countable set of linear orders \(S = \{ L_i \} _{i \in \omega}\) is the unique linear order obtained by partitioning the rationals into dense sets \(\{Q_i \}_{i \in \omega}\) and replacing each rational in \(Q_i\) by \(L_i\). The main result of this paper characterizes those \(S \subset \omega+1\) for which \(\sigma (S)\) is computable in terms of limit infimum sets ({LimInf} sets) and limitwise monotonic sets relative to \(0^\prime\) ({LimMon}(\(0^\prime \)) sets). In particular, the author proves that for \(S \subset \omega +1\), ``\(\sigma (S)\) is computable'' is equivalent to ``\(S\) is a LimInf set'' and also equivalent to ``\(S\) is a LimMon(\(0^\prime\)) set.'' This can be applied to give a succinct proof that if \(S \subset \omega\) is \(\Sigma^0_3\), then \(\sigma (S \cup \{ \omega \} )\) is computable, a result originally proved by \textit{C. J. Ash}, \textit{C. G. Jockusch}, and \textit{J. F. Knight} [``Jumps of orderings'', Trans. Am. Math. Soc. 319, No. 2, 573--599 (1990; Zbl 0705.03022)]. More about LimMon(\(0^\prime\)) sets can be found (for example) in [\textit{D. R. Hirschfeldt}, ``Prime models of theories of computable linear orderings'', Proc. Am. Math. Soc. 129, No.~10, 3079--3083 (2001; Zbl 0974.03040)].
    0 references
    shuffle sums
    0 references
    limit infimum functions
    0 references
    limitwise monotonic functions
    0 references
    computable orderings
    0 references

    Identifiers