Recently I was trying to put a “meaningful” measure on the set $\mathbb{N}$ of natural numbers. The first idea was to measure the density of a subset $A \subseteq \mathbb{N}$ on natural intervals $\{1,\ldots,n\}$ and take the limit of it, that is

$\lim_{n\to\infty}\frac{|\{1,\ldots,n\} \cap A|}{n}.$

However, the limit does not always exist (examples?). So here is a modification and we define a map $\mu:\mathcal{P}(\mathbb{N}) \to [0,1]$ by

$\mu(A) := \lim\inf_{n\to\infty}\frac{|\{1,\ldots,n\} \cap A|}{n}$ for all $A \subseteq \mathbb{N}$.

Question: is $\mu$ additive, that is for $A,B\subseteq \mathbb{N}$ with $A\cap B = \emptyset$ do we have $\mu(A\cup B) = \mu(A) + \mu(B)$? There is a surprising answer that I’ll post in a few days.

I'm interested in general topology, order theory, and graph theory. This link takes you to my preprints on arXiv.
This entry was posted in Uncategorized. Bookmark the permalink.

1. Carlos says:

It is not additive. Any example for which the lim does not exist will do. For example, take $A$ to be the union of $[2^{2j}, 2^{2j+1})$ when $j=0, \ldots, \infty$. The lim does not exist but the liminf is $1/3$ (take, for example, the subsequence $n= 2^{2k}-1$). Take $B$ to be the complement of $A$. Similarly the liminf is 1/3.

2. Qiaochu Yuan says:

The first measure you describe is called the natural density. As you say, a big problem with it is that it does not always exist. However, it can in some sense be approximated by measures which always exist, namely the measures

$\displaystyle \frac{\sum_{n \in A} \frac{1}{n^s}}{\zeta(s)}$

where $s > 1$ is a real number and $\zeta(s)$ is the Riemann zeta function. These (probability) measures have the lovely property that being divisible by $p$ and being divisible by $q$, for two distinct primes $p \neq q$, are independent events. Moreover, as $s \to 1$ they converge to a related measure called the logarithmic density, when it exists. The logarithmic density itself has the further desirable property that if it and the natural density both exist then they must agree.

This can be used to explain why, for example, the probability (in a suitable sense) that two random integers are relatively prime is $\frac{1}{\zeta(2)}$. See, for example, this blog post.

3. Salvo says:

Carlos’ answer has it right, but you may find interesting that there is a deeper reason why the answer to your question is negative: The existence in ZF of an additive measure $\mu: \mathcal P(\mathbf N) \to \bf R$ that vanishes on singletons implies the existence of $\bf R$ without the property of Baire, see Sections 29.37 and 29.38 in: E. Schechter, Handbook of Analysis and its Foundations, Academic Press, 1996. However, ZF alone does not prove the existence of such an additive measure, see D. Pincus, “The strength of the Hahn-Banach theorem”, 203-248 in: A. E. Hurd and P. Loeb (eds.), Victoria Symposium on Nonstandard Analysis, Lecture Notes in Math. 369, Springer: Berlin, 1974. And on the other hand, the upper asymptotic density is a well-defined widget in ZF.

• Salvo says:

A meant “[…] the existence of a subset of $\bf R$ without the property of Baire.” It’s annoying that you can’t edit your comments, isn’t it?

4. dominiczypen says:

Brilliant – thanks Salvo! – Have any of the open questions you mention in your article been resolved?

• Salvo says:

@Dominic. So far, none of the questions in the section “Closing remarks and open questions” has been solved, though Paolo and I have made some progress on Question 4: More precisely, we have proved that any upper quasi-density has the strong Darboux property, see http://mathoverflow.net/questions/219274/ for the terminology; these and some related results are the content of a paper that we have just finished writing and should appear on arXiv in a couple of days or so.

For the record, I would be very happy with an answer (either positive or not) to Questions 7 and 8, in spite of the fact that they are admittedly much less interesting than others. But a counterexample to either of them, if it exists, is probably rather complicated, if you think of the construction that was necessary to prove the existence of a non-monotone upper quasi-density (Theorem 1).

• comerane says:

@Dominic. I couldn’t retrieve your email address, so I’m dropping a message here: Just in case you may be interested, the preprint I was referring to in my previous comment is now available from the url http://arxiv.org/abs/1510.07473.

Let me note that, in the past few days, we seem to have found a negative answer Question 2 (in Section 6) for the part concerning the “shift-invariant case”, but the construction is fairly long and complicated, so we have thought to write a second paper on this. On the other hand, we do not yet know whether the other part of the same question (i.e., “Does there exist a monotone, subadditive, and (-1)-homogeneous function $f: P({\bf N}) \to \bf R$ such that $f(\emptyset) = 0$, $f({\bf N}) = 1$, and $f$ has the weak, but not the strong, Darboux property?”) has a negative answer too. If you have any idea, comment, or whatever on this or other questions, please just let me know.have thought to write a second paper on this. On the other hand, we do not yet know whether the other part of the same question (i.e., “Does there exist a monotone, subadditive, and (-1)-homogeneous function $f: P({\bf N}) \to \bf R$ such that $f(\emptyset) = 0$, $f({\bf N}) = 1$, and $f$ has the weak, but not the strong, Darboux property?”) has a negative answer too. If you have any idea, comment, or whatever on this or other questions, please just let me know.