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

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)].