人気ブログランキング | 話題のタグを見る

べき集合の濃度

任意の集合Xのべき集合2^XとXの全単射が存在しないことは次のように証明できる。

いまψを集合Xから2^Xへの写像であるとする。Xの部分集合Yを

Y = {x| x ∈ X, x /∈ ψ(x)}

と定義すると、Yは明らかにXの部分集合であるから、Y ∈ 2^X である。また、

x ∈ Y ⇔ x ∈ X ∧ x /∈ ψ(x)

である。いま x0 ∈ X で、ψ(x0) = Y であるとする。すると上の式から、もし、x0 ∈ Y ならば、x0 /∈ ψ(x0) = Y でなければならない。また、x0 /∈ Y であるとしても、やはり上の式から x0 ∈ Y でなければならないことになってパラドックスが発生する。したがって、ψ(x) = Y となるような、x を X の要素に見つけることはできない。

この推論は、「集合Aの要素のうちの自分自身を要素として含まない集合を集めた集合R'」が集合Aの要素として含まれることはないことを証明するときのR'の定義式、

x ∈ R' ⇔ x ∈ A ∧ x /∈ x

と全く同じ形をしている。その後の議論も全く同じだ。実際 X -> X の恒等写像を 1(x) とすると、この定義式は、

x ∈ R' ⇔ x ∈ A ∧ x /∈ 1(x)

となって、べき集合の議論と全く同型の式になる。集合からその冪集合への写像が全射でないことの証明は、ラッセルのパラドックスの証明と全く同じ議論になる。

さらに、∈ 記号が、p(x, y) -> {1, 0} という要素 x, y から2値集合 {1, 0} への写像と同一視できるため、次の、関数型の対角線論法が適用できることがわかる。

x を集合とし、φ : X × X -> {0, 1} を写像とする。φ(x, y) を φx(y) と書くことにすると、各 x ∈X に対し φx は x ∈ X から {0, 1} への写像である。ここで g : X -> {0, 1} を g(x) = ¬φx(x) で定義すると、このとき、φx0 = g となる x0 ∈ X は存在しない。

なぜなら、g(x0) = ¬φx0(x0) = ¬g(x0) となって、g(x0) が¬演算子の不動点になってしまうからだ。

また、床屋のパラドックスについても、自然数と実数の濃度についてのパラドックスについても全く同じ形式の議論を適用することができる。

したがって、上の議論で述べたように、対角線論法では、∈記号が何を表しているかに関係なく、式の置き換えだけで議論をすすめることができる。集合の直積集合から2値集合 {0, 1} への関数について考える場合、対角線論法はどのような場合にも成り立ち、その議論は、記号列の置き換え、つまり記号の統語論的な推論で証明されてしまう。

言い換えると、対角線論法は、∈記号の内容なんであれ、記号の操作で証明できてしまうということだ。

x ∈ A という式を見ると、要素 x が 集合 A の要素であることをイメージするが、要素 x と要素 A が夫婦であることを意味していると考えても、対角線論法の結論は有効なのだ。

参考サイト: Wikipedia の対角線論法の記述
by tnomura9 | 2011-05-08 09:11 | 考えるということ | Comments(0)
<< 関数の対角線論法 アリストテレスの解決 >>