Disjoint Sets: Is |A ∪ B| = N + M?

Hey guys! Today, we're diving deep into the fascinating world of set theory, specifically looking at a super common question: If you have two disjoint and finite sets, A and B, with sizes |A| = n and |B| = m, is it always true that the size of their union, |A ∪ B|, is equal to n + m? Let's break this down, explore why the answer is a resounding 'yes', and get a solid grasp on the underlying principles. This isn't just some abstract mathematical concept; understanding this property is fundamental to many areas of math and computer science, from counting principles to probability. So, grab your thinking caps, and let's get started on unraveling this neat piece of set theory.

Understanding Disjoint Sets and Their Union

First off, let's get our definitions straight. What exactly are disjoint sets? In simple terms, two sets are disjoint if they have absolutely no elements in common. Think of them as completely separate entities. Mathematically, we say sets A and B are disjoint if their intersection is the empty set, denoted as $A \cap B = \emptyset$. The empty set is like a container with nothing inside it. So, if the intersection is empty, it means there isn't a single element that belongs to both A and B simultaneously. This is a crucial condition for our problem.

Now, what about the union of sets, $A \cup B$? The union of two sets A and B is a new set that contains all the elements from set A and all the elements from set B. If an element is in A, it's in the union. If an element is in B, it's also in the union. If an element happens to be in both A and B, it's still only included once in the union (because sets, by definition, don't contain duplicate elements). The size of a set, often denoted by vertical bars like $|A|$, simply tells us how many elements are in that set. So, if $|A| = n$, it means set A has 'n' distinct elements, and if $|B| = m$, set B has 'm' distinct elements.

Our core question boils down to this: when A and B don't share any elements ($A \cap B = \emptyset$), and A has 'n' elements while B has 'm' elements, does the combined set $A \cup B$ automatically have $n + m$ elements? The answer, my friends, is a categorical YES! And the reason is elegantly simple, stemming directly from the definition of disjoint sets. Because the sets are disjoint, every element we count from set A is unique and not present in set B, and every element we count from set B is unique and not present in set A. Therefore, when we combine them to form the union, we are simply adding up the distinct elements from each set without any overlap or double-counting. This fundamental principle is known as the Addition Principle in combinatorics, and it's a cornerstone of counting.

Imagine you have a bag of red marbles (set A, with n red marbles) and another bag of blue marbles (set B, with m blue marbles). If these bags are completely separate and no marble is in both bags (disjoint), and you pour all the marbles from both bags into a single large box (the union $A \cup B$), how many marbles will be in the box? You'll have the 'n' red marbles plus the 'm' blue marbles, for a total of $n + m$ marbles. There's no trickery, no overlap, just a straightforward sum of the individual quantities. This intuitive example perfectly mirrors the mathematical concept. The condition of being disjoint is what allows this simple addition to hold true. If the sets were not disjoint, we would have to subtract the elements in the intersection to avoid counting them twice, leading to the more general formula $|A \cup B| = |A| + |B| - |A \cap B|$. But for disjoint sets, $|A \cap B| = 0$, simplifying the formula back to our desired $|A \cup B| = n + m$. So, yes, for disjoint finite sets, the size of their union is indeed the sum of their individual sizes.

Proof of the Principle

Let's solidify this understanding with a formal proof, shall we? This will give us that extra layer of confidence in our answer. We are given two finite sets, A and B, such that they are disjoint. This means their intersection is the empty set: $A \cap B = \emptyset$. We are also given that the size of set A is $|A| = n$, and the size of set B is $|B| = m$. We want to prove that $|A \cup B| = n + m$.

To prove this, we can construct a one-to-one correspondence (a bijection) between the elements of $A \cup B$ and a set of $n + m$ distinct objects. A common way to represent $n + m$ distinct objects is using the set of integers from 1 to $n + m$, which we can denote as $S = \{1, 2, 3, \dots, n + m\}$. If we can show that there's a perfect pairing between the elements in $A \cup B$ and the elements in $S$, then their sizes must be equal.

Since A and B are finite and disjoint, we can list the elements of A as $A = \{a_1, a_2, \dots, a_n\}$ and the elements of B as $B = \{b_1, b_2, \dots, b_m\}$. Because $A \cap B = \emptyset$, we know that none of the $a_i$ elements are the same as any of the $b_j$ elements. This means all the elements $a_1, \dots, a_n, b_1, \dots, b_m$ are distinct.

The union $A \cup B$ is the set containing all these elements: $A \cup B = \{a_1, \dots, a_n, b_1, \dots, b_m\}$. The total number of elements in this combined set is the sum of the number of elements in A and the number of elements in B, since there's no overlap. So, $|A \cup B| = n + m$ directly from the definition of union and disjointness.

To be more rigorous, let's define a function $f: A \cup B \to S$. We can define $f$ as follows:

• For any element $x \in A$, let $f(x) = i$, where $x = a_i$ (i.e., map the i-th element of A to the integer i).
• For any element $y \in B$, let $f(y) = n + j$, where $y = b_j$ (i.e., map the j-th element of B to the integer $n + j$).

Now, let's check if this function $f$ is a bijection (both injective and surjective).

Injectivity (One-to-One): We need to show that if $f(x_1) = f(x_2)$, then $x_1 = x_2$ for any $x_1, x_2 \in A \cup B$. There are three cases:

1. If $x_1, x_2 \in A$, then $f(x_1) = i_1$ and $f(x_2) = i_2$. If $f(x_1) = f(x_2)$, then $i_1 = i_2$. Since the mapping from $a_i$ to $i$ is unique, $x_1 = a_{i_1}$ must equal $x_2 = a_{i_2}$. So $x_1 = x_2$.
2. If $x_1, x_2 \in B$, then $f(x_1) = n + j_1$ and $f(x_2) = n + j_2$. If $f(x_1) = f(x_2)$, then $n + j_1 = n + j_2$, which implies $j_1 = j_2$. Since the mapping from $b_j$ to $n+j$ is unique, $x_1 = b_{j_1}$ must equal $x_2 = b_{j_2}$. So $x_1 = x_2$.
3. If $x_1 \in A$ and $x_2 \in B$, then $f(x_1) = i_1$ (which is between 1 and n) and $f(x_2) = n + j_2$ (which is between $n+1$ and $n+m$). Since the ranges of values assigned to elements from A and B are disjoint (one is $[1, n]$ and the other is $[n+1, n+m]$), $f(x_1)$ can never equal $f(x_2)$. Thus, if $f(x_1) = f(x_2)$, they must be in the same set, as shown in cases 1 and 2.

So, $f$ is indeed injective.

Surjectivity (Onto): We need to show that for every element $k \in S = \{1, 2, \dots, n + m\}$, there exists an element $x \in A \cup B$ such that $f(x) = k$.

• If $1 \le k \le n$, let $x = a_k \in A$. Then $f(x) = f(a_k) = k$. So all integers from 1 to n are covered.
• If $n + 1 \le k \le n + m$, let $k = n + j$, where $1 \le j \le m$. Let $x = b_j \in B$. Then $f(x) = f(b_j) = n + j = k$. So all integers from $n+1$ to $n+m$ are covered.

Since $A \cup B$ contains all $a_i$'s and all $b_j$'s, and $S$ contains all integers from 1 to $n+m$, every element in $S$ is mapped to by some element in $A \cup B$. Thus, $f$ is surjective.

Since $f$ is both injective and surjective, it is a bijection. The existence of a bijection between $A \cup B$ and $S$ proves that $|A \cup B| = |S|$. And we know that $|S| = n + m$. Therefore, $|A \cup B| = n + m$. This formal proof confirms our intuition and the Addition Principle for disjoint sets. It’s a beautiful demonstration of how definitions lead directly to powerful properties in mathematics!

Why Disjointness is Key

So, we've established that yes, $|A \cup B| = n + m$ when A and B are disjoint finite sets. But why is that specific condition of