1Proofs and logic

IA Numbers and Sets

1.2 Examples of proofs

Apart from having a proof, it is very important that a proof is correct. Here we

will look at some examples of proofs and non-proofs.

We first start with a simple example.

Proposition. For all natural numbers n, n

3

− n is a multiple of 3.

Proof.

We have

n

3

−n

= (

n −

1)

n

(

n

+ 1). One of the three consecutive integers

is divisible by 3. Hence so is their product.

Proposition. If n

2

is even, then so is n.

Proof.

If

n

is even, then

n

= 2

k

for some integer

k

. Then

n

2

= 4

k

2

, which is

even.

This is incorrect! We wanted to proof “

n

2

is even”

⇒

“

n

is even”, but what

we proved is “n is even” ⇒ “n

2

is even”, which are distinct statements.

Instead, a correct proof is as follows:

Proof.

Suppose

n

is odd. Then

n

= 2

k

+ 1 for some integer

k

. Then

n

2

=

4

k

2

+ 4

k

+ 1 = 2(2

k

2

+ 2) + 1, which is odd. This contradicts our assumption

that n

2

is even.

This is an example of proof by contradiction. We assume what we want to

prove is false, and show that this leads to nonsense.

Proposition. The solutions to x

2

− 5x + 6 = 0 are x = 2 and x = 3.

Note that these are actually 2 different statements:

(i) x = 2 and x = 3 are solutions

(ii) There are no other solutions

We can write this as an “if and only if” statement:

x

is a solution if and only if

x

= 2 or

x

= 3. Alternatively, we say “

x

is a solution iff

x

= 2 or

x

= 3”; or “

x

is a solution ⇔ x = 2 or x = 3”.

Proof.

(i) If x = 2 or x = 3, then x − 2 = 0 or x − 3 = 0. So (x − 2)(x − 3) = 0.

(ii)

If

x

2

−

5

x

+ 6 = 0, then (

x −

2)(

x −

3) = 0. So

x −

2 = 0 or

x −

3 = 0.

Then x = 2 or x = 3.

Note that the second direction is simply the first argument reversed. We can

write this all in one go:

x = 3 or x = 2 ⇔ x − 3 = 0 or x − 2 = 0

⇔ (x − 3)(x − 2) = 0

⇔ x

2

− 5x − 6 = 0

Note that we used the “if and only if” sign between all lines.

We’ll do another non-proof.

Proposition. Every positive number is ≥ 1.

Proof. Let r be the smallest positive real. Then either r < 1, r = 1 or r > 1.

If

r <

1, then 0

< r

2

< r

. Contradiction. If

r >

1, then 0

<

√

r < r

.

Contradiction. So r = 1.

Now this is obviously false, since 0

.

5

<

1. The problem with this proof is

that the smallest positive real need not exist. So we have to make sure we justify

all our claims.