Proof

What is a proof? It’s a way of showing that some belief we have about a relationship between mathematical objects is always true (for a given set of assumptions). In this video I introduce proof and some terminology used for talking about proofs.

Watch the video and then answer the questions below.

Eleven-minute video

You can also view this video on YouTube

You can find the slides here and also as .odp.

Key Points

Definitions

  • A definition gives names to particular mathematical objects to allow us to refer to them, like “Let a be an integer”, or “Let S(n) be the sum of the first n natural numbers”
  • An axiom, or postulate is something you assume to be true before you begin your proof, and that you do not attempt to prove.
  • A conjecture is something we think might be right - something that is interesting enough to try and prove.
  • A theorem is a conjecture that has a proof - so long as the proof is valid, theorems must be true.
  • A proof is a mathematical argument that a theorem is true, or it is the activity of creating such an argument.
  • A lemma is intermediary conclusion that is proved as part of proving a theorem.
  • A corollary is something that follows directly once a theorem has been proved.

It’s also useful to know that:

  • An even number (integer) m can be written as m = 2k for some (integer) k.
  • An odd number (integer) m can be written as m = 2k + 1 for some (integer) k.

Direct Proof

A direct proof is a series of steps that takes us from what we have assumed to our conclusion. They make use of modus ponens.

Modus Ponens is the most basic form of logical argument. It has two premises (P1 and P2 below) and a conclusion (C)

P1:  If P then Q
P2:  P is true
C:   Q is true

In propositional logic, this would be (P ⇒ Q) ∧ P ⇔ Q.

For example, to attempt to construct a direct prove the conjecture “if x is odd, x2 is odd”, you would work forwards from the antecedent “x is odd” until you can prove the consequent “x2 is odd”.

Example Proof

Theorem: If x is an odd number x2 is an odd number.

Proof: Let x be an integer. If x is odd, then x = 2k + 1.

Thus, x2 = (2k + 1)2

x2 = 4k2 + 4k + 1

As 4k2 + 4k is divisible by 2, it is an even number. Therefore, as we add 1 to get 4k2 + 4k + 1 = x2, this must be an odd number ■

Questions

1. Check your knowledge

In which of the following cases would direct proof be appropriate?

Check Answers

2. On paper

Spot the error in the following proof

“Theorem”: 1 = 2

“Proof”: Let a = b. Then

ab = a2

a2 + ab = a2 + a2

a2 + ab = 2a2

a2 + ab − 2ab = 2a2 − 2ab

a2 − ab = 2a2 − 2ab

1(a2 − ab) = 2(a2 − ab)

Dividing both sides of the equation by a 2 − ab, we get

1 = 2 ∎

Prove the following
  1. If m^2 is even, then m is even
  2. If m is odd, then m^2 is odd
Divisibiliy Proof

A number, n is said to be divide another number a (written n | a, or “b divides a”) if there is some natural number i such that ni = a. In other words, n divides a if and only if there is a whole number you can multiply by n to get a. Here i is just a variable - we could use a different one if we wish.

That means in a proof where we are trying to show n | a, we can replace it with the formula a = ni.

  1. For the given n, a, show n|a by finding an i with a = ni. For example, to show that 9 | 36, we can observe that 9i = 36 where i=4
    1. 6|18
    2. -5|30
    3. 3|-9
    4. -10|−100
    5. 1|34
  2. Prove, directly from the definition of |, that for any integer x≠0, x|0, 1|x and x|x.
  3. Let a and b be integers where a≠0. Prove that if a | b, then a2 | b 2.

Summary

In this section we have learned about proof.

  • You should be able to recognise where direct proof may be appropriate, and use it to prove simple theorems.
  • You should be able to use the definition of odd and even numbers in proofs.

In the next section, we will look at another technique for proof, proof by cases.