Produce an infinite collection of sets $A_1, A_2, A_3,...$ with the property that

Question

Abbott's Understanding Analysis, Problem 1.2.4

Produce an infinite collection of sets $A_1, A_2, A_3,...$ with the property that every set $A_i$ in the collection:

(1) Contains an infinite number of elements,

(2) $$A_i \cap A_j = \emptyset, \quad \forall i \neq j,$$

and

(3) $$\cup_{i=1}^{\infty} A_i = \mathbb{N}.$$

I am unable to come up with a response. The property that $$\cup_{i=1}^{\infty} A_i = \mathbb{N}$$ implies that these sets can only contain elements of the natural numbers. However, it seems to me difficult to produce an infinite collection of sets that contain infinitely many natural numbers each and that are mutually disjoint.

Thank you, for your help. :)

Answer 1

You can give an example by diddling with prime factorizations, as suggested. Or do this: Start with $$\Bbb N=A_1\cup B_1,$$where $A_1$ and $B_1$ are infinite and disjoint. Now write $$B_1=A_2\cup B_2.$$Etc.

Edit: That gives us an infinite sequence of disjoint infinite sets $A_j$. It may not hold that $\Bbb N=\bigcup A_j$. But that's no problem: If $B=\Bbb N\setminus\bigcup A_j\ne\emptyset$ just let $A_1'=A_1\cup B$ and $A_j'=A_j$ for $j>1$.

(For example maybe $A_1$ is the odd integers and $B_1$ the even integers. Next split $B_1$ into the set of $2k$ with $k$ odd and the set of $2k$ with $K$ even... You end up with $A_n$ equal to the set of integers divisible by $2^{n-1}$ but not by $2^n$.)

Answer 2

For instance, you could let $A_i$ be the multiples of the $i$-th prime that contain none of the lower primes as factors. (You need to add $1$ to any one of these sets, since it occurs in none of them.)

Answer 3

Let $A_2$ be the even numbers, and for primes $p>2$ let $$A_p=\{n\in \mathbb{N} \;|\; n=kp \text{ for some natural number } k \text{ and } n\notin A_q \text{ for } q<p\}$$

Since the primes are countable this will give you your collection.

Answer 4

There's a really rich structure on $\mathbb{N}$ that comes from the Fundamental Theorem of Arithmetic. If we order the primes $p_1, p_2, p_3, \cdots$ we can set $P_i = \{p_i^{k_1}p_2^{k_2} \cdots p_i^{k_i} : k_i \neq 0\}$. Thus $P_1 = \{2,2^2,2^3, \cdots\}$, and $P_2$ contains $3,3^2,3^3, \cdots$ but also $2\cdot3,2\cdot3^2,2\cdot3^3, \cdots$, $2^2\cdot3,2^2\cdot3^2,2^2\cdot3^3, \cdots$, $2^3\cdot3,2^3\cdot3^2,2^3\cdot3^3,$ and so on. It is easy to show these are disjoint as each number only has one largest prime factor. Then you get to use FTA to show they cover $\mathbb{N}.$ You just need to pick a set to cram $1$ into and you'll be done.

Answer 5

Let $$A_1 = \{1, 2, 4, 6, 8, \ldots\}$$ $$A_2 = \{3,6,9,12, \ldots\} \setminus A_1$$ $$A_3 = \{5,10,15,20, \ldots\} \setminus (A_1\cup A_2)$$

In general $A_n = \{k \cdot p_n : k \in \mathbb{N}\} \setminus (A_1 \cup \cdots \cup A_{n-1})$ where $p_n$ is the $n$-th prime number.

The sets are pairwise disjoint by construction, and are infinite because

$$\{p_n, p_n^2, p_n^3, \ldots\}\subseteq A_n$$

Finally, $1 \in A_1$ and every $k \ge 2$ is in $A_n$ where $p_n$ is the smallest prime factor of $k$. Therefore

$$\bigcup_{n\in\mathbb{N}} A_n = \mathbb{N}$$