# π 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

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

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)\):

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\).

**By contradiction**

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

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.

**By mathematical induction**

Example

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

## 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

Each lecture will suggest some material for further reading and learning

YouTube video on Wason selection task