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.
Best Answer
\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|$.