Subsets of $\mathbb{N}$ whose lower density respects complements

Question

The lower density of $A\subseteq\mathbb{N}$ is defined to be $\lambda(A)=\lim\text{inf}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n}$. We set $${\cal C} = \{A\subseteq \mathbb{N}: \lambda(\mathbb{N}\setminus A) = 1 - \lambda(A)\}.$$

Do both ${\cal C}$ and ${\cal P}(\mathbb{N})\setminus {\cal C}$ have cardinality $2^{\aleph_0}$?

Answer 1

The answer is yes: Given a set $A$ in $\mathcal{C}$ or in $\mathcal{P}(\mathbb{N}) \setminus \mathcal{C}$, you can take any subset $B \subset \mathbb{N} \setminus A$ of lower density $0$, and $A \cup B$ is still in $\mathcal{C}$ or in $\mathcal{P}(\mathbb{N}) \setminus \mathcal{C}$, depending on which of the two classes $A$ itself belongs to. Now, unless $A$ is cofinite, the cardinality of the set of subsets of $\mathbb{N} \setminus A$ with lower density $0$ is $2^{\aleph_0}$, so you have $2^{\aleph_0}$ choices for $B$. The result follows since each of the classes $\mathcal{C}$ and $\mathcal{P}(\mathbb{N}) \setminus \mathcal{C}$ has at least one member which is not cofinite, and since the set of cofinite subsets of $\mathbb{N}$ is countable.

Answer 2

Let $\alpha \in {]0,1]}$. On the one hand, the set $\{\lfloor \alpha^{-1}n \rfloor: n \in \mathbf N\}$ has (natural) density equal to $\alpha$, so it belongs to $\mathcal C$. On the other hand, the set $\bigcup_{n \ge 1} [\![(2n-1)!\,\alpha + (2n)!\,(1-\alpha) + 1, (2n)!+1]\!]$ has lower (natural) density equal to $0$ and upper (natural) density equal to $\alpha$ (as it follows from here), so it belongs to $\mathcal P(\mathbf N) \setminus \mathcal C$.

Edit (July 05, 2015). For those who may care, here is a complement to Stefan Kohl's and my own answer, to highlight some differences between the two approaches (and suggest a couple of questions that someone else will hopefully find interesting).

To start with, let an upper quasi-density (on $\mathbf N$) be a function $\mu^\ast: \mathcal P(\mathbf N) \to \mathbf R$ such that, for all $X,Y \subseteq \mathbf N$ and $h,k \in \mathbf N^+$, the following hold:

1. $\mu^\ast(\mathbf N) = 1$;
2. $\mu^\ast(X \cup Y) \le \mu^\ast(X) + \mu^\ast(Y)$;
3. $\mu^\ast(k \cdot X + h) = \frac{1}{k} \mu^\ast(X)$;
4. $\mu^\ast(X) \le 1$.

If, in addition, $\mu^\ast$ is monotonic, viz. $\mu^\ast(X) \le \mu^\ast(Y)$ whenever $X \subseteq Y \subseteq \mathbf N$, then we call $\mu^\ast$ an upper density (on $\mathbf N$), in which case condition 4 is implied by the others.

Given an upper quasi-density $\mu^\ast$, we define its lower dual $\mu_\ast$ as the function $$ \mathcal P(\mathbf N) \to \mathbf R: X \mapsto 1 - \mu^\ast(\mathbf N \setminus X), $$ and accordingly we let the quasi-density induced by $\mu^\ast$ be the partial function $$ \mu: \mathcal P(\mathbf N) \rightharpoonup \mathbf R: X \mapsto \mu^\ast(X) $$ whose domain is the set $$ \mathcal D_\mu := \{X \in \mathcal P(\mathbf N): \mu_\ast(X) = \mu^\ast(X)\}. $$ Since the upper asymptotic density is an upper density in the sense of the definitions above (the same is also true, among the others, for the upper Banach density, upper logarithmic density, upper analytic density, and Buck's measure density), we see that the OP is asking whether $\mathcal D_\mu$ and $\mathcal P(\mathbf N) \setminus \mathcal D_\mu$ have both the same cardinality of $\mathbf R$.

In fact, it can be proved, see Theorem 2 here, that for every $\alpha \in [0,1]$ there exists $X \subseteq \mathbf N$ such that $\mu(X) = \alpha$, which yields that $|\mathcal D_\mu| = |\mathbf R|$: This is based on the explicit construction of such a set $X$, and can't be proved by Stefan Kohl's argument, insofar as we don't know whether $\mu^\ast(X) = \mu^\ast(X \cup Y)$ for every finite set $Y \subseteq \mathbf H$ (this is Question 7 in the linked preprint).

On the other hand, if $\mu^\ast$ is an upper density (i.e., is monotonic), then the "invariance-under-union-with-finite-sets property" is true, and Stefan Kohl's reasoning can be adapted to prove that $|\mathcal P(\mathbf N) \setminus \mathcal D_\mu| = |\mathbf R|$ if $\mathcal D_\mu \subsetneq \mathcal P(\mathbf N)$, namely $\mu_\ast(X) < \mu^\ast(X)$ for some $X \subseteq \mathbf N$ (see the note below), whereas my argument can't, insofar as we don't know whether it is true, again under the (necessary) assumption that $\mathcal D_\mu \subsetneq \mathcal P(\mathbf N)$, if for every $\alpha \in [0,1]$ there exists $X \subseteq \mathbf N$ such that $\mu_\ast(X) = 0$ and $\mu^\ast(X) = \alpha$ (which is a special case of Question 3 in the same linked preprint).

Note. In ZFC, say, there exist upper densities on $\mathbf N$ for which the inequality is false, see Question 209706: Unicity of additive, $(−1)$-homogeneous, and shift invariant probability measures on $\mathbf N^+$.