Proof verification: $P(\mathbb{Z}^+)$ is uncountable

70 Views Asked by At

I construct an injection from $(0,1) \setminus \mathbb{Q}$ to $P(\mathbb{Z}^+)$.
Here's basically how it works:
Take an irrational, say $$0.214560000012511...$$

Split it into strings of digits like this:
$$2|14|560|0000|12511|...$$

So each string is of different length and these strings make up the decimal part entirely. To turn these strings into a subset of the integers, concat $1$ at the beginning of each string: $$12|114|1560|10000|112511|...$$

We do that, since a string like $0000$ is not an integer. Anyway, we have converted an irrational in $(0,1)$ to a subset of the integers. Now if two irrationals in $(0,1)$ are not equal, then atleast one of these strings will be unequal, so the integers that they form will also be unequal; therefore the subsets will be unequal; so the map is injective.

Does that make sense?

Here is the proof:
Let $0.a_1a_2a_3\ldots$ be an irrational. Define the strings of digits:

$$A_1 = a_1,\\ A_2 = a_2a_3,\\ A_3 = a_4a_5a_6,\\ A_4 = a_7a_8a_9a_{10},\\ \cdots$$

So each $A_i$ is a sequence of $i$ digits in the decimal part of the irrational $0.a_1a_2a_3...$. Now, notice that an $A_i$ could be just a string of 0's. Therefore, let $A_i'$ be the integer formed by concatenating 1 at the end of $A_i$. For instance, if $A_3 = 000$ then $A_3' = 1000$. Then, $\{A_1',A_2',\ldots\}$ is a subset of the integers. This is our map: $0.a_1a_2a_3\ldots$ maps to $\{A_1',A_2',\ldots\}$.

To see that this is injective, let $0.a_1a_2a_3\ldots$ and $0.b_1b_2b_3\ldots$ be irrationals and suppose $\{A_1',A_2',\ldots\} = \{B_1',B_2',\ldots\}$. Now, for any $i$, $A_i'$ is the only integer in $\{A_1',A_2',\ldots\}$ with $i+1$ digits (plus 1 since we concatenate). Therefore, $A_i' = B_i'$. Then, by the definition of $A_i'$, clearly $A_i'=B_i'$ being the same integer implies that $A_i$ and $B_i$ are the same string of digits. That is, $A_i=B_i$ for all $i$. Since $\{A_i\}$ contains all decimals of the irrational $0.a_1a_2a_3\ldots$, we must have that $0.a_1a_2a_3\ldots$ and $0.b_1b_2b_3\ldots$ are the same irrational number; hence the map is injective.