Exercise 3.6.9 (Cardinality of a union of two sets)

My proof below unfortunately cheats in that I’m going to show $\#(A\cup B)=\#(A)+\#(B)-\#(A\cap B)$ instead. This is essentially the same as what we need to show, but we are utilizing the notion of subtraction which we have not defined at this point in the text (except technically in Lemma 3.6.9). If anyone else has an alternative proof which is "more correct" than mine, please post it. I suspect that proof would need to create a bijection in some way, but I found that difficult to conceive.

Proof.

We first show that $A\cup B$ and $A\cap B$ are finite. With $A$ and $B$ finite, we automatically know $A\cup B$ is finite by part (b) of Proposition 3.6.14. As for $A\cap B$, we know, by Exercise 3.1.7, that $A\cap B\subseteq A$; since $A$ is finite, we have, by part (c) of Proposition 3.6.14, that $A\cap B$ is finite.

We now show $\#(A\cup B)=\#(A)+\#(B)-\#(A\cap B)$. By Exercise 3.1.10, we have that

where $A\setminus B$, $B\setminus A$, and $A\cap B$ are disjoint. I first want to show that $\#(A\cup B)=\#(A\setminus B)+\#(B\setminus A)+\#(A\cap B)$. To show this, we quickly prove the following claim:

Claim. $A\setminus B$, $B\setminus A$, and $A\cap B$ are mutually disjoint, that is,

• (A $\setminus B)\cap (B\setminus A)=\varnothing$
• (A $\setminus B)\cap (A\cap B)=\varnothing$
• (B $\setminus A)\cap (A\cap B)=\varnothing$

Proof of Claim, bullet 1. Let $x\in (A\setminus B)\cap (B\setminus A)$. Then $x\in A\setminus B$ and $x\in B\setminus A$. This implies $(x\in A\text{and}x\notin B)$ and $(x\in B\text{and}x\notin A)$. But this would mean $(x\in A\text{and}x\notin A)$ and $(x\in B\text{and}\notin B)$, which is impossible. Hence, $x\notin (A\setminus B)\cap (B\setminus A)$, implying $(A\setminus B)\cap (B\setminus A)=\varnothing$.

Proof of Claim, bullet 2. Let $x\in (A\setminus B)\cap (A\cap B)$. Then $x\in A\setminus B$ and $x\in A\cap B$. This implies $(x\in A\text{and}x\notin B)$ and $(x\in A\text{and}x\in B)$. But this implies $x\in B\text{and}x\notin B$, which is impossible. Hence, $x\notin (A\setminus B)\cap (A\cap B)$, implying $(A\setminus B)\cap (A\cap B)=\varnothing$.

Proof of Claim, bullet 3. Same as above, just interchange the roles of $A$ and $B$.

Thus, we have shown that $A\setminus B$, $B\setminus A$, and $A\cap B$ are mutually disjoint.

Now, observe the following:

implies

By our Claim above, we must have that the set $[(A\setminus B)\cup (B\setminus A)]$ and $A\cap B$ are disjoint (easy to show). Thus, by part (b) of Proposition 3.6.14, we have that

Furthermore, by our Claim and by (b) of Proposition 3.6.14, we have that

Putting this altogether, we have:

But we have that $A\setminus B=A\setminus (A\cap B)$ and $B\setminus A=B\setminus (A\cap B)$ (these are easy to show). Then $\#(A\setminus B)=\#(A\setminus (A\cap B))$ and $\#(B\setminus A)=B\setminus (A\cap B)$. By repeated use of Lemma 3.6.9, we get that $\#(A\setminus (A\cap B))=\#(A)-\#(A\cap B)$ and $\#(B\setminus (A\cap B))=\#(B)-\#(A\cap B)$. Thus we get:

and we are done.

By part (b) of Proposition 3.6.14, $A\cup B$ is finite.

Next, $A\cap B\subseteq A$; since $A$ is finite, $A\cap B$ is finite by part (c) of Proposition 3.6.14.

Let $\#(A)=m$, $\#(B)=n$. To prove the final result, we fix $m$ and proceed by induction on $n$.

For the base case, let $n=0$. Then $B=\varnothing$, which means $A\cup B=A$ and $A\cap B=\varnothing$, so that we have

which proves the base case.

Now assume the result holds for some $n$. We want to show that it does for $n+1$. Choose $x\in B$, and let $B^{\prime }=B\setminus \{x\}$. Applying Lemma 3.6.1, we have $\#(B^{\prime })=n$, and by Proposition 3.6.14 (a), $\#(B^{\prime }\cup \{x\})=n+1$. So

and applying the inductive step, we obtain

There are two possibilities:

1.

$x\in A$. Then $A\cup B^{\prime }=A\cup B$, so that $\#(A\cup B^{\prime })=\#(A\cup B)$.

We next claim that $A\cap B^{\prime }=(A\cap B)\setminus \{x\}$. For let $a\in A\cap B^{\prime }$. Then $a\in A$ and $a\in B^{\prime }$, which means $a\in B$ since $B^{\prime }\subseteq B$. And since $x\notin B^{\prime }$, $a\ne x$. So $a\in (A\cap B)\setminus \{x\}$.

Going the other way, let $a\in (A\cap B)\setminus \{x\}$. Then $a\in A$ and $a\in B$. Since $B^{\prime }=B\setminus \{x\}$, $a\in B^{\prime }$. So $x\in A\cap B^{\prime }$, and by extensionality, $A\cap B^{\prime }=(A\cap B)\setminus \{x\}$. By Lemma 3.6.9, therefore, $\#(A\cap B^{\prime })=\#(A\cap B)-1$.

Thus $\#(A\cap B^{\prime })=\#[(A\cup B)\setminus \{x\}]$. Combining equalities, we obtain

$$\begin{array}{lll}\hfill \#(A)+\#(B)& =\#(A\cup B^{\prime })+\#(A\cap B^{\prime })+1& \hfill \text{(6)}\\ \hfill & =\#(A\cup B)+\#[(A\cap B)\setminus \{x\}]+1& \hfill \text{(7)}\\ \hfill & =\#(A\cup B)+(\#(A\cap B)-1)+1& \hfill \text{(8)}\\ \hfill & =\#(A\cup B)+\#(A\cap B).& \hfill \text{(9)}\end{array}$$

2.

$x\notin A$. Then $A\cup B^{\prime }=(A\cup B)\setminus \{x\}$, and by Lemma 3.6.1, $\#(A\cup B^{\prime })=\#(A\cup B)-1$.

We now show that $A\cap B^{\prime }=A\cap B$. Let $a\in A\cap B^{\prime }$. Then $a\in A$, and since $B^{\prime }\subseteq B$, $a\in B$. So $a\in A\cap B$.

Going the other way, let $a\in A\cap B$. Then $a\in A$ and $a\in B$. Since $x\notin A$, $a\ne x$. So $a\in B\setminus \{x\}$, or $a\in B^{\prime }$. Thus $a\in A\cap B^{\prime }$. So

$$\begin{array}{lll}\hfill \#(A)+\#(B)& =\#(A\cup B^{\prime })+\#(A\cap B^{\prime })+1& \hfill \text{(10)}\\ \hfill & =(\#(A\cup B)-1)+\#(A\cap B)+1& \hfill \text{(11)}\\ \hfill & =\#(A\cup B)+\#(A\cap B).& \hfill \text{(12)}\end{array}$$

We have shown that $\#(A)+\#(B)=\#(A\cup B)+\#(A\cap B)$ for finite sets $A$ and $B$.