Prove $\cup_{i=1}^\infty A_i = \mathbb{N}$ where $A_i = 2^{i-1}\{1,3,5,7,...\}$

Question

To show the equality we need to show that i) $\cup_{i=1}^\infty A_i \subseteq \mathbb{N}$ and ii) $\mathbb{N} \subseteq \cup_{i=1}^\infty A_i$.

i) $\cup_{i=1}^\infty A_i \subseteq \mathbb{N}$:    This is straight forward to prove.

ii) $\mathbb{N} \subseteq \cup_{i=1}^\infty A_i$:     if $x\in \mathbb{N}$ then $x$ is either odd or even:

       ii_1) if $x$ is odd then $x \in A_1$ $\rightarrow$ $x \in \cup_{i=1}^\infty A_i$

       ii_2) if $x$ is even then $x$ is either a power of 2 or not.:

                ii_2_1) if x is power of 2 then $\exists j \in \mathbb{N}$ s.t $x =2^j$ and hence $x \in A_{j+1}$ $\rightarrow$ $x \in \cup_{i=1}^\infty A_i$

                ii_2_2) if x is not a power of 2 then $\exists l \in \mathbb{N}, k \in A_1$ s.t $x =2^lk$ and hence $x \in A_{l+1}$ $\rightarrow$ $x \in \cup_{i=1}^\infty A_i$

Hence, given ii_1, ii_2_1, and ii_2_2, $\mathbb{N} \subseteq \cup_{i=1}^\infty A_i$.

I have the following questions:

1. This proof looks like a nested if statements in programming. Is this a correct proof technique? and if it is does it have a name?

2. Is there an alternative proof for this problem?

Answer 1

Your proof makes the clumsiness (it is not really an error) of separating out special cases that are also covered by the general case; this makes the proof needlessly long. What you need to prove is that every positive integer (you must belong to those who do not believe $0\in\Bbb N$, which is wrong by the way) can be written as a product of a power of $2$ and an odd positive integer. The power of $2$ can be $2^0=1$ and the odd number can be $1$ as well, so there is no need to put these aside. The property is immediate if you know about unique factorisation of positive integers, since you put any and all factors $2$ into the power of $2$, and all remaining prime factors are odd, so multiplying those gives the odd factor. A product of no (prime) numbers at all is defined to be $1$ (as it must).

By the way you do not actually need prime factorization here. If as long as a positive number is even you repeat dividing it by $2$ you eventually (and possibly already after $0$ divisions) you end up with an odd number, and this gives you the decomposition of your original number as a power of $2$ times an odd number. (Formally, the proof would be by induction.)

It is very convenient to not just give $0$ the membership card of the natural numbers, but also realise the reason this membership is deserved: it is a valid possibility to be dealt with when counting elements, terms, factors or iterations.

Answer 2

Your approach can be considered an example of proof by cases. But I think you can combine your cases:

Note we essentially want to show that every positive integer is the product of $2^{k_1}$ and a positive odd integer, for $k_1\in \mathbb{Z}_{\geq 0}$. This follows from the fundamental theorem of arithmetic since any positive integer $n>1$ is represented by a unique prime factorization:

$$n=2^{k_1}\underbrace{3^{k_2}5^{k_3}7^{k_4}...}_{\text{positive odd integer}}$$

Answer 3

Take the set of (non-zero) natural numbers $\mathbb{N}=\{1, 2, 3, 4, 5, \cdots\},$ and define a relation on it by $a\sim b$ if and only if the prime factorization of both numbers has the same power of $2.$

This is equivalence relation, and let's name the equivalence classes as $A_1, A_2, \cdots,$ where $a\in A_{i+1}$ if $i$ is the maximum power of $2$ that divides $a.$ So,

• $A_1=\{1, 3, 5, 7, \cdots\}$
• $A_2=\{2, 6, 10, 14, \cdots\}$
• $A_3=\{4, 12, 20, 28, \cdots\}$
• $\cdots$

By the Fundamental Theorem on Equivalence Relations,
$A_i\cap A_j=\emptyset$ for $i\neq j,$ and $$\bigcup_{i\in\mathbb{N}}A_i=\mathbb{N}.$$