Multiplying each element in the set of odd integers by $\{2^0,2^1,2^2,\dots\}$

Question

How can I prove that the sets created by doubling each element from the set of odd integers to infinity contain no duplicate numbers in any of the sets created by doubling the odd integers?

Set of odd integers $\ge 1: \{1,3,5,7,9,11,\dots\}$

Doubling $ \{1, 2, 4, 8, 16, 32,\dots \}$

Doubling $3: \{3, 6, 12, 24, 48,\dots\}$

Doubling $5: \{5, 10, 20, 40, 80,\dots \}$

Doubling $7: \{7, 14, 28, 56, 112,\dots\}$

How can I prove that there will be no duplicate elements in the sets created from the doubled odd integers?

Answer 1

It appears that you are not "doubling each element from the set of odd integers" at all. That set would be $$\{\dots,2(-3),2(-1),2(1),2(3),\dots\}=\{4k+2:k\in\Bbb Z\}.$$

Rather, you are taking odd multiples of the set of all non-negative integer powers of $2.$

If you're trying to ask whether the sets thus generated are disjoint, then you'll use uniqueness of prime factorization to prove it.

Answer 2

Consider the function $R:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$ defined as $R(p,q) = (2p+1) 2^q$. Then, for a given $p$, $S_p = R(p,\mathbb{N}) = \{x \in \mathbb{N} \ | \ x = (2p+1)2^q \text{ for some } q\in\mathbb{N}\}$ is an indexed family of sets which corresponds with your given sets. Your question is then asking whether it is true that $S_{p_1} \cap S_{p_2} = \emptyset$ for all $p_1\neq p_2\in\mathbb{N}$.

To show this, we take arbitrary pair of sets with indices $p_1,p_2$ (WLOG assume that $p_1 > p_2$), and from each set take some element with index $q_1,q_2$ respectively. Then, if the claim is false, there will be a pair of choices for $q_1,q_2$ such that $R(p_1,q_1) = (2p_1+1)2^{q_1} = (2p_2+1)2^{q_2} = R(p_2,q_2)$, or equivalently, $\frac{R(p_1,q_1)}{R(p_2,q_2)} = \frac{2p_1+1}{2p_2+1}2^{q_1-q_2} = 1$.

If $q_1 = q_2$, then $2p_1 + 1 = 2p_2 + 1 \Rightarrow p_1 = p_2$, a contradition.

If $q_1 > q_2$, $2^{q_2-q_1} > 1$ and since $p_1>p_2$, $\frac{2p_1+1}{2p_2+1} > 1$, so $\frac{R(p_1,q_1)}{R(p_2,q_2)} = \frac{2p_1+1}{2p_2+1}2^{q_1-q_2} > 1$.

If $q_1<q_2$, then let $q_2-q_1 = d\in\mathbb{N}$. We can then write $2^{q_1-q_2} = \frac{1}{2^d}$. The Fundamental Theorem of Arithmetic states that each number $2\leq k \in \mathbb{N}$ has a unique factorization in primes given by $\prod_{i=1}^n \pi_i^{\alpha_i}$, where $\pi_i$ are primes and $1\leq\alpha_i \in \mathbb{N}$. Further, if $k$ is odd, then each $\pi_i$ is odd as well, i.e. $\pi_i \neq 2$ for any $i$.Let $k_1 = 2p_1+1$ and $k_2 = 2p_2+1$. In order to satisfy the original equality, we need $k_1 = 2^d k_2 = k_3$. Since $k_2\geq 1$ and $2^d \geq 2$ are natural numbers, $k_3 \geq 2$ is a natural number with a factor of $2$. Since $k_1 = k_3$, that means $k_1$ must also have a factor of $2$ (since the prime factorization is unique) which is a contradiction since $k_1$ is odd.

Since, for any $p_1,p_2$, there is no choice $q_1,q_2$ such that $R(p_1,q_1) = R(p_2,q_2)$, we must have that $S_{p_1} \cap S_{p_2} = \emptyset$.