0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Whenever someone writes "it's clear," it usually means that there is a gap in the proof at that point... $\endgroup$ Oct 8, 2018 at 3:29
  • 1
    $\begingroup$ "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)\}$. $\endgroup$
    – JMoravitz
    Oct 8, 2018 at 3:46
  • 3
    $\begingroup$ 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|$. $\endgroup$
    – JMoravitz
    Oct 8, 2018 at 3:49
  • $\begingroup$ Thank you so much for pointing out my mistake @JMoravitz! Your approach is definitely better. $\endgroup$
    – Akira
    Oct 8, 2018 at 4:38
  • $\begingroup$ 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? $\endgroup$
    – Asaf Karagila
    Oct 8, 2018 at 9:45

2 Answers 2

1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ "Does my proof look fine or contain logical gaps and flaws?", how is your answer helpful, then? $\endgroup$
    – Asaf Karagila
    Oct 8, 2018 at 9:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .