Note:
In the following I will denote:
The set of natural numbers by $\mathbb{N}=\{1,2,3...\}$
And the set of nonegative integers by $\mathbb{N}_0=\mathbb{N}\cup\{0\}=\{0,1,2,3,...\}$
Let $X$ be some general finite set, (I.e. $|X|\in \mathbb{N}_0$, The cardinallity of $X$ is a nonegative integer).
Prove that, for any infinte sequence of subsets of $X$, $\{A_n\subseteq X\}_{n=1}^\infty$, We have:
$\exists m\in\mathbb{N},$ $\bigcup_{n=1}^{\infty}A_n = \bigcup_{n=1}^{m}A_n.$
We just have to prove that $\exists m\in\mathbb{N},\bigcup_{n=1}^{\infty}A_n \subseteq \bigcup_{n=1}^{m}A_n$, As the other inclusion is trivial:
Proof by contradiction:
Suppose that it is not true that $\exists m\in\mathbb{N},\bigcup_{n=1}^{\infty}A_n \subseteq \bigcup_{n=1}^{m}A_n$,
I.e., Suppose that $\forall m\in\mathbb{N},\bigcup_{n=1}^{\infty}A_n \nsubseteq \bigcup_{n=1}^{m}A_n$,
Then we get by definition of set inclusion that $\forall m\in\mathbb{N},\exists x\in\bigcup_{n=1}^{\infty}A_n, x\notin \bigcup_{n=1}^{m}A_n$,
Now by definition of union of familiy of sets we get that $\forall m\in\mathbb{N},\exists n\in\mathbb{N},\exists x\in A_n, \lnot (\exists \hat{n}\in \{1,...m\},x\in A_\hat{n})$
(The small ^ hat symbol was introduced over the $n$ in the expression between the parentheses, inorder to distinguish between the two $n$'s in the whole logical expression).
Which in words mean:
For each natural number $m\in\mathbb{N}$, There exist a natural number $n\in\mathbb{N}$ for which there exist an element $x\in A_n$ such that it is not true for this $x$, that $\exists \hat{n}\in \{1,...m\},x\in A_\hat{n}$.
And by negating the expression between the parentheses we get that:
(I) $\forall m\in\mathbb{N},\exists n\in\mathbb{N},\exists x\in A_n, \forall \hat{n}\in \{1,...m\},x\notin A_\hat{n}$
Which in words mean:
For each natural number $m\in\mathbb{N}$, There exist a natural number $n\in\mathbb{N}$ for which there exist an element $x\in A_n$ that satisfies $\forall \hat{n}\in \{1,...m\},x\notin A_\hat{n}$
Now we'll prove by using (I) that:
(II) $\forall m\in\mathbb{N},\exists m<n\in\mathbb{N},\exists x\in A_n, \forall \hat{n}\in \{1,...m\},x\notin A_\hat{n}$,
Which in words mean:
For each natural number $m\in\mathbb{N}$, There exist a natural number $n\in\mathbb{N}$ greater than $m$, for which there exist an element $x\in A_n$ that satisfies $\forall \hat{n}\in \{1,...m\},x\notin A_\hat{n}$
Proof of (II)
Let $m\in\mathbb{N}$ be some natural number, Then by (I) we get that $\exists n\in\mathbb{N},\exists x\in A_n, \forall \hat{n}\in \{1,...m\},x\notin A_\hat{n}$,
We'll prove by contradiction that it is impossible for $n$ to satisfy $n\leq m$:
Suppose by contradiction that it is not true that $m<n$, I.e. suppose that $n\leq m$, Then since $n\in\mathbb{N}$ we get that $n$ is an integer that is greater than or equal to $1$ and less that or equal to $m$, And thus satisfy $n\in\{1,...,m\}$, And we can conclude that $x\notin A_n$, Which contradicts the fact that $x\in A_n$.
Thus it must be the case that $m<n$ as was to be shown, And we conclude that
$\forall m\in\mathbb{N},\exists m<n\in\mathbb{N},\exists x\in A_n, \forall \hat{n}\in \{1,...m\},x\notin A_\hat{n}$,
Q.E.D.
Now by using (II) we will build a sequence $x:\mathbb{N}\to X$ inductively that is one-to-one:
Step 1:
Choose some natrual number $n_0\in\mathbb{N}$, By (II) we get that $\exists n_0<n_1\in\mathbb{N},\exists x_1\in A_{n_1}, \forall \hat{n}\in \{1,...,n_0\},x\notin A_\hat{n}$
Step 2:
By using the $n_1\in\mathbb{N}$ from the previous step which its existence was guaranteed, Use (II) on this $n_1$ to get that:
$\exists n_1<n_2\in\mathbb{N},\exists x_2\in A_{n_2}, \forall \hat{n}\in \{1,...,n_1\},x\notin A_\hat{n}$.
Step 3:
By using the $n_2\in\mathbb{N}$ from the previous step which its existence was guaranteed, Use (II) on this $n_2$ to get that:
$\exists n_2<n_3\in\mathbb{N},\exists x_3\in A_{n_3}, \forall \hat{n}\in \{1,...,n_2\},x\notin A_\hat{n}$.
. . .
Step $k$ (Supposing $1\leq k \in\mathbb{N}$):
By using the $n_{k-1}\in\mathbb{N}$ from the previous step which its existence was guaranteed, Use (II) on this $n_{k-1}$ to get that:
$\exists n_{k-1}<n_k\in\mathbb{N},\exists x_k\in A_{n_k}, \forall \hat{n}\in \{1,...,n_{k-1}\},x\notin A_\hat{n}$.
. . .
(Continuing in this process to infinity....)
Thus we've built two sequences, an infinite sequence of natural numbers $\{n_k\in\mathbb{N}\}_{k=0}^\infty$ that satisfy $n_0 < n_1 < n_2 < n_3 < ... < n_k < ...$, I.e. an increasing sequence of natural numbers, And an infinte sequence of elements from $X$, $\{x_k\in X\}_{k=1}^\infty$ (Note: Indeed each $x_k\in X$, since each $x_k \in A_{n_k}$ and $A_{n_k}\subseteq X$).
Now we'll prove that the sequence $\{x_k\in X\}_{k=1}^\infty$ is indeed a one-to-one sequence, I.e., We'll prove that $\forall k_1,k_2\in\mathbb{N}, k_1 \neq k_2 \to x_{k_1} \neq x_{k_2}$:
Suppose by contradiction that the sequence $\{x_k\in X\}_{k=1}^\infty$ is not one-to-one, I.e. Suppose that $\exists k_1,k_2\in\mathbb{N}, k_1 \neq k_2 \land x_{k_1} = x_{k_2}$, Without loss of generaly we'll suppose that $k_1< k_2$.
Since $x_{k_1}\in X$ and $x_{k_2}\in X$ are elements that were chosen according to the inductive process shown obove, We get that $x_{k_1}\in A_{n_{k_1}}$ and $\forall \hat{n}\in \{1,...,n_{k_1-1}\},x\notin A_\hat{n}$, And that $x_{k_2}\in A_{n_{k_2}}$ and $\forall \hat{n}\in \{1,...,n_{k_2-1}\},x\notin A_\hat{n}$.
Now since $k_1,k_2\in\mathbb{N}$ and since $k_1<k_2$, We get that $k_1 + 1 \leq k_2$, And thus, $k_1 \leq k_2 - 1$, Now since the sequence $\{n_k\in\mathbb{N}\}_{k=0}^\infty$ is an increasing sequences, We get that $n_{k_1} \leq n_{k_2 - 1}$, But since $n_{k_1}\in\mathbb{N}$ we get that $n_{k_1}$ is an integer that satisfy $1 \leq n_{k_1} \leq n_{k_2-1}$, And therefore, We have, $n_{k_1} \in\{1,...,n_{k_2-1}\}$ and by using the fact that $\forall \hat{n}\in \{1,...,n_{k_2-1}\},x\notin A_\hat{n}$, We get that in particualar for this $n_{k_1}$, That $x\notin A_{n_{k_1}}$ which contradicts the fact that $x_{k_1}\in A_{n_{k_1}}$, Thus we've reached a contradiction and the sequence $\{x_k\in X\}_{k=1}^\infty$ must be a one-to-one sequence.
Now since a sequence is actually a function from the natural numbers to some set, We have that $x:\mathbb{N}\to X$ is a one-to-one function from the set of natural numbers $N$ to the set $X$, And thus we have $\aleph_0 = |\mathbb{N}|\leq |X|$, (I.e. $X$ is an infinite set), which contradicts the fact that $|X|\in\mathbb{N}_0$ (I.e. Contradicts the fact that $X$ is finite).
Thus it must be the case that $\exists m\in\mathbb{N},\bigcup_{n=1}^{\infty}A_n \subseteq \bigcup_{n=1}^{m}A_n$ as was to be shown.
Q.E.D.
What do you think about this proof? Is it a good proof? Are there better/shorter ways to prove the proposition? Thank you.
(Note: My book on Measure Theory, Supposed this proposition to be true without showing any proof, So I've tried to prove this proposition myself)
Here is a shorter way:
if $x \in \cup_{n \in \mathbb N} A_n$, then there exists some $i$ so that $x \in A_i \subset A$, so $\cup_{n \in \mathbb N} A_n \subset A$, and hence it is finite, and let's suppose it has $k$ elements.
In this case, order the elements of the union $\{a_1, \dots a_k\}$, and for each of them, select some corresponding $A_j$ so that $a_j \in A_j$. There are at most $k$ of them.