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.