Proving two sets are equal

We will need to sometimes need to argue two sets (which are potentially defined differently) are indeed the same. This note lays down a common trick to do so.

The Basics

  1. This can also be modified suitably for infinite sets but we'll not go in there for now!

  2. To use Trick 1' here you might need to use some linear algebra.

A reasonably common problem we will encounter in this course it to prove that two sets $S$ and $T$ are in fact equal. Of course if both $S$ and $T$ have the exact description, this problem will be trivial. However, typically the descriptions of $S$ and $T$ will be different and hence, if we claim that $S=T$, then we need to present a proof for the claim. Below we will talk about one very common proof trick to prove set equality.

Trick 1: Prove $S\subseteq T$ and $T\subseteq S$

This trick is based on the simple fact that $S=T$ if and only if $S\subseteq T$ and $T\subseteq S$:

Trick 1

First prove $S\subseteq T$. Then prove $T\subseteq S$.

We will apply this trick on the following exercise:

Exercise 1

You are an investigative journalist who is looking into two companies. The two companies are in the niche area which builds tiles with integral dimensions. WeLoveEvenSides claims to be the only company on earth to have all possible rectangular tiles where at least the length or the breadth is even. WeLoveEvenArea claims to be the only company on earth to have all possible rectangular tiles whose area is divisible by two. Your preliminary investigations have led you to believe that these two companies are indeed the same. Now deliver the knockout argument by proving that the set of rectangular tiles manufactured by WeLoveEvenSides is exactly the same as the set of rectangular tiles manufactured by WeLoveEvenArea (which by the claims of the companies shows that they are the same).

As an aside:

Exercise 2

Argue why you cannot deliver the knockout blow in Exercise 1 if the dimensions of the tiles can be real numbers.

Tip

Whenever you see such a verbose problem statement as in Exercise 1, it is useful to abstract out the mathematical problem.

I claim that the above is the same as the following problem (it is an exercise to convince yourself that my claim is indeed true):

Exercise 3

Let $R$ be the set of all rectangles with integral length and breadth. Let $R_1\subseteq R$ be the set of rectangles with even length or breadth. Let $R_2$ be the set of all rectangles with even integral area. Prove that $R_1=R_2$.

We now use our trick to solve Exercise 3.

Proof Idea (Ex. 3)

We will first argue that $R_1\subseteq R_2$. Then we will argue that $R_2\subseteq R_1$. To do this we will use the fact that a rectangle with length $\ell$ and breadth $b$ has an area of $\ell\cdot b$.

Proof Details

We first prove $R_1\subseteq R_2$. Consider an arbitrary $r\in R_1$ with length $\ell$ and breadth $b$. Since $r\in R_1$ either $\ell$ or $b$ is even. Since multiplying an even number with another integer results in another even number, we conclude that $\ell\cdot b$ is even. This, by definition implies $r\in R_2$. Since the choice of $r$ was arbitrary, we have $R_1\subseteq R_2$.

We now prove that $R_2\subseteq R_1$. Consider an arbitrary $r\in R_2$ with area $a$. This implies that $a$ is even. Now let $\ell$ and $b$ denote the length and breadth of $r$. Note that this implies that $\ell\cdot b$ is even. We claim that either $\ell$ or $b$ is even. (We will prove this claim shortly.) Note that by definition this implies that $r\in R_1$. Since the choice of $r$ was arbitrary, we have $R_2\subseteq R_1$, as desired.

Finally, we prove the claim. For the sake of contradiction, let us assume that both $\ell$ and $b$ are odd. Since the product of two off integers results in an odd integer, it must be the case that $a=\ell\cdot b$ is odd. This is a contradiction (since $a$ is even), which proves the claim.

Trick 1' (for finite sets)

We now present a variant of Trick 1 that works for finite sets.1 This is based on noting the following property:

Exercise 4 (Trick 1')

Let $S$ and $T$ be finite sets. Then $S=T$ if and only if $S\subseteq T$ and $|S|\ge |T|$.

In this note we will not dwell much on Trick 1' (since we won't really use it in CSE 331) but here is an exercise where you can apply Trick 1':2

Exercise 5

Let $S=\{ (0,0), (1,1)\}$ and $T=\{(a,b)|a\oplus b=0\text{ and } a,b\in\{0,1\}\}$. Prove that $S=T$.