Archive for Mathematical Logic 47 (3):211-219 (2008)

The main result is that for sets ${S \subseteq \omega + 1}$ , the following are equivalent: The shuffle sum σ(S) is computable.The set S is a limit infimum set, i.e., there is a total computable function g(x, t) such that ${f(x) = \lim inf_t g(x, t)}$ enumerates S.The set S is a limitwise monotonic set relative to 0′, i.e., there is a total 0′-computable function ${\tilde{g}(x, t)}$ satisfying ${\tilde{g}(x, t) \leq \tilde{g}(x, t+1)}$ such that ${{\tilde{f}(x) = \lim_t \tilde{g}(x, t)}}$ enumerates S.Other results discuss the relationship between these sets and the ${\Sigma^0_3}$ sets
Keywords Shuffle sums  Limit infimum functions  Limitwise monotonic functions
Categories (categorize this paper)
DOI 10.1007/s00153-008-0077-3
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 60,826
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Computable Models of Theories with Few Models.Bakhadyr Khoussainov, Andre Nies & Richard A. Shore - 1997 - Notre Dame Journal of Formal Logic 38 (2):165-178.
Computability Theory and Linear Orders.Rod Downey - 1998 - In I͡Uriĭ Leonidovich Ershov (ed.), Handbook of Recursive Mathematics. Elsevier. pp. 138--823.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Order-Computable Sets.Denis Hirschfeldt, Russell Miller & Sergei Podzorov - 2007 - Notre Dame Journal of Formal Logic 48 (3):317-347.
Bounding Prime Models.Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare - 2004 - Journal of Symbolic Logic 69 (4):1117 - 1142.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.
Computability of Measurable Sets Via Effective Topologies.Yongcheng Wu & Decheng Ding - 2006 - Archive for Mathematical Logic 45 (3):365-379.
Η-Representation of Sets and Degrees.Kenneth Harris - 2008 - Journal of Symbolic Logic 73 (4):1097-1121.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Uncomputably Noisy Ergodic Limits.Jeremy Avigad - 2012 - Notre Dame Journal of Formal Logic 53 (3):347-350.
Computability & Unsolvability.Martin Davis - 1958 - Dover Publications.
Euclidean Functions of Computable Euclidean Domains.Rodney G. Downey & Asher M. Kach - 2011 - Notre Dame Journal of Formal Logic 52 (2):163-172.


Added to PP index

Total views
49 ( #212,330 of 2,438,854 )

Recent downloads (6 months)
1 ( #435,061 of 2,438,854 )

How can I increase my downloads?


My notes