計算機科学のブログ

帰納的定義と証明技法 集合の有限の濃度と冪集合の濃度、帰納法

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第3章(帰納的定義と証明技法)、章末問題の問3.1の解答を求めてみる。

集合Aの濃度が0のとき、 すなわち空集合のとき、そのべ
き集合は

P ( A ) = P ( ϕ ) = { ϕ }

よって、濃度は

1 = 2 0

また、 Aの濃度をm、aをAに含まれない要素とする。

このとき、

B = A ∪ { a }

の濃度は

m + 1

で、 集合

P ( B ) \ P ( A )

の元は

P ( A )

の各元と集合

{ a }

との和集合なので、

よって、

card P ( B ) = card ( P ( A ) ∪ P ( B ) \ P ( A ) ) = 2 · 2 n = 2 m + 1

よって、帰納法により成り立つ。

（証明終）