Boole代数雑記
自分あてのメモ
定理:Boole代数が無限であることと非単項超フィルターを持つことは同値
まず,以下の補題を示す.
補題1:atomic無限Boole代数のatomは無限に存在する
[証明] atomic Boole代数についてatomが有限であると仮定する. このとき,各は,とすると を満たす.なぜなら,とすると,より なるatomが取れるからである.このときかつとなり矛盾. したがってという対応は単射なので,の濃度はatom全体の集合をとしたとき,の濃度以下である. q.e.d.
[定理の証明] を有限とし,をの超フィルターとする. は有限のフィルターなのでであり,はにより生成される. すなわち,は単項フィルター .
が無限であるとする.
がatomicであるとする.このとき,をのatom全体として,とする. が有限交叉性を持つことを示す. とすると,となる. このとき,補題からと異なるatom をとることができるが, となり矛盾. したがって,は超フィルターへと拡大できるが,このフィルターはatomを含まないので単項でない.
また,がatomicでないとすると,あるについて,なるatomは存在しない. このとき,から生成されるフィルターを拡大して得られる超フィルターは非単項である. なぜなら,がatom により生成されるとするととなり矛盾するからである. q.e.d.
Stoneの表現定理その3 フィルター
Stoneの表現定理その2 Boole代数の原子
この記事は
の続きです.
前回はBoole代数を定義して,順序を導入しました.
今回は導入した順序を元にBoole代数の性質を確認し,Boole代数の原子を定義します.
- 順序の性質
- Boole代数の原子
- 参考文献
端点なしの可算稠密線形順序とは,すなわち有理数上の順序
この記事は 好きな証明 Advent Calendar 2018 - Adventar の2日目の記事です.
1日目は鯵坂もっちょさんの www.ajimatics.com でした
端点なしの可算稠密線形順序は同型を除いて一意に定まります.今回はこの定理の証明を紹介したいと思います.
用語の確認
まずは用語の確認です.
- 線形順序とは,任意の2元が比較可能な順序です.全順序とも言います.
- 稠密順序とは,任意のに対してあるがあって,となる順序です.
- 線形順序が端点を持たないとは,任意のに対して,あるがあってとなることを言います.すなわち,最大元も最小元も持たない線形順序です.
ところで,稠密線形順序(Dense Linear Order)は英語の頭文字をとってDLOと呼ばれることが多いので,以下そのように書くことにします.
具体例
では,端点なしの可算DLOとしてどんなものがあるでしょうか?
すぐに出てくる例として,有理数全体に通常の順序を入れたものが挙げられます.これが端点なしの可算DLOであることはすぐに確認できますね.
定理:端点なしの可算DLOは全て同型である
[証明] を端点なしの可算DLOとする. また,とする.
以下のようにして,をにより数え上げる.
まず,とする.
次に,とする.このとき,次のようにを定める:
であれば,となる最小のを取り,とする.
の場合,として,あとは同様である.
今度は,をの元で,による番号が最小のものとする.
このとき,の大小関係は以下の3パターンのいずれかである.
- が最小である.
- が最大である.
- はとの間に入る.
1.の場合,より小さいのうち,番号が最小のものを取りとする. 他の2パターンの場合も同様に,順序を保つようにを定める(いずれの場合も,は端点なしかつ稠密なので対応する元を取ってくることができる).
以下は同様に,に対して順序を保つようにを定め, 次にに対して順序を保つようにを定める,というのを繰り返していけば良い. はまだによって数え上げられていないもののうち,による番号が最小のものをとってきているので,による数え上げがによる数え上げを網羅しているのは明らかである. また,各に対してとが同型になるようにを定めたので, とが同型となることも直ちに従う. //
かくして,端点なしの可算DLOは全て同型であることが示されました. 具体例のところで書いた通り,有理数上の通常の順序は端点なしの可算DLOでした.したがって,「端点なしの可算稠密線形順序とは,すなわち有理数上の順序」というわけです.
往復論法
この証明のポイントは,基準となる元をから交互にとることで,が全体を数え上げている,という点です. 常に片側を基準にしていると,埋め込みを構成することはできるのですが,全射になっているかどうかはわからないというわけですね.*1
このように,の両側から交互に基準を取って同型を作る方法は,往復論法(back-and-forth)と呼ばれています.数学基礎論でよく使われる手法で,上記の例に限らず,構造同士が同型であることを示すのに役立ちます.便利な手法ということで,好きな証明方法の一つです.