Catalan 数の計算について
Catalan 数のことは語らんよ ? …嘘です, ちょっとだけ語らせて !
先だって発売された新刊「数学ガールの秘密ノート/場合の数」に Catalan 数が登場する.
数学ガールの秘密ノート/場合の数 (数学ガールの秘密ノートシリーズ)
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2016/04/20
- メディア: 単行本
- この商品を含むブログ (2件) を見る
同書では, 二項係数を一度階乗を使って書き直して計算していたが, は最終的にそのままの形で残るので, 以下のように計算することもできる.
直観主義論理の入り口~Heyting 代数~(その 10・最終回)
完備 Heyting 代数
Heyting 代数は束として完備であるとき, 完備 Heyting 代数(complete Heyting algebra)と言います. 良く cHa などと略されます.
同様に Boole 代数が束として完備であるとき, 完備 Boole 代数(complete Boole algebra, cBa)と言います.
既に見たように, Boole 代数は Heyting 代数なので, cBa は cHa になっていますが, 実は無限分配律
を満たす完備束 は cHa となることが以下のように示されます. ただし に対して
と定義します.
と置くとき, 完備性により が存在します. このとき無限分配律が成り立つことにより
なので が成り立ち, したがって が存在するので は cHa.
Heyting 代数はなぜ直観主義論理への入り口なのか ?
今回, 「直観主義論理への入り口」と題して Heyting 代数を紹介してきましたが, なぜ Heyting 代数は直観主義論理への入り口なのでしょうか ?
既に見たように, (完備) Boole 代数では や と言った見慣れた式が成り立ちますが, (完備) Heyting 代数ではこれらの式は一般には成り立ちません.
古典論理は真偽値の集合を完備 Boole 代数に取ったものと考えられますが, もし, 真偽値の集合を完備 Heyting 代数に取ったらどうなるでしょうか ? そのような論理体系では, もはや排中律は成り立ちません.
これは一見すると少し変わった論理体系のように思えます. しかし, もう少し「人間的な」見方をすると, ある事柄 について, であることを確認する方法がなかったからと言って ではないと言い切るのは自然でしょうか ?
このように, 実は排中律が成り立たない論理体系の方が実は人間の感覚により近いのです. そして, それを数学の言葉で実現するための入り口が Heyting 代数なのです.
完備 Heyting 代数は層の理論の定式化にも用いられ, 必然的に層と直観主義論理は密接な関係にあります.
このあたりの話を知りたい方には, 以下の書籍をお勧めします.
- 作者: 竹内外史
- 出版社/メーカー: 日本評論社
- 発売日: 1978/01/20
- メディア: 単行本
- 購入: 3人 クリック: 39回
- この商品を含むブログ (17件) を見る
- 作者: 竹内外史
- 出版社/メーカー: 紀伊國屋書店
- 発売日: 2008/11
- メディア: 単行本
- クリック: 3回
- この商品を含むブログを見る
これらの書籍で用いられる圏の理論により詳しい書籍としては
Categories for the Working Mathematician (Graduate Texts in Mathematics)
- 作者: Saunders Mac Lane
- 出版社/メーカー: Springer
- 発売日: 2013/10/04
- メディア: ペーパーバック
- クリック: 4回
- この商品を含むブログを見る
和訳本もあります.
- 作者: S.マックレーン,Saunders MacLane,三好博之,高木理
- 出版社/メーカー: 丸善出版
- 発売日: 2012/07/17
- メディア: 単行本
- クリック: 25回
- この商品を含むブログ (4件) を見る
層の理論と論理学の関係については
Sheaves in Geometry and Logic: A First Introduction to Topos Theory (Universitext)
- 作者: Saunders MacLane,Ieke Moerdijk
- 出版社/メーカー: Springer
- 発売日: 1994/11/01
- メディア: ペーパーバック
- クリック: 6回
- この商品を含むブログ (3件) を見る
補遺 : 古い束論の洋書などを参照する場合, Heyting 代数は "Brouwer lattices" という名称で紹介されています.
直観主義論理の入り口~Heyting 代数~(その 9)
前回に引き続き Heyting 代数の性質を見ていきます.
最小元 を持つ Heyting 代数 において と定義し, これを の擬補元と言うのでした. 今回は擬補元の性質を中心に見ていきます.
1. ならば
2.
の定義より明らか.
3.
2. より
4.
3. で を で置き換えると 一方で 3. に 1. を適用すると よって
5.
6.
これは長いので証明は省略.
4., 5. と前記事の 7. を使えば証明可能.
正則性
さて, は常に成り立つのですが, 等号 に関しては常に成り立つとは限りません. については, 以下の 2 条件が同値であることが分かります.
- となる が存在する.
は明らかですが, については
が上のいずれかの条件(したがって両方)を満たすとき, は正則(regular)であると言います. もし全ての が正則ならば, は Boole 代数であることが, 以下のように示されます.
と置きます. 定義により です. 分配則により
なので と がともに成り立ちます. 故に かつ が成り立つので すなわち
よって
以上により は の補元となり, は Boole 代数である.
Heyting 代数にはまだまだ面白い性質があります(6. のような弱い形での de Morgan の法則が強い意味で成り立つための様々な条件の同値性など)が, 一般論はここまでにして, 次回, 完備 Heyting 代数のお話をします.
直観主義論理の入り口~Heyting 代数~(その 8)
今回は Heyting 代数の性質についてもう少し詳し見ていきます. 以下 は Heyting 代数とし, とします.
1.
より明らか.
2. ならば
より.
3.
函手 が極限を保つことから従う.
4.
と から
により
よって
分配圏の性質としても導くことができる.
5.
と から従う.
6.
と から従う.
7.
圏論の冪の性質から従う.
直観主義論理の入り口~Heyting 代数~(その 7)
今回は Boole 代数に関する大事な性質について見ていきます.
Boole 代数ではない Heyting 代数が存在する
補題 を Heyting 代数とする. もし に対してその補元が存在するならば, それは擬補元 である.
(証明)
を の補元とする. このとき であるから である. よって単調性により
であるから は定義より直ちにわかるから, も の補元である. は分配的だから, 補元は存在すれば一意である. 故に
を, 通常の大小関係を入れて順序集合と見ると, これは有界束になっています. このとき は
で は
です. そして については
が成り立ちます. よって擬補元については以下の表のようになります.
が Boole 代数になるためには擬補元が補元に一致する必要がありますが, においては
なので, は Boole 代数ではありません. しかし Heyting 代数ではあるので, これは Boole 代数ではない Heyting 代数の例になっています.
直観主義論理の入り口~Heyting 代数~(その 6)
前回まで束に関する一般的な性質を見てきましたが, 今回からいよいよ Heyting 代数の話をします.
Heyting 代数の定義
は有界束とします. このとき が Heyting 代数であるとは, が圏*1として冪を持つことを言います. すなわち函手
が右随伴函手
を持つことを言います.
このとき, 圏の一般論から が余極限を保つこと, 特に
が成り立つので, は分配束であることが分かります.
に関しては
かつ
で特徴づけることができます. つまり圏の言葉を使わずに定義するならば, 有界束 は
に常に最大元が存在するときに Heyting 代数であるといい, のことを と書きます. これを の に対する相対擬補元と言います.
特に の に対する相対擬補元 を単に擬補元と言い, と書きます.
Boole 代数
Heyting 代数の性質を細かく見る前に, Heyting 代数より真に強い概念*2である Boole 代数について見ていきたいと思います.
相補律
有界束 が相補律を満たすとは, 任意の に対して
を満たす が存在することを言います. このとき は の補元であると言います. 一般には補元は一意ではありません. 相補律は自己双対な概念です.
Boole 代数
有界束 が分配束でかつ相補律を満たすとき, は Boole 代数(もしくは Boole 束)であると言います. Boole 代数においては, がともに の補元ならば
が成り立ち, 同様に も示せますので, が成り立ちます. すなわち, 補元は一意に決まります. したがって, Boole 代数では の補元を と書くのが習わしです.
の補元の一意性から が成り立ちます. つまりある元を補元に移すという写像は対合になっています.
de Morgan の法則
は de Morgan の法則として有名です. 証明は
もう一方はその双対です.
ならば なので de Morgan の法則により
が成り立つので が成り立ちます. つまり, 補元を取るという操作は順序を逆にします.
直交相補束
有限次元ベクトル空間 の部分空間の全体は有界束になります. と を部分空間とするとき, 結びは , 交わりは になります.
が の補元であることは と表せますが, 一般に補元は一意でないことは次のような例を考えるとわかります.
とおくと, 明らかに ですが, 一方で任意の は
と表すことができ, また なので も成り立ちます.
しかし, に内積を与えたとき, に対して
とおけば
が成り立ちます.
このことを一般化して, 有界束 について が
を満たしているとき, を直交相補束と言います. 一般に有界束 の直交相補束としての構造は複数入る可能性があります(上記の例では, 内積の取り方によって異なる直交相補束としての構造が考えられる).
直交相補束においては
であり, ならば だから であり, よって であるから が成り立ちます. 同様に も成り立ちます(de Morgan の法則).
Boole 代数は明らかに直交相補束です.
直観主義論理の入り口~Heyting 代数~(その 5)
ある方から証明を教えていただくことができた(正確には証明が載っている書籍を紹介していただいた)ので, 前回あいまいにしていた部分を消化しておきます.
定理. が分配束でなければ
を満たす が存在する.
(証明)
1. がモジュラー束でないとき
このとき かつ を満たす が存在する. 明らかに
が成り立っており, 単調性から
故
と
故
が成り立つ. 従って
が条件を満たす.
2. がモジュラー束のとき
仮定により を満たす が存在する.
と置くと
ここに と から
同様にして
双対で
このことから, のうちいずれか二つが等しければ
となり仮定に反するから, は互いに異なる元であり, これが定理の条件を満たす.