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

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\).


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


[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
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.