お勉強の記録

勉強したことを書いたりする予定

対角線論法 ブール代数編

この記事は

好きな証明 Advent Calendar 2018 - Adventar 14日目の記事です

今回のテーマはみんなが大好き対角線論法についてです．

対角線論法

対角線論法といえば，実数が自然数より多いこと，あるいはより一般にベキ集合の濃度がもとの集合*1の濃度より大きいことを証明するときに使われる方法として有名ですね．さっくり説明すると， Xの部分集合のリスト \{A_i: i \in I\}が与えられたときに，各iに対して b_i \in A_i^cを取ってくることで \{b_i: i \in I\}という新しい部分集合を得ること，といった感じでしょうか． Iや b_iの取り方を工夫することで様々な応用の効く議論です．たとえば， |X| \lt |\mathcal{P}(X)|の証明だと I =Xとして， x \not \in A_x のとき b_x = xとします( x \in A_xのときは b_xは定義しません)． 定義された b_x全体を集めると， \{A_x : x \in X\}に現れない新たな部分集合が得られるので， Xから \mathcal{P}(X)への全射は存在しない，ということがわかります．

上の議論はかなり有名だと思いますが，それ以外の例となるとパッと出てくることってあんまりないような気がします*2．せっかく便利な論法なので，他の使用例を紹介します．

準備

\mathcal{P}(X)を Xのベキ集合とし， B \subseteq \mathcal{P}(X)を集合体とします． Bの空でない部分集合 Fは以下の条件を満たすとき，フィルターと呼ばれます．

  • \varnothing \not \in F

  • \forall x,y \in B \ (x \in F & x \subseteq y \Rightarrow y \in F)

  • \forall x,y \in F \ (x \cap y \in F)

\varnothing \neq x \in Bに対して， \{ y \in B: x \subseteq y\}はフィルターとなります．これを xの生成する単項フィルターと呼びます．

フィルター Fが \forall x \in B \ (x \in F または x^c \in F)を満たすとき， Fを超フィルターと言います． この条件は， Fが包含関係について極大なフィルターであることと同値です． Bの部分集合族が有限交叉性を持つとき(すなわち，任意有限部分の共通部分が空でないとき)，それを包含するような超フィルターが存在します．

また， B \setminus \{\varnothing \}の中で包含関係について極小な物を Bの原子と呼びます． 任意の x \in Bについて， x \neq \varnothingのときに y \subseteq xとなる原子 yが存在するとき， Bは原子的であると言います．超フィルターが単項であることと原子から生成されることは同値です．

定理

定理：非単項超フィルターが高々可算な集合体は原子的である．

[証明] Bの非単項超フィルターを p_0 ,p_1, \ldots と数え上げる． 「 x \neq \varnothingについて， x \supseteq x_0 \supseteq x_1 \cdotsというそれぞれの項が空でない降下列で x_i \not \in p_iとなるものが取れる *3． このとき \{x, x_0 , x_1, \ldots \}は有限交叉性を持つので超フィルター pへと拡大できるが，各 iについて p \neq p_iである．」 したがって pはある原子 yにより生成される単項フィルターであるが，このとき y \subseteq xである． q.e.d.


上の証明で，カギカッコに囲まれた部分が対角線論法を使っている部分になります．非単項超フィルターの数え上げに入らない超フィルターが得られたので，それは単項である，というわけです．

*1:余談だが漢字で書くと元の集合となり，的を射てるんだが紛らわしんだかよくわからない表記となります

*2:計算論だとc.e.集合であって計算可能でないものの存在とかが有名ですが…．

*3: xが原子のときは x= x_0 とすればよい．そうでないときは \varnothing \subsetneq x' \subsetneq xが取れるので， x' \not \in p_0であれば x_0=x'，そうでなければ x_0= x \cap x'^cとすればよい．以下， x_{i+1}についても同様に x_iから得られる．