直観主義論理の入り口~Heyting 代数~(その 4)
束についてもう少し
一般の束に関する性質をもう少し見ていきましょう.
が成り立ちます(単調性).
これは
と からわかります.
また
… (*)
が成り立ちます. これは定義に従って地道に示せますので, 証明は省略します.
(*) 式から が導かれます. このことと単調性を上手く使うと
が示せます. (*) 式は自己双対ですが, 上の二式は互いに双対な式になっています. 逆にこの二式から (*) 式を示すこともできるので, この二式を合わせたものは (*) 式と同値です.
直観主義論理の入り口~Heyting 代数~(その 3)
圏としての束
もう少し束の話を続けたいのですが, 圏論の知識を持っているといろいろと楽なことが多いので, 束を圏とみなす方法を紹介します.
一般に束 はそれ自体半順序集合です. これを圏とみなすためには以下のようにします.
- 圏 の対象は の元.
- 圏 の対象 の間の射は
- 射 と射 に対して合成を で定義.
このとき が束であることと, が常に 2 個の対象の余積と積を持つことと同値です. 余積は交わり, 積は結びに相当します. また, が有界束であることは が(余積と積に加えて)始対象と終対象を持つことと同値です. 始対象は最小元 で終対象は最大元 になります. さらに, が完備束であることは が無限余積と無限積を持つことと同値です.
双対圏(逆圏)
一般に圏 が与えられたとき, その双対圏 が定義できます. の対象は の対象で, 射は において であるとき であるとします.
このとき, 例えば が始対象を持つならば、それは における終対象になっていますが, このような関係にある概念は互いに双対概念であると言います.
束を圏とみなしたとき, 交わりと結び, 最小元と最大元は互いに双対概念になっています. また, 束の命題について, その順序関係を逆にし, なおかつ交わりと結びを入れ替えたものが双対命題になっています. 束の双対はまた束なので, 束である命題が成り立つならば, その双対命題も成り立つことが分かります.
直観主義論理の入り口~Heyting 代数~(その 2)
有界束と完備束
有界束
束 は自然な方法で半順序集合とみなせることは前回分かりました. そうなると最小元や最大元は存在するのか, は自然な興味の対象になりますし, 当然ながら常に存在するとは限りません.
最小元と最大元がともに存在する束を有界束と言います. 束の場合は最小元は で, 最大元は で表すのが習わしです. 最小元と最大元については以下が成り立ちます.
証明はいずれも簡単なので省略します. 逆に代数的に定義した束 で, 上記の性質を満たす と があれば, が最小元, が最大元になります.
ちなみに最小元も最大元も存在すれば順序の意味では当然一意に定まりますが, 例えば の他に で を満たすものがあったとすれば
となり, そのような元は代数的にも一意に定まります.
さて, の空でない任意の有限部分集合 については交わりと結び
が自然に定義できます( のときは と約束する). なおかつ の空でない有限部分集合 については
が成り立つのですが, 仮に とすると
という式が出てきます.
気分としては は
を満たすようなものですから, 記号論理の知識がある人ならこれは
を満たすものでなければならないことがわかるでしょう. つまり は の最小元でなければならないのです. 同様に なるものが存在すれば, それは最大元でなければならないはずです. そこで, 有界束においては
とすることで上記の式の整合性が保たれます. 逆に空集合も含めた任意の有限部分集合に交わりと結びが存在するような束は有界束となります.
完備束
ここまでは有限部分集合のみに話を絞っていましたが, 有限とは限らない一般の の部分集合 に対して (交わり)であるということを
を満たすものとして定義します. 順序集合的に言えば ということです. 結びの定義も同様で, 順序集合的には になります.
もちろん, どちらも一般的には存在しないのですが, これが必ず存在するような束を完備束と言います. 完備束 には明らかに最小元 と最大元 が存在するので, 完備束は常に有界束です.
実は完備束においては, 「交わりと最小元」か「結びと最大元」のどちらか一方の存在を仮定すれば, もう一方が定義できます. 例えば交わりと最小元が常に存在するとして, 結びは
*1
で定義します. この式の右辺を と置くとき, 任意の に対して なので が導かれます. *2
直観主義論理の入り口~Heyting 代数~(その 1)
半年ぶりの記事です. 今回は, 数回にわたって Heyting 代数について書きたいと思います.
半順序集合と束
半順序集合から束
を半順序集合とします. すなわち について
- (反射律)*1
- (反対称律)
- (推移律)
が成り立つものとします.
について
を満たす が存在するとき, これを と書き, と の交わり(join)と言います. このような元は, 常に存在するとは限りませんが, 存在すれば一意であることは明らかです.
同様に について
を満たす が存在するとき, これを と書き, と の結び(meet)と言います.
任意の に対して, 常に と が存在するとき, は束(lattice)であると言います.*2
束の結びと交わりについて, 以下の法則が成り立ちます.
- (交換法則)
- (結合法則)
- (吸収法則)
これらのうち吸収法則が成り立つことについては少し難しいと思いますので, 片方だけ証明します.
定義から は明らかです. また が成り立つので も成り立ちます. よって反対称律により
これに以下の冪等法則を加えているケースもあります.
しかしこれは
のように吸収法則を 2 回使えば証明できるので必須ではありません.
束から半順序集合
集合 と, 上の演算 の組 が, 上記の交換法則, 結合法則および吸収法則を満たすとき, やはり は束であると言います.
このとき, 上の関係 を で定義すると は半順序集合になります. 試しに推移律を示すと
故, 定義により
ちなみに
で, 逆も成り立つので, 関係 の定義は
で置き換えても同じです.
しかも, このようにして作った順序から作った束は元の束と一致します. したがって, 束とは半順序集合を含む真に強い概念であると言えます.
代数曲線と消去イデアル
ここまでさまざまな(パラメーター表示や極方程式で定義された)曲線を と の多項式によって陰関数表示してきた. それにより, それらが代数曲線であることもわかったわけであるが, そこで暗黙的に使っていた理論がある.
の ideal に対し
を 番目の消去イデアルという.
消去イデアルを手で計算するのは一見すると簡単ではないが, Gröbner 基底を使うことでそれができるようになる. 詳しい証明は省略するが, に辞書式順序を となるように決めたうえで の Gröbner 基底を計算することで簡単に計算できる.
もっともこのようなことが成り立つためには は代数閉体である必要があるのだが, まぁその辺の詳しいことは割愛.
陰関数表示についてもう少し
もう少し、いろいろな図形の陰関数表示を見ていこう。
レムニスケート(lemniscate)
極方程式 で定義される.
Use QQ[a, x, y, r, c, s]; I := ideal(r^2 - 2*a^2*(c^2 - s^2), x - r*c, y - r*s, r^2 - (x^2 + y^2)); elim(r..s, I); > ideal(-2*a^2*x^2 +x^4 +2*a^2*y^2 +2*x^2*y^2 +y^4)