# Comparing density of countable infinite sets by examining the association

The two questions that i am asking are in bold.

To be clear, i am talking about whole number here.

Having seen 3 is everywhere by Numberphile that shows that almost 100% of the whole the numbers have the digit three in them, i have been thinking of approaching the same problem from the different perspective:

We have the following method of generating numbers with 3:

Take any whole number without digit 3, add 3 to the left of it, and then keep adding whatever digits to the left of that 3 for as long as you want.

What this tells me is that i can generate infinite amount of numbers with 3 for each one number without 3. I can then trivially show that each infinite set of numbers with 3 was not double-counted (i.e. any 3 possessing number could have been generated for just 1 number without 3).

For me, this means the the question can then be restated as:

If you have an infinite set and a single number, and you randomly select a single number out of the superset, what are the chances of getting a single number?

However, i've been pointed out that because we are talking about sets both of which are infinite, then we have to take into account that you can divide the set of numbers without 3 into infinitely many subsets, each of which is infinite (which i cannot dispute). And thus there maybe a way to write my generation method in reverse, and if so, then the argument is internally contradictory.

The question then becomes: Is there anything preventing us from generating sets with numbers that have no digit 3, in such a way that each set is infinite, each of these sets can be associated with some number that has the digit 3, and no number without 3 is associated to more than one number that has 3?

Here is how i have attempted to reason about this question, but i maybe missing something.

1. The superset of numbers with 3 and the numbers without 3 is the set of all the whole numbers.
2. It has already been shown that numbers with 3 have some specific way to be associated with numbers without 3. Thus we can write each number with 3 as TyT₄T₃T₂3Nx…N₄N₃N₂N₁N₀ where N are digits that cannot be 3 and T are digits that can be 3.
3. Even with some other form of generating numbers in reverse, it must be possible to represent them this way.
4. If we allow infinite sets of numbers without 3 to be generated for each of the numbers with 3, then our x must go to infinity at some point.
5. But that would mean that we must allow to position at least one digit 3 past infinity, which is nonsense.

The second question then becomes: What is nonsense? My logic or the possibility of generating infinite number of infinite sets without number 3 for each number with 3 without double counting?

• You first say "line of numbers" which means "the real numbers" but then you talk about the natural numbers. So it's not clear to me what do you mean. Are you talking about real numbers or integers or natural numbers? – Asaf Karagila Aug 1 '14 at 12:47
• Whole numbers only. I never said "line of numbers" but i have edited to state it from the get-go. – v010dya Aug 1 '14 at 12:50
• If you have an infinite number of something, you can easily generate an infinite number of infinite sets of those things. It doesn't show you anything new... – Thomas Andrews Aug 1 '14 at 13:36
• One thing you'll find is that "picking a random whole number" is actually an impossibility, if you want each whole number to have equal probability. This is why density is defined as a limit, as $N\to\infty$ of picking randomly from $1,2,\dots,N$. – Thomas Andrews Aug 1 '14 at 13:40
• It's unclear what you are trying to do. Are you trying to find a flaw in the argument in the video? A lot of your terminology is imprecise. "... the question can then be restated as ..." Which question? – Thomas Andrews Aug 1 '14 at 13:52

## 1 Answer

The problem with your reasoning is that you can apply it to any infinite set with infinite complement.

Let's do it with the set of odd numbers.

For any odd number, $n$, consider the set:

$$\{n,2n,4n,\dots,2^kn,\dots\}$$

By your argument, then, I can "pick a random whole number" by first picking one of these sets at random, and then picking randomly from the set. You'd get an odd number with probability zero, and thus the density of the odd numbers is zero.

More generally, let $X$ be the any infinite set of natural numbers so that $Y=\mathbb N\setminus X$ is also infinite. Write $X=\{x_1<x_2<\dots<x_n<\dots\}$ and $Y=\{y_1<y_2<\dots<y_n<\dots\}$.

Then we can get an infinite set of sets $$X_n = \left\{x_n,y_{2n-1},y_{2(2n-1)},\dots,y_{2^k(2n-1)},\dots\right\}$$

It's easy to show that $\bigcup_{n=1}^\infty X_n = X\cup Y=\mathbb N$, and each $y_N$ occurs in exactly one $X_n$. Given $y_N$, $N$ can be written uniquely as $2^kn_0$ where $n_0$ is odd, and then $y_N\in X_{\frac{n_0+1}{2}}$ and no other $X_i$.

So your argument would say that any infinite set with infinite complement has density zero.

In particular, this argument would mean that the set of whole numbers with $3$ in the digits is also density zero.

The intuitive error in your argument is that you can pick a random number from an infinite set with equal probability. That turns out to be impossible.

This is why we define the density of a set of whole numbers as a limit. That is, if $X$ is a set, then define $p_n(X)$ as the probability, when picking a random whole number from $1$ to $n$ that the number chosen is in $X$. Then we define the "density of $X$" as the limit:

$$d(X)=\lim_{n\to\infty} p_n(X)$$

when that limit exists. This measure is not really a "probability," but a limit. There is no nice way to express this value rigorously as a probability. Intuitively it is like a probability, but it is risky to treat it as one.

• Thanks a lot. This answers the question very well. – v010dya Aug 1 '14 at 17:53