Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: In Memory of S. Barry Cooper (1943–2015)
Guest editors: Benedikt Löwe
Article type: Research Article
Authors: Cooper, S. Barrya | Gay, Jamesb | Harris, Charles M.c | Lee, Kyung Ild | Morphett, Anthonye
Affiliations: [a] School of Mathematics, University of Leeds, Leeds LS2 9JT, U.K. | [b] School of Mathematics, University of Leeds, Leeds LS2 9JT, U.K.. jamesrkg@gmail.com | [c] School of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, U.K.. harris.charles@gmail.com | [d] Department of Mathematics and Statistics, Minnesota State University, 273 Wissink Hall, Mankato, MN 56001, U.S.A.. kyung-il.lee@mnsu.edu | [e] School of Mathematics and Statistics, The University of Melbourne, Parkville 3010, Australia. a.morphett@unimelb.edu.au
Abstract: A partial order is computably well founded if it does not computably embed a copy of ω∗, the order type of the negative integers. It is computably scattered if it does not computably embed a copy of η, the order type of Q. It is known that, for each of these properties, there are computable partial orders satisfying the property which do not have a computable linear extension with the same property. Rosenstein showed, however, that for both of these properties, every computable partial order satisfying the property has a Δ20 linear extension also satisfying the property. Thus, linear extensions of a computable order preserving the properties of computable well foundedness or computable scatteredness can always be found at the Δ20 level of the arithmetical hierarchy, but not at the Δ10 level. In this paper, we investigate at which level of the Ershov hierarchy such linear extensions can be found. We show that, for both properties, every computable partial order satisfying the property has an ω-c.e. linear extension with the same property. We establish that this is the best possible result within the Ershov hierarchy by constructing, respectively, computably well founded and computably scattered orders which do not have n-c.e. linear extensions which are computably well founded and computably scattered respectively, for any n<ω. In a strengthening of Rosenstein’s theorems in another direction, we show that a linear extension preserving each of these properties can be computed using any oracle satisfying an escape property, which includes the class of non-generalised low2 sets. Finally, we show that the analogue of Rosenstein’s theorems do not hold for the property of not computably embedding a copy of ζ, the order type of the integers, by constructing a computable partial ordering which does not embed ζ, but such that every Δ20 linear extension of the ordering does admit a computable embedding of ζ.
Keywords: Computable, partial order, linear extension, well founded, scattered, Ershov hierarchy, arithmetical hierarchy
DOI: 10.3233/COM-170080
Journal: Computability, vol. 7, no. 2-3, pp. 143-169, 2018
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl