Normal numbers and subsets of N with given densities

Fundamenta Mathematicae (1994)

• Volume: 144, Issue: 2, page 163-179
• ISSN: 0016-2736

top

Abstract

top
For X ⊆ [0,1], let ${D}_{X}$ denote the collection of subsets of ℕ whose densities lie in X. Given the exact location of X in the Borel or difference hierarchy, we exhibit the exact location of ${D}_{X}$. For α ≥ 3, X is properly ${D}_{\xi }\left({\Pi }_{\alpha }^{0}\right)$ iff ${D}_{X}$ is properly ${D}_{\xi }\left({\Pi }_{1+\alpha }^{0}\right)$. We also show that for every nonempty set X ⊆[0,1], ${D}_{X}$ is ${\Pi }_{3}^{0}$-hard. For each nonempty ${\Pi }_{2}^{0}$ set X ⊆ [0,1], in particular for X = x, ${D}_{X}$ is ${\Pi }_{3}^{0}$-complete. For each n ≥ 2, the collection of real numbers that are normal or simply normal to base n is ${\Pi }_{3}^{0}$-complete. Moreover, ${D}_{ℚ}$, the subsets of ℕ with rational densities, is ${D}_{2}\left({\Pi }_{3}^{0}\right)$-complete.

How to cite

top

Ki, Haseo, and Linton, Tom. "Normal numbers and subsets of N with given densities." Fundamenta Mathematicae 144.2 (1994): 163-179. <http://eudml.org/doc/212021>.

@article{Ki1994,
abstract = {For X ⊆ [0,1], let $D_X$ denote the collection of subsets of ℕ whose densities lie in X. Given the exact location of X in the Borel or difference hierarchy, we exhibit the exact location of $D_X$. For α ≥ 3, X is properly $D_ξ(Π^0_α)$ iff $D_X$ is properly $D_ξ(Π^0_\{1+α\})$. We also show that for every nonempty set X ⊆[0,1], $D_X$ is $Π^0_3$-hard. For each nonempty $Π^0_2$ set X ⊆ [0,1], in particular for X = x, $D_X$ is $Π^0_3$-complete. For each n ≥ 2, the collection of real numbers that are normal or simply normal to base n is $Π^0_3$-complete. Moreover, $D_ℚ$, the subsets of ℕ with rational densities, is $D_2(Π^0_3)$-complete.},
author = {Ki, Haseo, Linton, Tom},
journal = {Fundamenta Mathematicae},
keywords = {Borel hierarchy; Borel class; densities},
language = {eng},
number = {2},
pages = {163-179},
title = {Normal numbers and subsets of N with given densities},
url = {http://eudml.org/doc/212021},
volume = {144},
year = {1994},
}

TY - JOUR
AU - Ki, Haseo
AU - Linton, Tom
TI - Normal numbers and subsets of N with given densities
JO - Fundamenta Mathematicae
PY - 1994
VL - 144
IS - 2
SP - 163
EP - 179
AB - For X ⊆ [0,1], let $D_X$ denote the collection of subsets of ℕ whose densities lie in X. Given the exact location of X in the Borel or difference hierarchy, we exhibit the exact location of $D_X$. For α ≥ 3, X is properly $D_ξ(Π^0_α)$ iff $D_X$ is properly $D_ξ(Π^0_{1+α})$. We also show that for every nonempty set X ⊆[0,1], $D_X$ is $Π^0_3$-hard. For each nonempty $Π^0_2$ set X ⊆ [0,1], in particular for X = x, $D_X$ is $Π^0_3$-complete. For each n ≥ 2, the collection of real numbers that are normal or simply normal to base n is $Π^0_3$-complete. Moreover, $D_ℚ$, the subsets of ℕ with rational densities, is $D_2(Π^0_3)$-complete.
LA - eng
KW - Borel hierarchy; Borel class; densities
UR - http://eudml.org/doc/212021
ER -

References

top
1. [1] L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, Wiley, New York, 1974. Zbl0281.10001
2. [2] A. Louveau and J. Saint-Raymond, Borel classes and closed games: Wadge-type and Hurewicz-type results, Trans. Amer. Math. Soc. 304 (1987), 431-467. Zbl0655.04001
3. [3] D. A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), 363-371.
4. [4] D. E. Miller, The invariant ${\Pi }_{\alpha }^{0}$ separation principle, Trans. Amer. Math. Soc. 242 (1978), 185-204.
5. [5] I. Niven, Irrational Numbers, The Carus Math. Monographs 11, Math. Assoc. America, Quinn and Boden, Rahway, N.J., 1956.
6. [6] W. Schmidt, On normal numbers, Pacific J. Math. 10 (1960), 661-672. Zbl0093.05401
7. [7] W. Wadge, Degrees of complexity of subsets of the Baire space, Notices Amer. Math. Soc. 19 (1972), A-714-A-715 (abstract 72T-E91).

top

NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.