# Prove there exists a countably infinite subset $A$ of $P(\mathbb{N})$ that satisfies given conditions [duplicate]

Prove that there exists a countably infinite set $A \subseteq$ $P(\mathbb{N})$ that satisfies all of the following conditions:

$i)$ $X \cap Y = \emptyset$ for all $X, Y \in A$ such that $X \neq Y$
$ii)$ $\mathbb{N} = \bigcup A$
$iii)$ Every element in $A$ is countably infinite

For all the sets I tried, the three conditions were satisfied but $A$ was not countably infinite, so now I'm stuck. Any help would be greatly appreciated.

## marked as duplicate by Hanul Jeon, Asaf Karagila♦, David, Claude Leibovici, mauMay 8 '14 at 8:05

• If $A$ was not countably infinite, condition ii) would fail. – Umberto P. May 8 '14 at 4:26
• What do you know about partitions? – Asaf Karagila May 8 '14 at 4:27
• A simple example is $A=\{A_0,A_1,A_2,\ldots\}$, where $A_i$ is the set of natural numbers divisible by $2^i$ but not $2^{i+1}$. – mjqxxxx May 8 '14 at 4:29
• I'd suggest looking at sets made up of multiples of primes that are not divisible by the primes before. $A_2={1,2,4,6,...}, A_3={3,9,15,21,...}$. And so on. – Steven F May 8 '14 at 4:32
• @UmbertoP. It could be that ii) holds and i) fails. – bof May 8 '14 at 4:38

Define the set $$A_1=\{1\}\cup\{n\in\mathbb{N}:n\;\mathrm{is\; product\; of\; two\; or \; more\; distinct \; primes}\}$$ And for each prime number $p$, let $A_p\{p^n:n\in\mathbb{N}$. Finally, let $A$ be the collection of this sets. It is not hard to see that this $A$ is the desires partition of $\mathbb{N}$.

Let $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ be a bijection.

Define

$$A_n=\{ f(n,m) | m \in \mathbb{N} \} \,.$$

Let each set contain integers that are the product of $k$ primes. Add the value 0 and 1 into the first set.

It is obvious that all the conditions are satisfied.

• Except $0$ and $1$ are in their own classes. :-) – Asaf Karagila May 8 '14 at 5:56
• @asaf lol thanks. – Calvin Lin May 8 '14 at 12:48