A Measure on the Naturl Numbers

Where am I coming from

The other day I wondered why I don't know of a measure on the natural numbers $\NN$. On the reals, $\RR$, we have a measure deriving from the length of intervals as $\mu([a,b]) = b-a$. On $\NN$ we can assign a size to a subset by the number of elements it contains — for finite subsets. Is there something possible for infinite subsets.

Definition of a System of Sets

For $k\in\NN$ let $k\NN := \{kn \,|\, n\in\NN\}$, so $7\NN = \{7, 14, 21, \dots\}$. We also allow to shift such sets to the left to be able to start at $1$:

$$\Mset(k,i) := \{kn -i \,|\, n\in\NN\} \quad\text{ for } k\in\NN \text{ and } 0\leq i\lt k.$$

So $\Mset(5,4) = \{1, 6, 11, \dots\}$. For convenience lets define

$$\DD = \{\Mset(k,i) \,|\, k\in\NN \land 0\leq i\lt k\}.$$

With union over the shifts $i$ we get the natural numbers:

$$\NN = \bigcup_{i=0}^{k-1} \Mset(k,i).$$

But what happens with the intersection of two set of $\DD$?

Proposition: For two set $A, B\in\DD$ we have either $ A\cap B = \emptyset$ or $A\cap B \in \DD$.

Proof: Suppose $A = \Mset(k,i)$ and $B=\Mset(l,j)$ are not disjoint. Then let $s$ be the smallest element in $ A\cap B$. By definition of $A$ and $B$ we can find $n_k, n_l\in\NN$ such that

$$ s = kn_k -i = ln_l -j \qquad \text{with } i,j\in\NN. $$ Let $q = \lcm(k, l)$ be the least common multiple of $k$ and $l$. Then we can find $0\leq r \lt q$ and $t\in\NN$ such that $s = qt - r$. Namely chose $t = \lfloor\frac{s}{q}\rfloor + 1$ and $r = s - tq$.

Assume that $t>1$. Then define $s_0 = q - r \lt s$ and we have

\begin{align*} s - s_0 &= qt - r -(q -r)\\ &= q(t-1)\\ \text{or}\qquad s_0 &= s - q(t-1) \end{align*}

Since $q=\lcm(k,l)$ we can write $q=q_kk=q_ll$ for some $q_k, q_l\in\NN$ and so we get

\begin{align*} s_0 &= s - q_kk(t-1) &&= s - q_ll(t-1)\\ &= kn_k -i - q_kk(t-1) &&= ln_l -j - q_ll(t-1)\\ &= k(n_k -q_kk(t-1)) -i &&= l(n_l -q_ll(t-1)) -j\\ \end{align*} This shows that $s_0\in \Mset(k,i)\cap\Mset(l,j)$ though $s$ was defined to be the smallest of those. Therefore we have actually $s=s_0= q-r$.

We now show that $A\cap B = \Mset(q,r)$.

Backward direction: Let $t'\in\NN$ and define $s'=qt' - r\in\Mset(q,r)$. Then we have $$s'-s = qt'-r - (q-r) = q(t' -1).$$ Similar to the reasoning above it follows that

$$ \begin{align*} s' &= s + k q_k(t'-1) &&= s + l q_l(t'-1) \\ &= kn_k - i + k q_k(t'-1) &&= ln_l -j + l q_l(t'-1)\\ &= k(n_k+q_k(t'-1))-i &&= l(n_l+q_l(t'-1)) -j\\ \end{align*} $$ And since $t'-1\ge 0$ this shows that $s'\in A\cap B$.

Forward direction: Let $s'\in \Mset(k,i)\cap\Mset(l,j)$ so we have $$ s' = kn_k' - i = ln_l' -j. $$ It follows that \begin{align*} s'-s &= kn_k' - i - (kn_k-i)&&= ln_l' - j -(ln_l-j) \\ &= k(n_k'-n_k) && = l(n_l'-n_l) \end{align*} Consquently $s' -s$ is a multiple of both, $k$ and $l$, which means $q=\lcm(k,l)$ is a factor of $s' - s$, say $s'-s = q_sq$. But then we have

\begin{align*} s' &= s + q_sq\\ &= q - r + q_sq\\ &= q(q_s + 1) -r\\ & \in\Mset(q,r). \end{align*}