1
$\begingroup$

Definition: A set A is countable if there exists a bijection $f:\mathbb{N}\rightarrow A$. NOTE: According to the definition i'm using, countable = countably infinite.

Definition: A set is at most countable if it is finite or countable.

Let $(A_i)_i$ be a countable family of finite sets such that the family contains non-empty terms. Then $\bigcup_{n \in \mathbb{N}}A_n$ is countable.

My proof: As $(A_i)_i$ is a family of countable sets, we may enumerate the family as a sequence ($A_1,A_2,A_3....$) such that each term is distinct. Let $A_1$ $=(a_{11},a_{21},a_{31}…,a_{n1})$. So for an arbitrary j, we may enumerate the elements of $A_j$ as $(a_{1j},a_{2j}…,a_{m_{j}j})$. How should I enumerate the union?

$\endgroup$
  • 1
    $\begingroup$ Just an FYI: The way you define countable is usually known as countably infinite. The standard definition of countable is what you call at most countable: i.e., there exists an injection from set $A\to\mathbb N$. $\endgroup$ – Don Thousand Oct 25 '19 at 16:19
  • $\begingroup$ The proof is on the right track, I just think it's a bit too handwavy at points. $\endgroup$ – Don Thousand Oct 25 '19 at 16:21
  • $\begingroup$ @DonThousand may you please elaborate? $\endgroup$ – orientablesurface Oct 25 '19 at 16:22
  • $\begingroup$ 'As each $𝐴_i$ is distinct, we will be left with infinitely many distinct elements and therefore the union is countable." - too vague $\endgroup$ – Don Thousand Oct 25 '19 at 16:22
  • $\begingroup$ @DonThousan $A_i\neq A_j$ for $i\neq j$ and we have countably infinite of them. How should I make this more clear? $\endgroup$ – orientablesurface Oct 25 '19 at 16:23
0
$\begingroup$

With these definitions, the assertion is false as stated: just let $A_n=\emptyset$ for all $n$. Or, more generally, fix a finite set $U$ and choose every $A_n$ to be a subset of $U$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok. Suppose $A_n$ is non-empty. If U is finite, then it has finite many subsets. I'm assuming that each subset is distinct and that I have countably infinite of them. $\endgroup$ – orientablesurface Oct 25 '19 at 16:33
  • 1
    $\begingroup$ That clarification makes the assertion both true and interesting. I recommend that you edit the original post to make the statement clear. By the way, you've pretty much just outlined a proof (by contradiction) of the statement! $\endgroup$ – Greg Martin Oct 25 '19 at 16:34
  • $\begingroup$ i'm really not sure what to do next. $\endgroup$ – orientablesurface Oct 25 '19 at 16:39
  • $\begingroup$ @topologicalmagician Next, follow Greg Martin's advice and edit your question to make it clear that the $A_n$ are supposed to be distinct. $\endgroup$ – Mirko Oct 26 '19 at 1:43
0
$\begingroup$

Prove the contrapositive (or arrive at a contradiction) using the pigeon-hole principle.

It should be clear the $U=\bigcup_{n \in \mathbb{N}}A_n$ is "at most countable", i.e. it is either finite or countable (=countably infinite). You want to rule out the possibility that $U$ is finite. Clearly $A_n\subseteq U$ for every $n$. If $U$ were finite then its power-set $\mathcal P(U):=\{V:V\subseteq U\}$ would also be finite. (This just says that $2^n$ is a natural number whenever $n$ is.) But every $A_n$ is an element of $\mathcal P(U)$, and we cannot have infinitely many distinct elements in a finite set.

| cite | improve this answer | |
$\endgroup$

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.