Computable shuffle sums of ordinals
type: Item
instance of: scholarly article
title: Computable shuffle sums of ordinals
zbMATH Open document ID: 1149.03034
author: Asher M. Kach
published in: Archive for Mathematical Logic
publication date: 2008-08-18T00:00:00Z
review text: 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)].
reviewed by: Jeffry L. Hirst
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 5313047
zbMATH Keywords: shuffle sums
zbMATH Keywords: limit infimum functions
zbMATH Keywords: limitwise monotonic functions
zbMATH Keywords: computable orderings
MaRDI profile type: Publication
full work available at URL: s00153-008-0077-3
OpenAlex ID: W1971838439
cites work: Jumps of Orderings
cites work: On initial segments of computable linear orders
cites work: Effective categoricity of equivalence structures
cites work: Q4249724
cites work: Prime models of theories of computable linear orderings
cites work: Computable models of theories with few models
DOI: 10.1007/S00153-008-0077-3
description: scientific article; zbMATH DE number 5313047