Concerning the proof of the Cantor–Bernstein theorem I've seen two proofs for the Cantor–Bernstein theorem which says that for two sets $X$ and $Y$ if $\#X \le \#Y$ and $\#Y \le \#X$ then $\#X=\#Y$, equivalently if we can find an injection from $X$ to $Y$ and $Y$ to $X$ then we can find a bijection between the two sets. One proof says that one can assume WLOG $Y \subset X$ another says WLOG $X \cap Y =\emptyset$ . What I don't get is that if we say $Y \subset X$ , we can find a set such that $Y \not\subset X$ and $X \not\subset Y$. How is generality not lost?
 A: Let $X$ and $Y$ two sets and $f \colon X \to Y$ and $g \colon Y \to X$ injections. 
(i) Note, that $Y' := g(Y)\subseteq X$ is a set equinumerous with $Y$ ($g$ is the required bijection). Replacing $Y$ by $Y'$, $g$ by the identity and $f$ by $g\circ f$, we may wlog assume that $Y \subseteq X$.
(ii) If $X$ and $Y$ are arbitrary, $X\times \{0\}$ and $Y\times \{1\}$ are disjoint sets, equinumerous with $X$ resp. $Y$. That justifies us to say that we may wlog assume that $X \cap Y = \emptyset$.
A: If $f:Y\to X$ is an injection, we can identify $Y$ with $f[Y]$, replacing each $y\in Y$ with its image $f(y)\in X$. The injection $g:X\to Y$ then has to be replaced with the injection $f\circ g:X\to f[Y]$. If we let $Y'=f[Y]$ and $g'=f\circ g$, we now have $Y'\subseteq X$ and an injection $g':X\to Y'$. If we can find a bijection $h:X\to Y'$, $f^{-1}\circ h$ will be the desired bijection from $X$ to $Y$. Thus, there’s no harm in assuming from start that $Y\subseteq X$: if it isn’t, we work with $Y'$ and then use $f^{-1}$ to transfer the resulting bijection into the one that we really wanted.
Similarly, if $X\cap Y\ne\varnothing$, let $X'=X\times\{0\}$ and $Y'=Y\times\{1\}$. Then $X'$ and $Y'$ are disjoint, and there are obvious bijections $\varphi:X\to X':x\mapsto\langle x,X\rangle$ and $\psi:Y\to Y':y\mapsto\langle y,1\rangle$. If $f:Y\to X$ and $g:X\to Y$ are the original injections, we can replace them by the injections
$$f':Y'\to X':\langle y,1\rangle\mapsto\langle f(y),0\rangle$$
and
$$g':X'\to Y':\langle x,0\rangle\mapsto\langle g(x),1\rangle$$
and work with those instead.
In both cases the point is that we can replace $Y$ with any other set $Y'$ such that there is a bijection between $Y$ and $Y'$, and similarly for $X$: we just adjust the injections correspondingly.
