4.3 Proving two sets are equal

You may have previously used Venn diagrams to indicate that two sets are equal. While they can be useful for your understanding of what is going on, these do not constitute stringent proofs in themselves.

The most common method to directly prove that two sets $A$ and $B$ are equal to each other is to first show that $A\subseteq B$ and then show that $B\subseteq A$ . If both of these are true, we must have $A=B$ .

Exercise 4.25.

Why does showing that both $A\subseteq B$ and $B\subseteq A$ mean that we necessarily have $A=B$ ?

Solution (please try for yourself before looking)

If $A\subseteq B$ then for every element $a\in A$ , $a\in B$ .

Moreover, if $B\subseteq A$ , then every $b\in B$ also has $b\in A$ .

As every element of $A$ is therefore in $B$ and vice versa, then $A=B$ .

To show one set $A$ is a subset of another set $B$ , we can take a general element of $A$ and show that it must also belong to $B$ . This is the strategy we use in the next proof.

Theorem 4.26 (De Morgan’s Laws).

Let $A$ and $B$ be two sets, then

a)

$(A\cup B)^{c}=A^{c}\cap B^{c}$ ,
b)

$(A\cap B)^{c}=A^{c}\cup B^{c}$ .

Proof (of Theorem 4.26 a)).

To prove $(A\cup B)^{c}=A^{c}\cap B^{c}$ , we first show that $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ and then show that $A^{c}\cap B^{c}\subseteq(A\cup B)^{c}$ .

Let $x\in(A\cup B)^{c}$ . Then, by definition of the complement, $x\notin A\cup B$ . As $x$ is not an element of $A$ or $B$ , then we must have that $x\notin A$ and $x\notin B$ . Equivalently, $x\in A^{c}$ and $x\in B^{c}$ so $x$ belongs to an intersection of two sets $A^{c}$ and $B^{c}$ i.e. $x\in A^{c}\cap B^{c}$ . Hence, we’ve shown that any element $x\in(A\cup B)^{c}$ is also an element of $A^{c}\cap B^{c}$ so $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ .

To show $A^{c}\cap B^{c}\subseteq(A\cup B)^{c}$ , consider an element $y\in A^{c}\cap B^{c}$ . Then

	$\displaystyle y\in A^{c}\cap B^{c}\quad$
$\displaystyle\iff$	$\displaystyle y\in A^{c}\text{ and }y\in B^{c}\quad$	by definition of intersection
$\displaystyle\iff$	$\displaystyle y\notin A\text{ and }y\notin B$	by definition of complement
$\displaystyle\iff$	$\displaystyle y\notin A\cup B$	by definition of union
$\displaystyle\iff$	$\displaystyle y\in(A\cup B)^{c}$	$\displaystyle\text{ by definition of complement}.$

We have therefore shown that $A^{c}\cap B^{c}\subseteq(A\cup B)^{c}$ . As we have also seen that $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ , then we must have $(A\cup B)^{c}=A^{c}\cap B^{c}$ .

In the proof above, the argument that $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ is written in a different style to the argument that $A^{c}\cap B^{c}\subseteq(A\cup B)^{c}$ . Both styles are valid but we would usually stick to one style throughout the same proof.

If we look at this proof carefully, we notice that the equivalence of the statements within it actually reduce the proof to the following (much shorter) argument:

Proof.

Observe that

	$\displaystyle y\in A^{c}\cap B^{c}\quad$
$\displaystyle\iff$	$\displaystyle y\in A^{c}\text{ and }y\in B^{c}\quad$	by definition of intersection
$\displaystyle\iff$	$\displaystyle y\notin A\text{ and }y\notin B$	by definition of complement
$\displaystyle\iff$	$\displaystyle y\notin A\cup B$	by definition of union
$\displaystyle\iff$	$\displaystyle y\in(A\cup B)^{c}$	$\displaystyle\text{ by definition of complement}.$

Hence, $y\in A^{c}\cap B^{c}\iff y\in(A\cup B)^{c}$ and thus, $(A\cup B)^{c}\subseteq A^{c}\cap B^{c}$ and $A^{c}\cap B^{c}\subseteq(A\cup B)^{c}$ . Therefore, $(A\cup B)^{c}=A^{c}\cap B^{c}$ .

Exercise 4.27.

Using the proof of part a) as a guide, prove part b) of Theorem 4.26.

Note that the order in which we show one set is a subset of the other doesn’t matter: we could swap the second and third paragraph in the previous proof and it would remain logically consistent.

Exercise 4.28.

Consider the following sets

	$\displaystyle S$	$\displaystyle=\{n\in\mathbb{Z}:n=a^{2}-b^{2},\text{ for some }a,b\in\mathbb{Z}\},$
	$\displaystyle O$	$\displaystyle=\{n\in\mathbb{Z}:n\text{ is odd}\},$
	$\displaystyle F$	$\displaystyle=\{n\in\mathbb{Z}:n\text{ is divisible by }4\}.$

Prove that $S=O\cup F$ .

Solution (please try for yourself before looking)

We first show $S\subseteq O\cup F$ . Let $n$ be an arbitrary element of $S$ so $n=a^{2}-b^{2}=(a+b)(a-b)$ for some $a,b\in\mathbb{Z}$ .

If $a-b$ is even then there is some $k\in\mathbb{Z}$ such that $a-b=2k$ . Moreover, $a+b=(a-b)+2b=2k+2b=2(k+b)$ is also even and $n=(a-b)(a+b)=(2k)(2(k+b))=4k(k+b)$ . This means $n$ is divisible by 4 so $n\in F$ and, more generally, $n\in O\cup F$ .

If $a-b$ is odd, then for some $k\in\mathbb{N}$ , $a-b=2k+1$ and $a+b=2(k+b)+1$ . The product of two odd numbers is itself odd so we have $n\in O$ and $n\in O\cup F$ .

In either case, $n\in O\cup F$ meaning $S\subseteq O\cup F$ .

We next prove the inclusion $O\cup F\subseteq S$ . Let $m$ be any element of $O\cup F$ .

If $m\in O$ , then $m=2k+1$ for some $k\in\mathbb{Z}$ and we can write this as a difference of two squares: $2k+1=(k-1)^{2}-k^{2}$ . Therefore $m\in S$ .

If $m\in F$ , then $m$ is a multiple of 4 so $m=4k$ for some $k\in\mathbb{Z}$ . Consider $(k+1)^{2}-(k-1)^{2}=4k=m$ . As we can write $m$ as the difference of two squares, then we again have $m\in S$ .

In either case, $m\in S$ meaning $O\cup F\subseteq S$ .

Overall, we have shown both $O\cup F\subseteq S$ and $S\subseteq O\cup F$ so can conclude that $S=O\cup F$ .