Proving $ \bigcup_{i=1}^n A_{i} \text{ is finite.} $ by Induction.

Question

Prove : If $A_{1},A_{2},...,A_{n} \text{ are finite sets, then } $$$ \bigcup_{i=1}^n A_{i} \text{ is finite.} $$

Proof:

(I) Basis Step : $p(1)$ is true because it is true because it is finite. There is a first one and a last one.

(II) Induction Step: Suppose $p(k)$ is ture.

$$ \bigcup_{i=1}^k A_{i} \text{ is finite.} $$

Show : $P(k+1)$ is true LHS.

$$ \bigcup_{i=1}^{k+1} A_{i} \text{ is finite.} $$

Here is where I get stuck because I do not know what the right hand side of this problem is. I also do not know if you are to multiply or add to the original left hand side. How does one prove this is true for all $n \in \Bbb N ?$

Answer 1

By definition, $$\bigcup\limits_{i=1}^{k+1} A_i = [\bigcup\limits_{i=1}^k A_i] \cup A_{k+1}$$ Since $p(k)$ is true, $\bigcup\limits_{i=1}^k A_i$ is finite. Since $p(2)$ is true (i.e. the union of two finite sets is finite), so is $p(k+1)$.

I want to point out that if $A_1, ... , A_n$ are sets, $\bigcup\limits_{i=1}^n A_i$ doesn't necessarily make sense. In order to take the union of a bunch of sets, they must all be subsets of some larger set.

Answer 2

I'm not sure what you mean by multiplying or adding anything. You need to show that

$$\bigcup_{i=1}^{k+1}A_i$$ is finite. In particular $$\bigcup_{i=1}^{k+1}A_i=\left(\bigcup_{i=1}^{k}A_i\right)\bigcup A_{k+1}$$ and thus you have the union of two finite sets.

Depending on your definition of finite, this may be all you have to say (i.e. the union of two finite sets is finite, so we are done). Formally, you could form a bijection from the set to a bounded set of natural numbers, but that may be overkill depending on context.

Answer 3

The induction step breaks down to:

Let $X = \cup_{i=0}^n A_i$; a union of $n$ finite sets that is, by assumption finite.

Let $Y = A_{n+1}$; a finite set.

So $\cup_{i=0}^{n+1} A_i = X \cup Y$; the union of two finite sets. Suffices to show the union of two finite sets is finite. Which is so absolutely obvious we just know it's going to be hard to prove.

Let $a_1,......, a_n$ be a finite indexing of set $X$. Let $b_1..... b_m$ be a finite indexing of set $Y$. Let $c_1........ c_{n+m}$ be such that if $i \le n$, $c_i = a_i$ and if $i > n$ then $c_i = b_{i-n}$. Then $c_1...c_{n+m}$ is an indexing that accounts for, possibly with some redundancy, a complete indexing of $X \cup Y$.

So $X \cup Y$ is finite.