数学 – 集合と写像 - 写像に関する諸概念(有限集合, 部分集合の総数)

集合・位相入門
(岩波書店)
松坂 和夫 (著)

学習環境

• 数式入力ソフト(TeX, MathML): MathType
• MathML対応ブラウザ: Firefox、Safari
• MathML非対応ブラウザ(Internet Explorer, Google Chrome...)用JavaScript Library: MathJax

集合・位相入門(松坂 和夫(著)、岩波書店)の第1章(集合と写像)、4(写像に関する諸概念)、問題17.を解いてみる。

問題17.

Aをm個の元から成る有限集合とする。B'をBのm個の元から成る部分集合とする。

そのとき、AからB'への単射の総数は、${\left(m\right)}_m=m!$ となる。

問題の規定より、Bのm個の元から成る部分集合の総数は、$\left(\begin{array}{l}n\\ m\end{array}\right)$なので、AからBへの単射の総数は、${\left(n\right)}_m=m!·\left(\begin{array}{l}n\\ m\end{array}\right)$ 。

よって、$\left(\begin{array}{l}n\\ m\end{array}\right)=\frac{{\left(n\right)}_m}{m!}$である。

$\left(\begin{array}{l}n\\ 0\end{array}\right)+\left(\begin{array}{l}n\\ 1\end{array}\right)+···+\left(\begin{array}{l}n\\ n\end{array}\right)$はBの部分集合の総数なので、$2^n$ 。

$b_0$ をBの元とする。XをBの偶数個の元から成る部分集合全部の集合、YをBの奇数個の元から成る部分集合全部の集合とする。

その時、Yの各元yに対し、$b_0$を含むなら、$y-\left\{b_0\right\}$、含まないなら$y\cup \left\{b_0\right\}$ とした元の集合をY'とする。そしてその元同士を対応させた写像を考えると、それは全単射となる。

また、Y'はBの偶数個の元から成る部分集合全部の集合と一致する。

よって、XからYへの写像で全単射が存在し、XとYの元の個数、すなわちBの偶数個の元から成る部分集合全部の集合の元の個数とBの奇数個の元から成る部分集合全部の集合の元の個数は等しい。

よって、$\left(\begin{array}{l}n\\ 0\end{array}\right)-\left(\begin{array}{l}n\\ 1\end{array}\right)+···+{\left(-1\right)}^{-1}\left(\begin{array}{l}n\\ n\end{array}\right)=0$ である。