2^κ - κ = 2^κ のやつ

lemma.txt

補題: Xを集合、 f: X -> 2 * P(X) 単射 とする。 g: P(X) -> 2 * P(X) 単射 であって像がfと非交なものが存在する。

証明:

A in P(X) とする。(1,A)がfの像でないときはg(A)=(1,A)と定める。
以下(1,A)がfの像でないときを考える。f(y)=(1,A)とする。(fが単射なのでyは一意にとれる)

B = { x in X | (x notin π2(f(x))) xor x=y} (π2は第二射影)

とおくと(0,B)はfの像ではない。もしf(z)=(0,B)とするとz != yであるから、
z in π2(f(z))
<=> z in π2((0,B))
<=> z in B
<=> (z notin π2(f(z))) xor z=y
<=> z notin π2(f(z))
となり矛盾する。

そこでg(A)=(0,B)と定める。このgの定義では非決定的な選択をしていないのでgは選択公理によらずにとれる。

gがfと非交であることは既に示してあるので、単射であることを示す。
g(A)=g(A') とする。(1,A), (1,A')のいずれもfの像でない場合は明らかにA=A'である。
どちらか片方だけがfの像でない場合には左の値が異なるので矛盾する。
そこで、(1,A), (1, A')のいずれもfの像である場合を考える。このときf(y)=(1,A), f(y')=(1,A')を用いて
g(A) = (0, { x in X | (x notin π2(f(x))) xor x=y})
g(A') = (0, { x in X | (x notin π2(f(x))) xor x=y'})
と書けるから、
y in π2(g(A)) <=> y in π2(g(A'))
となり、したがって
y=y <=> y=y'
となる。左辺は恒真なのでy=y'が成立する。したがってA=A'である。

(証明終了)