On Kierstead’s conjecture

Ng, Keng Meng; Zubkov, Maxim

doi:10.1090/tran/7858

On Kierstead’s conjecture
HTML articles powered by AMS MathViewer

by Keng Meng Ng and Maxim Zubkov PDF

Trans. Amer. Math. Soc. 372 (2019), 3713-3753 Request permission

Abstract:

We settle the long-standing Kierstead conjecture in the negative. We do this by constructing a computable linear order with no rational subintervals, where every block has order type finite or $\zeta$, and where every computable copy has a strongly nontrivial $\Pi ^0_1$ automorphism. We also construct a strongly $\eta$-like linear order where every block has size at most $4$ with no rational subinterval such that every $\Delta ^0_2$ isomorphic computable copy has a nontrivial $\Pi ^0_1$ automorphism.

References

R. G. Downey, Computability theory and linear orderings, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 823–976. MR 1673590, DOI 10.1016/S0049-237X(98)80047-5
Rodney G. Downey, Asher M. Kach, and Daniel Turetsky, Limitwise monotonic functions and their applications, Proceedings of the 11th Asian Logic Conference, World Sci. Publ., Hackensack, NJ, 2012, pp. 59–85. MR 2868506, DOI 10.1142/9789814360548_{0}004
Rodney G. Downey and Michael F. Moses, On choice sets and strongly nontrivial self-embeddings of recursive linear orders, Z. Math. Logik Grundlag. Math. 35 (1989), no. 3, 237–246. MR 1000966, DOI 10.1002/malq.19890350307
Ben Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600–610. MR 4862, DOI 10.2307/2371374
Andrey N. Frolov and Maxim V. Zubkov, Increasing $\eta$-representable degrees, MLQ Math. Log. Q. 55 (2009), no. 6, 633–636. MR 2582163, DOI 10.1002/malq.200810031
A. N. Frolov and M. V. Zubkov, Limitwise monotonic functions relative to the Kleene’s Ordinal Notation System, Lobachevskii J. Math. 35 (2014), no. 4, 295–301. MR 3284616, DOI 10.1134/S1995080214040167
Kenneth Harris, $\eta$-representation of sets and degrees, J. Symbolic Logic 73 (2008), no. 4, 1097–1121. MR 2467206, DOI 10.2178/jsl/1230396908
Charles M. Harris, Kyung Il Lee, and S. Barry Cooper, Automorphisms of $\eta$-like computable linear orderings and Kierstead’s conjecture, MLQ Math. Log. Q. 62 (2016), no. 6, 481–506. MR 3601091, DOI 10.1002/malq.201400109
Asher M. Kach and Daniel Turetsky, Limitwise monotonic functions, sets, and degrees on computable domains, J. Symbolic Logic 75 (2010), no. 1, 131–154. MR 2605885, DOI 10.2178/jsl/1264433912
Henry A. Kierstead, On $\Pi _1$-automorphisms of recursive linear orders, J. Symbolic Logic 52 (1987), no. 3, 681–688. MR 902983, DOI 10.2307/2274356
Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662564
Steven Thomas Schwarz, QUOTIENT LATTICES, INDEX SETS, AND RECURSIVE LINEAR ORDERINGS, ProQuest LLC, Ann Arbor, MI, 1982. Thesis (Ph.D.)–The University of Chicago. MR 2611822
Steven Schwarz, Recursive automorphisms of recursive linear orderings, Ann. Pure Appl. Logic 26 (1984), no. 1, 69–73. MR 739913, DOI 10.1016/0168-0072(84)90041-1
Guohua Wu and Maxim Zubkov, The Kierstead’s conjecture and limitwise monotonic functions, Ann. Pure Appl. Logic 169 (2018), no. 6, 467–486. MR 3780011, DOI 10.1016/j.apal.2018.01.003
M. V. Zubkov, Sufficient conditions for the existence of ${\bf 0}’$-limitwise monotone functions for computable $\eta$-like linear orders, Sibirsk. Mat. Zh. 58 (2017), no. 1, 107–121 (Russian, with Russian summary); English transl., Sib. Math. J. 58 (2017), no. 1, 80–90. MR 3686945, DOI 10.1134/s0037446617010128