Cardinality, Finite Sets Proof Let $S$ and $T$ be finite sets. Prove that if $|T-S| = |S-T|$, then $|S| = |T|$.
 A: $1$. Show that $S = (S \cap T) \cup (S-T)$ and $T = (S \cap T) \cup (T-S)$.
$2$. Show that $(S \cap T)$, $(S-T)$ and $(T-S)$ are disjoint.
$3$. Hence, $\left \vert S \right \vert = \left \vert S \cap T \right \vert + \left \vert S-T \right \vert$ and $\left \vert T \right \vert = \left \vert S \cap T \right \vert + \left \vert T-S \right \vert$
$4$. Now conclude what you want.
A: For fun, you can prove this by induction on $|S\cap T|$.
If $|S\cap T|=0$, $S-T=S$ and $T-S=T$ and the result follows immediately.
Assume that $k>0$ and that the theorem is true when $|S\cap T|<k$.
To show: If $S$ and $T$ are sets for which $|S\cap T|=k$ and $|S-T|=|T-S|$ then $|S|=|T|$.
Let $S$ and $T$ be such sets. Choose $x\in S\cap T$ (possible because $|S\cap T|=k>0$); let $T'=T-\{x\}$ and $S'=S-\{x\}$. The assumptions of the theorem hold for $T'$ and $S'$ (show this). Furthermore, $|S'\cap T'|=k-1<k$, and therefore by the inductive hypothesis, $|S'|=|T'|$. Then there exists a one-to-one and onto function $f':S'\to T'$. Define $f:S\to T$ by $f(s)=f'(s)$ when $s\neq x$ and $f(x)=x$. The function $f$ is one-to-one and onto (show).
