Where does the collection of sets with positive upper density lie in the Borel hierarchy?

Question

The upper density of a set $A\subset\mathbb{N}$ is defined as $\bar{d}(A) = \limsup_{N\to\infty}\frac{|A\cap\{1,\ldots,N\}|}{N}$. If we identify a set $A$ with its characteristic function $\chi_A$, which we treat as an element of $2^{\mathbb{N}}$, it makes sense to talk about the upper density of an infinite $\{0, 1\}$ sequence. I'll abuse notation and write $\bar{d}(\chi_A) = \bar{d}(A)$.

What does the set of reals $\{y\in 2^{\mathbb{N}}:\bar{d}(y) > 0\}\subset 2^{\mathbb{N}}$ look like in terms of its complexity? Can we place it somewhere definitively in the Borel hierarchy $\cup_{\xi<\omega_1}\Sigma^0_{\xi}$?

Answer 1

Fix an integer $N$ and a real $r$. The set $D_{N, r}$ of sets $A$ satisfying ${\vert A\cap\{1, ..., N\}\vert\over N}\ge r$ is clopen (since this condition only depends on the first $N$ bits of $A$.

Now a set $A$ has upper density $\ge r$ if for infinitely many $N$, we have $A\in D_{N, r}$. This turns out to correspond to two levels in the Borel hierarchy, as follows. Let $D_{N^+, r}=\bigcup_{M\ge N} D_{M,r}$. Each $D_{N^+, r}$ is open (being a countable union of clopen sets), and (exercise) $A$ is in infinitely many $D_{N, r}$s iff $A\in D_{N^+, r}$ for every $N$; that is, iff $A\in\bigcap_{N\in\mathbb{N}}(\bigcup_{M\ge N}D_{M, r})$, and this latter set is $\Pi^0_2$.

So to recap, the set of sets with upper density $\ge r$ is (at worst) $\Pi^0_2$ for each $r$. Now, a set has positive upper density iff it has upper density $\ge q$ for some positive rational $q$, and there are only countably many positive rationals; so the set of sets of positive upper density is a countable union of $\Pi^0_2$ sets, hence $\Sigma^0_3$.

Now this is just an upper bound; we still need to show that it's not $\Pi^0_3$ to make this upper bound sharp. This is messy, but not too hard, and is a good exercise.