この記事は UEC 2 Adovent Calendar 2024 2日目の記事です。
1日目はNdgtさんによるアニメーションソフトの記事でした。
すこしだけ記事を覗かせてもらいました。モデリングとかに詳しくない私には「ほぇ〜 (バカの顔) 」でしたが、世の中のアニメーションが作られる過程を少しだけ垣間見ることができてたのしかったです。
UEC 1 の方ではぼいどさんによるIoT通信系の記事でした。...見えていない？おかしいなぁ...。僕のスマホでも見れないや。
また、UEC 1 の2日目の記事ではUdonさんがWeb Audio APIをつかってみた話をかいています。
API、今年はこれに翻弄された年と言っても過言ではないので、私は少し身構えてしまいます。...ん？なんで同じ2日目の僕の記事で紹介されているかって？そんなことはどうでもいいんですよ。
はじめに
前置きが長くなってしまいましたね。こんにちは、CS所属、2年のSHINNです！今年もUEC2の2日目を担当させていただきます。昨年は私の大学1年の話をつらつらと書きましたが、今年は趣向を変えて、私の好きな数学について語っていこうと思います。ぜひ最後まで記事を読んでいってください！
そういえば自分の個人サイトに投稿するといった話はどうなったんですかねぇははっ
概要
この記事ではε論法について紹介していこうと思います。しかし、「どれだけ小さくしてもうんぬん...」といった話は皆さん聞き飽きていると思います。そこで、この記事では「論理学の視点からε論法をみる」というテーマでε論法を紹介していきます。本記事の流れは以下のとおりです。
- 数学的な準備
- 定義
- 例題1: 「収束するならば収束する」型の問題
- 例題2: 「収束を示せ」型の問題
さっそく最初のトピックから見ていきましょう！
注意
用語の使用等には細心の注意を払いますが、もし間違いがございましたらお知らせください。また、便宜上用語の定義を一部省略する場合があります。ご了承ください。
0. 数学的な準備
ここでは知っておいた方がいい数学(論理学)の知識について話します。
0.1. 命題と述語
まずは論理学を語る上では避けて通れない2つの用語について確認します。
定義: 命題
真か偽か判定することのできる主張。一般的には$P$と表される。
例えば次のものが命題です。
例1. 犬は哺乳類である -> この主張は真であると判定できるから命題
例2. 冷蔵庫は生物である -> この主張は偽であると判定できるから命題
逆に次の主張は命題ではありません。
例3. この料理は美味しい -> 美味しいかどうかは人それぞれ変わってしまい一意に真偽を判定できないので命題ではない
例4. お母さんは厳しい -> これも人によってことなる回答がでてしまうので命題ではない
大事なのは「誰が読んでも真偽を一意に判定できる」ことです。ちなみに、この根底にある「誰が読んでも」までを疑ってしまうと、それはもう数学というより哲学の分野になってしまうのでココらへんで勘弁。
定義: 述語
値の決まっていない変数を含み、その変数の値が決まることで真か偽か決まる主張のこと。一般的には変数を$x$としたときに述語は$P(x)$と表される。
たとえば次のものは述語です。
例1. $x > 0$
例2. $x^2 + y^2 = 1$
これらはそれ単体では真偽を判定することができませんが、$x$や$y$に具体的な値を入れることで命題となります。例えば1の例において$x = 2$とすれば、この述語は$1 > 0$となり真と判定できる命題になります。
0.2. 全称命題と存在命題
0.2.1. 定義
ここでは数学の命題でよく出てくる「どんな〜に対しても」と「ある〜に対して」に相当する全称命題・存在命題について確認していきます。とりあえず定義を見てみましょう。
定義: 全称命題
「集合$U$に含まれるすべての元$x$について、述語$P(x)$に代入すると真を返すか」という命題を全称命題といい次のように表す。
\forall x \in U\ \ [P(x)]
定義: 存在命題
「集合$U$に含まれる元$x$のうち、一つでも述語$P(x)$が真を返す元は存在するか」という命題を存在命題といい次のように表す。
\exists x \in U\ \ [P(x)]
...は？と思いますよね。私も書いていて思いました。そういうときは例を確認しましょう。
例1. $\forall x \in \mathbb R \ \ [x^2 \geq 0]$
この命題を言い換えると「どんな実数$x$を持ってきても$x^2$は$0$よりも大きいか同じである」です。これは真であることがわかります。次の命題はどうでしょう？
例2. $\forall x \in \mathbb R \ \ [x^2 > 0]$
この命題は「どんな実数$x$を持ってきても$x^2$は$0$よりも大きい」と言い換えられます。が、これは偽です。$x \neq 0$のときは必ず$x^2 > 0$となりますが、$x = 0$の場合は$x^2 = 0$となり、条件を満たしません。
そうです、一つでも条件を満たさない元$x$が見つかってしまったら全称命題は偽となってしまうのです。
では次に、存在命題について考えてみましょう。
例3. $\exists x \in \mathbb R \ \ [x^2 \geq 0]$
これは真です。なぜなら$x = 1$という元において$x^2 = 1 \geq 0$を満たすからです。次の命題はどうでしょうか？
例4. $\exists x \in \mathbb R \ \ [x^2 > 0]$
先程の全称の場合は偽でしたが、これはどうでしょう...？答えは真です。なぜなら$x = 1$という元において$x^2
= 1 > 0$を満たすからです。
以上2つの例でお気づきの方も多いと思いますが、「一つでも述語を真にすることができる元」を見つけることさえできれば存在命題は真となるのです。逆に言えば、存在命題が偽であることを示したければ、すべての元$x$について条件$P(x)$に値を代入すると偽になることを示せば良いのです。
0.2.2. 証明の方法
全称命題と存在命題にはそれぞれ証明の型が存在します。ここでは、その型について説明していきます。これはε論法の問題を解く際にとても重要になってくるのでしっかり確認しましょう。
0.2.2.1. 全称命題の証明
全称命題の証明の手順は以下のとおりです。
- 集合$U$から「任意に$x'$を一つとってきて」、固定する
- 述語$P(x)$に$x'$を代入した命題$P(x')$が真であることを証明する
たったこの手順を踏むだけで証明することができます。例を見て確認していきましょう。
例. $\forall x \in \mathbb R \ \ [x^2 + 2x + 4 > 0]$
この命題が真であることを先程の手順を踏んで証明してみましょう。
まず$x' \in \mathbb R$を任意にとってきて、その値で固定します。次に述語$P(x): x^2 + 2x + 4 > 0$に$x = x'$を代入したときの命題が真であることを証明していきます。
\begin{align}
x'^{\ 2} + 2x' + 4 &= (x' + 1)^2 + 3 \\
&\geq 3 \\
& > 0
\end{align}
となり、$x'^{\ 2} + 2x' + 4 > 0$であることが証明されました。したがって、命題$\forall x \in \mathbb R \ \ [x^2 + 2x + 4 > 0]$は真であることが証明されました。
勘の良い方はお気づきかと思いますが、これは受験数学のテクニックとして知られている「一文字固定法」に過ぎません(地域差あるかもですが私はこう読んでいます)。一文字固定法も「すべての〜」という問題に使っていたと思いますが、そのからくりはここにあったわけですね。
0.2.2.2 存在命題の証明
次は存在命題についてです。存在命題の証明手順は以下のとおりです。
- 集合$U$から元$x'$を一つだけ「自分で選んで」取ってくる
- 述語$P(x)$に元$x'$を代入した命題$P(x')$が真であることを証明する
さて、存在命題のポイントは2つあります。
1つ目は元$x'$を「自分で選んでとってくる必要がある」ことです。もっと突っ込むと「述語P(x)に代入したら真になる元を一つでもいいから自分で見つけてきて、それを使う」ということです。先程の全称命題との違いは「全部じゃなくて、一つ値をみつけてきてしまえばそれでおっけー」ということです。...ちょっとわかりにくいですかね。これについても後ほど例題を通して理解していきましょう。
2つ目は「都合のいい$x'$を見つけてくる過程は証明に記さなくていい」という点です。とにかく、「こんな$x'$を突っ込めば真になるからそれでよくね」というスタンスで行けばいいのです。これも例題を通して理解していきましょう。
さて例題です。
例. $\exists (x, y) \in \mathbb R^2 \ \ [x^2 + y^2 = 1]$
こちらも手順にしたがって証明していきましょう。まず$\mathbb R^2$の元の一つとして$(x, y) = (1, 0)$を取ってきます。このとき述語$P(x, y): x^2 + y^2 = 1$に代入すると$1^2 + 0^2 = 1$となり、$P(1, 0)$は真であることが証明されました。よって、題意は示されました。
0.3. ならばの証明の方法
最後に「ならば($A \ \Rightarrow \ B$)」の型の証明の方法を教えます。これに関しては割とみなさんが慣れ親しんだ形だと思いますが、復習も兼ねてしっかりと確認しておきましょう。ならば型の証明の方法を以下のとおりです。
- 全称命題の証明の通り、集合$U$から任意に$x$を取ってくる
- 命題$A$が成立することを仮定する
- $A$が成り立つことを利用して命題$B$が真であることを証明する
最初の「全称命題の〜」が気になりますが...、これも例題を通して確認してみましょう。その際の注意点も一緒に説明します。
例. $x \neq 0 \Rightarrow x^2 > 0$
さて、この命題をみて、こう思った人がいるのではないでしょうか？「これって$P(x) \Rightarrow Q(x)$みたいな述語ならば述語の形だから、コレ自体も述語何じゃないの？」これは至極まっとうな意見だと思います。さて、このことを解決するにはこの命題の背後には全称記号が隠れていることを意識しなければいけません。何が言いたいかといいますとこの命題を正しく書き直すと次のような形になるということです。
\forall x\ [ x \neq 0 \Rightarrow x^2 > 0 ]
このことを念頭において証明にかかりましょう。さて、まずは全称命題の証明方法に則って$x'$を任意に取ってきましょう。すると、示すべき命題は$x' \neq 0 \Rightarrow x'^{\ 2} > 0$となります。では次のステップに移りましょう。次$x' \neq 0$が成立することを仮定します。最後にこの仮定のもとで$x'^{\ 2} > 0$が成り立つことを示します。...が、これはとても自明なことなのでまぁいいでしょう。以上のことより$x \neq 0 \Rightarrow x^2 > 0$が真であると証明されました。
補足
証明の中で$x = 0$の場合を考慮していませんでしたが、この場合、そもそも仮定を満たしていなことになります。このとき「$A \Rightarrow B$」という命題は必ず真になるため、仮定が偽になる場合は考慮する必要がないのです。
1. ε論法の定義
ε論法とは数列や関数の極限の定義そのものです。まずは数列の極限に関するε論法を見てみましょう。
定義: 数列の極限
\lim_{n \to \infty} a_n = \alpha \Leftrightarrow \forall \epsilon > 0, \exists n_0 \in \mathbb N\ \ [n \geq n_0 \Rightarrow | a_n - \alpha | < \epsilon ]
次に関数の極限に関するε論法を見てみましょう。
定義: 関数の極限
\lim_{x \to a}f(x) = \alpha \Leftrightarrow \forall \epsilon > 0, \exists \delta > 0 \ \ [| x - a | < \delta \Rightarrow | f(x) - \alpha | < \epsilon]
数列のε論法について解読してみると「どんな正の$\epsilon$に対しても、$n \geq n_0$ならば$|a_n - \alpha| < \epsilon$となる整数$n_0 \in \mathbb N$が少なくとも一つは存在する」です。...意味はわかりにくいですが、私達は今回この論理式を読み解けれさえできていればそれでいいです。ちなみに、関数の極限に関するε論法については端折りましたが、同じように読み解くことができます。では、実際に問題を解いて見ましょう。
2. 「収束するならば収束する」の証明
では以下の命題を証明してみましょう。
[\lim_{n \to \infty}a_n = \alpha, \lim_{n \to \infty}b_n = \beta] \Rightarrow [\lim_{n \to \infty}(a_n + b_n) = \alpha + \beta]
さて、まずは$\lim_{n \to \infty}a_n = \alpha, \lim_{n \to \infty}b_n = \beta$を仮定します。これはすなわち次の命題が成立することを示しています。
\forall \epsilon > 0 , \exists n_a \in \mathbb N, [n \geq n_a \Rightarrow |a_n - \alpha| < \epsilon]
\forall \epsilon > 0, \exists n_b \in \mathbb N, [n \geq n_b \Rightarrow |b_n - \beta| < \epsilon]
次に$\lim_{n \to \infty}(a_n + b_n) = \alpha + \beta$を示していきます。まずこの命題は全称命題なので、$\epsilon > 0$を任意に取ってきます。すると任意の$\epsilon$に対して示すべき命題は$\exists n_0 \in \mathbb N \ [n \geq n_0 \Rightarrow |(a_n + b_n) - (\alpha + \beta)| < \epsilon]$となります。さて、これは存在証明なので、中の命題を満たす$n_0$を見つけてくる必要があります。この$n_0$を次のように定義します。
n_0 = \text{max}(n_a, n_b)
このようにすると仮定した$a_n$と$b_n$の収束性から$n \geq n_0$のとき
\begin{align}
|(a_n - \alpha) + (b_n - \beta)| &\leq |a_n - \alpha| + |b_n - \beta| \ \ \text({三角不等式より)} \\
&< \epsilon + \epsilon \ \ \text{(仮定した収束性より)}\\
&= 2\epsilon
\end{align}
よって$\epsilon$で抑えることができたので、題意は示されました。
このように論理学について知見を得ると、あれだけ怖かったε論法も可愛く見えてきません...か？
終わりに
いかがでしたでしょうか？論理学の視点からε論法をみてみるとまた違った面白さが見えてくると思います。そういえばなにかセクションを忘れているような気がしなくもないですが...。まぁ終わったことですし、気にしなくていいんです！(実際には私の気力がなくなってしまったからというのが大きいのですが...)
さて、次回はbubuzukeくんによる記事です。MBPかホップフィールドネットワークの話をしてくれるとか。リアルでも彼とは面識がありますが、彼のそこしれない知識の一端を垣間見ることができる気がして、明日が楽しみです。それでは、bubuzukeくんに圧激励のことばとともにこの記事を閉めようと思います。「たのしみにしています！」
その他
2024/12/02 21:51 一部間違いを訂正しました。