bijective function verification

Question

Let $A$ and $B$ be sets. Suppose that $|A|\leq |B|$ and $|B| \leq |A|.$ Then $|A|= |B|.$

Below is an almost complete proof.

Choose injective functions $f:A\to B$ and $g :B\to A$. Since the functions $f :A\to f(A), g : B\to g(B),$ and $f : g(B) \to f(g(B))$ are bijective we have $|A| = |f(A)| $ and $|B| = |g(B)| = |f(g(B))| .$ Let $X = f(g(B)), Y=f(A), Z=B.$ Then $|X|=|Z|$ and $X\subseteq Y\subseteq Z.$ We need to show $|Y| = |Z|.$

The function $h = f\circ g : Z\to X$ is a bijection. Define for $n\in\mathbb{N}, Z_0 = Z,Z_n := h(Z_{n-1})$ and $Y_0 = Y, Y_n = h(Y_{n-1}).$ Since $Y_0 = Y, Z_0 = Z, Z_1 = h(Z_0) = h(Z)=X,$ so $Z_1 \subseteq Y_0\subseteq Z_0.$ Assume inductively that for some $1\leq n\in\mathbb{N}, Z_n\subseteq Y_{n-1}\subseteq Z_{n-1}.$ Then $Z_{n+1} = h(Z_{n})\subseteq h(Y_{n-1})\subseteq h(Z_{n-1}),$ since $h$ is injective, so $Z_{n+1}\subseteq Y_n\subseteq Z_n$. Now let $U_n = Z_n\backslash Y_n, U= \cup_{n=0}^{\infty} U_n$ and $V = Z\backslash U.$ Define $H : Z\to Y$ by $H(x) =\begin{cases}h(x),&\text{ if $x\in U$}\\ x,&\text{ if $x\in V$}.\end{cases}$

My question is, why is $H$ bijective? Clearly, it's injective because if $H(x)=H(y) \in Y,$ then since $U$ and $V$ are disjoint, $x,y \in V$ or $x,y\in U$ and in both cases it's easily verified that $x = y.$ Now to show $H$ is surjective, I was thinking of showing that $h(U) = Y\backslash V$ because clearly $H(V) = V$ and $H(U\cup V) = H(U)\cup H(V) = h(U)\cup V$. Also, $h(Z_n\backslash Y_n) = h(Z_n)\backslash h(Y_n).$ Indeed, suppose $x \in h(Z_n\backslash Y_n)\Rightarrow x = h(a), a \in Z_n\backslash Y_n.$ Then if $x = h(y)$ for some $y \in Y_n,$ we have $a = y = h^{-1}(x),$ which is a contradiction as $y\in Y_n$ while $a$ is not in $Y_n.$ sO $h(Z_n\backslash Y_n)\subseteq h(Z_n)\backslash h(Y_n).$ Now if $x = h(b)\in h(Z_n)\backslash h(Y_n),$ then $b\not \in Y_n$ because otherwise $h(b)\in h(Y_n),$ a contradiction. Thus, since $b\in Z_n, h(b)\in h(Z_n\backslash Y_n).$ The above two justifications imply that $h(U)=h(\cup_{n\geq 0} Z_n\backslash Y_n) = \cup_{n\geq 0} h(Z_n)\backslash h(Y_n) = \cup_{n\geq 0}Z_{n+1}\backslash Y_{n+1},$ but I'm not sure how to show that this equals $Y\backslash V$; the sets $Z_n\backslash Y_n$ may not be disjoint. Am I doing something wrong?

Answer 1

The sets $Z_n\setminus Y_n$ are pairwise disjoint: if $n<m$, we have

$$Y_m\subseteq Z_m\subseteq Y_n\subseteq Z_n\,,$$

so

$$\begin{align*} (Z_m\setminus Y_m)\cap(Z_n\setminus Y_n)&\subseteq Z_m\cap(Z_n\setminus Y_n)\\ &\subseteq Y_n\cap(Z_n\setminus Y_n)\\ &=\varnothing\,. \end{align*}$$

The crude diagram of $B$ shown below may be helpful: $H$ simply pushes each $U_n$ down to $U_{n+1}$, thereby translating $U$ downward one block, and leaves the blocks of $V$ alone, more or less as shown on the right.

      -------------
      |    U_0    |
      -------------        -------------
      |  Y_0\Z_1  |        |  Y_0\Z_1  |
      -------------        -------------
      |    U_1    |        |   H[U_0]  |
      -------------        -------------
      |  Y_1\Z_2  |        |  Y_1\Z_2  |
      -------------        -------------
      |           |        |   H[U_1]  |
      |     |     |        -------------
      |     V     |        |     |     |
      V           V        V     V     V