濃度
Contents
濃度とは
濃度 (英:cardinality) とは、二つの集合の元に対する、一般化された個数比較の概念こと。
\[ \mathfrak a = |A| \]
濃度の二項関係
濃度の比較は、単射・全射・全単射を用いて定義付けられる。また二項関係 $\le$ は、反射性, 推移性, 反対称性を満たすため、半順序でもある。
大小関係:
始集合 $A$ から終集合 $B$ に対して単射が存在するとき、$A$ の濃度は $B$ の濃度以下である。
\[ \exists f:A\hookrightarrow B\lrArr |A|\le |B| \]
始集合 $A$ から終集合 $B$ に対して全射が存在するとき、$A$ の濃度は $B$ の濃度以上である。
\[ \exists f:A\twoheadrightarrow B\lrArr |A|\ge |B| \]
相等関係:
二つの集合 $A,B$ の間に全単射が成り立つとき、$A,B$ の濃度は等しい。
\[ \exists f:A\lrarr B\lrArr |A|=|B| \]
濃度の二項演算
二つの集合の濃度に対して、以下の二項演算を定義することができる。
加法:
\[ \mathfrak a +\mathfrak b = |A\sqcup B| \]
乗法:
\[ \mathfrak a\mathfrak b = |A\times B| \]
冪法:
\[ \mathfrak a^\mathfrak b = |\mathrm{Map}(B,A)| \]