Let $X_1,X_2,\ldots$ be a collection of countable sets. Prove that $\bigcup_{n\in\mathbb N}X_n$ is countable. I'm a recent HS graduate, and this is my proof for this statement. It feels very informal and loosey goosey. What are your thoughts?
Here are some definitions I'm working from: (1) 2 sets X and Y have the same cardinality (Card(X)=Card(Y)) if there exists a bijection f: X --> Y; (2) Consider the set n = {1,2,3, $\cdots$, n} for any positive integer n. Then a set S is finite if card(S)=card(n) or card(S)=card($\emptyset$); and (3) A set S is countable if either S is finite or card($\mathbb N$)=card(S)
Q: Let $X_1,X_2,\ldots$ be a collection of countable sets. Prove that $\bigcup_{n\in\mathbb N}X_n$ is countable. A: I will show that $\bigcup_{n\in\mathbb N}X_n$ is either finite or $card(\mathbb N)=card(\bigcup_{n\in\mathbb N}X_n)$.
In the $card(\mathbb N)=card(\bigcup_{n\in\mathbb N}X_n)$ case, suppose that $x_{11}, x_{12}, \cdots$ denotes the first, second, and so on element in a countable set, $X_1$, and $x_{21}, x_{22} \cdots$ denotes the first, second, and so on element in a countable set, $X_2$. We can construct a grid of values such that $j$ denotes the $j$th element in the $i$th countable set. In short, $X_{ij}$ denotes the jth element in the ith countable set, assuming such an element exists.
[For some reason, my diagram isn't properly rendering, and so here's a link to the proof technique I'm using: https://i.stack.imgur.com/HLeM6.gif]
We construct a function $f : \mathbb N \to \bigcup_{n\in\mathbb N}X_n$ as follows: let $n=1$ and starting from the top left node, $x_{11}$, assign n to it, and then follow the arrows, incrementing $n$ by 1 and assigning that new $n$ to the next node. However, if a node appears more than once or there does not exist an element $X_{ij}$ at that node, skip it. In short, map 1 to $x_{11}$, 2 to $x_{12}$, 3 to $x_{21}$, and so on.
We know this function is injective because whenever $f(x_1) = f(x_2)$, $x_1=x_2$, since each element in the image is hit exactly once, by construction. This function is also surjective because each $X_{ij}$ in the codomain corresponds to an $n$ in the domain. Thus, $f$ is bijective, and we conclude that $\bigcup_{n\in\mathbb N}X_n$ is countable.
In the finite case, to show that $card(\bigcup_{n\in\mathbb N}X_n)=card(\{1,\cdots,n\})$ for a positive integer n, we construct a function $g : \bigcup_{n\in\mathbb N}X_n \mapsto \{1,\cdots,n\}$ in the same way as above, but switch the domain and codomain.
A: Since $X_k$ is countable, there is a surjection $b_k:\mathbb{N} \to X_k$.
Then $g(k,l) = b_k(l)$ is a surjection $g: \mathbb{N}^2 \to \cup_{n=1}^\infty X_n$.
Hence $| \mathbb{N}^2| \ge | \cup_{n=1}^\infty X_n|$.
