Proof of countable family of finite sets

Question

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?

Answer 1

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.

Edit. Just trying to comment on your question as to how to enumerate the union, starting with your suggestion that $A_j=(a_{1j},a_{2j}…,a_{m_j j})$. You could make the additional assumption that for each $j$ there is $k_j$ with $0\le k_j\le m_j$ such that if $n\le k_j$ then $a_{n,j}$ does not belong to any $A_i$ with $i<j$, and on the other hand if $k_j<n\le m_j$ then $a_{n,j}$ belongs to at least one $A_i$ with $i<j$.

Just to clarify this notation, if $k_j=m_j$ then all elements of $A_j$ are "new", i.e they do not appear in any "earlier" $A_i$'s (with $i<j$). On the other hand, if $k_j=0$ then none of the elements of $A_j$ is "new", i.e each element of $A_j$ is already an element of $A_i$'s for some $i<j$ (where $i$ need not be unique and may depend on the particular element of $A_j$).

Since the family $(A_i)_i$ is countably infinite, there are infinitely many $j$ with $k_j\ge1$. (Hint for this part. If there were a largest $j$ with $k_j\ge1$ then let $B=\bigcup_{i\le j}A_i$. Then $B$ is finite and hence has only finitely many subsets, but on the other hand every $A_i$ with $i>j$ is one of these finitely many sets, a contradiction.)

Let $J=\{j:k_j\ge1\}=\{j_1,j_2,j_3,...\}$ where $j_1<j_2<j_3<...$
Then $\bigcup_{n \in \mathbb{N}}A_n$ can be listed as
$(a_{1j_1},…,a_{k_{j_1} j_1},a_{1j_2},…,a_{k_{j_2} j_2},a_{1j_3},…,a_{k_{j_3} j_3},…)$

Answer 2

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