0

I have a set $A_n$ = $ \{2^i(2n-1): i \in \mathbb{N} \cup {0} \}$

It is said that the set $P = $ $\{A1, A2, A3,...\}$ partitions the natural numbers.

I am attempting to solve this by the definition of a partition, I can see that no $An = \emptyset$, but I can't see how the union of all the $An$'s would give $\mathbb{N}$ can anyone help?

Asaf Karagila
  • 393,674

2 Answers2

1

A good way to get some intuition is to take some numbers and see which set they belong to. For example, $12=2^2\cdot 3 \in A_3$ You divide out all the factors of $2$ and are left with an odd number $N$. You let $N=2n-1, n=\frac 12(N+1)$ and that is the set $A_n$ it belongs to.

Ross Millikan
  • 374,822
1

Consider $A_1$. This is the set $\{2^i\}$, which contains the elements $1,2,4,8,16,\cdots$. Now consider $A_2$, which is $2^i\times3$ which contains the elements $3,6,12,24,\cdots$. Do something similar for $A_4$ and so on. You should see that the least element of $A_{k}$ is always the $k$th odd number, which is $2k-1$ , and so you can generate every odd element of $\mathbb{N}$ in such a way. By the definition of the set, we can multiply every element by $2$, which makes every even number. Now you need only formalise this proof.

  • Could you clarify what you mean by the statement you've made on the 3rd line and how that shows I can generate every natural number. –  Feb 05 '21 at 16:20
  • Hi, so what I was saying is that for the set $A_n$, the elements are $2^i(2n-1)$. For $n=2$ we have elements of $2^i\times{3}$ as $I$ ranges over the non-negative integers. Substitute in $i=0,1,2,\cdots$. This generates the terms $3,6,12,24,\cdots$. For $A_4$ we have $2^i\times{5}$, so we get $5,10,20,\cdots$. As such we will get every odd number as the minimum element of $A_k$. As such we will get every even number as their sum, which is contained in the union - we have every odd number, and we can multiply each by any power of $2$, so all the naturals are achieved. –  Feb 05 '21 at 16:39
  • Thank you for clearing that up for me, that makes more sense now. So is it just a fact that we can generate any even natural number by multiplying a particualr odd natural number by a particular power of 2? –  Feb 05 '21 at 16:44
  • Yes, so long as your statement is refined. Since we generate every odd number, without loss of generality including some odd number $n$, we also get $2n,4n,\cdots$ and by varying $n$ we get every even number as well. A good way to think about this is the integers on a number line - how do we get 28, for example? It would be $28\rightarrow 14\rightarrow 7\rightarrow 2(3)+1$. Does this make sense? –  Feb 05 '21 at 17:51