べき集合の濃度

（命題） 任意の集合 S に対して， |S| < |P(S)|
（証明）

1. |S| ≤ |P(S)| であること

|S| = |T| となる T ⊆ P(S) が存在することを示す．

ここで T = { {x} | x ∈ S } を選べば，明らかに |S| = |T|．




2. |S| ≠ |P(S)| であること

背理法を用いて示す．

一対一対応 f: S → P(S) が存在すると仮定する．

f を用いて，新たに集合 V = { x ∈ S | x ∉ f(x) } を定義する．

このとき，V ⊆ S より V ∈ P(S) である．

よって，f(a) = V となる元 a ∈ S がただ1つ存在する．




1. a ∈ V のとき

V = f(a) より a ∈ f(a) ．

このとき，V の定義より a ∉ V となり矛盾する．


2. a ∉ V のとき

V = f(a) より a ∉ f(a) ．

このとき，V の定義より a ∈ V となり矛盾する．



仮定から矛盾が導かれたので，|S| ≠ |P(S)| が成り立つ．

以上より，与命題は示された．■

（補足）

「2. |S| ≠ |P(S)| であること」 は対角線論法によって証明している．

a₁ ∉ f(a₁) ， a₁ ∈ f(a₂) ， a₁ ∈ f(a₃) ，...
a₂ ∈ f(a₁) ， a₂ ∉ f(a₂) ， a₂ ∈ f(a₃) ，...
a₃ ∈ f(a₁) ， a₃ ∈ f(a₂) ， a₃ ∉ f(a₃) ，...
: