引き続き進めていきます。Week 6 です。もう少し Proof(証明) に踏み込んだ内容となります。
講義自体は、YouTube で公開されてます。リンクがこちらにあるので、興味がある人はぜひ。
https://www.youtube.com/watch?v=LN7cCW1rSsI
※ あくまで素人が趣味で防備のノートとしてまとめているだけなので、解釈違い、数学的な厳密さの欠如についてはご容赦ください。
Lecture 8A – Proofs with Quantifiers 1
To prove \( \exists x A(x) \). The obvious way is to find an object \( a \) for which \( A(a) \).
e.g., To show there is an irrational number, prove that \( \sqrt{2} \) is irrational.
This does not always work. Sometimes we use indirect proofs.
Theorem: There are irrationals \( r, s \) such that \( r^{s} \) is rational.
Proof: we consider two cases.
Case 1, If \( \displaystyle \sqrt{2}^{\sqrt{2}} \) is rational, take \( r = s = \sqrt{2} \).
Case 2, If \( \displaystyle \sqrt{2}^{\sqrt{2}} \) is irrational, take \( \displaystyle r = \sqrt{2}^{\sqrt{2}} \) and \( s = \sqrt{2}\).
Then \( \displaystyle r^{s} = (\sqrt{2}^{\sqrt{2}}) ^ \sqrt{2} = (\sqrt{2} \ )^ {\sqrt{2} \sqrt{2}} = ( \sqrt{2} \ )^{2} = 2 \).
The theorem is proved.
This technique is known as “Method of proof by cases“.
この証明方法は面白いです。
Case 1 のように前提条件がそもそも rational(有理数) であれば、その場合の証明が完結し、逆に同様の前提条件の Case 2 で、irrational (無理数) である場合にのみ有理数となるような具体例を見つけ出す。 前提条件の設定の仕方が肝ですね。
To prove \( \forall x A(x) \) : One way is to take an arbitrary \( x \) and show that it satisfies \( A(x) \).
e.g., To prove \( \forall n \exists m ( m \gt n^{2}) \).
Let \( n \) be an arbitrary natural number. Set \( m = n^{2} + 1 \). Then \( m \gt n^{2} \).
This proves \( \exists m ( m \gt n^{2}) \). It follows that \( \forall n \exists m ( m \gt n^{2}) \).
NOTE: This works because the “\( n \)” is arbitrary.
ここで、「任意の」自然数とは「すべての」自然数の意味合いなのであり、「任意に特定の自然数を選ぶ」ということではないことにも注意。
Another approach is to use the method of contradiction.
To prove \( \forall x A(x) \), assume \( \lnot \forall x A(x) \).
This is equivalent to \( \exists x \lnot A(x) \). Let \( c \) be an object such that \( \lnot A(c) \).
Now reason with c (and the fact that \( \lnot A(c) \)) to derive a contradiction.
To prove: \( (\forall x \gt 0) (\exists y \gt 0) [ x \lt y ] \), where variables range over rational numbers.(which means given any positive rational, you can always find a smaller one.)
To prove it, pick a positive rational \( p \) arbitrary, say \( p = 0.001 \). Take \( q = 0.0001 \). Thus \( 0 \gt q \gt p \). <= WRONG IDEA!
Since our choice of \( p \) was arbitrary, this proves the desired result.
Letting p be arbitrary is not the same as picking in arbitrary fashion a specific p. The choice may have been arbitrary but once you’ve made it, it’s specific.
ちょっと面白いイディオムがあったので、-> “And to drive this point home, let me give you an example.”
ここで、”home” は、「原点」や「中心」みたいな意味で使われてるみたいですね。
drive your message/point home
to state something in a very forceful and effective way:
ついでに、英語で反面教師は、”cautionary tale” というみたいです。「教師」というよりも、「教訓」のような意味合いの方が、字面的には強いかも。 => “And it’s a cautionary tale telling us not to jump to conclusions based on numerical evidence.”
cautionary tale
a story that gives a warning:
続いて、induction：帰納法についてです。ちなみに、deduction が対義語、演繹です。
INDUCTION
To prove statements of the form \( \forall n A(n) \), where \( n \) ranges over the natural numbers.
e.g., Prove that \( \displaystyle 1+2+3+ … +n = \frac{1}{2} n (n=1) \)
First step: check the first few steps
\(\displaystyle n=1, \ 1 = \frac{1}{2} \cdot 1 \cdot (1+1) = \frac{1}{2} \cdot 1 \cdot 2 = 1 \)
\(\displaystyle n=2, \ 1+2 = \frac{1}{2} \cdot 2 \cdot (2+1) = \frac{1}{2} \cdot 2 \cdot 3 = 3 \)
\(\displaystyle n=3, \ 1+2+3 = \frac{1}{2} \cdot 3 \cdot (3+1) = \frac{1}{2} \cdot 3 \cdot 4 = 6 \)
This is NOT a proof. => BEWARE OF JUMPING TO CONCLUSIONS!
Consider the formula, \( P(n) = n^2 – n + 41 \). All values of \( P(n) \) for \( n = 1, 2, 3, … \) etc are prime numbers until you reach \( n = 41 \). \( P(41) = 1681 = 41^{\ 2} \). This example is due to the famous Swiss mathematician, Leonard Euler in 1772.
METHOD | PRINCIPLE OF MATHEMATICAL INDUCTION
To prove \( \forall n A(n) \), establish the following two statements:
- \( A(1) \) Initial case, initial step.
- \( (\forall n) [ A(n) \Rightarrow A(n+1) ]\). (Induction step)
Intuitively, this gives \( \forall n A(n) \) as follows: By step 1, \( A(1) \). By step 2, \( A(1) \Rightarrow A(2) \). So from \( A(1) \) we can conclude \( A(2) \). By \( A(2) \) and the induction step, we can conclude \( A(3) \), etc.
(So this basically says, knock the first domino down. And put the domino close enough together. So that when one falls, the next falls.)
いわゆる、学生時代に習う数学的帰納法です。（ドミノの絵も描いてあったような)
You need an axiom (or principle) to make this work called the principle of mathematical induction.
The PMI is what tells you that step 1 and 2 above yield \( \forall n A(n) \)
Theorem: For all \( n \). \( \displaystyle 1+2+3+ … +n = \frac{1}{2} n (n+1) \).
Proof: By mathematical induction.
For \( n = 1 \), the identity reduces to \( \displaystyle 1 = \frac{1}{2} (1)(1+1) = \frac{1}{2} \), which is true, since both sides equal 1.
ここで、equation: 方程式 ではなく、identity: 恒等式 という表現が使われていることに注意。
equation は解を求めるためのものであり、identity は等しいことを示すために用いられる。(ただし、数学者でも日常会話では、両者の境界は曖昧になりがち)
The expression is an equation if it can be solved for x.
The expression is an identity if it is valid for all x.
Wikipedia -> Identity
Assume the identity hold, for \( n \), i.e., \( \displaystyle 1+2+3+ … +n = \frac{1}{2} n (n+1) \). -(*)
[ Want to deduce, \( \displaystyle 1+2+3+ … +(n+1) = \frac{1}{2} (n+1) \left \{ (n+1)+1 ) \right \} \). ]
Add \( (n+1) \) to both sided of (*):
\( \displaystyle 1+2+3+ … +n+(n+1) = \frac{1}{2} n(n+1) + (n+1) =\frac{1}{2} [n(n+1) + 2(n+1)] \)
\( \displaystyle \qquad \qquad \frac{1}{2} [n^2 + n + 2n + 2] = \frac{1}{2} [n^2+3n+2] \)
\( \displaystyle \qquad \qquad \frac{1}{2} [(n+1)(n+2)] = \frac{1}{2} (n+1) \left \{ (n+1)+1 ) \right \} \),
which is the identity with \( n+1 \) in place of \( n \).
Hence, by the principle of mathematical induction, the identity holds. For all \( n \)
Lecture 8B – Proofs with Quantifiers 2
いきなり珍しい表現があったので、”set sth on fire” はもちろん「火をつける」って意味もありますが、この文脈では「興奮させる、震撼させる」って意味の方がしっくりきます。
Okay, this result is not going to set the mathematical world on fire, but it is a good example to illustrate the way mathematical induction works.
set something/someone on fire
to cause something or someone to start burning:
Theorem: Of \( x = 0 \), then for any \( n \), \( (1+n)^{\ (n+1)} \gt 1+(n+1)x \).
Proof: By mathematical induction, let \( A(x) \) be the statement \( (1+x)^{(n+1)} \gt 1 + (n+1)x \).
I will prove \( \forall n A(n) \).
\( A(1) \) is the statement \( (1+x)^2 \gt 1+2x \) (since \( x^2 \gt 0\))
To prove \( \forall n [A(n) \Rightarrow A(n+1)] \). Pick an arbitrary \( n \) and prove \( A(n) \Rightarrow A(n+1) \).
We assume \( A(n) \) and deduce \( A(n+1) \), where \( A(n) = (1+x)^{(n+1)} \gt 1 + (n+1)x \) and \( A(n+1) = (1+x)^{(n+2)} \gt 1 + (n+2)x \).
\( (1+x)^{(n+2)} = (1+x)(1+x)^{(n+1)} \gt (1+x) [1 + (n+1)x] \)
\( \hspace{ 13em } = 1 + (n+1)x + x + (n+1)x^2 \)
\( \hspace{ 13em } = 1 + (n+2)x + (n+1)x^2 \gt 1 + (n+2)x \)
This proves \( A(n+1) \). The theorem follows by induction.
INDUCTION – SUMMARY
- You want to prove that some statement \( A(n) \) is valid for all natural numbers \( n \).
- First prove \( A(1) \). Usually a matter of single observation.
- Give an algebraic argument to establish the conditional, \( A(n) \Rightarrow A(n+1) \).
— deduce \( A(n+1) \) to a form where you can use \( A(n) \). - Conclusion: By the principle of mathematical induction, this proves \( \forall n A(n) \).
INDUCTION — COMMON VARIANT
We sometimes need to prove a statement of the form
\( \hspace{5em} (\forall n \ge n_0) A(n) \).
The first step is to verify \( A(n_0) \). [\( A(1) \) may not be true.]
The induction step is to prove,
\( \hspace{5em} (\forall n \ge n_0) [A(n) \Rightarrow A(n+1) ] \).
e.g., The Fundamental Theorem of Arithmetic.
Definition: A prime number is a positive integer \( n \), greater than 1, whose only exact divisors are 1 and \( n \).
Also: 0 is not a natural number.
Theorem: Every natural number greater than 1 is either a prime or a product of primes.
Proof: By induction. The induction statement, \( A(n) \) is:
\( \hspace{3em} \forall n [2 \le m \le n \Rightarrow m \text{ is either a prime or a product of primes.}] \)
For \( n=2 \), \( A(2) \) says, “2 is either a prime or a product of primes”. This is true!
Assume \( A(n) \), and deduce \( A(n+1) \). Let \( m \) be a natural number, \( 2 \le m \le n+1 \).
If \( m \le n \), then by \( A(n) \), \( m \) is either a prime or a product of primes.
If \( m = n+1 \), and if \( n+1 \) is a prime, then n is a prime.
If \( m = n+1 \), and \( n+1 \) is not a prime, then there are natural numbers \( p, q \) such that \( 1 \lt p, q \lt n+1 \) and \( n+1 = pq \). Since \( 2 \le p,q \le n \). By \( A(n) \), \( p, q\) are either primes or products of primes. Hence ( n+1 ) is a product of primes. The theorem follows by induction.
ここで、”Proof by cases” の手法が2回使われている。
- \( m \le n \) の場合
- \( m = m +1 \) の場合：
- \( m = n+1 \), and if \( n+1 \) is a prime の場合
- \( m = n+1 \), and \( n+1 \) is NOT a prime の場合
また、\( A(n) \) の antecedent: 前件 が \( 2 \le m \le n \) のような表現となっているのは、最終的に、\( n+1 \) のケースでも \( A(n) \) を適用できるように導きたいため。
個人的には、\( 1 \lt p, q \lt n+1 \) という範囲は、自然数において、\( 2 \le p,q \le n \) と表現できるってとこが肝だと思ってます。
その他いろいろ
とりあえず珍しい表現があったので、
And one of the bricks I had drilled into me in high school, was that P squared minus 1 is P minus1, P plus 1.
drill something into someone
to tell someone something repeatedly so that they remember it:
こちらは辞書に載っているような表現ではなさそう。
I would have appeared that this was a rabbit out of a hat trick.
-> 帽子からウサギを取り出す＝奇術みたいに見える、みたいなニュアンスですかね。ちなみに、サッカーのハットトリックはまた違う語源みたいです（クリケットに起源がある）
続いて珍しい表現、”couch” カウチソファとかのカウチです。動詞としても使えるみたい、初めてみた。ソファに「横たわる」みたいなイメージで、「文として述べる」といったとこでしょうか。
One of the techniques is, just say, how could I possibly get the answer that I’m asked to find? Now, I’m couching this in terms of classroom questions.
couch something in/as something
to express something in a particular way:
数学の未解決問題の一つである The Goldbach conjecture: “Every even integer greater than 2 can be written as the sum of two primes.” が真と仮定して証明を行う謎の問題が出ます。-> 証明というより、言い換え？
まとめ
Since if \( x \) is a set with exactly one element, say \( x \) equals singleton \( a \), then there are just two subsets.
-> singleton: 単集合のこと
あまり聞いたことない表現だったので、メモ。
「実はそんなに難しくないことにやたらと時間を使う」って意味で使われてます。
Okay, I’m making heavy weather of this one just as I did in the previous one.
make heavy weather of something
to find something hard to do and spend a lot of time on it, although it is not difficult:
次はあまり一般的な用法ではないと思います。 cloak が 「隠すもの」転じて「数学者達の閉じた世界」のような意味で使われています。
It is trivial, but now it only works in the cloak of professional mathematicians, it’s certainly not the case that an undergraduate taking a course could get away with that.
cloak
something that hides, covers, or keeps something else secret:
最後、 Problem Set 6 は、集合理論やら整数論やらの基礎的な証明を読んで、何かしらの矛盾があるとかないとかを見つける問題が多いです。 個人的にちょっと苦手、、、このあたりは、個人的にもっと慣れていくべきですね。
学生の時に習った数学的帰納法は、主に数列に対して適用されていましたが、実際に、集合や整数関係の問題に利用される、その一片を見ることができただけでも価値ありかと思います。
まだまだ楽しめてるので、続いて、 Week 7 進めていきます。
それでは！
コメント