Prove that 2-adic equivalence gives a partition of $\mathbb{N}$

Question

Let the collection be denoted by

$\{A_k: k \in\mathbb{N}\cup\{0\}\}$, where each set $A_k$ = $\{2^kn: n \in \mathbb{N}\: and\: n\: is\: odd\}$

To prove that none of the sets in the collection are the empty set (condition (i)), it's clear that $2^k$ is in every set $A_k$ by letting $n=1$.

Now I'm having trouble proving condition (ii) of a partition $\mathcal{P}$, which is that if $X \in\mathcal{P}$ and $Y\in\mathcal{P}$, then $ X = Y$ or $X \cap Y = \emptyset$.

After writing out the first few sets $A_k$ it's hard to determine whether condition (ii) is true at first glance,

$A_0 = \{1,3,5,7,9,11,13,...\}$

$A_1 = \{2,6,10,14,18,22,26,...\}$

$A_2 = \{4,12,20,28,36,44,52,...\}$

$A_3 = \{8,24,40,56,72,88,104,...\}$

and so on

My proof for condition (ii) currently,

Let $X_a, Y_b \in \mathcal{P}$

Suppose $X_a \neq\ Y_b$ and $X_a \cap Y_b \neq \emptyset$

Let $x \in X_a \cap Y_b$

$x = 2^an$ such that n is odd and $x = 2^am$ such that m is odd

$2^an = 2^bm$ if and only if $a = b$ and $n = m$ (where I think my proof is faulty since I'm not sure how to prove this)

In order for this to happen, $X_a$ must equal $Y_b$. This is a contradiction so either $X_a = Y_b$ or $X_a \cap Y_b = \emptyset$

And for proving the last condition (iii) of a partition $\mathcal{P}$, which is that the union of all the sets in the collection equals $\mathbb{N}$, I'm not sure whether to split the proof into evens and odds or to show that some arbitrary natural number, $m \in \mathbb{N}$ belongs to the union of all sets $A_k$. Which approach is more feasible? And am I on the right track to proving condition (ii)?

Answer 1

Given a number $n$ if it is odd it belongs to $A_0$. If not divide by 2, getting $n=2n_1$. If $n_1$ is odd then $n\in A_1$. If not repeat with $n_1$, divide it by 2. If $n_1=2n_2$ with $n_2$ odd, then $n=2^2n_2$, belongs to $A_2$, and so on. Keep dividing by 2 until you get an odd number if after $k$ divisions you got an ood number means $n=2^km$ with $m$ odd and belongs to$A_k$. Note that as each division by 2 yields a smaller number given any $n$ this process has to terminate with at most $n$ steps (in fact $\log_2 n$ steps, that is no important).

Another way of viewing this is: write the number in base 2. If the rightmost $k$ digits are $0$ then the number belongs to $A_k$.

Answer 2

For (ii): I see some typos but in general your solution is correct. And for the proof of $2^an=2^bm$ if and only if $a=b,m=n$, you can say that from Fundamental theorem of arithmetic, we follow $a=b,m=n$. It's pretty much obvious to imply $a=b,m=n$ right away without mentioning the theorem.

For (iii): Your second idea is the way to go: Prove that for any $m \in \mathbb{N}$ then $m \in A_i$ for some $i$. This is also obvious since we can represent $m=2^xy$ with odd $y$, which follow immediately $m \in A_x$.

This is also based on Fundamental theorem of arithmetic since there is only one way to represent $m$ as $2^xy$.

Note on Fundamental theorem of arithmetic: It basically says that all positive integers greater than $1$ factor uniquely into primes.