📖 Elements of logic and proofs

📖 Elements of logic and proofs#

⏱ | words

References and additional materials
_images/shsc2016.png

[Sydsæter, Hammond, Strøm, and Carvajal, 2016]

Chapters 1.3, 1.4

  • 3blue1brown Grant Sanderson’s video tale of two problem solvers YouTube

Definition

\(\implies\) denotes logical implication:
If whenever logical statment \(P\) is true, \(Q\) is also true, we write \(P \implies Q\).

Example

If \(x\) is an even number, then \(x^2\) is also an even number.

OR

\(x\) is an even \(\implies\) \(x^2\) is also even.

Necessary and Sufficient conditions#

Definition

\(P\) is a sufficient condition for \(Q\) means \(P \implies Q\)
\(P\) is a necessary condition for \(Q\) means \(Q \implies P\), or \(P \impliedby Q\)

Definition

\(P\) is said to be if and only if \(Q\) when \(P \implies Q\) and \(Q \implies P\), also written as \(P \iff Q\)

Example

\[\begin{split} x > 3 \implies x^2 >9 \text{ yet converse is not true} \\ x^2 > 9 \iff \{x > 3 \text{ or } x<-3\} \end{split}\]

Converse and contrapositive#

Definition

A logical statement \(P \implies Q\) is converse to \(Q \implies P\)

Definition

A logical statement opposite to \(P\) is denoted \(\neg P\)

Definition

A logical statement \(\neg P \implies \neg Q\) is contrapositive to \(Q \implies P\)

Fact: Contrapositive principle

The statement \(P \implies Q\) is equivalent to the statement \((\text{not } Q) \implies (\text{not }P)\):

\[ (P \implies Q) \iff (\neg Q \implies \neg P) \]

  • this is very handy in proofs: instead of proving a statement it may be easier to prove its contrapositive

Note

There is no logical relationship between a statement and its converse!

  • bases for common logical mistakes

Example

“All cats are animals who have tails” does not imply “All animals with tails are cats”

Types of mathematical proofs#

Direct proof#

\(A\) is true \(\implies\) \(B\) is True \(\implies\) \(S\) is True

Example

Prove that \(p^2-1\) is divisible by 24 for all prime \(p>3\).

Proof

Note that \(p^2-1 = (p-1)(p+1)\).

  1. Since \(p\) is prime, \(p\) is odd and \(p-1\) and \(p+1\) are even. Thus, \(p^2-1\) is divisible by 2 twice.

  2. Moreover, since \(p-1\) and \(p+1\) are two consecutive even numbers, one of them is divisible not only by 2, but also 4. Thus, \(p^2-1\) is divisible by 8.

  3. Finally, since \(p-1\), \(p\), and \(p+1\) are three consecutive integers, one of them is divisible by 3.

Overall, we have that \(p^2-1 = (p-1)(p+1)\) is divisible by 2, by 4, and by 3, and thus by its product 24. \(\blacksquare\)

Note

The symbol \(\blacksquare\) marks the end of the proof, and is equivalent to the QED symbol (”quod erat demonstrandum”, or “that which was to be demonstrated”).

Proof by contradiction#

\[\begin{split} \left. \begin{array}{r} \text{Assume } S \text{ is not True }\\ A \text{ is True} \end{array} \right \} \implies \text{Contradiction} \implies \text{Assumption was wrong} \implies S \text{ is True } \end{split}\]

Example

Prove that the set of prime numbers is infinite.

Proof

The standard proof of the infinitude of the primes is attributed to Euclid and uses the fact that all integers greater than 1 have a prime factor.

Lemma: Every integer greater than 1 has a prime factor.

Proof. We argue by induction (see below) that each integer \(n > 1\) has a prime factor. For the base case \(n = 2\), 2 is prime and is a factor of itself.

Now assume \(n > 2\), all integers greater than 1 and less than \(n\) have a prime factor. To show \(n\) has a prime factor, we take cases.

Case 1: \(n\) is prime. Since \(n\) is a factor of itself, \(n\) has a prime factor when \(n\) is prime.

Case 2: \(n\) is not prime. Since \(n\) is not prime, it has a factorization \(n = ab\) where \(1 < a,b < n\). Then by the inductive hypothesis, \(a\) has a prime factor, say \(p\). Since \(p | a\) and \(a | n\), also \(p | n\) and thus \(n\) has prime factor \(p\).

Theorem: There are infinitely many primes.

Proof. (due to Euclid) To show there are infinitely many primes, we’ll show that every finite list of primes is missing a prime number, so the list of all primes can’t be finite.

To begin, there are prime numbers such as 2. Suppose \(p_1, \ldots, p_r\) is a finite list of prime numbers. We want to show this is not the full list of the primes. Consider the number

\[ N = p_1 \cdot \ldots \cdot p_r + 1. \]

Since \(N > 1\), it has a prime factor \(p\) by Lemma 2.1. The prime \(p\) can’t be any of \(p_1, \ldots, p_r\) since \(N\) has remainder 1 when divided by each \(p_i\). Therefore \(p\) is a prime not on our list, so the set of primes can’t be finite.

Proof by mathematical induction#

\[\begin{split} \left. \begin{array}{r} S_1 \text{ is True }\\ S_n \text{ is True} \implies S_{n+1} \text{ is True} \end{array} \right \} \implies S_k \text{ is True for all } k=1,2,3,\dots \end{split}\]

Example

Prove that \(n^3+2n\) is divisible by 3 for all \(n=1,2,\dots\)

Proof

  1. Base of the induction: For \(n=1\), we have \(1^3+2\cdot 1 = 3\) which is divisible by 3. \(S_1\) is true.

  2. Induction step. Assume that \(n^3+2n\) is divisible by 3 for some \(n\), in other words that \(S_n\) is true. The job is to show that it is also true for \(n+1\), i.e. that \(S_{n+1}\) is true.

Writing the initial expression \(n^3+2n\) for \(n+1\) we have

\[ (n+1)^3+2(n+1) = (n+1)(n^2+2n+1)+2n+2 = \]
\[ =n^3+3n^2+3n+1 +2n+2 = (n^3+2n) + 3(n^2+n+1) \]

The second term is obviously divisible by 3, and the first term is divisible by 3 by the induction hypothesis. Thus, we have shown that \(S_{n+1}\) is also true.

  1. By the principle of mathematical induction, we have thus shown that \(n^3+2n\) is divisible by 3 for all \(n=1,2,\dots\) \(\blacksquare\)