4.5 有限集合の濃度

有限集合 (finite set) とは有限個の要素しか持たない集合を意味する。集合の要素数を集合の濃度 (cardinality) と呼ぶ:

有限集合は要素を \(0\) 個持つ (空集合である) か、\(1\) 個持つか、\(2\) 個持つか、\(\ldots\ \) のいずれかなので、有限集合の濃度は常に非負整数である。

\(R\colon A \to B\) を関数とする。このとき \(R\) を図示すると、\(A\) の要素ごとに最大 \(1\) 本の矢印が存在する。よって \(R\) が関数なら次の不等式¹が成り立つ:

もし \(R\) が全射なら、\(B\) の全ての要素に対応する矢印が存在する。よって矢印は少なくとも \(B\) のサイズと同じだけ存在する:

二つの不等号を組み合わせると、\(R\) が全射なら \(|A| \geq |B|\) が成り立つと分かる。

\(A\) から \(B\) への全射関数が存在するとき、省略して \(A \mathrel{\text{\small surj}} B\) と書く。前段落で示した事実は「\(A\), \(B\) が有限集合で \(A \mathrel{\text{\small surj}} B\) なら \(|A| \geq |B|\)」と表現できる。次の定義と補題は二項関係の特徴を始域と終域のサイズの大小に関連付ける:

証明 \(\text{1.}\) の含意は先ほど示した。\(\text{2.}\) の含意は次のように示せる: 二項関係 \(R\) が関数の条件「外 \(\leq 1\)」と全射の条件「内 \(\geq 1\)」を満たすとき、\(R^{-1}\) は全域かつ単射になる。つまり \(A \mathrel{\text{\small surj}} B \ \longleftrightarrow\ B \mathrel{\text{\small inj}} A\) であり、ここから \(\text{2.}\) の含意は直ちに従う。最後に、全単射は全射関数かつ全域単射関係なので、\(\text{3.}\) の含意は最初の二つの不等式から分かる。 ■

補題 4.5.3 は逆方向にも成り立つ: \(A\), \(B\) が有限集合で \(|A| \geq |B|\) なら、\(A\) から \(B\) への全射関数が存在する。実は、この全射関数は全域関数にできる。この事実を確認するために、次の例を考えよう:

このとき全域関数 \(f\colon A \to B\) を次の規則で定義する:

さらに正確に表現すれば:

\(5 \geq 3\) より、\(f\) は全射になる。

よって \(A\), \(B\) が有限集合のとき \(|A| \geq |B|\) と \(A \mathrel{\text{\small surj}} B\) が同値だと分かった。他の含意に関しても同様の議論を行うと、有限集合の濃度と特定の特徴を持った関係の存在を結び付ける次の定理が得られる:

4.5.1 有限集合の部分集合の個数

全単射に関する写像則 (定理 4.5.4) の使用例として、次の事実の簡単な証明を示す:

例えば \(3\) 要素集合 \(\left\{ a_{1}, a_{2}, a_{3} \right\}\) は次に示す \(8\) 個の部分集合を持つ:

定理 4.5.5 は、\(A\) の部分集合全体の集合から長さ \(n\) のビット列全体の集合 \(\left\{ 0, 1 \right\}^{n}\) への単純な全単射が存在する事実から示せる。具体的には次の通りである。\(a_{1}\), \(a_{2}\), \(\ldots\), \(a_{n}\) を \(A\) の要素とする。任意の部分集合 \(S \subseteq A\) を次の規則を満たすビット列 \((b_{1}, \ldots, b_{n})\) に対応付ける次の関係は全単射である:

例えば \(n=10\) のとき、部分集合 \(\left\{ a_{2}, a_{3}, a_{5}, a_{7}, a_{10} \right\}\) には次に示す長さ \(10\) のビット列が対応する:

よって全単射に関する写像則 (定理 4.5.4) より、次の等式が分かる:

情報科学者なら誰でも知っている²ように、長さ \(n\) のビット列は \(2^{n}\) 個ある！ これで定理 4.5.5 は証明された。