自然数の大小関係と有限集合の濃度の大小関係の対応について

1. $f(x)=y$のとき、$g=f$とすればよい。
2. $f(x)\neq y$かつ$b\in \mathrm{Im} f$のとき、単射性より$f(x^{\prime})=y$となる$x^{\prime}\in X$がただ一つ存在して、$x^{\prime}\neq x$となる。$f(x)=y^{\prime}$として、
   $$G:=\{(a,b)|a\in X-\{x,x^{\prime}\},b=f(a)\}\cup \{(x,y),(x^{\prime},y^{\prime})\} $$
   とすれば$g:=< X,Y,G>$は条件を満たす。
   3.$f(x)\neq y$かつ$b\notin \mathrm{Im} f$のとき、
   $$G:=\{(a,b)|a\in X-\{x\},b=f(a)\}\cup \{(x,y)\} $$
   とすれば$g:=< X,Y,G>$は条件を満たす。

• $n=1$のとき、単射$f:\{1,2,\cdots,m\} \to \{1\}$がが存在すると仮定して矛盾を導く。関係$g$を
  $$g:=<\{1\},\{1,2,\cdots,m\},\{(1,1)\} >$$
  で定義すると、$g$は$\{1\}$から$\{1,2,\cdots,m\}$への単射である。よって、ベルンシュタインの定理より、全単射
  $$h:\{1\}\to\{1,2,\cdots,m\}$$
  が存在する。$h$の全射性より$h(1)=1$かつ$h(1)=2$が成立するが、$h$は写像なのでこれは矛盾する。よって単射$f$は存在しない。
• $n=k$のときに成立すると仮定すると、$n=k+1$のときに単射$f:\{1,2,\cdots,m\}\to\{1,2,\cdots,k+1\}$が存在しないことを、単射$f:\{1,2,\cdots,m\}\to\{1,2,\cdots,k+1\}$が存在すると仮定して矛盾を導くことで証明する。補題4より、単射$g:\{1,2,\cdots,m\}\to\{1,2,\cdots,k+1\}$で$g(m)=k+1$となるものが存在する。よって、
  $$h:=<\{1,2,\cdots,m-1\},\{1,2,\cdots,k\},\{(a,b)|a\in \{1,2,\cdots,m-1\},b=g(a)\}>$$
  として単射
  $$h:\{1,2,\cdots,m-1\}\to\{1,2,\cdots,k\}$$
  が構成できる。しかしこれは$n=k$の仮定に矛盾する。したがって、$n=k+1$のときも成立する。

数学的帰納法により命題5は成立することがわかる。

• 前半について
  仮に、対応する数字が2つあるとする。$m,n$と置くと、自然数は大小関係において全順序なので$m>n$または$n>m$のどちらか一方が成立する。$m>n$としても一般性を失わないので以降$m>n$とする。定義1より全単射$f:\{1,2,\cdots,m\}\to A$および全単射$g:\{1,2,\cdots,n\}\to A$が存在する。このとき
  $$g^{-1}\circ f:\{1,2,\cdots,m\}\to \{1,2,\cdots,n\}$$
  は全単射となるがこれは命題5に矛盾する。対応する数字が3つ以上あるときも同様に矛盾することが示せる。
• 後半について
  $|A|>|B|$のとき、単射$h:B\to A$が存在し、全単射$f:\{1,2,\cdots,m\}\to A$および全単射$g:\{1,2,\cdots,n\}\to B$が存在する。
  $$f^{-1}\circ h \circ g:\{1,2,\cdots,n\}\to \{1,2,\cdots,m\} $$
  は単射なので命題5より$m\geq n$である。$m=n$とすると、
  $g\circ f^{-1}:A\to B$は全単射となるが、これは$|A|>|B|$に矛盾する。よって$m>n$となる。
  逆に、$m>n$のとき、$|A|\leq|B|$と仮定すると、単射$h:B\to A$が存在し、上の$f,g$に対して
  $$f^{-1}\circ h \circ g:\{1,2,\cdots,m\} \to \{1,2,\cdots,n\}$$
  は単射となるから、定理5より$m\leq n$となり矛盾する。よって$|A|>|B|$