zbMATH — the first resource for mathematics

Computable shuffle sums of ordinals. (English) Zbl 1149.03034
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 C. J. Ash, C. G. Jockusch, and 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 [D. R. Hirschfeldt, “Prime models of theories of computable linear orderings”, Proc. Am. Math. Soc. 129, No. 10, 3079–3083 (2001; Zbl 0974.03040)].

03D45 Theory of numerations, effectively presented structures
Full Text: DOI
[1] Ash C.J., Jockusch C.G. Jr, Knight J.F.: Jumps of orderings. Trans. Am. Math. Soc. 319(2), 573–599 (1990) · Zbl 0705.03022 · doi:10.2307/2001255
[2] Coles R.J., Downey R.G., Khoussainov B.M.: On initial segments of computable linear orders, order. J. Theory Order. Sets Appl. 14(2), 107–124 (1997/1998) · Zbl 0915.03040
[3] Calvert W., Cenzer D., Harizanov V., Morozov A.: Effective categoricity of equivalence structures. Ann. Pure Appl. Log. 141, 61–78 (2006) · Zbl 1103.03037 · doi:10.1016/j.apal.2005.10.002
[4] Downey, R.G.: Computability theory and linear orderings. In: Handbook of recursive mathematics, vol. 2, Stud. Logic Found. Math., vol. 139. North-Holland, Amsterdam, pp. 823–976 (1998) · Zbl 0941.03045
[5] Hirschfeldt, D.R.: Prime models of theories of computable linear orderings. Proc. Am. Math. Soc. 129(10), 3079–3083 (2001) (electonic) · Zbl 0974.03040
[6] Khisamiev, N.G.: Criterion for constructivizability of a direct sum of cyclic p-groups. Izvestiya Akademii Nauk KazakhskoÄ­ SSR. Seriya Fiziko-Matematicheskaya (1), 51–55, 86, (1981)
[7] Khoussainov B.M., Nies A., Shore R.A.: Computable models of theories with few models. Notre Dame J. Formal Log. 38(2), 165–178 (1997) · Zbl 0891.03013 · doi:10.1305/ndjfl/1039724885
[8] Rogers H. Jr: Theory of recursive functions and effective computability, 2nd edn. MIT Press, Cambridge (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.