濃度 - イガブロギュ

集合の"大きさ"を比べるには, 二つの集合間の写像を考えると都合がよいのです.
例えば, 二つの集合間に全単射が存在すれば, 二つの集合の"大きさ"は等しいと考えることができます.
というわけで, $X$ , $Y$ の間に全単射が存在するとき
$|X|=|Y|$
とかき, 二つの集合は同じ濃度(cardinality)を持つとか, equipotent であるなどと言います.
これが同値関係になることは明らかです.
さて, 各集合 $X$ に対してその濃度 $|X|$ を表す集合として基数(cardinal number)というものを考えたいと思います.
しかしながら, 各集合 $X$ に対してその濃度が存在することを言うためには, 正則性の公理か選択公理が必要であることが知られています.
選択公理を使うと, これは「任意の集合を整列順序づけられる」という主張と同値であることが証明できるので, 整列順序を用いて基数を定義することができるのであります.
基数の定義は後回しにして, その前に基数の順序を定義しておきます.
$X$ から $Y$ への単射が存在するとき, $|X| \leq |Y|$ と定義します.
特に, 全射が存在しないなら $|X| < |Y|$ とします.
これは半順序で, さらに選択公理を仮定すると全順序になることが確かめられます.
ところで, 次が成り立ちます.

任意の $X$ に対して $|X| < |P(X)|$ .

基数はまだ定義していませんので, 単射が存在して全射は存在しないという主張です.

証明
$X$ から $P(X)$ への全射が存在しないことをみるために, 任意の写像 $f:X \rightarrow P(X)$ に対してある $Y \subset P(X)$ が存在して, それが $f$ の像に含まれないことをみます.
$Y = \{x \in X : x \notin f(x)\}$
と定義します.
ここで, $f(z) = Y$ となる $z \in X$ が存在したとすると
$z \in Y$ なら $z \notin f(z) = Y$ となり矛盾し,
$z \notin Y$ なら $z \in f(z) = Y$ となり, やはり矛盾.
以上により, 全射は存在しないことが分かりました.
$X$ から $P(X)$ への単射が存在することは明らかです.

次の定理は, 高校数学で言うところの「はさみうちの原理」のようなもので, あとの証明に使われます.

$A_1 \subset B_0 \subset A_0$ かつ $|A_1| = |A_0|$ ならば $|A_1| = |B_0| = |A_0|$ .

証明
$f$ を $A_0$ から $A_1$ への全単射とします.
そして,
$A_{n+1} = f(A_n)$
$B_{n+1} = f(B_n)$
と定義します.
明らかに
$A_n \supset A_{n+1}$ , $B_n \supset B_{n+1}$ です.
さらに, $A_0 \supset B_0$ より $A_n \supset B_n$ です.
ここで, $C_n = A_n \setminus B_n$ とし,
$C = \bigcup_{n=0}^{\infty}C_n$ , $D=A \setminus C$ とおきます.
$f$ が単射であることにより
$f(C_n) = f(A_n \setminus B_n) = f(A_n) \setminus f(B_n) = A_{n+1} \setminus B_{n+1} = C_{n+1}$
なので
$f(C) = \bigcup_{n=0}^{\infty}f(C_n) = \bigcup_{n=0}^{\infty} C_{n+1} = \bigcup_{n=1}^{\infty} C_n$ .
そして, $A_0$ から $B_0$ への写像 $g$ を, $x \in C$ なら $g(x)=f(x)$ , $x \in D$ なら $g(x)=x$ と定義します.
$x \in C$ なら $f(x) \in C$ であることにより $f|C$ と $f|D$ の値域は互いに素で, それぞれ単射なので, $g$ は単射です.
また, $g$ の値域は $f(C) \cup D = A_0 \setminus C_0 = B_0$ です.
よって $g$ は全単射ですぞ.

他にも色々な証明が知られているようです.
ともあれ, このことから直ちに次の定理が導かれ, 基数の順序が半順序になることが分かります.

$|A| \leq |B|$ かつ $|A| \geq |B|$ ならば $|A| = |B|$ .

証明
$A$ から $B$ への単射を $f$ ,
$B$ から $A$ への単射を $g$ とおきますよ.
明らかに $g(f(A)) \subset g(B) \subset A$ です.
$g \circ f:A \rightarrow A$ は単射で値域が $g(f(A))$ なので $A$ から $g(f(A))$ への全単射が存在することになり $|A| = |g(f(A))|$ .
同じ理屈で $|B| = |g(B)|$ .
そんなわけで, 上の定理で $A_0 = A$ , $B = g(B)$ , $A_1 = g(f(A))$ とおけば証明終了です.

基数の演算は次のように定義されます.

$|A| = \kappa$ , $|B| = \lambda$ で $A$ と $B$ が互いに素のとき
$\kappa + \lambda = |A \cup B|$ .
$\kappa \cdot \lambda = |A \times B|$ .
$\kappa^{\lambda} = |A^B|$ .

集合 $A$ と $B$ の選び方によらないことは明らかです.