📖 Logic and proofs

📖 Logic and proofs#

⏱ | words

The Wason selection paradox#

  • Mathematics relies on rules of logic

  • Yet, for human brain applying mathematical logic may be difficult, and dependent on the domain

_images/wason.png

  • Peter Cathcart Wason (1924 – 2003)

  • cognitive psychologist at University College, London

  • pioneered the psychology of reasoning

The Wason selection task

Given four cards showing 3, 8, blue and red faces, which cards have to be flipped over to ensure the rule if card shows even number on one side, the other side is blue is satisfied?

Let’s play Wason Selection Task at Mentimeter

Analysis of Wason selection task

  • Let \(P\) denote card shows even number on one side

  • Let \(Q\) denote the side is blue

Numbver

Color

\(P\)

\(Q\)

Rule is satisfied

Even

Blue

True

True

Yes

Even

Red

True

False

No

Odd

Blue

False

True

Yes

Odd

Red

False

False

Yes

  • the rule we are checking is \(P \implies Q\)

  • it is only brocken in case \(P\) is True and \(Q\) is False

  • therefore the two cards that have to be flipped are

    • Even, \(P\) is True

    • Red, \(Q\) is False

Definition

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

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}\]

Definition

A logical statement \(P \implies Q\) is converse to \(Q \implies P\)
A logical statement opposite to \(P\) is denoted \(\neg P\)
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#

  1. 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

Proof on the board

  1. 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.

  1. 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

Proof on the board

References and further reading#

References

  • [Simon and Blume, 1994]: Appendix A1.3 Proofs (pp.851-855).

  • [Sundaram, 1996]: Appendix A.2 Propositions: Contrapositives and Converses (p. 316), Appendix A.4 Necessary and Sufficient Conditions (p. 320)

Further reading and self-learning
Contents