ε-N論法について

ε-N論法に興味を持ち、ε-N論法とは何を言っているのか？について、考えていました。そこで自分なりに理解したイメージを以下にまとめてみます。

##ε-N論法とは

```math
∀ε>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℃の定義が「水の沸点」なので、トートロジーなんですが…）。

コードで書くと、「任意の（∀）」はこんなイメージです。

```c:is_all.c
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匹すべてがオスであった場合でも同様です。

```c:is_exist.c
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のすべての箱について、「ある番号」が存在するため、「任意の箱について、ある番号より後のヒヨコがすべてオスであるような、そんな番号が存在する」と言えます。論理式で擬似的に表現すると、こうなります。

```math
∀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をもつ配列を作ってみます。

```c:ipsd.c

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]);
}

```

```bash:実行結果
$ ./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に収束しそうな雰囲気が感じ取れます。代数的には、この配列は以下のように定義されます。

```math
\lim_{n \to INT\_MAX-1} 1/n
```

ここでεの値として、例えばε=0.08をとると、

```bash:ε=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論法の以下の部分式で表されるものです。

```math
～s.t.　∀n\in\mathbb{N},n>N⇒|a_n-α|<ε
```

```
「任意のnのもとで、nがNより大きいならば、a[n]と極限値αとの距離はε未満である」
```

ちなみに、

```math
|a_n-α|<ε
```

の部分ですが、|A-B|とは、A-Bの絶対値、つまりA～B間の距離を意味します。つまりε-N論法とは、極限値αへの収束を「αとの距離」として扱うことで、その距離がε未満であることを示すものです。この数列の場合、極限値αは0のため、|a_n-α|はa_nと同じことですが。

εの値を、もっと小さくしてみます。

```bash:ε=0.001005近辺
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となります。

というように、「εの値を変化させても上記の関係が成立する」ことを、以下の式で表現しています。

```math
∀ε>0,∃N\in \mathbb{N}　s.t.～
```

```
「すべてのεについて、～が成り立つような、そんなNが存在する。」
```

「任意のε」という表現が必要なのは、εをどれほど小さくしても、Nの存在が成り立つことを示すためです。これが、「ある数列がある値に収束する」ことの代数的な定義です。