イプシロン計算については次のエントリーなどで紹介したことがあります。
ε記号はヒルベルトあたりが導入したんじゃないのかな、よく調べてないけど。ところで、再帰的計算に関連してμ（ミュー）やν（ニュー）という記号が出てきますが、これはεと似たようなものです。そのことをちょっと述べておきます。
内容：
集合の内包的記法
Pがなんらかの条件を表す論理式のとき、{x∈X | P(x)} という書き方はよく使われます。集合の内包的記法ですね。Xをあらかじめ決めて固定しておけば、{x | P(x)} でもいいでしょう。以下の例では、X = R（実数全体の集合）として、条件Pは足し算・掛け算・大小順序などを使って書くことにします。
{x | P(x)} という書き方は広く普及して安定した構文ですが、ここではあえて σx.P(x) と書いてみます。σは、setのsに対応するギリシャ小文字です。わざわざ σx.P(x) なんて書いたのは、ギリシャ小文字を使った一連の記法に慣れてもらうためです。このテの記法で一番ポピュラーなのはラムダ記法 λx.E でしょう。
σx.P(x) の基本的な性質は次です。
- a∈σx.P(x) ⇔ P(a)
例えば、
- 2∈σx.(x≧0 AND x*x ≦ 10) ⇔ (2≧0 AND 2*2 ≦ 10)
ε記号
ε記号を使った式 εx.P(x) の基本的な性質は次のようになります。
- a = εx.P(x) ⇒ P(a)
σ記号の性質と少し似てます。P(a) のaに a = εx.P(x) を代入すると次の形です。
- P(εx.P(x))
これが成立する背景は：
- a = εx.P(x) ⇒ a∈σx.P(a)
あるいは：
- εx.P(x)∈σx.P(a)
つまり、εx.P(x) とは、集合σx.P(a)の要素を適当に選んだものだ、ということです。ただし、集合σx.P(a)が空だと要素を選べません。
例えば、σx.(x*x ＜ 0) とかです。この特殊ケースへの対処法はいくつかあります。
- σx.P(a) が空でないときだけ考える。
- σx.P(a) が空のときは、εx.P(x) は未定義だとする。（「未定義の定義」をちゃんとする必要があります。）
- σx.P(a) が空のときは、εx.P(x) はなんでもいいとする。そして、基本的な性質として (∃x.P(x)) ⊃ P(εx.P(x)) （「⊃」は含意）を採用する。
ここでは、「σx.P(a) が空のときは、εx.P(x) は未定義」として、未定義を特殊な値⊥を使って表現することにします。
μ記号
考えている範囲全体である集合Xに順序が入っているとします。すると、集合σx.P(x)も自然に順序集合となります。集合σx.P(x)から適当な要素を選んでεx.P(x)とするわけですが、順序集合のときは、特に目立つ「代表的な要素」として最小元を取ることができます。もちろん、最小元があれば、ですが。
σx.P(x)の最小元を（それがあれば）ε↓x.P(x) と書くことにします。すると、ε↓はεと同じ性質を持ちます。
- a = ε↓x.P(x) ⇒ P(a)
あるいは：
- P(ε↓x.P(x))
ここで、P(x) として、x = f(x) という不動点方程式を取ります。そんときの ε↓x.P(x) は、ε↓x.(x = f(x)) ですから：
- P(ε↓x.P(x)) ≡ (ε↓x.(x = f(x)) = f(ε↓x.(x = f(x))) )
ウーン、なんか括弧が多くて鬱陶しいな。a = ε↓x.(x = f(x)) と置いて、aの性質を書けば：
- a = f(a)
- x = f(x) を満たすxのなかでaが最小
a = ε↓x.(x = x*x) の場合で考えてみましょう。まず、σx.(x = x*x) = {0, 1} となります。{0, 1}のなかで最小は0ですから、a = ε↓x.(x = x*x) = 0 です。実際：
- 0 = 0*0
- x = x*x を満たすxのなかで0が最小
ε↓x.(x = f(x)) の略記が μx.f(x) です。例えば、μx.(x*x) = 0 ですね。μ記号は、不動点方程式という特殊な条件に限定して、最小元を選ぶ方法を採用したε記号です。
次のような場合はμ記法の値は定義されないことに注意してくだささい。
- μx.(x*x + 1) -- x = x*x + 1 となるxがない（あくまでR内でのことです）。
- μx.(x) -- x = x となるxはいくらでもあるが、最小のものを選べない。
ν記号
ν記号は、μ記号の「最小元」を「最大元」に置き換えたもので、ε↑x.(x = f(x)) の略記だと思えばいいでしょう。もちろん、↑は最大元を選ぶことを意味します。例えば、νx.(x*x) = 1 となります。ν記号に関する性質や注意は、最小と最大の違いを除いてμ記号と同じです。
