How to prove that a collection of pairwise disjoint subsets of natural number has to be finite or countable I think if I could assume there exists an infinite and uncountable family of sets then prove its a contradiction, this question could be solved. But don't know how to do it. Many thanks.
 A: We can prove it in the following way using a property of the integers called the Well Ordering Principle. If you're not familiar, it states

Every set of positive integers has a least element.

Hopefully this is somewhat intuitive! Now, let's start by letting $\mathcal{C}\subseteq\mathcal{P}(\mathbb{N})$ be our collection of subsets, such that for any $A,B\in\mathcal{C}$, it follows that $A\cap B=\emptyset$. Now, consider two arbitrary sets $A,B\in\mathcal{C}$, and by applying the W.O.P., let $a$ and $b$ be the least elements of these sets, respectively. Since $A\cap B=\emptyset$, we know that $a\ne b$. Hence, we have the following function:
$$\phi:\mathcal{C}\to\mathbb{N}\text{ defined by  }A\mapsto a$$
This a function that maps sets in $\mathcal{C}$ to $\mathbb{N}$ by identifying a set's least element. To show that $\mathcal{C}$ is either finite or countable, we only have to show that $\phi$ is injective. 
To that end, suppose that $\phi(A)=\phi(B)$ for sets $A,B\in\mathcal{C}$. Then this implies that $a=b$, where $a$ and $b$ are the least elements of $A$ and $B$. However, this implies that $A=B$ since no two sets have the same least element. Therefore, $\phi$ is injective, and we're done. 
As an exercise, you should explain to yourself why the injectivity of $\phi$ gives us our result.
A: Any such collection of subsets is in bijective correspondence with the subset of natural numbers consisting of the smallest element of each of them (unless it includes the empty set, but the modification for this case, while a bit of a pain, is not hard).
