Introduction to Mathematical Thinking, Week 5

お次は Week 5です。のんびり受講しているので、だいぶ時間がかかってますが、そろそろ中盤戦です。趣向が変わって、”Proofs” つまり「証明」についての内容となります。今までの、論理演算子とか量化記号とか使う感じかな？と受講前時点では予想してます。

講義自体は、YouTube で公開されてます。リンクがこちらにあるので、興味がある人はぜひ。
https://www.youtube.com/watch?v=LN7cCW1rSsI

※ あくまで素人が趣味で防備のノートとしてまとめているだけなので、解釈違い、数学的な厳密さの欠如についてはご容赦ください。

Lecture 7A – Proofs 1
1. Proof example #1
2. Proof example #2
Lecture 7B – Proofs 2
その他いろいろ
まとめ

Lecture 7A – Proofs 1

There is a connection in that a good proof will preemptively counter, explicitly or implicitly, all the objections, the counterarguments, that a reader might put forward.
要するに、「良い証明は、反論の余地をなくす」ということ。

Proofs are constructed for two many purposes, to establish truth and to communicate to others.
（数学的な）証明の目的とは大きく2つ、「真実を立証すること」、そして「それを伝達すること」

Proofs are about logical structure, not what they look like.
証明とは、論理的構造であって、どのように見えるかではない。

めずらしい単語があったので、
Proofs written for students or laypersons generally have to supply more explanations.

someone who is not an expert in or does not have a detailed knowledge of a particular subject:
専門家ではない人 -> 素人とか、一般の人。複数形は laypeople も可

layperson – Cambridge Dictionary

Proof example #1

Proposition: “There are infinitely many primes”

Proof:

List the primes in increasing order as \( p_1, p_2, p_3, … p_n, …\) and show that the list must continue forever.
Given the list up to some stage \( n \), \( p_1, p_2, p_3, … ,p_n \), show there is another prime that can be added to the list.
Let \( N \) be the number we get when we multiply together all the primes we have listed so far and then add 1.
\[ N = (p_1 \cdot p_2 \cdot p_3 \cdot … \cdot p_n ) + 1 \]
Obviously, \( N \) is bigger than all the primes in our list.
If \( N \) is prime, we know there is a prime bigger than \( p_n \), and then the list can be continued.
If \( N \) is not prime, then there must be a prime \( q \lt N \) such that \( q \) divides \( N \).
But none of \( p_1, … , p_n \) divides \( N \), since the division of \( N \) by any one of these leaves a remainder of 1.
So, \( q \) must be bigger than \( p_n \). Hence there is a prime bigger than \( p_n \), and the list can be continued.
Either way, there is another prime to added to the list.
It follows that there are infinitely many primes. The result is proved.

Proof example #2

Theorem: \( \sqrt{2} \ \) is irrational.

Proof:

Assume, on the contrary, that \( \sqrt{2} \ \) were rational.

Then there are natural numbers \( p, q \), with no common factors, such that

\[ \sqrt{2} = p/q \]

Squaring:

\[ 2 = p^2/q^2 \]

Rearranging:

\[ 2q^2 = p^2 \]

So \( p^2 \) is even. Hence \( p \) is even. So \( p = 2r \), for some \( r \).

Substituting for p: \( 2q^2 = (2r)^2 = 4r^2 \).

Cancelling the 2: \( q^2 = 2r \). So \( q^2 \) is even.

So \( q \) is even. So \( p, q \) are both even.

But this is impossible, since \( p, q \) have no common factors.

Hence \( \sqrt{2} \ \) must be irrational.

Q.E.D or ◻

Lecture 7B – Proofs 2

Proof of Contradiction:

You want to prove some statement \( \phi \).
You start by assuming \( \lnot \phi \).
You reason until you reach a conclusion that is false.
- often by deducing both \( \psi \) and \( \lnot \psi \) for some \( \psi \).
  e.g., “p, q have no common factors” and “p, q are both even”
A true assumption cannot lead to a false conclusion.
Hence the assumption \( \lnot \phi \) must be false.
In other words, \( \phi \) must be true.

Truth Table Analysis of Proof by Contradition:

What can we conclude from a proof of \( \theta \Rightarrow \psi \) when \( \psi \) is false? where \( \theta \Rightarrow \psi \) itself is true.

\( \theta \)	\( \psi \)	\( \theta \Rightarrow \psi \)
T	T	T
T	F	F
F	T	T
F	F	T

So \( \theta \) is false.

Another guideline:

We want to prove a conditional \( \phi \Rightarrow \psi \).

We know this is true if \( \phi \) is false, so we can assume \( \phi \) is true.

To prove it, we assume \( \phi \), and deduce \( \psi \).

For example, let \( x, y \) be variables for real number, and prove:

\[ \text{[ x, y are rational ]} \Rightarrow \text{[ x+y is rational.]} \].

Assume \( x, y \) are rational.

Then there are integers \( p, q, m, n \) such that \( x=p/m \), \( y=q/n \).

Then \( \displaystyle x+y =\frac{p}{m} + \frac{q}{n} = \frac{pn+qm}{mn} \).

Hence \( x+y \) is rational. Q.E.D.

Here is what we did:

We began by assuming \( x \) and \( y \) are rational.
There was an argument to demonstrate that. (in the middle)
We concluded that the sum is rational.

Conditionals involving quantifiers:

Conditionals involving quantifiers are sometimes best handled by proving the contrapositives. To prove \( \phi \Rightarrow \psi \), prove \( (\lnot \psi) \Rightarrow (\lnot \phi) \).

To prove:
\( (sin \theta \neq 0) \Rightarrow (\forall n \in \mathbb{N})(\theta \neq n \pi ) \).

The statement is equivalent to:
\( \lnot (\forall n \in \mathbb{N})(\theta \neq n \pi) \Rightarrow \lnot (sin \theta \neq 0 )\)

In positive form:
\( ( \exists n \in \mathbb{N})(\theta = n \pi) \Rightarrow (sin \theta = 0 )\)

To prove a bi-conditional \( \phi \Leftrightarrow \psi \):

we generally construct two proofs, one of \( \phi \Rightarrow \psi \), the other of \( \psi \Rightarrow \phi \).

Occasionally, it is easier to prove the two conditionals \( \phi \Rightarrow \psi \) and \( (\lnot \phi) \Rightarrow (\lnot \psi) \)

その他いろいろ

Prove that “between any two unequal rationals there is a third rational”.

Let \( x, y \in \mathbb{Q}, x \lt y\). Then \( \displaystyle x = \frac{p}{q}, y = \frac{r}{s} \), where \( p, q, r, s \in \mathbb{Z} \) となるが、例えば平均を取ると、

Then \( \displaystyle \frac{x+y}{2} = \frac{\frac{p}{q} + \frac{r}{s}}{2} = \frac{ps+qr}{2qs} \in \mathbb{Q} \)

But \( \displaystyle x \lt \frac{x+y}{2} \lt y \)

ちなみに、\( \mathbb{N} \)は自然数(Natural numbers)、\( \mathbb{Z} \)は整数(Integer)であるが、もろもろの事情で、Integer の頭文字である “I” ではなく、ドイツ語の Zahlen から来ている。