Question

Prove that the union of two finite sets is finite.
Hint: A U B = (A - B) U (B - A) U (A ∩ B)
where U = union and ∩ = intersection

Answer 1

To prove that the union of two finite sets is finite, we will show that the cardinality of the union set is finite. Recall that the cardinality of a set is the number of elements in the set. We will use the hint provided.

Let A and B be finite sets. We are given that:

A U B = (A - B) U (B - A) U (A ∩ B)

We know that since A and B are finite sets, they have a finite number of elements. Let |A| = m and |B| = n, where m and n are integers.

Now, let's consider the three sets in the given equation:

1. (A - B): This set contains all the elements that are in A but not in B. Since A is finite with m elements, the maximum number of elements in (A - B) would be m if none of the elements of A are in B. Therefore, |A - B| ≤ m.

2. (B - A): This set contains all the elements that are in B but not in A. Since B is finite with n elements, the maximum number of elements in (B - A) would be n if none of the elements of B are in A. Therefore, |B - A| ≤ n.

3. (A ∩ B): This set contains all the elements that are in both A and B. The maximum number of elements in this set would be the minimum of m and n because it cannot contain more elements than either A or B. Therefore, |A ∩ B| ≤ min(m, n).

Now, let's consider the union of these three sets:

|A U B| = |(A - B) U (B - A) U (A ∩ B)|

Since these three sets are disjoint (i.e., no common elements between them), we can add the cardinality of the three sets:

|A U B| = |A - B| + |B - A| + |A ∩ B|

From our earlier observations, we know:

|A U B| = (|A - B| ≤ m) + (|B - A| ≤ n) + (|A ∩ B| ≤ min(m, n))

Since m and n are integers, we can say |A U B| is an integer as it is the sum of three integers. This means the union of the two finite sets A and B is also a finite set.

Therefore, the union of two finite sets is finite.