4

I am having trouble showing that this is a partition:

$\{A_k|k\in \mathbb N \cup \{0\}\}$ where each $A_k=\{2^kn | n \in \mathbb N \text{ and n - odd}\}$ is a partition of the natural numbers.

I understand I need to use the definition of partition but I am not to sure how to apply this. For the first part of the definition I think I need to say something like X in Ak. I want to solve it using the three part of the definition of partitions as this is how I will understand it

I asked my professor for help and she said to start with X=Ak for some vale of k and to go from there.

Martin Sleziak
  • 53,687
Sam
  • 1,088

1 Answers1

4

Start by showing that $\forall A_k \ne \varnothing $, which is true because $2^k\cdot 1 \in A_k$.

Then show that $A_k \cap A_t = \varnothing$ for $k \ne t$, which again is true, otherwise if we suppose $\exists m \in A_k \cap A_t$ then $m=2^k\cdot m_k$ and $m=2^t\cdot m_t$. Given $k \ne t$ then $2^k \ne 2^t$ and we obtain that one of the $m_k$ or $m_t$ is even, which is a contradiction.

Then, the remaining part is to show that $\forall n \in \mathbb{N}, \exists k: n \in A_k$. If $n$ is odd then $n \in A_0$. If $n$ is even, then the fundamental theorem of arithmetic says $n=2^{k}\cdot p_{i_1}^{\alpha_1}\cdot p_{i_2}^{\alpha_2}...\cdot p_{i_l}^{\alpha_l}$, $p_{i_j}$-odd prime $\forall j=\overline{1,l}$, thus $n \in A_{k}$.

rtybase
  • 16,907
  • Sorry, but why did you write $2^k\cdot p_{i_1}^{\alpha_1}\cdot ...\cdot p_{i_t}^{\alpha_t}$ instead $2^k\cdot p_1^{\alpha_1}\cdot ... \cdot p_t^{\alpha_t}$ ?I mean, why $p_{i_j}$ if $p_j$ would be ok? – Rodrigo Dias Nov 04 '16 at 01:19
  • $p_1,p_2,p_3,...$ can be interpreted as members of the primes set in exactly that order, i.e. $p_1=2,p_2=3,p_3=5,p_4=7,...$ I tried to avoid this confusion. – rtybase Nov 04 '16 at 01:28
  • @rtybase but why would I need some other variable t to prove this? – Sam Nov 04 '16 at 02:11
  • I do not understand it this way. I get it by proving each of the three parts of a partition – Sam Nov 04 '16 at 03:00
  • @Sam, $t$ is another arbitrary element. Which part you don't understand? – rtybase Nov 04 '16 at 06:49
  • @rtybase This doesn't make sense to me but I asked my professor for help as well and she said to start with X=Ak for some k to show its non empty and to go from there. So I didn't this step but then I am not sure if I need to go further. – Sam Nov 04 '16 at 23:05
  • @Sam the definition is formed of 3 parts, https://en.wikipedia.org/wiki/Partition_of_a_set, so is my proof. 1st part shows that any $A_k$ is non empty, so the partition doesn't include the empty set. 2nd part shows that two distinct sets of the partition has no common elements, I used proof by contradiction in this case. 3rd part is equivalent to $\bigcup_{k} A_k = \mathbb{N}$ – rtybase Nov 04 '16 at 23:57
  • @rtybase yes I understand the steps now I am only confused on the last Union part because I haven't used than theorem in my class. Can't we use the definition of Union over to prove this instead? – Sam Nov 06 '16 at 16:06
  • The last one relies on the definition of the sets equality, i.e. $A = B \Leftrightarrow A \subset B$ and $B \subset A$. We took an arbitrary $n \in \mathbb{N}$ and found an $A_k$ such that $n \in A_k$. This is equivalent to $\mathbb{N} \subset \bigcup_{k} A_k$. The $\bigcup_{k} A_k \subset \mathbb{N}$ part is obvious, because any element of any $A_k$ is a natural number. – rtybase Nov 06 '16 at 16:59
  • Union of sets is a set. And we take an arbitrary element of the union of the sets, which according to part 2, belongs (the element) to only one of the $A_k$. So it's $n \in A_k$ - element of a set. – rtybase Nov 06 '16 at 19:23
  • To prove UAk= natural numbers we have to prove UAk is a subset of N and the other way around right? – Sam Nov 06 '16 at 19:25
  • We have to prove $\bigcup_{k} A_k \subset \mathbb{N}$ and $\mathbb{N} \subset \bigcup_{k} A_k$. The latter I already proved in my answer by taking an arbitrary $n \in \mathbb{N}$ and showing that it belongs to a $A_k$, thus it belongs to $\bigcup_{k} A_k$ too. – rtybase Nov 06 '16 at 19:29
  • Let us continue this discussion in chat. – Sam Nov 06 '16 at 19:37