読者です 読者をやめる 読者になる 読者になる

Red cat の数学よもやま話・新装開店

はてなダイアリー「Red cat の数学よもやま話」から徐々にこちらに移行していきます。

Catalan 数の計算について

Catalan 数のことは語らんよ ? …嘘です, ちょっとだけ語らせて !

先だって発売された新刊「数学ガールの秘密ノート/場合の数」に Catalan 数が登場する.

{\displaystyle \mathrm{C}_n = {2n \choose n} - {2n \choose n + 1} = \frac{1}{n + 1} {2n \choose n}.}

同書では, 二項係数を一度階乗を使って書き直して計算していたが, {2n \choose n} は最終的にそのままの形で残るので, 以下のように計算することもできる.

{\begin{align}
  {2n \choose n} - {2n \choose n + 1}
    &= {2n \choose n} - {2n \choose n - 1} \\
    &= {2n \choose n} - \frac{n}{2n + 1} {2n + 1 \choose n} \\
    &= {2n \choose n} - \frac{n}{2n + 1} {2n + 1 \choose n + 1} \\
    &= {2n \choose n} - \frac{n}{2n + 1} \frac{2n + 1}{n + 1} {2n \choose n} \\
    &= {2n \choose n} - \frac{n}{n + 1} {2n \choose n} \\
    &= \frac{1}{n + 1} {2n \choose n}.
\end{align}}

直観主義論理の入り口~Heyting 代数~(その 10・最終回)

完備 Heyting 代数

Heyting 代数は束として完備であるとき, 完備 Heyting 代数(complete Heyting algebra)と言います. 良く cHa などと略されます.

同様に Boole 代数が束として完備であるとき, 完備 Boole 代数(complete Boole algebra, cBa)と言います.

既に見たように, Boole 代数は Heyting 代数なので, cBa は cHa になっていますが, 実は無限分配律
(\bigvee X) \wedge a = \bigvee (X \wedge a)
を満たす完備束 L は cHa となることが以下のように示されます. ただし X \subset L, a \in L に対して
X \wedge a = \{ x \wedge a | x \in X\}
と定義します.

P(a,b) = \{ x | x \wedge a \le b \} と置くとき, 完備性により \bigvee P(a,b) が存在します. このとき無限分配律が成り立つことにより
( \bigvee P(a,b) ) \wedge a = \bigvee(P(a,b) \wedge a) \le b
なので \bigvee P(a,b) \in P(a,b) が成り立ち, したがって \max P(a,b) が存在するので L は cHa.

Heyting 代数はなぜ直観主義論理への入り口なのか ?

今回, 「直観主義論理への入り口」と題して Heyting 代数を紹介してきましたが, なぜ Heyting 代数は直観主義論理への入り口なのでしょうか ?

既に見たように, (完備) Boole 代数では \neg \neg x = xx \vee \neg x = 1 と言った見慣れた式が成り立ちますが, (完備) Heyting 代数ではこれらの式は一般には成り立ちません.

古典論理は真偽値の集合を完備 Boole 代数に取ったものと考えられますが, もし, 真偽値の集合を完備 Heyting 代数に取ったらどうなるでしょうか ? そのような論理体系では, もはや排中律は成り立ちません.

これは一見すると少し変わった論理体系のように思えます. しかし, もう少し「人間的な」見方をすると, ある事柄 P について, P であることを確認する方法がなかったからと言って P ではないと言い切るのは自然でしょうか ?

このように, 実は排中律が成り立たない論理体系の方が実は人間の感覚により近いのです. そして, それを数学の言葉で実現するための入り口が Heyting 代数なのです.

完備 Heyting 代数は層の理論の定式化にも用いられ, 必然的に層と直観主義論理は密接な関係にあります.

このあたりの話を知りたい方には, 以下の書籍をお勧めします.

層・圏・トポス―現代的集合像を求めて

層・圏・トポス―現代的集合像を求めて

OD>直観主義的集合論 (紀伊國屋数学叢書 20)

OD>直観主義的集合論 (紀伊國屋数学叢書 20)

これらの書籍で用いられる圏の理論により詳しい書籍としては

Categories for the Working Mathematician (Graduate Texts in Mathematics)

Categories for the Working Mathematician (Graduate Texts in Mathematics)

和訳本もあります.

圏論の基礎

圏論の基礎

層の理論と論理学の関係については

Sheaves in Geometry and Logic: A First Introduction to Topos Theory (Universitext)

Sheaves in Geometry and Logic: A First Introduction to Topos Theory (Universitext)

補遺 : 古い束論の洋書などを参照する場合, Heyting 代数は "Brouwer lattices" という名称で紹介されています.

直観主義論理の入り口~Heyting 代数~(その 9)

前回に引き続き Heyting 代数の性質を見ていきます.

最小元 0 を持つ Heyting 代数 H において \neg x = x \to 0 と定義し, これを x の擬補元と言うのでした. 今回は擬補元の性質を中心に見ていきます.

1. x \le y ならば \neg y \le \neg x.
\neg y = y \to 0 \le x \to 0 = \neg x.

2. x \wedge \neg x = 0.
\neg x の定義より明らか.

3. x \le \neg \neg x
2. より x \le \neg x \to 0 = \neg \neg x.

4. \neg x = \neg \neg \neg x.
3. で x\neg x で置き換えると \neg x \le \neg \neg \neg x, 一方で 3. に 1. を適用すると \neg \neg \neg x \le \neg x, よって \neg x = \neg \neg \neg x.

5. \neg(x \vee y) = \neg x \wedge \neg y.
{\begin{align}
 \neg(x \vee y) &= (x \vee y) \to 0 \\
                &= (x \to 0) \wedge (y \to 0) \\
                &= \neg x \wedge \neg y.
\end{align}}

6. \neg(x \wedge y) = \neg \neg(\neg x \vee \neg y).
これは長いので証明は省略.
4., 5. と前記事の 7. を使えば証明可能.

正則性

さて, x \le \neg \neg x は常に成り立つのですが, 等号 x = \neg \neg x に関しては常に成り立つとは限りません. x \in H については, 以下の 2 条件が同値であることが分かります.

  1. x = \neg \neg x.
  2. x = \neg y となる y \in H が存在する.

1. \Rightarrow 2. は明らかですが, 2. \Rightarrow 1. については
x = \neg y \Rightarrow \neg \neg x = \neg \neg \neg y = \neg y = x.

x \in H が上のいずれかの条件(したがって両方)を満たすとき, x正則(regular)であると言います. もし全ての x \in H が正則ならば, H は Boole 代数であることが, 以下のように示されます.

y = \neg(x \vee \neg x) と置きます. 定義により y \wedge (x \vee \neg x) = 0 です. 分配則により
0 = y \wedge (x \vee \neg x) = (y \wedge x) \vee (y \wedge \neg x)
なので y \wedge x = 0y \wedge \neg x = 0 がともに成り立ちます. 故に y \le x \to 0 = \neg x かつ y \le \neg x \to 0 = \neg \neg x = x が成り立つので y \le \neg x \wedge x = 0, すなわち y = 0.
よって x \vee \neg x = \neg \neg(x \vee \neg x) = \neg y = \neg 0 = 1.
以上により \neg xx の補元となり, H は Boole 代数である.

Heyting 代数にはまだまだ面白い性質があります(6. のような弱い形での de Morgan の法則が強い意味で成り立つための様々な条件の同値性など)が, 一般論はここまでにして, 次回, 完備 Heyting 代数のお話をします.

直観主義論理の入り口~Heyting 代数~(その 8)

今回は Heyting 代数の性質についてもう少し詳し見ていきます. 以下 H は Heyting 代数とし, a, b, c, a', b' \in H とします.

1. b \le a \to b.
b \wedge a \le b より明らか.

2. a \le a', b' \le b ならば a' \to b' \le a \to b.
(a' \to b') \wedge a \le (a' \to b') \wedge a' \le b' \le b より.

3. a \to (b \wedge c) = (a \to b) \wedge (a \to c).
函手 a \to (-) : H \to H が極限を保つことから従う.

4. (a \vee b) \to c = (a \to c) \wedge (b \to c).
(a \vee b) \to c \le a \to c(a \vee b) \to c \le b \to c から (a \vee b) \to c \le (a \to c) \wedge (b \to c),
{\begin{align}
(a \to c) \wedge (b \to c) \wedge (a \vee b)
 &=   ( (a \to c) \wedge a \wedge (b \to c) ) \vee ( (a \to c) \wedge (b \to c) \wedge b ) \\
 &\le ( c \wedge (b \to c) ) \vee ( (a \to c) \wedge c ) \\
 &=    c \vee c = c
\end{align}}
により (a \to c) \wedge (b \to c) \le (a \vee b) \to c,
よって (a \vee b) \to c = (a \to c) \wedge (b \to c).
分配圏の性質としても導くことができる.
{\begin{align}
 \hom(x, (a \vee b) \to c)
  &\simeq \hom(x \wedge (a \vee b), c) \\
  &\simeq \hom( (x \wedge a) \vee (x \wedge b), c ) \\
  &\simeq \hom(x \wedge a, c) \times \hom(x \wedge b, c) \\
  &\simeq \hom(x, a \to c) \times \hom(x, b \to c) \\
  &\simeq \hom( x, (a \to c) \wedge (b \to c) ).
\end{align}}

5. (a \to c) \vee (b \to c) \le (a \wedge b) \to c.
a \to c \le (a \wedge b) \to cb \to c \le (a \wedge b) \to c から従う.

6. (a \to b) \vee (a \to c) \le a \to (b \vee c).
a \to b \le a \to (b \vee c)a \to c \le a \to (b \vee c) から従う.

7. a \to (b \to c) = (a \wedge b) \to c.
圏論の冪の性質から従う.
{\begin{align}
 \hom( x, a \to (b \to c) )
  &\simeq \hom(x \wedge a, b \to c) \\
  &\simeq \hom( (x \wedge a) \wedge b, c ) \\
  &\simeq \hom(x \wedge (a \wedge b), c) \\
  &\simeq \hom(x, (a \wedge b) \to c).
\end{align}}

直観主義論理の入り口~Heyting 代数~(その 7)

今回は Boole 代数に関する大事な性質について見ていきます.

Boole 代数は Heyting 代数である

補題 {x \wedge a \le b \Leftrightarrow x \le \neg a \vee b.}

(証明)
{(\Rightarrow)}
{\begin{align}
x &=   x \wedge 1 \\
  &=   x \wedge (\neg a \vee a) \\
  &=   (x \wedge \neg a) \vee (x \wedge a) \\
  &\le (x \wedge \neg a) \vee b \le \neg a \vee b.
\end{align}}

{(\Leftarrow)}
{\begin{align}
x \wedge a &\le x \wedge (a \vee b) \\
           &\le (\neg a \vee b) \wedge (a \vee b) \\
           &=   (\neg a \wedge a) \vee b \\
           &=   0 \vee b = b. \Box
\end{align}}

定理 Boole 代数は Heyting 代数である.

(証明)
{\begin{align}
(\neg a \vee b) \wedge a &= (\neg a \wedge a) \vee (b \wedge a) \\
                         &= 0 \vee (a \wedge b) \\
                         &= a \wedge b \le b
\end{align}}
補題により {a \to b = \neg a \vee b. \Box}

Boole 代数ではない Heyting 代数が存在する

補題 {H} を Heyting 代数とする. もし {a \in H} に対してその補元が存在するならば, それは擬補元 {\neg a} である.

(証明)
{x}{a} の補元とする. このとき {a \wedge x = 0} であるから {x \le \neg a} である. よって単調性により
{1 = a \vee x \le a \vee \neg a}
であるから {a \vee \neg a = 1.} {a \wedge \neg a = 0} は定義より直ちにわかるから, {\neg a}{a} の補元である. {H} は分配的だから, 補元は存在すれば一意である. 故に {x = \neg a. \Box}

{H = \Bigl\{ 0, \dfrac12, 1 \Bigr\}} を, 通常の大小関係を入れて順序集合と見ると, これは有界束になっています. このとき {a \wedge b}

{a \backslash b} {0} {\dfrac12} {1}
{0} {0} {0} {0}
{\dfrac12} {0} {\dfrac12} {\dfrac12}
{1} {0} {\dfrac12} {1}

{a \vee b}

{a \backslash b} {0} {\dfrac12} {1}
{0} {0} {\dfrac12} {1}
{\dfrac12} {\dfrac12} {\dfrac12} {1}
{1} {1} {1} {1}

です. そして {a \to b} については

{a \backslash b} {0} {\dfrac12} {1}
{0} {1} {1} {1}
{\dfrac12} {0} {1} {1}
{1} {0} {\dfrac12} {1}

が成り立ちます. よって擬補元については以下の表のようになります.

a {\neg a}
{0} {1}
{\dfrac12} {0}
{1} {0}

{H} が Boole 代数になるためには擬補元が補元に一致する必要がありますが, {H} においては
{\dfrac12 \vee \neg \dfrac12 = \dfrac12 \vee 0 = \dfrac12 \ne 1}
なので, {H} は Boole 代数ではありません. しかし Heyting 代数ではあるので, これは Boole 代数ではない Heyting 代数の例になっています.

直観主義論理の入り口~Heyting 代数~(その 6)

前回まで束に関する一般的な性質を見てきましたが, 今回からいよいよ Heyting 代数の話をします.

Heyting 代数の定義

L有界束とします. このとき LHeyting 代数であるとは, L が圏*1として冪を持つことを言います. すなわち函手
(-) \wedge a : L \to L
が右随伴函手
a \to (-) : L \to L
を持つことを言います.

このとき, 圏の一般論から (-) \wedge a が余極限を保つこと, 特に
a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)
が成り立つので, L分配束であることが分かります.

c = a \to b に関しては
 c \wedge a \le b かつ x \wedge a \le b \Leftrightarrow x \le c
で特徴づけることができます. つまり圏の言葉を使わずに定義するならば, 有界L
\{ x | x \wedge a \le b \}
に常に最大元が存在するときに Heyting 代数であるといい, \max \{ x | x \wedge a \le b \} のことを a \to b と書きます. これを ab に対する相対擬補元と言います.

特に a0 に対する相対擬補元 a \to 0 を単に擬補元と言い, \neg a と書きます.

Boole 代数

Heyting 代数の性質を細かく見る前に, Heyting 代数より真に強い概念*2である Boole 代数について見ていきたいと思います.

相補律

有界L相補律を満たすとは, 任意の x \in L に対して
x \wedge x' = 0, x \vee x' = 1
を満たす x' \in L が存在することを言います. このとき x'x補元であると言います. 一般には補元は一意ではありません. 相補律は自己双対な概念です.

Boole 代数

有界L分配束でかつ相補律を満たすとき, LBoole 代数(もしくは Boole 束)であると言います. Boole 代数においては, x', x'' がともに x の補元ならば
{\begin{align}
x' &= x' \wedge 1 \\
   &= x' \wedge (x \vee x'') \\
   &= (x' \wedge x) \vee (x' \wedge x'') \\
   &= 0 \vee (x' \wedge x'') = x' \wedge x''
\end{align}}
が成り立ち, 同様に x'' = x' \wedge x'' も示せますので, x' = x'' が成り立ちます. すなわち, 補元は一意に決まります. したがって, Boole 代数では x の補元を \neg x と書くのが習わしです.

\neg x の補元の一意性から \neg \neg x = x が成り立ちます. つまりある元を補元に移すという写像は対合になっています.

de Morgan の法則

\neg(a \vee b) = \neg a \wedge \neg b, \neg(a \wedge b) = \neg a \vee \neg b
de Morgan の法則として有名です. 証明は
{\begin{align}
(a \vee b) \wedge (\neg a \wedge \neg b)
  &= ( (a \wedge \neg a) \vee (\neg a \wedge b) ) \wedge \neg b \\
  &= ( 0 \vee (\neg a \wedge b) ) \wedge \neg b \\
  &= (\neg a \wedge b) \wedge \neg b \\
  &= \neg a \wedge (b \wedge \neg b) \\
  &= \neg a \wedge 0 = 0,
\end{align}}
{\begin{align}
(a \vee b) \vee (\neg a \wedge \neg b)
  &= a \vee ( b \vee (\neg a \wedge \neg b) ) \\
  &= a \vee ( (\neg a \vee b) \wedge (b \vee \neg b) ) \\
  &= a \vee ( (\neg a \vee b) \wedge 1 ) \\
  &= a \vee (\neg a \vee b) \\
  &= (a \vee \neg a) \vee b \\
  &= 1 \vee b = 1.
\end{align}}
もう一方はその双対です.

a \le b ならば a \vee b = b なので de Morgan の法則により
\neg a \wedge \neg b = \neg(a \vee b) = \neg b
が成り立つので \neg b \le \neg a が成り立ちます. つまり, 補元を取るという操作は順序を逆にします.

直交相補束

有限次元ベクトル空間 V の部分空間の全体は有界束になります. W_1 \subset VW_2 \subset V を部分空間とするとき, 結びは W_1 \cap W_2, 交わりは W_1 + W_2 になります.
W'W の補元であることは V = W \oplus W' と表せますが, 一般に補元は一意でないことは次のような例を考えるとわかります.

V = \mathbb{R}^2, W = \{ (x, 0) | x \in \mathbb{R} \}, W' = \{ (0, y) | y \in \mathbb{R} \}, W'' = \{ (y, y) | y \in \mathbb{R} \}
とおくと, 明らかに V = W \oplus W' ですが, 一方で任意の (x, y) \in V
(x, y) = (x - y, 0) + (y, y) \in W + W''
と表すことができ, また W \cap W'' = \{\boldsymbol{0}\} なので V = W \oplus W'' も成り立ちます.

しかし, V内積を与えたとき, W \subset V に対して
W^\perp = \{ \boldsymbol{v} \in V | (\forall \boldsymbol{w} \in W)( (\boldsymbol{v}, \boldsymbol{w}) = 0 )\}
とおけば
V = W \oplus W^\perp, (W^\perp)^\perp = W, W_1 \subset W_2 \Rightarrow {W_2}^\perp \subset {W_1}^\perp
が成り立ちます.

このことを一般化して, 有界L について \perp : L \ni a \mapsto a^\perp \in L

  • a \wedge a^\perp = 0, a \vee a^\perp = 1
  • (a^\perp)^\perp = a
  • a \le b \Rightarrow b^\perp \le a^\perp

を満たしているとき, \langle L, \perp \rangle直交相補束と言います. 一般に有界L の直交相補束としての構造は複数入る可能性があります(上記の例では, 内積の取り方によって異なる直交相補束としての構造が考えられる).

直交相補束においては
a^\perp \le (a \wedge b)^\perp, b^\perp \le (a \wedge b)^\perp
であり, a^\perp \le x, b^\perp \le x ならば x^\perp \le a, x^\perp \le b だから x^\perp \le a \wedge b であり, よって  (a \wedge b)^\perp \le x であるから (a \wedge b)^\perp = a^\perp \vee b^\perp が成り立ちます. 同様に (a \vee b)^\perp = a^\perp \wedge b^\perp も成り立ちます(de Morgan の法則).

Boole 代数は明らかに直交相補束です.

*1:束演算から定義される順序を導入して, 順序集合がなす小さな圏と考える.

*2:このことは後で証明します.

直観主義論理の入り口~Heyting 代数~(その 5)

ある方から証明を教えていただくことができた(正確には証明が載っている書籍を紹介していただいた)ので, 前回あいまいにしていた部分を消化しておきます.

定理. L分配束でなければ
a \vee c = b \vee c, a \wedge c = b \wedge c, a \ne b
を満たす a, b, c \in L が存在する.

(証明)
1. L がモジュラー束でないとき
このとき x \lt z かつ x \vee (y \wedge z) \lt (x \vee y) \wedge z を満たす x, y, z \in L が存在する. 明らかに
y \wedge z \le x \vee (y \wedge z) \lt (x \vee y) \wedge z \le x \vee y
が成り立っており, 単調性から
x \vee y = ( x \vee (y \wedge z) ) \vee y \le ( (x \vee y) \wedge z ) \vee y \le x \vee y

( x \vee (y \wedge z) ) \vee y = ( (x \vee y) \wedge z ) \vee y

y \wedge z \le ( x \vee (y \wedge z) ) \wedge y \le ( (x \vee y) \wedge z ) \wedge y = y \wedge z

( x \vee (y \wedge z) ) \wedge y = ( (x \vee y) \wedge z ) \wedge y
が成り立つ. 従って
a = x \vee (y \wedge z), b = (x \vee y) \wedge z, c = y
が条件を満たす.

2. L がモジュラー束のとき
仮定により (x \wedge y) \vee (y \wedge z) \vee (z \wedge x) \lt (x \vee y) \wedge (y \vee z) \wedge (z \vee x) を満たす x, y, z \in L が存在する.
{\begin{eqnarray}
a & = & (y \wedge z) \vee ( x \wedge (y \vee z) ) & = & ( (y \wedge z) \vee x ) \wedge (y \vee z) \\
b & = & (z \wedge x) \vee ( y \wedge (z \vee x) ) & = & ( (z \wedge x) \vee y ) \wedge (z \vee x) \\
c & = & (x \wedge y) \vee ( z \wedge (x \vee y) ) & = & ( (x \wedge y) \vee x ) \wedge (x \vee y) \\
\end{eqnarray}}
と置くと
{\begin{align}
a \vee b
 &= (y \wedge z) \vee ( x \wedge (y \vee z) ) \vee ( y \wedge (z \vee x) ) \vee (z \wedge x) \\
 &= (y \wedge z) \vee ( (x \vee y) \wedge (y \vee z) \wedge (z \vee x) ) \vee (z \wedge x) \\
 &= (x \vee y) \wedge (y \vee z) \wedge (z \vee x),
\end{align}}
ここに x \wedge (y \vee z) \le x \le z \vee xy \le y \vee z から
{\begin{align}
( x \wedge (y \vee z) ) \vee ( y \wedge (z \vee x) )
 &= ( ( x \wedge (y \vee z) ) \vee y ) \wedge (z \vee x) \\
 &= ( (x \vee y) \wedge (y \vee z) ) \wedge (z \vee x).
\end{align}}
同様にして
a \vee b = b \vee c = c \vee a = (x \vee y) \wedge (y \vee z) \wedge (z \vee x).
双対で
a \wedge b = b \wedge c = c \wedge a = (x \wedge y) \vee (y \wedge z) \vee (z \wedge x).
このことから, a, b, c のうちいずれか二つが等しければ
(x \wedge y) \vee (y \wedge z) \vee (z \wedge x) = (x \vee y) \wedge (y \vee z) \wedge (z \vee x)
となり仮定に反するから, a, b, c は互いに異なる元であり, これが定理の条件を満たす.