$S$ and $T$ are two sets. Prove that if $|S-T|=|T-S|$, then $|S|=|T|$.

Question

Here is the problem that I am currently working on:

$S$ and $T$ are two sets. Prove that if $|S-T|=|T-S|$, then $|S|=|T|$.

I have access to the answer for this proof, and wanted help with the first assumption. Here is the answer I have been given to the proof:

Since $|S-T|=|T-S|$, there exists a bijective function $g\colon S-T\to T-S$. Let $i\colon S\cap T\to S\cap T$ be the identity function on $S\cap T$.

Then we know that the function $f\colon S\to T$ defined by $$ f(x)= \begin{cases} g(x) &\text{if $x\in S-T$}\\ i(x) &\text{if $x\in S\cap T$} \end{cases} $$ is bijective. Now using the fact of cardinality $\Rightarrow |S|=|T|$.

My first question is: how would I have known to make the leap into assuming that a bijective function exists? Would I need to consider that I am performing an operation on two sets, and that since I have that equal to another set (with operations), that I can allow this to exist as a bijective function? Or should I come to this assumption because I am showing that the cardinalities of two different groups of sets are the same, meaning that I am trying to show numerical equivalence (which requires a bijective function)?

Assuming that I need the bijection to show numerical eq., my next question is regarding the identity function step. I'm not sure where or why we jump to that assumption...

Thanks. I am studying for my final in proofs on Wednesday, and while I have a pretty good piecemeal understanding of each topic we've learned, I sometimes have a hard time piecing together multiple proof topic\techniques.

Answer 1

\begin{align} |S| & = |S-T| + |S\cap T| \\[8pt] |T| & = |T-S| + |S\cap T| \end{align}

If $|S-T|=|T-S|$, then the two right sides are the same, so the two left sides are the same.

We can also write a proof explicitly dealing with bijections.

You ask why one would "assume" a bijection exists. The bijection $g$ that you write about is not simply "assumed" to exist. Rather, you have $|S-T|=|T-S|$ and equality of cardinalities by definition means there is a bijection.

You need a bijection from $S$ to $T$. You have a bijection $g$ from part of $S$ to part of $T$. The other part of $S$ is the same as the other part of $T$: it is $S\cap T$. You need a bijection from that set to itself. The simplest bijection from a set to itself is the identity.

You can split the union of two sets into three parts: $$ \begin{array}{cccccccccccc} & \underbrace{a \quad b \quad c}_{S\,-\,T} \qquad \underbrace{p \quad q \quad r \quad s}_{S\,\cap\, T} \qquad \underbrace{x \quad y \quad z}_{T\,-\,S} \\[10pt] \text{or two parts, thus:} & \underbrace{a \quad b \quad c \qquad p \quad q \quad r \quad s}_S \qquad \underbrace{x \quad y \quad z}_{T\,-\,S} \\[10pt] \text{or two parts, thus:} & \underbrace{a \quad b \quad c}_{S\,-\,T} \qquad \underbrace{p \quad q \quad r \quad s \qquad x \quad y \quad z}_T \end{array} $$ Here's a bijection: $$ \begin{array}{cccccccccccc} S: & & a & b & c & \qquad & p & q & r & s \\ & & \updownarrow & \updownarrow & \updownarrow & & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \\ T: & \quad & x & y & z & \qquad & p & q & r & s \end{array} $$ The last four arrows are the identity function on $S\cap T$. The first three are the bijection between $S-T$ and $T-S$ that must exist because $|S-T|=|T-S|$.

Answer 2

The big key to this realization is that $$(S\setminus T)\cup (S\cap T)=S$$

$$(S\setminus T)\cap (S\cap T)=\emptyset$$

Answer 3

Hint. So we have $|S-T| = |T-S|$.

Then there is a bijection $g: (S-T) \to (T-S)$.

The identity function on $S \cap T$, which I denote $i_{S \cap T}$, is a bijection [I leave this as an exercise].

Define $f: S \to T$ by $$f(s) = \begin{cases} i_{S \cap T}(s), & s \in S \cap T \\ g(s), & s \notin S - T\text{.} \end{cases}$$ Note that $f$ is indeed a bijection $S \to T$, since $(S \cap T) \cup (S-T) = S$ is a union of the disjoint sets $S \cap T$ and $S - T$ and when restricted to both of these disjoint sets, it is a bijection.

Edit. In case you're new to this idea of showing that the piecewise function $f: S \to T$ defined by $$f(s) = \begin{cases} i_{S \cap T}(s), & s \in S \cap T \\ g(s), & s \notin S - T\text{.} \end{cases}$$ is a bijection, split it into cases.

Injectivity. Suppose $f(s_1) = f(s_2)$, $s_1, s_2 \in S$.

Without loss of generality, suppose $s_1 \in S \cap T$ and $s_2 \in S - T$. Then $f(s_1) = i_{S \cap T}(s_1) \in S \cap T$ and $f(s_2) = g(s_2) \in S - T$ since $i_{S \cap T}$ and $g$ are bijections on $S \cap T$ and $S-T$ respectively. But $S \cap T$ and $S-T$ are disjoint (and hence $f(s_1) \neq f(s_2)$ since $f(s_1)$ and $f(s_2)$ are of disjoint sets, a contradiction).

Hence $s_1$ and $s_2$ must be both of either $S \cap T$ and $S-T$. If both of them are of $S \cap T$, we then have $s_1 = s_2$. If they are both of $S-T$, we then have $g(s_1) = g(s_2)$. But $g$ is a bijection, hence injective. So $s_1 = s_2$ and $f$ is an injection.

I leave proof of $f$ being surjective to you.

Answer 4

Two sets have the same cardinality if and only if there exists a bijection between them, so the first step follows from definition.

Given this definition, since the question asks you to show that $S$ and $T$ have the same cardinality, you know that your goal is to find a bijection between $S$ and $T$ (this bijection is $f$).

The reason for using the inclusion function $i$ in the definition of $f$ is that the domain of $g$ is the set $S\setminus T$, so $g$ doesn't know where to send the elements in in $S\cap T$. (As Thomas Andrews noted, $S = (S \cap T) \cup (S \setminus T)$, so this proof defines a bijection on all of $S$ by defining bijections on its disjoint components)

A good way to understand this proof would be to check that $f$ is a bijection.

• For surjectivity, let $t$ be an element of $T$. Can you find an element of $S$ that gets mapped to $T$? (Hint: this depends on whether $t$ is also an element of $S$, so you'll have to look at two different cases.)
• For injectivity, suppose $f(t_1)=f(t_2)$. What does that tell you about $t_1$ and $t_2$? Is it possible for one to be in $S\setminus T$ while the other one is in $S\cap T$?