{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

# How to compare two sets?

## Problem

Prove that $\{3k + 1: k\in\mathbb{Z}\} = \{3k - 2: k\in\mathbb{Z}\}$.

## Thought

To understand the problem, **it is critical to translate the notation into something that you can read** !

We want to show that the two sets are equal. The set on the left hand side can be read as "every number that can be written as $3k + 1$ with $k$ integer". The set on the left hand side can be read as "every number that can be written as $3k - 2$ with $k$ integer". Intuitively, both of them are $\{\ldots, -2, 1, 4, \ldots\}$, so they must be equal.

Beyond intuition (which can be wrong sometimes), what we need to show is "every number of the form $3k + 1$ can be written as $3k' + 1$ for some integer $k'$", and the other way around. Note that $k$ and $k'$ need not to be equal.

## Sample answer

Let $X = \{3k + 1: k\in\mathbb{Z}\}$ and $Y = \{3k - 2: k\in\mathbb{Z}\}$. We need to show that $x\in X$ implies $x\in Y$ and $y\in Y$ implies $y\in X$.

Suppose $x\in X$. Then $x$ can be written as $x = 3k + 1$ for some integer $k$. Thus, $x = 3k + 3 - 2 = 3(k+1) - 2$, so $x\in Y$.

On the other hand, suppose $y\in Y$. Then $y = 3k - 2$ for some integer $k$. Thus, $y = 3k - 3 + 1 = 3(k-1) + 1$, so $y\in X$.

In summary, we have $X = Y$.

## Note

This is a standard procedure to compare two sets. We use the fact that the following are equivalent.

- $X\subseteq Y$
- If $x \in X$, then $x \in Y$.

If we want to show $X = $Y, then we need to show $X\subseteq Y$ and $Y\subseteq X$.

Once you are familiar with this type of argument. It would be fun to play with the following problem as an exercise.

Let $A$ be an $m\times n$ matrix, $\bp\in\mathbb{R}^n$, and $\bb\in\mathbb{R}^m$ such that $A\bp = \bb$. Show that

$$
\{\bp + \bh: A\bh = \bzero\} = \{\bx: A\bx = \bb\}.
$$

*This note can be found at Course website > Learning resources.*