冪集合の要素の個数

$X：集合$

$\mathfrak{P}(X)：Xの冪集合$

とする．このとき

$∀x［x∈\mathbb{N}→∃x［x∈\mathbb{N}∧x=a］］$ 　( $aは自由変項$ )

$x=［n］_\mathbb{N}$ 　(∀-除去)

$Xの元の個数|X|=n$

に対して， $\mathfrak{P}(X)$ の元の個数は $2^n$ であること，すなわち

$|\mathfrak{P}(X)|=2^n$

を示せ．

(証明)

　二重否定除去則で示す．

1　(1)　 $￢(\mathfrak{P}(X)=2^n)$ 　　仮定

$n:=1$ と置く．このとき $|X|=1$ であるから，たとえば $X:=\{1\}$ と置けば，冪集合の定義により $\mathfrak{P}(X)=\{\varnothing,\{1\}\}$ を構成できる．

1　 (2)　 $|\mathfrak{P}(X)|=2$ 　　冪集合の定義による

1　 (3)　 $\perp$ 　　1,2.￢-除去

　 (4)　 $￢￢(\mathfrak{P}(X)=2^n)$ 　　1-3.￢-導入

　 (5)　 $\mathfrak{P}(X)=2^n$ 　　4.DN規則

　したがって， $|\mathfrak{P}(X)|=2^n$ が示された．▢

日記2