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.}$

2015-09-26

cardioid の陰関数表示

数学・代数数学・幾何

astroid に続いては cardioid の陰関数表示を.

cardioid は ${r=a(1 + \cos \theta)}$ という極方程式によって与えられる平面曲線である.

(図は ${a=2}$ )

astroid のときと同じように ${\mathbb{Q}[a, x, y, r, c, s]}$ の ideal

${\mathfrak{I}=\langle r - a(1 + c), x - rc, y - rs, r^2 - (x^2 + y^2)\rangle}$

から ${r, c, s}$ を消去すると陰関数表示が得られる.

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

${- 2ax^3 + x^4 - a^2 y^2 - 2axy^2 + 2x^2 y^2 + y^4}$
なる式を得る. 整理の仕方はいろいろあるが, 一例は ${(x^2 - ax + y^2)^2 - a^2(x^2 + y^2)=0.}$

2015-09-25

astroid の陰関数表示

数学・代数数学・幾何

1 年振りでございました…orz

astroid という曲線をご存じであろうか.

${\left\{\begin{align} x &= a \cos^3 \theta \\ y &= a \sin^3 \theta \end{align}\right.}$

というパラメーター表示を持つ曲線である.

(上図は ${a=1}$ )

これのよく知られた陰関数表示として ${x^{\frac23}+y^{\frac23}=a^{\frac23}}$ があるが, 多項式じゃないから美しくない*1.

実は astroid にはれっきとした多項式による表示がある.

*1:と思うのはきっと私だけだ.

2014-09-23

Möbius 関数の Dirichlet 母関数(その 2)

数学・組み合わせ数学・解析

いよいよ Dirichlet 母関数の話.

${n = 1}$ から始まる系列 ${\langle g_1, g_2, g_3, \dots\rangle}$ について
$\tilde{G}(z) = \sum_{n\geqslant 1}\frac{g_n}{n^z}$
を Dirichlet 母関数という.

このとき, 二つの Dirichlet 母関数の積は, 系列のどのようなたたみ込みに相当するか調べると,
${\begin{align} \tilde{F}(z)\tilde{G}(z) &= \sum_{l,m\geqslant 1}\frac{f_l}{l^z}\frac{g_m}{m^z} \\ &= \sum_{n\geqslant 1}\frac{1}{n^z}\sum_{l,m\geqslant 1}f_l g_m [lm = n] \\ &= \sum_{n\geqslant 1}\frac{1}{n^z}\sum_{d\backslash n}f_d g_{n/d} \end{align}}$
であるから,
$h_n = \sum_{d\backslash n}f_d g_{n/d}$
というたたみ込みに相当していることがわかる.

さて, Möbius 関数の定義式
$[n = 1] = \sum_{d\backslash n}\mu(d)$
は, 系列 ${\langle \mu(1), \mu(2), \mu(3),\dots \rangle}$ と定数系列 ${\langle 1, 1, 1, \dots \rangle}$ のたたみ込みであると解釈できる. 定数系列 ${\langle 1, 1, 1, \dots \rangle}$ の Dirichlet 母関数は ${\zeta(z)}$ であるから
$\tilde{M}(z)\zeta(z) = \sum_{n\geqslant 1}\frac{[n = 1]}{n^z} = 1$
なので ${\tilde{M}(z) = \zeta(z)^{- 1}.}$