それでは、Week 4です。引き続き Quantifiers についてです。基礎から応用へ向けて、の内容となります。
講義自体は、YouTube で公開されてます。リンクがこちらにあるので、興味がある人はぜひ。
https://www.youtube.com/watch?v=LN7cCW1rSsI
※ あくまで素人が趣味で防備のノートとしてまとめているだけなので、解釈違い、数学的な厳密さの欠如についてはご容赦ください。
Lecture 6A – Working with Quantifiers 1
Let \( A(x) \) be some property of x. (e.g., x is a real root of the equation: \( x^2 + 2x + 1 = 0 \) )
We’ll show that \( \lnot [\forall x A(x)] \) is equivalent to \( \exists x [ \lnot A(x) ]\).
e.g., “It is not the case that all motorists run red lights.” ⇔ “There is a motorists who does not run red lights.”
\( \Rightarrow \) Assume \( \lnot [\forall x A(x)]\). If it is not the case that for all x. \( A(x) \), then at least one x must fail to satisfy \( A(x) \).
So, for at least one x, \( \lnot A(x)\) is true.
In symbols, \( \exists x [\lnot A(x)]\).
\( \Leftarrow \) Assume \( \exists x [\lnot A(x)]\). Then there is an x for which A(x) is false.
Then \( A(x) \) cannot be true for all x. In other words, \( \forall x A(x) \) must be false.
In symbols, \( \lnot [\forall x A(x)] \).
And so, \( \lnot[ \exists x A(x)] \Leftrightarrow \forall x [\lnot A(x)] \)
“All domestic cars are badly made.”
Let C be the set of all cars, \( D(x) \) means x is domestic, \( M(x) \) means x is badly made.
\( (\forall x \in C) [D(x) \Rightarrow M(x) ] \)
Negation is \( (\exists x \in C) \lnot [D(x) \Rightarrow M(x)] \)
\( \lnot [D(x) \Rightarrow M(x)] \) is \( D(x) \land \lnot M(x) \).
So \( \lnot (\forall x \in C) [D(x) \Rightarrow M(x) ] \) is equivalent to:
\( (\exists x \in C) [D(x) \land \lnot M(x) \)
i.e., “There is a domestic car that is not badly made.”
Lecture 6B – Working with Quantifiers 2
“All prime numbers are odd.”
Let \( P(x) \): x is prime, \( Q(x) \): x is odd
Negate \( \forall x [P(x) \Rightarrow O(x)] \):
\( \lnot \forall x [P(x) \Rightarrow O(x)] \Leftrightarrow \exists x [P(x) \land \lnot O(x) ]\)
In words. i.e., “there is a prime that is not odd. “
なお、ここで、
\( \lnot (\forall x \gt 2) [P(x) \Rightarrow O(x)] \) は、
\( \quad (\exists x \leq 2) [P(x) \land \lnot O(x)] \) とはならずに、
\( \quad (\exists x \gt 2) [P(x) \land \lnot O(x)] \) となることに注意。
記号を操作するだけではなく、命題の意味を理解することが重要。
Let x denote a person.
\( P(x) \): “x plays for sports team T.”
\( H(x) \): “x is healthy.”
So \( \exists x [P(x) \land \lnot H(x)] \) means “There is an unhealthy player on team T.”
Negating:
\( \quad \lnot \exists x [P(x) \land \lnot H(x)] \)
\( \quad \forall x \lnot [P(x) \land \lnot H(x)] \)
\( \quad \forall x [\lnot P(x) \lor H(x)] \)
\( \quad \forall x [ P(x) \Rightarrow H(x)] \)
Then it means “All players on team T are healthy.”
量化子(Quantifier) の領域について:
Domain of quantification という言葉がある。-> What does the x denote? ということ。
例えば、x が「人間」や「自動車」を表すのであれば、上の命題は意味を成さない。
そして、数字に限った話であっても、\( \forall x [ x \gt 0 \Rightarrow \exists y (xy=1)] \) という命題は、真にも偽にもなりうる。
e.g., \( x \in \mathbb{N} \) の時は偽であるし、\( x \in \mathbb{Q} \) の時は真である。
To make this more explicit, it is written as:
\( (\forall x \in \mathbb{Q}) [ x \gt 0 \Rightarrow \exists y (xy=1)] \)
ここで、x が有理数であるならば、y も有理数であると考えるのは合理的である。
もちろん、より明確に
\( (\forall x \in \mathbb{Q}) [ x \gt 0 \Rightarrow (\exists y \in \mathbb{Q}) (xy=1)] \) とも記述できる。
If there’s any possibility of misunderstanding or if there’s any potential ambiguity, it’s better to be explicit everywhere as to what the quantifiers denote.
Mathematicians sometimes omit quantifiers.
例えば、\( x \geq 0 \Rightarrow \sqrt{x} \geq 0 \) という命題は、
What that means is something like:
\( (\forall x \in \mathbb{R})[x \geq 0 \Rightarrow \sqrt{x} \geq 0] \) であるということが、推定される。
This is what’s known as implicit quantification. <- AVOID DOING THIS!
There is a caution about combining quantifiers with conjunction and disjunction.
Let \( \mathbb{N} \), the set of natural numbers, be the domain of quantification.
Let \( E(x) \): x is even, \( O(x) \): x is odd.
\( \forall x [ E(x) \lor O(x) ] \) … True
\( \forall x E(x) \lor \forall x O(x) \) … False
and the same thing happens
\( \exists x [ E(x) \land O(x) ] \) … False
\( \exists x E(x) \land \exists x O(x) \) … True
また、
\( \forall x [A(x) \lor B(x)]\) is NOT equivalent to \( \forall x A(x) \lor \forall x B(x) \)
\( \forall x [A(x) \land B(x)]\) is equivalent to \( \forall x A(x) \land \forall x B(x) \)
\( \exists x [A(x) \land B(x)]\) is NOT equivalent to \( \exists x A(x) \land \exists x B(x) \)
\( \exists x [A(x) \lor B(x)]\) is equivalent to \( \exists x A(x) \lor \exists x B(x) \)
したがって、以下のようなイメージを持つと良い
\( \forall \) is “like” \( \land \) … all
\( \exists \) is “like” \( \lor \) … at least one
基本的には、命題の domain of quantification を明確にし、そのあとは、明確にしたドメインのサブセットであっても新たなドメインを持ち込まない方が望ましい。
正しい or 誤っている、という観点からではなく、わかりやすい or わかりにくいの観点から。
まとめ
最後に、「Tutorial for Assignment 6」で、練習問題の解説がありますが、いわゆるイプシロン-デルタ論法について言及されます。これはなかなかの見ものです。
ご存知、かの悪名高い以下は、連続であることを示し、
\( (\forall \epsilon \gt 0)(\exists \delta \gt 0)(\forall x) \left[ \vert x-a \vert \lt \delta \Rightarrow \vert f(x)-f(a) \vert \lt \epsilon \right] \)
これの否定をとると
\( (\exists \epsilon \gt 0)(\forall \delta \gt 0)(\exists x) \left[ \vert x-a \vert \lt \delta \land \vert f(x)-f(a) \vert \geq \epsilon \right] \)
となるが、当然これは「非連続」であることを示します。
この辺りを図を用いて説明してくれるあたり、かなりイメージしやすかったです。
量化記号の意味をしっかり理解して、かつ、適切に操作するってのが大事ですね。それに、いろいろと記号で書いてるだけでも、なんだかかなり数学やってる感が出ます。
それでは、引き続き Module 5 もやっていきます。
コメント