2016-04-08

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

束についてもう少し

一般の束に関する性質をもう少し見ていきましょう.

$y \le z \Rightarrow x \wedge y \le x \wedge z, x \vee y \le x \vee z$
が成り立ちます(単調性).

これは
$(x \wedge y) \wedge (x \wedge z) = x \wedge y \wedge z = x \wedge y$ と $(x \vee y) \vee (x \vee z) = x \vee y \vee z = x \vee z$ からわかります.

また
$(x \wedge y) \vee (y \wedge z) \vee (z \wedge x) \le (x \vee y) \wedge (y \vee z) \wedge (z \vee x)$ … (*)
が成り立ちます. これは定義に従って地道に示せますので, 証明は省略します.

(*) 式から $x \le z \Rightarrow x \vee (y \wedge z) \le (x \vee y) \wedge z$ が導かれます. このことと単調性を上手く使うと

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

が示せます. (*) 式は自己双対ですが, 上の二式は互いに双対な式になっています. 逆にこの二式から (*) 式を示すこともできるので, この二式を合わせたものは (*) 式と同値です.

分配束

(*) 式で等号が成り立っているとき, 上記の式は全て等号で置き換えることができますが, そのような関係が成り立つ束を分配束と言います.

分配束 $L$ においては
「 $x, y \in L$ に対して $x \wedge z = y \wedge z$ かつ $x \vee z = y \vee z$ を満たす $z \in L$ が存在すれば $x = y$ 」*1
が成り立ちます. 実際
${\begin{align} x &= x \vee (x \wedge z) \\ &= x \vee (y \wedge z) \\ &= (x \vee y) \wedge (x \vee z) \\ &= (y \vee x) \wedge (y \vee z) \\ &= y \vee (x \wedge z) \\ &= y \vee (y \wedge z) = y. \end{align}}$

また, これ以外の $L$ が分配束になる必要十分条件には
$x \wedge (y \vee z) \le (x \wedge y) \vee z$
があります. 実際分配束においては $x \le x \vee z$ に単調性を用いて
$x \wedge (y \vee z) \le (x \vee z) \wedge (y \vee z) = (x \wedge y) \vee z$
が成り立ちますし, 逆に $x \wedge (y \vee z) \le (x \wedge y) \vee z$ ならば
${\begin{align} x \wedge (y \vee z) &= x \wedge ( x \wedge (y \vee z) ) \\ &\le x \wedge ( (x \wedge y) \vee z ) \\ &= x \wedge ( z \vee (x \wedge y) ) \\ &\le (x \wedge z) \vee (x \wedge y) \end{align}}$
が成り立つので, 一般の束で成り立つ $(x \wedge y) \vee (x \wedge z) \le x \wedge (y \vee z)$ と合わせて $x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z).$

モジュラー束

$x \le z \Rightarrow x \vee (y \wedge z) \le (x \vee y) \wedge z$ は常に成り立ちますが, これの等号が成り立つとき, すなわち
$x \le z \Rightarrow x \vee (y \wedge z) = (x \vee y) \wedge z$
が成り立つ束をモジュラー束と言います. 分配束は常にモジュラー束になりますが, 逆は成り立ちません.

なお, 断りなしに双対命題が成り立つことを使いましたが, 「分配束である」「モジュラー束である」という概念は自己双対概念であるため, 分配束やモジュラー束で成り立つ命題については, 常にその双対命題が成り立ちます.

*1:これは $L$ が分配束となるための必要十分条件であることが知られています.

2016-04-07

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

数学・基礎論

圏としての束

もう少し束の話を続けたいのですが, 圏論の知識を持っているといろいろと楽なことが多いので, 束を圏とみなす方法を紹介します.

一般に束 ${L}$ はそれ自体半順序集合です. これを圏とみなすためには以下のようにします.

圏 ${\mathcal{L}}$ の対象は ${L}$ の元.
圏 ${\mathcal{L}}$ の対象 ${x, y}$ の間の射は ${\hom(x, y) = \begin{cases} \{(x, y)\} & (x \le y) \\ \emptyset & (x \not\le y).\end{cases}}$
射 ${(x, y)}$ と射 ${(y, z)}$ に対して合成を ${(y, z) \circ (x, y) = (x, z)}$ で定義.

このとき ${L}$ が束であることと, ${\mathcal{L}}$ が常に 2 個の対象の余積と積を持つことと同値です. 余積は交わり, 積は結びに相当します. また, ${L}$ が有界束であることは ${\mathcal{L}}$ が(余積と積に加えて)始対象と終対象を持つことと同値です. 始対象は最小元 ${0}$ で終対象は最大元 ${1}$ になります. さらに, ${L}$ が完備束であることは ${\mathcal{L}}$ が無限余積と無限積を持つことと同値です.

双対圏(逆圏)

一般に圏 ${\mathcal{C}}$ が与えられたとき, その双対圏 ${\mathcal{C}^\mathrm{op}}$ が定義できます. ${\mathcal{C}^\mathrm{op}}$ の対象は ${\mathcal{C}}$ の対象で, 射は ${\mathcal{C}}$ において ${f : a \to b}$ であるとき ${f^\mathrm{op} : b \to a}$ であるとします.

このとき, 例えば ${\mathcal{C}}$ が始対象を持つならば、それは ${\mathcal{C}^\mathrm{op}}$ における終対象になっていますが, このような関係にある概念は互いに双対概念であると言います.

束を圏とみなしたとき, 交わりと結び, 最小元と最大元は互いに双対概念になっています. また, 束の命題について, その順序関係を逆にし, なおかつ交わりと結びを入れ替えたものが双対命題になっています. 束の双対はまた束なので, 束である命題が成り立つならば, その双対命題も成り立つことが分かります.

2016-04-06

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

数学・基礎論

有界束と完備束

有界束

束 $L$ は自然な方法で半順序集合とみなせることは前回分かりました. そうなると最小元や最大元は存在するのか, は自然な興味の対象になりますし, 当然ながら常に存在するとは限りません.

最小元と最大元がともに存在する束を有界束と言います. 束の場合は最小元は $0$ で, 最大元は $1$ で表すのが習わしです. 最小元と最大元については以下が成り立ちます.

$a \vee 0 = a (\Leftrightarrow a \wedge 0 = 0)$
$a \wedge 1 = a (\Leftrightarrow a \vee 1 = 1)$

証明はいずれも簡単なので省略します. 逆に代数的に定義した束 $\langle L, \vee, \wedge \rangle$ で, 上記の性質を満たす $0 \in L$ と $1 \in L$ があれば, $0$ が最小元, $1$ が最大元になります.

ちなみに最小元も最大元も存在すれば順序の意味では当然一意に定まりますが, 例えば $0$ の他に $0' \in L$ で $a \vee 0' = a$ を満たすものがあったとすれば
$0' = 0' \vee 0 = 0 \vee 0' = 0$
となり, そのような元は代数的にも一意に定まります.

さて, $L$ の空でない任意の有限部分集合 $A = \{a_1, a_2, \dots, a_n\} \subset L$ については交わりと結び
$\bigvee A = a_1 \vee a_2 \vee \dots \vee a_n, \bigwedge A = a_1 \wedge a_2 \wedge \dots \wedge a_n$
が自然に定義できます( $A = \{a\}$ のときは $\bigvee A = \bigwedge A = a$ と約束する). なおかつ $L$ の空でない有限部分集合 $A, B$ については
$\bigvee(A \cup B) = (\bigvee A) \vee (\bigvee B)$
$\bigwedge(A \cup B) = (\bigwedge A) \wedge (\bigwedge B)$
が成り立つのですが, 仮に $B = \emptyset$ とすると
$\bigvee A = \bigvee(A \cup \emptyset) = (\bigvee A) \vee (\bigvee \emptyset)$
$\bigwedge A = \bigwedge(A \cup \emptyset) = (\bigwedge A) \wedge (\bigwedge \emptyset)$
という式が出てきます.

気分としては $x = \bigvee \emptyset$ は

$(\forall a)(a \in \emptyset \Rightarrow a \le x)$
$(\forall y \in L)((\forall a)(a \in \emptyset \Rightarrow a \le y) \Rightarrow x \le y)$

を満たすようなものですから, 記号論理の知識がある人ならこれは
$(\forall y \in L)(x \le y)$
を満たすものでなければならないことがわかるでしょう. つまり $x$ は $L$ の最小元でなければならないのです. 同様に $\bigwedge \emptyset$ なるものが存在すれば, それは最大元でなければならないはずです. そこで, 有界束においては
$\bigvee \emptyset = 0, \bigwedge \emptyset = 1$
とすることで上記の式の整合性が保たれます. 逆に空集合も含めた任意の有限部分集合に交わりと結びが存在するような束は有界束となります.

ちなみに有界でない束を有界束に拡張する方法は至ってシンプルですので省略します.

完備束

ここまでは有限部分集合のみに話を絞っていましたが, 有限とは限らない一般の $L$ の部分集合 $A$ に対して $b = \bigvee A$ (交わり)であるということを

$(\forall a)(a \in A \Rightarrow a \le b)$
$(\forall x \in L)((\forall a)(a \in A \Rightarrow a \le x) \Rightarrow b \le x)$

を満たすものとして定義します. 順序集合的に言えば $\bigvee A = \sup A$ ということです. 結びの定義も同様で, 順序集合的には $\bigwedge A = \inf A$ になります.

もちろん, どちらも一般的には存在しないのですが, これが必ず存在するような束を完備束と言います. 完備束 $L$ には明らかに最小元 $0 = \bigwedge L$ と最大元 $1 = \bigvee L$ が存在するので, 完備束は常に有界束です.

実は完備束においては, 「交わりと最小元」か「結びと最大元」のどちらか一方の存在を仮定すれば, もう一方が定義できます. 例えば交わりと最小元が常に存在するとして, 結びは
$\bigwedge A = \bigvee \{x | (\forall a \in A)(x \le a)\} (= \sup A_* = \min (A_*)^*)$ *1
で定義します. この式の右辺を $b$ と置くとき, 任意の $a \in A$ に対して $a \in A \subset (A_*)^*$ なので $b \le a$ が導かれます. *2

*1: $X^*$ は集合 $X$ の上界の集合, $X_*$ は集合 $X$ の下界の集合を表す.

*2:最小元が存在するのでいかなる $A$ に対しても $A_*$ が空でないことを暗黙のうちに利用しています.

2016-04-05

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

数学・基礎論

半年ぶりの記事です. 今回は, 数回にわたって Heyting 代数について書きたいと思います.

半順序集合と束

半順序集合から束

$\langle L, \le \rangle$ を半順序集合とします. すなわち $a, b, c \in L$ について

$a \le a$ (反射律)*1
$a \le b, b \le a \Rightarrow a = b$ (反対称律)
$a \le b, b \le c \Rightarrow a \le c$ (推移律)

が成り立つものとします.

$a, b \in L$ について

$a \le c, b \le c$
$(\forall x \in L)(a \le x, b \le x \Rightarrow c \le x)$

を満たす $c \in L$ が存在するとき, これを $a \vee b$ と書き, $a$ と $b$ の交わり(join)と言います. このような元は, 常に存在するとは限りませんが, 存在すれば一意であることは明らかです.

同様に $a, b \in L$ について

$c \le a, c \le b$
$(\forall x \in L)(x \le a, x \le b \Rightarrow x \le c)$

を満たす $c \in L$ が存在するとき, これを $a \wedge b$ と書き, $a$ と $b$ の結び(meet)と言います.

任意の $a, b \in L$ に対して, 常に $a \vee b$ と $a \wedge b$ が存在するとき, $L$ は束(lattice)であると言います.*2

束の結びと交わりについて, 以下の法則が成り立ちます.

$x \vee y = y \vee x, x \wedge y = y \wedge x$ (交換法則)
$x \vee (y \vee z) = (x \vee y) \vee z, x \wedge (y \wedge z) = (x \wedge y) \wedge z$ (結合法則)
$x \vee (x \wedge y) = x, x \wedge (x \vee y) = x$ (吸収法則)

これらのうち吸収法則が成り立つことについては少し難しいと思いますので, 片方だけ証明します.

定義から $x \le x \vee (x \wedge y)$ は明らかです. また $x \le x, x \wedge y \le x$ が成り立つので $x \vee (x \wedge y) \le x$ も成り立ちます. よって反対称律により $x \vee (x \wedge y) = x.$

これに以下の冪等法則を加えているケースもあります.
$x \vee x = x, x \wedge x = x$
しかしこれは
$x \vee x = x \vee (x \wedge (x \vee x)) = x$
のように吸収法則を 2 回使えば証明できるので必須ではありません.

束から半順序集合

集合 $L$ と, $L$ 上の演算 ${\vee : L \times L \to L, \wedge : L \times L \to L}$ の組 $\langle L, \vee, \wedge \rangle$ が, 上記の交換法則, 結合法則および吸収法則を満たすとき, やはり $L$ は束であると言います.

このとき, $L$ 上の関係 $\le$ を $a \le b \Leftrightarrow a \vee b = b$ で定義すると $\langle L, \le \rangle$ は半順序集合になります. 試しに推移律を示すと
${\begin{align} a \le b, b \le c \Rightarrow a \vee c &= a \vee (b \vee c) \\ &= (a \vee b) \vee c \\ &= b \vee c = c \end{align}}$
故, 定義により $a \le c.$

ちなみに
$a \vee b = b \Rightarrow a \wedge b = a \wedge (a \vee b) = a$
で, 逆も成り立つので, 関係 $\le$ の定義は
$a \le b \Leftrightarrow a \wedge b = a$
で置き換えても同じです.

しかも, このようにして作った順序から作った束は元の束と一致します. したがって, 束とは半順序集合を含む真に強い概念であると言えます.

*1:私が参考にした「直観主義的集合論」では, この記述が抜けているように思います.

*2:同じく「束」と訳される数学の概念に bundle がありますが無関係です.

2015-10-03

代数曲線と消去イデアル

数学・代数

ここまでさまざまな(パラメーター表示や極方程式で定義された)曲線を ${x}$ と ${y}$ の多項式によって陰関数表示してきた. それにより, それらが代数曲線であることもわかったわけであるが, そこで暗黙的に使っていた理論がある.

${k[x_1, x_2, \dots, x_n]}$ の ideal ${\mathfrak{I}}$ に対し
${\mathfrak{I}_l = \mathfrak{I} \cap k[x_{l+1}, \dots, x_n]}$ を ${l}$ 番目の消去イデアルという.

消去イデアルを手で計算するのは一見すると簡単ではないが, Gröbner 基底を使うことでそれができるようになる. 詳しい証明は省略するが, ${k[x_1, x_2, \dots, x_n]}$ に辞書式順序を ${x_1\gt x_2\gt \dots \gt x_n}$ となるように決めたうえで ${\mathfrak{I}}$ の Gröbner 基底を計算することで簡単に計算できる.

もっともこのようなことが成り立つためには ${k}$ は代数閉体である必要があるのだが, まぁその辺の詳しいことは割愛.

2015-09-29

包絡線としての astroid

数学・代数数学・幾何

先日, 天下りに astroid のパラメーター表示を与えて, そこから陰関数表示を導き出した. しかし待って欲しい. みんなの持ってる astroid のイメージって多分こんなんでしょ ?

そう, 長さ一定の線分が端点の一方を ${x}$ 軸上, もう一方を ${y}$ 軸上に固定された状態で滑りながら動くときの包絡線が astroid だ.

この線分の方程式は
$\frac{x}{L\cos\theta} + \frac{y}{L\sin\theta} = 1$
だ.

ちょいと整理すると
${F(x, y, \theta) = x\sin\theta + y\cos\theta - L\cos\theta\sin\theta = 0}$
と書き直せる.

一般に, パラメーターを持つ曲線群 ${F(x, y, t) = 0}$ が与えられたとき, 包絡線は
${\displaystyle\left\{\begin{align} F(x, y, t) &= 0 \\ \frac{\partial F}{\partial t}(x, y, t) &= 0 \end{align}\right.}$
から ${t}$ を消去すると得られる.

実際今回の場合
${\displaystyle\frac{\partial F}{\partial \theta}(x, y, \theta) = x\cos\theta - y\sin\theta - L(\cos^2\theta - \sin^2\theta)}$
なので...

ハイ, 待って ! ちょっと待って !

2015-09-28

陰関数表示についてもう少し

数学・代数数学・幾何

もう少し、いろいろな図形の陰関数表示を見ていこう。

レムニスケート(lemniscate)

極方程式 ${r^2 = 2a^2 \cos 2\theta}$ で定義される.

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)

${(x^2 + y^2)^2 - 2a^2(x^2 - y^2) = 0.}$

リサジュー(Lissajous)図形

一般のケースは網羅し切れないので特別な場合について.

${\left\{\begin{align} x &= \cos 2\theta \\ y &= \sin\left(3\theta + \frac{\pi}{4}\right) \end{align}\right.}$

の場合,

Use QQ[a, x, y, c, s];
I := ideal(x - (c^2 - s^2), y - a*(c - s)*(c^2 + 4*c*s + s^2)/2, a^2 - 2, c^2 + s^2 - 1);
elim(c..s, I);

> ideal(a^2 -2, 16*x^6 -24*x^4 +4*y^4 +9*x^2 -4*y^2)

CoCoA では実数体を扱えないので少し工夫をして, 有理係数多項式環 ${\mathbb{Q}[a]}$ を ideal ${\langle a^2 - 2\rangle}$ で割って得られる体 ${\mathbb{Q}(\sqrt{2})}$ を擬似的に用いている.

${x^2(4x^2 - 3)^2 + 4y^2(y^2 - 1) = 0.}$

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

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

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

束についてもう少し

分配束

モジュラー束

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

圏としての束

双対圏(逆圏)

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

有界束と完備束

有界束

完備束

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

半順序集合と束

半順序集合から束

束から半順序集合

代数曲線と消去イデアル

包絡線としての astroid

陰関数表示についてもう少し

レムニスケート(lemniscate)

リサジュー(Lissajous)図形