Two more characterizations of \(K\)-triviality. (English) Zbl 1453.03041

Greenberg, Noam; Miller, Joseph S.; Monin, Benoit; Turetsky, Daniel

Notre Dame J. Formal Logic 59, No. 2, 189-195 (2018).

Summary: We give two new characterizations of \(K\)-triviality. We show that if for all \(Y\) such that \(\Omega\) is \(Y\)-random, \(\Omega\) is \((Y\oplus A)\)-random, then \(A\) is \(K\)-trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of \(K\)-triviality and answering a question of Yu. We also prove that if \(A\) is \(K\)-trivial, then for all \(Y\) such that \(\Omega\) is \(Y\)-random, \((Y\oplus A)\equiv_{\mathrm{LR}}Y\). This answers a question of Merkle and Yu. The other direction is immediate, so we have the second characterization of \(K\)-triviality.
The proof of the first characterization uses a new cupping result. We prove that if \(A\nleq_{\mathrm{LR}}B\), then for every set \(X\) there is a \(B\)-random set \(Y\) such that \(X\) is computable from \(Y\oplus A\).

MSC:

03D32	Algorithmic randomness and dimension
68Q30	Algorithmic information theory (Kolmogorov complexity, etc.)

Keywords:

\(K\)-triviality; Kolmogorov complexity; Martin-Löf randomness

References:

[1]	Chaitin, G. J., “Algorithmic information theory,” IBM Journal of Research and Development, vol. 21 (1977), pp. 350-59. · Zbl 0362.94035
[2]	Day, A. R., and J. S. Miller, “Cupping with random sets,” Proceedings of the American Mathematical Society, vol. 142 (2014), pp. 2871-79. · Zbl 1432.03079
[3]	Downey, R., and D. R. Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010. · Zbl 1221.68005
[4]	Downey, R., D. R. Hirschfeldt, J. S. Miller, and A. Nies, “Relativizing Chaitin’s halting probability,” Journal of Mathematical Logic, vol. 5 (2005), pp. 167-92. · Zbl 1093.03025
[5]	Gács, P., “Every sequence is reducible to a random one,” Information and Control, vol. 70 (1986), pp. 186-92. · Zbl 0628.03024
[6]	Hirschfeldt, D. R., A. Nies, and F. Stephan, “Using random sets as oracles,” Journal of the London Mathematical Society (2), vol. 75 (2007), pp. 610-22. · Zbl 1128.03036
[7]	Hölzl, R., and A. Nies, “CCR 2014: Open questions,” in Logic Blog, 2014, Part 1, Section 1, edited by A. Nies, available at http://arxiv.org/abs/1504.08163.
[8]	Kjos-Hanssen, B., “Low for random reals and positive-measure domination,” Proceedings of the American Mathematical Society, vol. 135 (2007), pp. 3703-9. · Zbl 1128.03031
[9]	Kučera, A., “Measure, \(Π^{0}_{1}\)-classes and complete extensions of \(\text{PA}\),” pp. 245-59 in Recursion Theory Week (Oberwolfach, 1984), vol. 1141 of Lecture Notes in Mathematics, Springer, Berlin, 1985.
[10]	Miller, J. S., and L. Yu, “On initial segment complexity and degrees of randomness,” Transactions of the American Mathematical Society, vol. 360 (2008), pp. 3193-210. · Zbl 1140.68028
[11]	Nies, A., “Lowness properties and randomness,” Advances in Mathematics, vol. 197 (2005), pp. 274-305. · Zbl 1141.03017
[12]	Nies, A., Computability and Randomness, vol. 51 of Oxford Logic Guides, Oxford University Press, Oxford, 2009. · Zbl 1169.03034
[13]	Posner, D. B., and R. W. Robinson, “Degrees joining to \(\mathbf{0}^{′}\),” Journal of Symbolic Logic, vol. 46 (1981), pp. 714-22. · Zbl 0517.03014
[14]	Reimann, J., and T. A. Slaman, “Measures and their random reals,” Transactions of the American Mathematical Society, vol. 367 (2015), pp. 5081-97. · Zbl 1375.03050
[15]	Simpson, S. G., and F. Stephan, “Cone avoidance and randomness preservation,” Annals of Pure and Applied Logic, vol. 166 (2015), pp. 713-28. · Zbl 1371.03052
[16]	Solovay, R. M., unpublished notes, May 1975.
[17]	van Lambalgen, M., “The axiomatization of randomness,” Journal of Symbolic Logic, vol. 55 (1990), pp. 1143-67. · Zbl 0724.03026
[18]	Yu, L., “Characterizing strong randomness via Martin-Löf randomness,” Annals of Pure and Applied Logic, vol. 163 (2012), pp. 214-24. · Zbl 1251.03048