Ergodic undefinability in set theory and recursion theory

Mundici, Daniele

doi:10.1090/S0002-9939-1981-0603611-1

Ergodic undefinability in set theory and recursion theory
HTML articles powered by AMS MathViewer

by Daniele Mundici PDF

Proc. Amer. Math. Soc. 82 (1981), 107-111 Request permission

Abstract:

Let $T$ be a measure preserving ergodic transformation of a compact Abelian group $G$ with normalized Haar measure $m$ on the collection $\mathcal {B}$ of Borel sets; call $g \in G$ generic w.r.t. a set $B \in \mathcal {B}$ iff, upon action by $T$, $g$ is to stay in $B$ with limit frequency equal to $m(B)$. We study the definability of generic elements in Zermelo-Fraenkel set theory with Global Choice (ZFGC, which is a very good conservative extension of ZFC), and in higher recursion theory. We prove $(1)$ the set of those $g \in G$ which are generic w.r.t. all ZFGC-definable Borel subsets of $G$ is not ZFGC-definable, and $(2)$ "being generic w.r.t. all hyperarithmetical properties of dyadic sequences" is not itself a hyperarithmetical property of dyadic sequences.

References

Manfred Denker, Christian Grillenberger, and Karl Sigmund, Ergodic theory on compact spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976. MR 0457675
Ulrich Felgner, Comparison of the axioms of local and universal choice, Fund. Math. 71 (1971), no. 1, 43–62. (errata insert). MR 289285, DOI 10.4064/fm-71-1-43-62
Nathaniel A. Friedman, Introduction to ergodic theory, Van Nostrand Reinhold Mathematical Studies, No. 29, Van Nostrand Reinhold Co., New York-Toronto, Ont.-London, 1970. MR 0435350
Haim Gaifman, Global and local choice functions, Israel J. Math. 22 (1975), no. 3-4, 257–265. MR 389590, DOI 10.1007/BF02761593
Paul R. Halmos, Naive set theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1974. Reprint of the 1960 edition. MR 0453532
Alexander S. Kechris, Measure and category in effective descriptive set theory, Ann. Math. Logic 5 (1972/73), 337–384. MR 369072, DOI 10.1016/0003-4843(73)90012-0
Azriel Lévy, Basic set theory, Springer-Verlag, Berlin-New York, 1979. MR 533962
Per Martin-Löf, On the notion of randomness, Intuitionism and Proof Theory (Proc. Conf., Buffalo, N.Y., 1968) North-Holland, Amsterdam, 1970, pp. 73–78. MR 0275483

Descriptive set theory: projective sets

L. S. Pontryagin, Topological groups, Gordon and Breach Science Publishers, Inc., New York-London-Paris, 1966. Translated from the second Russian edition by Arlen Brown. MR 0201557
Gerald E. Sacks, Measure-theoretic uniformity in recursion theory and set theory, Trans. Amer. Math. Soc. 142 (1969), 381–420. MR 253895, DOI 10.1090/S0002-9947-1969-0253895-6
Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
Hisao Tanaka, A basis result for $\Pi _{1}{}^{1}$-sets of postive measure, Comment. Math. Univ. St. Paul. 16 (1967/68), 115–127. MR 236017
Peter Walters, Ergodic theory—introductory lectures, Lecture Notes in Mathematics, Vol. 458, Springer-Verlag, Berlin-New York, 1975. MR 0480949

Recursive-theoretic hierarchies