(1)

\(\Rightarrow\)

\(X\)から\(Y\)への単射を\(f\)として、\(Y\)から\(X\)への単射を\(g\)とする。
集合\(A_{n}\)を
\[ \begin{cases} A_{1}=X\setminus g\left(Y\right)\\ A_{n+1}=g\left(f\left(A_{n}\right)\right) \end{cases} \] として、
\[ A=\bigcup_{k=1}^{\infty}A_{k} \] とする。
このとき、\(A_{1}=g^{c}\left(Y\right)\)なので、\(A^{c}=\left(\bigcup_{k=1}^{\infty}A_{k}\right)^{c}=\bigcap_{k=1}^{\infty}A_{k}^{c}\subseteq A_{1}^{c}=g\left(Y\right)\)となっている。
\(g\)は単射なので\(x\in A^{c}\subseteq g\left(Y\right)\)のとき、逆写像を定義でき、写像\(h\)を
\[ h\left(x\right)=\begin{cases} f\left(x\right) & x\in A\\ g^{\bullet}\left(x\right) & x\notin A \end{cases} \] とする。
このとき、
\begin{align*} h\left(X\right) & =f\left(A\right)\cup g^{\bullet}\left(X\setminus A\right)\\ & =f\left(A\right)\cup\left\{ g^{\bullet}\left(X\right)\setminus g^{\bullet}\left(A\right)\right\} \\ & =f\left(A\right)\cup\left\{ Y\setminus g^{\bullet}\left(\bigcup_{k=1}^{\infty}A_{k}\right)\right\} \\ & =f\left(A\right)\cup\left\{ Y\setminus\bigcup_{k=1}^{\infty}g^{\bullet}\left(A_{k}\right)\right\} \\ & =f\left(A\right)\cup\left\{ Y\setminus\left(g^{\bullet}\left(A_{1}\right)\cup\bigcup_{k=2}^{\infty}g^{\bullet}\left(A_{k}\right)\right)\right\} \\ & =f\left(A\right)\cup\left\{ Y\setminus\left(g^{\bullet}\left(A_{1}\right)\cup\bigcup_{k=2}^{\infty}g^{\bullet}\left(g\left(f\left(A_{k-1}\right)\right)\right)\right)\right\} \\ & =f\left(A\right)\cup\left\{ Y\setminus\left(g^{\bullet}\left(X\setminus g\left(Y\right)\right)\cup\bigcup_{k=1}^{\infty}f\left(A_{k}\right)\right)\right\} \\ & =f\left(A\right)\cup\left\{ Y\setminus\left(\left(g^{\bullet}\left(X\right)\setminus g^{\bullet}g\left(Y\right)\right)\cup f\left(\bigcup_{k=1}^{\infty}A_{k}\right)\right)\right\} \\ & =f\left(A\right)\cup\left\{ Y\setminus\left(\left(Y\setminus Y\right)\cup f\left(A\right)\right)\right\} \\ & =f\left(A\right)\cup\left\{ Y\cap f^{c}\left(A\right)\right\} \\ & =f\left(A\right)\cup Y\\ & =Y \end{align*} となるので\(h\)は全射となる。
また、\(a,b\in A\)とすると、\(f\)は単射なのでこのとき\(h\)は単射。
\(a,b\notin A\)とすると、\(g\)は単射でその逆の写像になるのでこのとき\(h\)は単射。
\(a\in A_{n};b\notin A\)とすると、\(f\left(a\right)=g^{\bullet}\left(b\right)\)が成り立つならば、\(b=g\left(f\left(a\right)\right)\)となるので\(b\in A_{n+1}\)となり矛盾。これより、このとき\(h\)は単射。
これらより、\(h\)は単射となる。
故に\(h\)は全単射となるので、全単射は存在する。

解説

例として、\(X=\left\{ x_{1},x_{2},\cdots\right\} ,Y=\left\{ y_{1},y_{2},\cdots\right\} \)で、\(f\left(x_{n}\right)=y_{n+1},g\left(y_{n}\right)=x_{n+1}\)とする。
このとき、
\[ A_{1}=\left\{ x_{1}\right\} \] \begin{align*} A_{2} & =g\left(f\left(x_{1}\right)\right)\\ & =g\left(y_{2}\right)\\ & =x_{3} \end{align*} \begin{align*} A_{3} & =g\left(f\left(x_{3}\right)\right)\\ & =g\left(y_{4}\right)\\ & =x_{5} \end{align*} \begin{align*} A_{n} & =g\left(f\left(A_{n-1}\right)\right)\\ & =g\left(f\left(x_{2\left(n-1\right)-1}\right)\right)\\ & =g\left(f\left(x_{2n-3}\right)\right)\\ & =g\left(y_{2n-2}\right)\\ & =x_{2n-1} \end{align*} となる。
これは、\(x_{1}\rightarrow\left(f\left(x_{1}\right)=y_{2}\right)\rightarrow\left(g\left(y_{2}\right)=x_{3}\right)\rightarrow\left(f\left(x_{3}\right)=y_{4}\right)\rightarrow\cdots\)となっている。
\(A_{1}\)は\(g\)で写されない点の集合となり、そこから\(f,g,f,g,\cdots\)と作用させているのである。
これを使って\(h\left(x\right)\)を全射にするが、\(g\)は単射なので逆写像が存在する点では基本的に\(g^{\bullet}\)を使うが、そのままでは\(g\)は全射ではないのでできない。
まず、\(g\left(Y\right)\)で写されない点\(x\in A_{1}\)については、\(f\left(x\right)\)に写るとして、そうすると、\(gf\left(x\right)\)を\(g^{\bullet}gf\left(x\right)=f\left(x\right)\)に写せなくなるから、\(gf\left(x\right)\)を\(fgf\left(x\right)\)に写すと順次対応していくのである。
そのため、\(A\)に含まれている点と含まれていない点に分けて考える。
\(A\)に含まれているものは
\begin{align*} h\left(x_{1}\right) & =f\left(x_{1}\right)\\ & =y_{2} \end{align*} \begin{align*} h\left(x_{3}\right) & =f\left(x_{3}\right)\\ & =y_{4} \end{align*} \begin{align*} h\left(x_{2n-1}\right) & =f\left(x_{2n-1}\right)\\ & =y_{2n} \end{align*} としている。
\(g\)は単射なので、\(A\)に含まれていない点\(x\in X\)は、ある\(y\in Y\)が唯一存在し、\(g\left(y\right)=x\)となるので、
\begin{align*} h\left(x_{2}\right) & =g^{\bullet}\left(x_{2}\right)\\ & =y_{1} \end{align*} \begin{align*} h\left(x_{4}\right) & =g^{\bullet}\left(x_{4}\right)\\ & =y_{3} \end{align*} \begin{align*} h\left(x_{2n}\right) & =g^{\bullet}\left(x_{2n}\right)\\ & =y_{2n-1} \end{align*} とできる。
こうして\(h\left(x\right)\)を全射にしているのである。

\(\Leftarrow\)

\(X\)から\(Y\)への全単射が存在するとき、明らかに\(X\)から\(Y\)への単射が存在する。
また、\(X\)から\(Y\)への全単射が存在するので逆写像が存在し、逆写像にもその逆写像つまり元の写像が存在するので、逆写像も全単射となる。
これより、逆写像は単射でもあるので、\(Y\)から\(X\)への単射が存在する。
従って、\(X\)から\(Y\)への単射が存在し、\(Y\)から\(X\)にも単射が存在するので\(\Leftarrow\)が成り立つ。

\(\Leftrightarrow\)

これらより\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。

(2)

\(\Rightarrow\)

\(X\)から\(Y\)への単射を\(f\)、\(Y\)から\(X\)への全射を\(g\)とする。
写像\(g\)を\(y\in f\left(X\right)\)なら\(f\)は単射なので\(f\left(x\right)=y\)を満たす\(x\)が1つのみ存在するので\(g\left(y\right)=f^{\bullet}\left(y\right)\)として、\(y\notin f\left(X\right)\)なら適当に\(x_{0}\in X\)を選んで、\(g\left(y\right)=x_{0}\)とする。
すなわち、
\[ g\left(y\right)=\begin{cases} f^{\bullet}\left(y\right) & y\in f\left(X\right)\\ x_{0}\in X & y\notin f\left(X\right) \end{cases} \] という\(g\left(y\right)\)を作る。
そうすれば任意の\(x\in X\)の要素に対し\(g\left(y\right)=x\)となる\(y\)は存在するので\(g\)は全射となる。

\(\Leftarrow\)

\(Y\)から\(X\)への全射を\(g\)、\(X\)から\(Y\)への単射を\(f\)とする。
\(g\)は全射なので、任意の\(x\in X\)に対し、\(g\left(y\right)=x\)となる\(y\in Y\)が少なくとも1つ存在する。
\(f\)として、選択公理より、\(g\left(y\right)=x\)を満たす\(y\in Y\)を1つ選べるので、その\(x,y\)について\(f\left(x\right)=y\)とする。
任意の\(x_{1},x_{2}\in X\)をとると、\(f\left(x_{1}\right)=f\left(x_{2}\right)\)のとき、\(x_{1}=g\left(f\left(x_{1}\right)\right)=g\left(f\left(x_{2}\right)\right)=x_{2}\)となるので、\(X\)から\(Y\)への単射が存在する。

-

これらより、\(\Rightarrow\)と\(\Leftarrow\)が成り立つので\(\Leftrightarrow\)が成り立つ。

(3)

条件より、\(X\)から\(Y\)への全射が存在するので、選択公理を認めると\(Y\)から\(X\)への単射が存在する。
同様に、条件より、\(Y\)から\(X\)への全射が存在するので、選択公理を認めると\(X\)から\(Y\)への単射が存在する。
これより、\(X\)から\(Y\)への単射が存在し、\(Y\)から\(X\)への単射が存在するので、ベルンシュタインの定理より、\(X\)から\(Y\)に全単射が存在する。
従って題意は成り立つ。

(4)

\(X\)から\(Y\)への全射が存在するので、選択公理を認めると\(Y\)から\(X\)への単射が存在する。
これより、\(X\)から\(Y\)への単射が存在し、\(Y\)から\(X\)への単射が存在するので、ベルンシュタインの定理より、\(X\)から\(Y\)に全単射が存在する。
従って題意は成り立つ。