Prove |P(A) X P(B)| = |P(A U B)| For Disjoint Sets

Hey guys, let's dive into a cool problem in elementary set theory: proving that for disjoint sets $A$ and $B$, the cardinality of the Cartesian product of their power sets, $|P(A) imes P(B)|$, is equal to the cardinality of the power set of their union, $|P(A ext{ U } B)|$. This might sound a bit technical with all those symbols, but stick with me, and we'll break it down piece by piece. We're going to check a proof and make sure it's solid. Remember, the cardinality of a set, denoted by $|X|$, is just the number of elements in that set. The power set $P(X)$ is the set of all possible subsets of $X$, including the empty set and $X$ itself. When $A$ and $B$ are disjoint, it means they have no elements in common, i.e., $A ext{ ∩ } B = ext{∅}$. This condition is super important and simplifies things quite a bit.

So, the goal is to show that $|P(A) imes P(B)| = |P(A ext{ U } B)|$. Let's recall what the Cartesian product $P(A) imes P(B)$ means. It's the set of all ordered pairs $(X, Y)$ where $X$ is a subset of $A$ (i.e., $X ext{ ∈ } P(A)$) and $Y$ is a subset of $B$ (i.e., $Y ext{ ∈ } P(B)$). The cardinality of this set is $|P(A)| imes |P(B)|$. Now, what about $P(A ext{ U } B)$? This is the set of all subsets of the union of $A$ and $B$. If $A$ and $B$ are disjoint, then the union $A ext{ U } B$ contains all elements from $A$ and all elements from $B$, with no overlap. The cardinality of $P(X)$ is $2^{|X|}$. So, if $|A| = m$ and $|B| = n$, then $|P(A)| = 2^m$ and $|P(B)| = 2^n$. Since $A$ and $B$ are disjoint, $|A ext{ U } B| = |A| + |B| = m + n$. Therefore, $|P(A ext{ U } B)| = 2^{m+n}$. Our task is to prove that $2^m imes 2^n = 2^{m+n}$, which is a fundamental property of exponents and holds true. The challenge here is to demonstrate this equality using set theory concepts, specifically by constructing a bijection (a one-to-one correspondence) between the two sets.

Let's consider the function $f: P(A) imes P(B) o P(A ext{ U } B)$ defined by $f(p_a, p_b) = p_a ext{ U } p_b$, where $p_a ext{ ∈ } P(A)$ and $p_b ext{ ∈ } P(B)$. To prove that the cardinalities are equal, we need to show that this function $f$ is a bijection. A bijection means the function is both injective (one-to-one) and surjective (onto). If we can prove $f$ is a bijection, then by definition, the two sets must have the same number of elements, i.e., the same cardinality.

Understanding the Function and the Goal

Alright guys, let's get a clearer picture of what we're trying to achieve here. We want to prove that $|P(A) imes P(B)| = |P(A ext{ U } B)|$, given that $A$ and $B$ are disjoint sets. Remember, $P(A)$ is the set of all subsets of $A$, and $P(B)$ is the set of all subsets of $B$. The Cartesian product $P(A) imes P(B)$ is the set of all possible pairs $(X, Y)$ where $X$ is any subset of $A$ and $Y$ is any subset of $B$. The cardinality of $P(A) imes P(B)$ is simply $|P(A)| imes |P(B)|$. On the other hand, $P(A ext{ U } B)$ is the set of all subsets of the combined set $A ext{ U } B$. Since $A$ and $B$ are disjoint, their union $A ext{ U } B$ contains all elements from $A$ and all elements from $B$, without any overlap. The cardinality of $P(A ext{ U } B)$ is $2^{|A ext{ U } B|}$.

Now, let's think about the function $f: P(A) imes P(B) o P(A ext{ U } B)$ defined by $f(p_a, p_b) = p_a ext{ U } p_b$. Here, $p_a$ is a subset of $A$, and $p_b$ is a subset of $B$. The function takes such a pair and returns their union. Since $p_a ext{ ⊆ } A$ and $p_b ext{ ⊆ } B$, and $A$ and $B$ are disjoint, any element in $p_a$ is not in $p_b$, and vice versa. The union $p_a ext{ U } p_b$ is a set containing all elements from $p_a$ and all elements from $p_b$. Crucially, because $A$ and $B$ are disjoint, $p_a ext{ U } p_b$ will always be a subset of $A ext{ U } B$. Why? Because every element in $p_a$ is in $A$, and every element in $p_b$ is in $B$, so every element in their union must be in $A ext{ U } B$. This confirms that the output of our function $f$ is indeed an element of $P(A ext{ U } B)$.

To prove that $|P(A) imes P(B)| = |P(A ext{ U } B)|$, we need to demonstrate that $f$ is a bijection. A bijection is a function that is both one-to-one (injective) and onto (surjective). If we can show these two properties, it means that every element in $P(A) imes P(B)$ maps to a unique element in $P(A ext{ U } B)$, and every element in $P(A ext{ U } B)$ is mapped to by exactly one element from $P(A) imes P(B)$. This one-to-one correspondence is the key to proving that the two sets have the same number of elements (cardinality).

Let's get started with checking these properties. It's where the real proof lies, and it requires careful logical steps. We'll examine injectivity first, then surjectivity. If both hold, we've got our proof! This is a classic way to establish equality of cardinalities in set theory, and it's a fundamental concept that pops up in many areas of mathematics. So, let's roll up our sleeves and tackle these proofs. It's going to be awesome!

Proving Injectivity (One-to-One)

Alright team, let's prove that our function $f(p_a, p_b) = p_a ext{ U } p_b$ is injective. This means that if we have two different pairs from the domain, say $(p_{a1}, p_{b1})$ and $(p_{a2}, p_{b2})$, their images under $f$ must also be different. Or, more formally, if $f(p_{a1}, p_{b1}) = f(p_{a2}, p_{b2})$, then it must be the case that $(p_{a1}, p_{b1}) = (p_{a2}, p_{b2})$. Let's start with the assumption that $f(p_{a1}, p_{b1}) = f(p_{a2}, p_{b2})$.

By the definition of $f$, this means:

$p_{a1} ext{ U } p_{b1} = p_{a2} ext{ U } p_{b2}$

Now, we need to show that this equality implies $p_{a1} = p_{a2}$ AND $p_{b1} = p_{b2}$. This is where the condition that $A$ and $B$ are disjoint is absolutely crucial. Since $A ext{ ∩ } B = ext{∅}$, any element in $A$ is not in $B$, and any element in $B$ is not in $A$.

Let's consider an arbitrary element $x$ that belongs to $p_{a1}$. Since $p_{a1} ext{ ⊆ } A$, $x$ must be an element of $A$. Because $A$ and $B$ are disjoint, $x$ cannot be an element of $B$.

Now, since $x ext{ ∈ } p_{a1}$, it must also be an element of the union $p_{a1} ext{ U } p_{b1}$. We are given that $p_{a1} ext{ U } p_{b1} = p_{a2} ext{ U } p_{b2}$. Therefore, $x$ must also be an element of $p_{a2} ext{ U } p_{b2}$.

Since $x ext{ ∈ } A$ and $A$ and $B$ are disjoint, $x$ cannot come from $p_{b2}$ (because $p_{b2} ext{ ⊆ } B$). This leaves only one possibility: $x$ must come from $p_{a2}$. So, we've shown that if $x ext{ ∈ } p_{a1}$, then $x ext{ ∈ } p_{a2}$. This implies that $p_{a1} ext{ ⊆ } p_{a2}$.

We can perform a symmetric argument. Let $y$ be an arbitrary element of $p_{a2}$. Since $p_{a2} ext{ ⊆ } A$, $y ext{ ∈ } A$. Because $A$ and $B$ are disjoint, $y$ cannot be in $B$. Since $y ext{ ∈ } p_{a2}$, it must be in $p_{a2} ext{ U } p_{b2}$. As $p_{a2} ext{ U } p_{b2} = p_{a1} ext{ U } p_{b1}$, $y$ must be in $p_{a1} ext{ U } p_{b1}$. Since $y ext{ ∈ } A$ and $A$ and $B$ are disjoint, $y$ cannot come from $p_{b1}$ (because $p_{b1} ext{ ⊆ } B$). Therefore, $y$ must come from $p_{a1}$. This implies $p_{a2} ext{ ⊆ } p_{a1}$.

Combining both results ($p_{a1} ext{ ⊆ } p_{a2}$ and $p_{a2} ext{ ⊆ } p_{a1}$), we conclude that $ extbf{p_{a1} = p_{a2}}$.

Now, let's do the same for the subsets of $B$. Consider an arbitrary element $z$ that belongs to $p_{b1}$. Since $p_{b1} ext{ ⊆ } B$, $z$ must be an element of $B$. Because $A$ and $B$ are disjoint, $z$ cannot be an element of $A$.

Since $z ext{ ∈ } p_{b1}$, it must also be an element of the union $p_{a1} ext{ U } p_{b1}$. We know $p_{a1} ext{ U } p_{b1} = p_{a2} ext{ U } p_{b2}$. Therefore, $z$ must also be an element of $p_{a2} ext{ U } p_{b2}$.

Because $z ext{ ∈ } B$ and $A$ and $B$ are disjoint, $z$ cannot come from $p_{a2}$ (since $p_{a2} ext{ ⊆ } A$). This leaves only one possibility: $z$ must come from $p_{b2}$. So, we've shown that if $z ext{ ∈ } p_{b1}$, then $z ext{ ∈ } p_{b2}$. This implies that $p_{b1} ext{ ⊆ } p_{b2}$.

Similarly, let $w$ be an arbitrary element of $p_{b2}$. Since $p_{b2} ext{ ⊆ } B$, $w ext{ ∈ } B$. Because $A$ and $B$ are disjoint, $w$ cannot be in $A$. Since $w ext{ ∈ } p_{b2}$, it must be in $p_{a2} ext{ U } p_{b2}$. As $p_{a2} ext{ U } p_{b2} = p_{a1} ext{ U } p_{b1}$, $w$ must be in $p_{a1} ext{ U } p_{b1}$. Since $w ext{ ∈ } B$ and $A$ and $B$ are disjoint, $w$ cannot come from $p_{a1}$ (since $p_{a1} ext{ ⊆ } A$). Therefore, $w$ must come from $p_{b1}$. This implies $p_{b2} ext{ ⊆ } p_{b1}$.

Combining these results ($p_{b1} ext{ ⊆ } p_{b2}$ and $p_{b2} ext{ ⊆ } p_{b1}$), we conclude that $ extbf{p_{b1} = p_{b2}}$.

Since we have shown that $p_{a1} = p_{a2}$ and $p_{b1} = p_{b2}$, it follows that $(p_{a1}, p_{b1}) = (p_{a2}, p_{b2})$. This completes the proof of injectivity. Our function $f$ maps distinct pairs to distinct pairs, which is exactly what we needed!

Proving Surjectivity (Onto)

Now, let's tackle the second part: proving that our function $f: P(A) imes P(B) o P(A ext{ U } B)$ defined by $f(p_a, p_b) = p_a ext{ U } p_b$ is surjective. For $f$ to be surjective, it means that for every element in the codomain, $P(A ext{ U } B)$, there must be at least one element in the domain, $P(A) imes P(B)$, that maps to it. In simpler terms, any subset of $A ext{ U } B$ can be formed by taking the union of some subset of $A$ and some subset of $B$. Let's grab an arbitrary element $S$ from the codomain, $P(A ext{ U } B)$. This means $S$ is a subset of $A ext{ U } B$, so $S ext{ ⊆ } A ext{ U } B$. Our goal is to find a pair $(p_a, p_b)$ where $p_a ext{ ∈ } P(A)$ and $p_b ext{ ∈ } P(B)$ such that $f(p_a, p_b) = S$, which means $p_a ext{ U } p_b = S$.

Since $S ext{ ⊆ } A ext{ U } B$, we can split $S$ into two parts: the elements of $S$ that are also in $A$, and the elements of $S$ that are also in $B$. Let's define:

$p_a = S ext{ ∩ } A$ $p_b = S ext{ ∩ } B$

Now, we need to verify a few things about these newly defined sets $p_a$ and $p_b$. First, are they indeed elements of the domain sets? That is, is $p_a ext{ ∈ } P(A)$ and $p_b ext{ ∈ } P(B)$?

Since $p_a = S ext{ ∩ } A$, and $S ext{ ⊆ } A ext{ U } B$, any element in $p_a$ must be in both $S$ and $A$. If an element is in $A$, it's certainly a subset of $A$. So, $p_a ext{ ⊆ } A$. This means $ extbf{p_a ∈ P(A)}$.

Similarly, since $p_b = S ext{ ∩ } B$, any element in $p_b$ must be in both $S$ and $B$. If an element is in $B$, it's certainly a subset of $B$. So, $p_b ext{ ⊆ } B$. This means $ extbf{p_b ∈ P(B)}$.

Great! We've found a pair $(p_a, p_b)$ from the domain $P(A) imes P(B)$. Now, we need to check if their union is equal to our arbitrary set $S$. That is, does $p_a ext{ U } p_b = S$?

Let's consider the union $p_a ext{ U } p_b = (S ext{ ∩ } A) ext{ U } (S ext{ ∩ } B)$.

We know that for any sets $X, Y, Z$, the distributive property of intersection over union holds: $X ext{ ∩ } (Y ext{ U } Z) = (X ext{ ∩ } Y) ext{ U } (X ext{ ∩ } Z)$. A similar distributive property holds for union over intersection, but it's not directly applicable here. However, we can use the property that for any sets $S, A, B$, $(S ext{ ∩ } A) ext{ U } (S ext{ ∩ } B) = S ext{ ∩ } (A ext{ U } B)$.

So, $p_a ext{ U } p_b = S ext{ ∩ } (A ext{ U } B)$.

Since $S$ is an element of $P(A ext{ U } B)$, we know that $S ext{ ⊆ } A ext{ U } B$. When a set $S$ is a subset of another set $U$, the intersection $S ext{ ∩ } U$ is simply $S$. In our case, $S ext{ ⊆ } A ext{ U } B$, so $S ext{ ∩ } (A ext{ U } B) = S$.

Therefore, we have shown that $ extbf{p_a ext{ U } p_b = S}$.

This means that for any subset $S$ in $P(A ext{ U } B)$, we have found a pair $(p_a, p_b) ext{ ∈ } P(A) imes P(B)$ such that $f(p_a, p_b) = S$. This is precisely the definition of surjectivity. We've successfully shown that our function $f$ is surjective!

Conclusion: A Bijection is Born!

So, what does this all mean, guys? We started with the goal of proving that $|P(A) imes P(B)| = |P(A ext{ U } B)|$ for disjoint sets $A$ and $B$. We defined a function $f: P(A) imes P(B) o P(A ext{ U } B)$ by $f(p_a, p_b) = p_a ext{ U } p_b$. We then meticulously proved two crucial properties about this function:

1. Injectivity (One-to-One): We showed that if $f(p_{a1}, p_{b1}) = f(p_{a2}, p_{b2})$, then it must follow that $p_{a1} = p_{a2}$ and $p_{b1} = p_{b2}$. This ensures that each distinct pair in the domain maps to a distinct subset in the codomain.
2. Surjectivity (Onto): We showed that for any subset $S$ in $P(A ext{ U } B)$, we can find specific subsets $p_a ext{ ∈ } P(A)$ and $p_b ext{ ∈ } P(B)$ (namely, $p_a = S ext{ ∩ } A$ and $p_b = S ext{ ∩ } B$) such that their union $p_a ext{ U } p_b$ equals $S$. This confirms that every possible subset of $A ext{ U } B$ is