# Suppose that $B$ is a disjoint set of subsets of $\Bbb N$: if $A,A' \in B$ and $A \neq A'$, then $A \cap A' = \emptyset$. Show that B is countable

Suppose that $$B$$ is a disjoint set of subsets of $$\Bbb N$$: if $$A,A' \in B$$ and $$A \neq A'$$, then $$A \cap A' = \emptyset$$. Show that B is countable.

Does my proof look fine or contain logical gaps and flaws? Thank you so much for your verification!

My attempt:

Lemma: Let $$\mathfrak P$$ be a partition of $$\Bbb N$$. Then $$\mathfrak P$$ is countable.

Proof

If not, then $$\mathfrak P$$ is uncountable. It's clear that $$\{\min X\mid X\in \mathfrak P\}$$ and $$\mathfrak P$$ are equinumerous. Thus $$\{\min X\mid X\in \mathfrak P\}$$ is uncountable. On the other hand, $$\{\min X\mid X\in \mathfrak P\}\subseteq \Bbb N$$, then $$\{\min X\mid X\in \mathfrak P\}$$ is countable. This leads to a contradiction. Hence $$\mathfrak P$$ is countable.

We proceed to prove our main theorem.

It's clear that $$B\subseteq \mathfrak P$$ and $$\mathfrak P$$ is countable by Lemma. Then $$B$$ is countable. This completes the proof.

• Whenever someone writes "it's clear," it usually means that there is a gap in the proof at that point... Oct 8, 2018 at 3:29
• "It's clear that $B\subseteq \mathfrak{B}$." Not necessarily. For trivial example, let $B=\{\{1\},\{2\}\}$ and let $\mathfrak{B}=\{\Bbb N\}$. You introduced $\mathfrak{B}$ as simply being some arbitrary partition of $\Bbb N$ and did not bother relating it to $B$ in any way at the time of it's introduction. You could have instead constructed $\mathfrak{B}$ using $B$ instead by letting $\mathfrak{B} = B\cup \{\Bbb N\setminus (\bigcup B)\}$. Oct 8, 2018 at 3:46
• It would be clearer in my opinion to show $f~:~B\to \Bbb N$ given by $f(A)=\min(A)$ is an injection, which by theorem implies $|B|\leq |\Bbb N|$. Oct 8, 2018 at 3:49
• Thank you so much for pointing out my mistake @JMoravitz! Your approach is definitely better. Oct 8, 2018 at 4:38
• Let me add that you're not using any contradictions there. It's a direct proof. Why do you need to assume that your family is uncountable, then? Oct 8, 2018 at 9:45

From the statement I deduce that you're using countable in the sense of

either finite or equinumerous with $$\mathbb{N}$$

In this case, the statement that a partition of $$\mathbb{N}$$ is countable is correct. If $$\mathfrak{B}$$ is a partition of $$\mathbb{N}$$, then you can define $$f\colon\mathfrak{B}\to\mathbb{N} \qquad f(A)=\min A$$ which is an injective map. This is what you did.

There is a small detail: a partition, by definition, doesn't contain the empty set, but your set $$B$$ might.

Moreover you are failing to produce a suitable partition which $$B$$ is a subset of.

Let's call quasipartition of $$X$$ a set $$\mathfrak{B}$$ of subsets of $$X$$ such that $$\mathfrak{B}\setminus\{\emptyset\}$$ is a partition of $$X$$. Then every quasipartition of $$\mathbb{N}$$ is countable, because adding one element to a countable set produces a countable set.

Now consider your set $$B$$. If $$B_0=\bigcup_{A\in B}A$$, then $$\mathfrak{B}=B\cup\{\mathbb{N}\setminus B_0\}$$ is a quasipartition of $$\mathbb{N}$$ (prove it).

Each set of B, discarding a possible empty set, has at least one point. As the sets of B are pairwise disjoint, |B| <= |$$\cup$$B| <= |N|. Thus B is countable.

• "Does my proof look fine or contain logical gaps and flaws?", how is your answer helpful, then? Oct 8, 2018 at 9:45