## 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$$.

### MSC:

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

### References:

  Chaitin, G. J., “Algorithmic information theory,” IBM Journal of Research and Development, vol. 21 (1977), pp. 350-59. · Zbl 0362.94035  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  Downey, R., and D. R. Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010. · Zbl 1221.68005  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  Gács, P., “Every sequence is reducible to a random one,” Information and Control, vol. 70 (1986), pp. 186-92. · Zbl 0628.03024  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  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.  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  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.  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  Nies, A., “Lowness properties and randomness,” Advances in Mathematics, vol. 197 (2005), pp. 274-305. · Zbl 1141.03017  Nies, A., Computability and Randomness, vol. 51 of Oxford Logic Guides, Oxford University Press, Oxford, 2009. · Zbl 1169.03034  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  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  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  Solovay, R. M., unpublished notes, May 1975.  van Lambalgen, M., “The axiomatization of randomness,” Journal of Symbolic Logic, vol. 55 (1990), pp. 1143-67. · Zbl 0724.03026  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.