ε-N論法に興味を持ち、ε-N論法とは何を言っているのか？について、考えていました。そこで自分なりに理解したイメージを以下にまとめてみます。
ε-N論法とは
∀ε>0,∃N\in \mathbb{N} s.t. ∀n\in\mathbb{N},n>N⇒|an-α|<ε
なんだか宇宙語のようですが、これは目の慣れだと思います。Cの関数ポインタの宣言とか、perlの変態記法と同じ。
ε-N論法を理解するには、最低限、以下の述語論理の記号を知っておく必要があると思います。まずはこれらについて説明します。
- 述語論理の記号∀(すべて),∃(存在する)
- ∀,∃,∀の入れ子構造
任意の、すべての（∀）
「任意の」というと、日常的には「as you like」のニュアンスが強いですが、数学用語としては「すべての」に近いです。
「任意のヒヨコはオスである」
「任意の水は100℃で沸騰する」
箱の中にいるすべてのヒヨコがオスである場合、「任意のヒヨコはオスである」（箱の中からどのヒヨコを取り出しても、そのヒヨコはオス）とか、「任意の水は100℃で沸騰する」（地球上のどの水をもってきても、それの沸点は100℃である）といった具合。
要素の全量が10である場合、a[0..9]のすべてが条件を満たすイメージです（まあ、100℃の定義が「水の沸点」なので、トートロジーなんですが…）。
コードで書くと、「任意の（∀）」はこんなイメージです。
int is_all(){
fot(int n=0;n<sizeof(array)/sizeof(*array);n++){
if(!is_male(array[n]))
return false;
}
return true;
}
存在する（∃）
集合の要素のうち、少なくともいずれか一つの要素が条件を満たす場合、条件を満たす要素が「存在する」といいます。すべての要素が条件を満たす場合も同様です。
箱の中のヒヨコに、少なくともオスが1匹でも存在する場合はもちろん、10匹中10匹すべてがオスであった場合でも同様です。
int is_exist(){
for(int n=0;n<sizeof(array)/sizeof(*array); n++){
if(is_male(array[n]))
return true;
}
return false;
}
∀,∃が入れ子の場合
一つの箱に入った複数のヒヨコを考えてきましたが、さらに、箱が複数ある場合について考えて見ます。
A～Cの箱があります。それぞれの箱の中には、1～10の番号がついた10匹のヒヨコが入っているとします。どの箱をとっても、その中にいるヒヨコのうち、「ある番号」より後のヒヨコがすべてオスとなるような、そんな「ある番号」が存在する。これが、∀と∃が入れ子になった式のイメージです（M=オス、F=メスを意味します）。
| 箱 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ある番号 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| A | M | M | F | M | F | M | M | M | M | M | 5より後のヒヨコがすべてオス |
| B | M | M | F | M | F | M | F | F | M | M | 8より後のヒヨコがすべてオス |
| C | F | M | M | M | M | M | M | M | M | M | 1より後のヒヨコがすべてオス |
A・B・Cのすべての箱について、「ある番号」が存在するため、「任意の箱について、ある番号より後のヒヨコがすべてオスであるような、そんな番号が存在する」と言えます。論理式で擬似的に表現すると、こうなります。
∀box,∃Num s.t. ∀n, n>Num⇒IsMale(hiyoko[n])
任意の箱（box）について、ある番号（Num）以降のヒヨコがすべてオスであるような、そんな番号が存在する。
∀,∃が入れ子になった場合、「いっぺんに全部を考えようとしない」のがポイントです。まず、箱を一つにしぼって、「すべてのヒヨコがオスである」のか、「オスのヒヨコが存在する」のかを考える。つぎに、ヒヨコのことは忘れて「すべての箱がそう」なのか、「そんな箱が存在する」のかを考えると、よい感じです。
ε-N論法では、箱（数列）が一つなので、数列を一つにして考えてみます。
子供たちを一列に並ばせ、前から順に1,2,3,…と番号をつけます。その下に、それぞれの子供の身長を書き出します。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 160.5 | 160.4 | 159.9 | 158.2 | 160.1 | 140.1 | 139.8 | 138.2 | 137.6 | 136.5 |
身長が140cm未満の子供に★印をつけると、こうなります。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 160.5 | 158.2 | 159.9 | 139.9 | 160.1 | 140.1 | 139.8 | 138.2 | 137.6 | 136.5 |
| ★ | ★ | ★ | ★ | ★ |
この列において、「ある番号より後ろの子供がすべて140cm未満となるような、そんな”ある番号”」を探してみます。4番目の子供は139.9cmなので140cm未満ですが、後続の5～6番目の子供が140cm未満でない、つまり「後ろの子供がすべて140cm未満」の条件を満たさないため、「ある番号」は3ではありません。
7番目の子供をみると、後続の8～10番目の子供がすべて140cm未満であるため、6は「ある番号」に成りえます（6でなくても、7,8,9,10でもよいです）。
少し身長を下げて、基準身長を138cmとします。すると、9～10番目の子供が138cm未満であるため、ある番号は「8」となります。
この例では数列は有限ですが、どのような基準身長のもとでも「後続のすべての子供が、基準身長より小さくなるような、ある番号が存在する」が成り立つ。これが、ε-N論法のイメージです。
ε-N論法のイメージ
ε-N論法の理解に混乱を招く理由の一つとして、ε,N,n,αの値の「種類の違い」を混同してしまうことが挙げられます。この種類の違いとは、プログラミングでいう「配列の各要素の値」と「配列のインデックス」の違いです。「ε」が配列の各要素の値、N,nは配列のインデックス。εとn、Nの値の種類を混同しないように…。
具体的に、一般項に1/nをもつ配列を作ってみます。
int n;
float a[INT_MAX];
/* 数列を作成 */
for(n=1; n<INT_MAX; n++){
a[n]=1./n;
}
/* 数列を表示 */
for(n=1; n<sizeof(a)/sizeof(*a); n++){
printf("%d:%f\n", n, a[n]);
}
$ ./ipsd
1:1.000000
2:0.500000
3:0.333333
4:0.250000
5:0.200000
6:0.166667
7:0.142857
8:0.125000
9:0.111111
10:0.100000
11:0.090909
12:0.083333
13:0.076923
14:0.071429
15:0.066667
(中略)
96:0.010417
97:0.010309
98:0.010204
99:0.010101
100:0.010000
(中略)
995:0.001005
996:0.001004
997:0.001003
998:0.001002
999:0.001001
1000:0.001000
(以下略)
$
配列の中身をダンプしてみると、0に収束しそうな雰囲気が感じ取れます。代数的には、この配列は以下のように定義されます。
\lim_{n \to INT\_MAX-1} 1/n
ここでεの値として、例えばε=0.08をとると、
11:0.090909
12:0.083333 <== N=12
--------(ε=0.08)--------
13:0.076923 <== a[n=13]<ε が真
14:0.071429 <== a[n=14]<ε が真
15:0.066667 <== a[n=15]<ε が真
13番目以降の配列要素の値は、すべてε=0.08未満となっています。この部分が、ε-N論法の以下の部分式で表されるものです。
～s.t. ∀n\in\mathbb{N},n>N⇒|a_n-α|<ε
「任意のnのもとで、nがNより大きいならば、a[n]と極限値αとの距離はε未満である」
ちなみに、
|a_n-α|<ε
の部分ですが、|A-B|とは、A-Bの絶対値、つまりA～B間の距離を意味します。つまりε-N論法とは、極限値αへの収束を「αとの距離」として扱うことで、その距離がε未満であることを示すものです。この数列の場合、極限値αは0のため、|a_n-α|はa_nと同じことですが。
εの値を、もっと小さくしてみます。
995:0.001005 <== N=995
996:0.001004 <== a[n=996]<ε が真
997:0.001003 <== a[n=997]<ε が真
998:0.001002 <== a[n=998]<ε が真
999:0.001001 <== a[n=999]<ε が真
1000:0.001000 <== a[n=1000]<ε が真
(以下略)
ε=0.001005の場合、996以降の配列要素の値がε未満となるため、N=995となります。
というように、「εの値を変化させても上記の関係が成立する」ことを、以下の式で表現しています。
∀ε>0,∃N\in \mathbb{N} s.t.～
「すべてのεについて、～が成り立つような、そんなNが存在する。」
「任意のε」という表現が必要なのは、εをどれほど小さくしても、Nの存在が成り立つことを示すためです。これが、「ある数列がある値に収束する」ことの代数的な定義です。