0
$\begingroup$

Prove that the set $A=\{S:S\subseteq \mathbb N,|S|\le 1\}$ is countable.

Hello everyone. I understand that this set is countable because it is equinumerous to $\mathbb{N}$. But I am not sure how to write a formal proof for this.

$\endgroup$
3
  • $\begingroup$ That is a finite set???? $\endgroup$ – Prince M May 29 '20 at 0:10
  • $\begingroup$ Let $n \in \mathbb{N}$, then $S_n = \{n\} \in A$, thus $A$ is not a finite set because |$A$| $\geq$ |$S$| $\endgroup$ – Prince M May 29 '20 at 0:11
  • $\begingroup$ The first thing I would do would be describe $S$ better. $\endgroup$ – gen-ℤ ready to perish May 29 '20 at 0:39
5
$\begingroup$

Since $S\subset\Bbb N$ and $|S|\le1$, you get that either $S=\emptyset$ or $S=\{k\},k\in\Bbb N$.

Thus $$ A=\{\emptyset,\{k\}\;:\;k\in\Bbb N\} $$ which is clearly countable (and NOT FINITE!!), since its elements are in bijection with elements of $\Bbb N$.

$\endgroup$
1
  • $\begingroup$ Thank you. I realize that it is not finite. I got a little confused. $\endgroup$ – James Anderson May 29 '20 at 0:16
2
$\begingroup$

No, it is not a finite set! $A$ is the collection of all sets that either have $0$ elements, or only have $1$ element. So $A$ consists of the emptyset $\varnothing$ and all singletons $\{n\}$, $n\in\mathbb{N}$, i.e. $$A=\{\varnothing\}\cup\{\{n\}: n\in\mathbb{N}\} $$ You can count $A$, the first element is $\varnothing$, the second is $\{1\}$ the third is $\{2\}$ and so on. I believe you can write this enumeration explicitly by yourself!

$\endgroup$
1
  • $\begingroup$ Oops. I got the definitions mixed up somehow. I fixed it. Thanks for pointing that out. $\endgroup$ – James Anderson May 29 '20 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.