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
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.
To prove that the union of two finite sets is finite, we will use the hint provided in the question: A U B = (A - B) U (B - A) U (A ∩ B), where U represents the union of two sets, and ∩ represents the intersection of two sets.
Let's assume that A and B are two finite sets.
Step 1: (A - B) U (B - A) U (A ∩ B) is a set that consists of three parts: (A - B), (B - A), and (A ∩ B).
Step 2: (A - B) represents the elements that are in set A but not in set B. Since both A and B are finite sets, (A - B) will also be a finite set.
Step 3: Similarly, (B - A) represents the elements that are in set B but not in set A. Since both A and B are finite sets, (B - A) will also be a finite set.
Step 4: (A ∩ B) represents the elements that are common to both set A and set B. Since both A and B are finite sets, (A ∩ B) will also be a finite set.
Step 5: Now, we can conclude that (A - B) U (B - A) U (A ∩ B) is a union of three finite sets, which implies it is a finite set.
Step 6: Finally, since A U B = (A - B) U (B - A) U (A ∩ B), and we have shown that (A - B) U (B - A) U (A ∩ B) is finite, we can therefore conclude that the union of two finite sets, A U B, is also finite.
Thus, we have proven that the union of two finite sets is finite.
To prove that the union of two finite sets is finite, we can use the given hint: A U B = (A - B) U (B - A) U (A ∩ B), where U denotes the union and ∩ represents the intersection of sets.
Let's break down the hint step by step:
1. (A - B) represents the elements that are in set A but not in set B.
2. (B - A) represents the elements that are in set B but not in set A.
3. (A ∩ B) represents the elements that are common to both sets A and B.
Now, let's consider the three parts individually:
1. (A - B) U (B - A): This part consists of the elements that are in one set but not the other. Since both sets A and B are finite, the subsets (A - B) and (B - A) are also finite because they contain a limited number of elements.
2. (A ∩ B): This part consists of the elements that are common to both sets A and B. Again, since both sets A and B are finite, the intersection (A ∩ B) is also finite as it contains a limited number of elements.
Now, let's combine the three parts using the union operation:
(A - B) U (B - A) U (A ∩ B)
Since each of the three parts is finite, their union is also finite. Therefore, the union of two finite sets is finite, which proves the statement.