Set Density: are even numbers more numerous than odd ones?

In pure set-theoretic terms, the set of even positive numbers is the same size, or cardinality, as the set of all natural numbers: both are infinite countable sets that can be put in one-to-one correspondence through the mapping ${n \rightarrow 2n}$ . This was known to Galileo. However, with the usual ordering,

$\displaystyle \mathbb{N} = \{ 1, 2, 3, 4, 5, 6, \dots \} \,,$

every second number is even and, intuitively, we feel that there are half as many even numbers as natural numbers. In particular, our intuition tells us that if ${B}$ is a proper subset of ${A}$ , it must be smaller than ${A}$ .

Natural Density

The concept of natural density provides a means of expressing the relative sizes of sets that is more discriminating than cardinality. Density — also called asymptotic density or arithmetic density — is defined for many interesting subsets of ${\mathbb{N}}$ , although not for all subsets. The counting function of a subset ${A}$ of ${\mathbb{N}}$ defined as

$\displaystyle \kappa_{A}(n) = \bigl|\{a\in A : a \le n \} \bigr| \,,$

where ${|\ \ |}$ denotes the cardinality of a set. It measures the number of elements of ${A}$ less than or equal to ${n}$ . We can then define the density ${\rho(A)}$ of the set ${A\subset\mathbb{N}}$ by

$\displaystyle \rho(A) = \lim_{n\rightarrow\infty}\ \frac{\kappa_{A}(n)}{n} \,,$

whenever this limit exists (Tenenbaum, 1995). If necessary, we indicate the reference set ${\mathbb{N}}$ by writing ${\rho_\mathbb{N}(A)}$ .

If the proportion of elements of ${A}$ among the first ${n}$ numbers in ${\mathbb{N}}$ converges to a limit ${\rho(A)}$ as ${n}$ tends to infinity, then ${A}$ has density ${\rho(A)}$ . The definition implies that, if the natural density exists, it lies in the interval ${[0,1]}$ . The density of a sequence is the limit of the frequency of its terms in the first ${n}$ integers, as might be expected. This value is consistent with our intuition.

Any arithmetic progression ${\{a + n d \}}$ has density ${1/d}$ . In particular, the even and odd numbers both have density ${\frac{1}{2}}$ . As an example of a set without a density, we consider the positive numbers having an odd number of decimal digits.

Dependence of Density on Ordering

For a monotonic sequence ${A = \{a_1, a_2, a_3, \dots \}\subset \mathbb{N}}$ , we can define the density (if it exists) of ${A}$ in ${\mathbb{N}}$ as

$\displaystyle \rho_\mathbb{N}(A) = \lim_{n\rightarrow\infty}\ \frac{n}{a_n} \,,$

If the reference set ${D}$ is other than ${\mathbb{N}}$ , we write ${\rho_D(A)}$ .

Let us consider some examples. For ${A = \{2, 4, 6, \dots \}}$ we have ${{n}/{a_n} = \frac{1}{2}}$ , so ${\rho(A) = \frac{1}{2}}$ , as might be expected. This is consistent with our intuitive notion that ${50\%}$ of the natural numbers are even.

We next consider multiples of ${2}$ and multiples of ${3}$ . Defining

$\displaystyle A = \{ n : (2\ |\ n ) \wedge (3 \sim\mid n) \}$

$\displaystyle B = \{ n : (2 \sim\mid n) \wedge (3\ |\ n ) \}$

$\displaystyle C = \mathbb{N} \setminus ( A \cup B ) \,,$

we have ${\mathbb{N} = A\uplus B\uplus C}$ . Numbers divisible by 2 but not by 3 are in ${A}$ ; numbers divisible by 3 but not by 2 are in ${B}$ ; all other natural numbers are in ${C}$ . Now we reorder the natural numbers as

$\displaystyle D = \{ A_1, B_1, C_1, \dots A_n, B_n, C_n, \dots \}$

so that ${D_{3n-2} = A_n}$ , ${D_{3n-1} = B_n}$ and ${D_{3n} = C_n}$ . It is clear that ${\rho_D(A) = \rho_D(B) = \frac{1}{3}}$ , so that ${2\mathbb{Z}}$ (multiples of ${2}$ ) and ${3\mathbb{Z}}$ (multiples of ${3}$ ) are equally dense in ${D}$ (multiples of ${6}$ are in both ${2\mathbb{Z}}$ and ${3\mathbb{Z}}$ ).

Twice as many even as odd numbers

Next, we will rearrange the natural numbers into a set ${F}$ such that there are twice as many even as odd numbers in ${F}$ . Let

$\displaystyle O = \{1, 3, 5, \dots \} = \{o_1, o_2, o_3, \dots \}\,, \qquad \rho_\mathbb{N}(O) = \frac{1}{2}$

$\displaystyle E = \{2, 4, 6, \dots \} = \{e_1, e_2, e_3, \dots \}\,, \qquad \rho_\mathbb{N}(E) = \frac{1}{2} \,.$

We now reorder ${\mathbb{N}}$ as follows:

$\displaystyle F = \{ o_1,e_1, e_2, o_2, e_3, e_4, \dots o_n,e_{2n-1}, e_{2n}, \dots \} \,,$

so that ${F_{3n-2}=o_{n}}$ , ${F_{3n-1}=e_{2n-1}}$ and ${F_{3n}=e_{2n}}$ . It is clear that we have ${\rho_F(E) = \frac{2}{3}}$ and ${\rho_F(O) = \frac{1}{3}}$ . Extending this idea, we follow each odd number ${o_n}$ in a set ${G}$ by ${k}$ even numbers, so that ${\rho_G(E) = {k}/{(k+1)}}$ and ${\rho_G(O) = {1}/{(k+1)}}$ . For large ${k}$ , ${\rho_G(E)\approx 1}$ and ${\rho_G(O)\approx 0}$ .

Almost all natural numbers are even

Proceeding further, we construct a set ${H}$ with one odd number, one even number followed by an odd one, then two evens followed by an odd one, then three evens and an odd one, and so on:

$\displaystyle H = \{o,\ e,o,\ e,e,o,\ e,e,e,o,\ e,e,e,e,o, \dots \} \,.$

It is clear that the ${n}$ -th odd number is at the position of the triangular number ${T_n = n(n+1)/2}$ , and the count of even numbers to that point is ${\kappa(T_n) = T_n-n = T_{n-1} = n(n-1)/2}$ . Thus, the density is

$\displaystyle \rho_H(E) = \lim_{n\rightarrow\infty}\ \frac {T_{n-1}}{T_{n}} = \lim_{n\rightarrow\infty}\ \frac {n(n-1)/2}{n(n+1)/2} = 1 \,.$

Thus, we find that “almost all the elements of ${H}$ are even”.

These examples make it clear that density depends strongly on the ordering of the reference set. Our intuition is guided by the usual (natural) ordering of the natural numbers and the alternation between odd and even numbers leads us to the conclusion that, somehow, they are equal in number, each comprising “half” of the set of natural numbers. Density relative to ${\mathbb{N}}$ is consistent with this intuition.

Sources

${\bullet}$ Tenenbaum, Gerard, 1995: Introduction to Analytic and Probabilistic Number Theory. Cambridge Studies in Advanced Mathematics, 46. Cambridge University Press.

ThatsMaths