Large Turing independent sets

Kumar, Ashutosh; Shelah, Saharon

doi:10.1090/proc/16081

Large Turing independent sets
HTML articles powered by AMS MathViewer

by Ashutosh Kumar and Saharon Shelah

Proc. Amer. Math. Soc. 151 (2023), 355-367

DOI: https://doi.org/10.1090/proc/16081

Published electronically: August 18, 2022

HTML | PDF | Request permission

Abstract:

For a set of reals $X$ and $1 \leq n < \omega$, define $X$ to be $n$-Turing independent iff the Turing join of any $n$ reals in $X$ does not compute another real in $X$. $X$ is Turing independent iff it is $n$-Turing independent for every $n$. We show the following: (1) There is a non-meager Turing independent set. (2) The statement “Every set of reals of size continuum has a Turing independent subset of size continuum” is independent of ZFC plus the negation of CH. (3) The statement “Every non-meager set of reals has a non-meager $n$-Turing independent subset” holds in ZFC for $n = 1$ and is independent of ZFC for $n \geq 2$ (assuming the consistency of a measurable cardinal). We also show the measure analogue of (3).

References

Tomek Bartoszyński and Haim Judah, Set theory, A K Peters, Ltd., Wellesley, MA, 1995. On the structure of the real line. MR 1350295, DOI 10.1201/9781439863466
Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt, and Joseph S. Miller, Every 1-generic computes a properly 1-generic, J. Symbolic Logic 71 (2006), no. 4, 1385–1393. MR 2275865, DOI 10.2178/jsl/1164060461
P. Komjáth, A second category set with only first category functions, Proc. Amer. Math. Soc. 112 (1991), no. 4, 1129–1136. MR 1065086, DOI 10.1090/S0002-9939-1991-1065086-7
Ashutosh Kumar and Saharon Shelah, Avoiding equal distances, Fund. Math. 236 (2017), no. 3, 263–267. MR 3600761, DOI 10.4064/fm169-5-2016
Kenneth Kunen, Set theory, Studies in Logic and the Foundations of Mathematics, vol. 102, North-Holland Publishing Co., Amsterdam-New York, 1980. An introduction to independence proofs. MR 597342
Patrick Lutz, Results on Martin’s conjecture [thesis abstract], Bull. Symb. Log. 27 (2021), no. 2, 219–220. MR 4313010, DOI 10.1017/bsl.2021.27
Joseph S. Miller and Liang Yu, On initial segment complexity and degrees of randomness, Trans. Amer. Math. Soc. 360 (2008), no. 6, 3193–3210. MR 2379793, DOI 10.1090/S0002-9947-08-04395-X
Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, NJ, 1963. MR 186554
Saharon Shelah, The null ideal restricted to some non-null set may be $\aleph _1$-saturated, Fund. Math. 179 (2003), no. 2, 97–129. MR 2029228, DOI 10.4064/fm179-2-1
Wang Wei, Martin’s axiom and embeddings of upper semi-lattices into the Turing degrees, Ann. Pure Appl. Logic 161 (2010), no. 10, 1291–1298. MR 2652198, DOI 10.1016/j.apal.2010.04.002
Liang Yu, Measure theory aspects of locally countable orderings, J. Symbolic Logic 71 (2006), no. 3, 958–968. MR 2251548, DOI 10.2178/jsl/1154698584