1.5 Proofs

What does it mean to prove a statement, and how do we go about this?

A proof is a sequence of steps used to demonstrate that a statement is true.

A proof will begin with a premise, meaning a collection of statements, or predicates, that we accept as true. This provides the context in which we are proving the statement. For example suppose we wanted to prove the statement:

For an integer $n>2$ there are no positive integer solutions $a,b,c$ to the equation \[a^n+b^n=c^n\] Then our premise would be that $n$ is an integer greater than $2$ and that $a,b,c$ are positive integers.

We would then try to prove that $a,b,c$ do not give solutions to the equation $a^n+b^n=c^n$.

The result that we wish to show is true (when the premise is true) is called the conclusion.

A proof consists of a sequence of predicates each of which is true, under the assumptions of the premise. However we require more than just the condition that the predicates are true. Consider the following:

Let $n>2$ be an integer and let $a,b,c$ be positive integers.

Then $a^n+b^n\neq c^n$.

Though the second statement is true, the above does not provide a proof of Fermat’s Last Theorem because we have not justified why the second statement follows from the first.

For a sequence of predicates to be accepted as a proof, each must be:

Something which we assume to be true: a premise, definition, or axiom.
Something we already know to be true: a statement we have previously proved.
An additional assumption meaning that we are considering a particular case. We are then beginning a subproof which will prove part of the original assertion: to complete the proof we must make sure that all possible cases are considered.
A predicate which follows directly from one or more of the earlier steps of the proof.

We will now look at various examples of proofs. There may be steps in some proofs for which the mathematical ideas need further discussion at a later point, but for the moment our focus is on the shape and structure of proofs.

We also remark that the proofs in this section may seem rather long-winded. This is because we want to be absolutely precise in terms of what is and is not allowed in a proof. In practice one often omits some of the simple and routine steps from a proof, or combines steps, which is justified by the belief that one could “fill in the gaps” if challenged. At least for now, we will justify each logical step of a proof (though we may still abridge some algebraic manipulations).

1.5.1 Direct Proof

Example 1.13

Let us prove the statement

if $n$ is even then $n^2$ is even.

Before we write a proof let’s analyse the statement.

The premise is “$n$ is even.”

The conclusion is “$n^2$ is even”

Working backwards:

Looking at the conclusion we ask the following key question:

How do we prove that a number is even?

When asking this question we want to keep it general rather than asking “how do we prove the $n^2$ is even?” as this helps us to focus on the idea rather than the details.

To prove that a number is even we need to show that it can be written as $2$ times some other integer. So our aim is to find this integer.

Now that we have answered the general question we give a specific target statement. We aim to prove the assertion: \[\text{there is an integer $l$ such that }n^2=2l\]

Working forwards:

Now looking at the premise, what do we know? Since $n$ is even, again it must be $2$ times some integer. We will give this integer the name $k$: \[\text{there is an integer $k$ such that }n=2k\] When we write this statement we must choose a different name $k$ for this integer than we had in our target statement.

Note there is an important difference between the predicates we were considering: “$n$ is even” and “$n^2$ is even”. The first is the premise so we are allowed to take this as a true assertion. The second is something that we are trying to prove, so we cannot write it down as part of our proof until we know that it is true.

What we can write down if we wish, since this is a true statement regarding the conclusion is the conditional:

if there is an integer $l$ such that $n^2=2l$ then $n^2$ is even

or even

$n^2$ is even if and only if there is an integer $l$ such that $n^2=2l$.

Writing the proof:

Here is the proof written out, indicating what the justification is for each step.

$n$ is even (premise)

there is an integer $k$ such that $n=2k$ (definition of even)

so $n^2=(2k)^2$ (substitution)

$n^2=(2k)^2=4(k^2)=2(2k^2)$ (algebraic manipulation)

let $l=2k^2$ (define a variable called $l$)

then $n^2=2l$ (substitution)

there is an integer $l$ such that $n^2=2l$ (by construction)

$n^2$ is even (definition of even)

We have now proved the statement

if $n$ is even then $n^2$ is even.

We will come back to the question of the allowed steps of algebraic manipulation later.

What about the substitution step? This involves the rules of equality which we will consider in the next section.

Recap of the strategy

The basic strategy for proving an “if premise then conclusion” statement is to begin by asking the question “what condition is required to prove a general statement of the form conclusion”. From this we obtain a target statement to work towards (e.g. “there is an integer $l$ such that $n^2=2l$”). We then write down the premise and any statements which immediately follow from that. These statements typically involving the definitions of any predicates in the premise (e.g. we translate “is even” into the existence of a suitable $k$). At this point we try to work from the premise towards our towards our target statement. Note that although the target statement is the first thing we think about here it should appear at (or near) the end of the proof, not the beginning.

1.5.2 Equality

What does $=$ mean? When we write $a=b$ we mean that $a,b$ refer to the same “thing.” Remember that when we discussed variables we said that a variable does not have to be a number. It might also refer to a set or a vector or something else.

When we write $a=b$ we mean that whatever type of object $a$ and $b$ refer to they are indistinguishable from one another.

Since equality can apply across all sorts of different mathematical objects we will consider the properties of this separately from other algebraic properties which will vary depending upon he context. (For instance: $ab=ba$ is true for integers, real numbers or even complex numbers, but $AB=BA$ is false for matrices; if $b\neq 0$ then $ax=b$ is equivalent to $x=a/b$ for real or rational numbers but $a/b$ is not defined for integers. Algebra is therefore specific to the collection of values which are allowed for the variables.)

Here are some key properties of equality.

for any $a$, the statement $a=a$ is true
for any $a$ and $b$, the statement $a=b$ is true if and only if $b=a$ is also true
for any $a,b$ and $c$, if $a=b$ and $b=c$ are true then $a=c$ is true

We say that equality is:

reflexive $a=a$
symmetric $a=b \iff b=a$
transitive $a=b \;\land\; b=c \implies a=c$

Equals has one other important property which is substitution:

if $a=b$ then for any true statement involving $a$ we may replace one or more occurrences of $a$ with $b$.

This is the rule which allows us to conclude from $n=2k$ (and of course $n^2=n^2$) that $n^2=(2k)^2$.

1.5.3 Proof by cases

We will now consider another example of a proof.

Example 1.14

Prove that if $a$ is even or $b$ is even then $ab$ is even.

As in the previous example we need to prove that a number ($ab$) is even and so must find a way to write this as $2$ times some integer.

Our premise is a disjunction $a$ is even or $b$ is even. When we have a disjunction we will often split into cases.

In outline the proof will be:

show that if $a$ is even then $ab$ is even
show that if $b$ is even then $ab$ is even
combine these to say that if $a$ is even or $b$ is even then $ab$ is even

The first two steps involve “subproofs,” that is we have a proof of another statement embedded in our proof:

We make an additional assumption (in the first case that $a$ is even) and the steps following this assumption are statements which are true in this new context but may not have been true in general (it might have been the case that $a$ was odd and $b$ was even instead). The conclusion at the end of the subproof is that $ab$ is even in this context. But now we can write a statement which is true given our original premise, namely that “if $a$ is even then $ab$ is even.”

Writing the proof:

Here’s the proof: in this example we use indentation to indicate where we are in one of the subproofs.

$a$ is even or $b$ is even (premise)

Suppose $a$ is even (assumption)

then there exists $k$ such that $a=2k$ (definition of even)

so $ab=(2k)b$ (substitution)

$ab=2(kb)$ (associative rule)

therefore $ab$ is even (definition of even)

Hence if $a$ is even then $ab$ is even (conclusion of the first case)

Suppose $b$ is even (assumption)

then there exists $l$ such that $b=2l$ (definition of even)

so $ab=a(2l)$ (substitution)

$ab=2(al)$ (associative and commutative rules)

therefore $ab$ is even (definition of even)

Hence if $b$ is even then $ab$ is even (conclusion of the second case)

So if $a$ is even then $ab$ is even and if $b$ is even then $ab$ is even (combining the two statements)

Therefore if $a$ is even or $b$ is even then $ab$ is even

Our aim was to prove “($a$ is even $\lor$ $b$ is even) $\implies$ $ab$ is even” but what we actually argued by proving the two cases was “($a$ is even $\implies$ $ab$ is even) $\land$ ($b$ is even $\implies$ $ab$ is even).” However these statements are equivalent by the following logical equivalence: (see Theorem 1.12) \[(P\lor R )\implies R \;\equiv\; (P\implies R) \land (Q\implies R)\]

1.5.4 Proof by contrapositive

In the same way that we used a logical equivalence in the previous example, if we want to prove an implication $P\implies Q$ it is equivalent to prove the contrapositive $\lnot Q \implies \lnot P$.

Example 1.15

Suppose we want to prove the following statement for integer values of $n$:

if $n^2$ is even then $n$ is even.

It is equivalent to prove the statement

if $n$ is not even then $n^2$ is not even.

As we are talking about integers we might rephrase this as

if $n$ is odd then $n^2$ is odd.

Remark: If we take $n$ is odd to mean precisely that $n$ is not even then this is immediate. However instead we would like to take the view that $n$ is odd means there is an integer $k$ such that $n=2k+1$. The claim that $n$ is not even is the same as $n$ is odd therefore needs some justification which we will come back to later.

Our task is now to prove that

if $n$ is odd then $n^2$ is odd.

so now the premise is $n$ is odd while we are aiming for the conclusion that $n^2$ is odd.

Writing the proof:

$n$ is odd (premise)

there is an integer $k$ such that $n=2k+1$ (definition of odd)

$n^2=(2k+1)^2$ (substitution)

$n^2=4k^2+4k+1=2(2k^2+2k)+1$ (algebra)

so $n^2$ is odd (definition of odd)

we have shown that if $n$ is odd then $n^2$ is odd

so if $n^2$ is even then $n$ is even (logical equivalence and even $\equiv$ not odd)

1.5.5 Proof by contradiction

Another important proof technique is proof by contradiction. For example if you have seen a proof that $\sqrt{2}$ is irrational then this probably involved proof by contradiction.

As we only want to work with integers in this course let us rephrase the statement as

there are no positive integers $a,b$ satisfying $a^2=2b^2$

(The equivalence of these two statements is justified by the fact that $\sqrt{2}$ is defined as the positive solution of the equation $x^2=2$ and so if $x=a/b$ then $a^2=2b$.)

The strategy of proof by contradiction is to assume that the statement $P$ to be proved is false and to derive from this a contradiction: a statement which must logically by false such as $Q\land \lnot Q$).

The justification for this is that if we prove $\lnot P$ (the statement that $P$ is false) implies a false statement then we have shown that the statement \[\lnot P \implies F\] is true. But using logical equivalences \[\lnot P \implies F \;\equiv\; (\lnot\lnot P) \lor F \;\equiv\; P\lor F \;\equiv\; P\] where the equivalences are respectively the definition of $\implies$, the double $\lnot$ rule and the identity rule.

Hence proving $\lnot P \implies F$ is equivalent to proving $P$.

Example 1.16

Prove that there are no positive integers $a,b$ satisfying $a^2=2b^2$.

Writing the proof:

Suppose $a,b$ are integers such that $a^2=2b^2$ (premise)

Let $d$ be the greatest common divisor of $a$ and $b$ (define a variable $d$)

$d$ is a divisor of $a$ and is a divisor of $b$ (from the definition of greatest common divisor)

There exist integers $u,v$ such that $a=du$ and $b=dv$ (definition of divisor)

$(du)^2=2(dv)^2$ (substitution)

$d^2u^2=d^2(2v^2)$ (associativity and commutativity)

$u^2=2v^2$ (cancellation)

$u^2$ is even (definition of even)

$u^2$ is even $\implies$ $u$ is even (previous example)

$u$ is even (modus ponens)

there exists $k$ such that $u=2k$ (definition of even)

$(2k)^2=2v^2$ (substitution)

$2(2k^2)=2v^2$ (associative and commutative rules)

$2k^2=v^2$ (cancellation)

$v^2$ is even (definition of even)

$v$ is even (previous example)

there exists $l$ such that $v=2l$ (definition of even)

$a=d(2k)=(d\cdot 2)k$ (substitution and associativity)

$b=d(2l)=(d\cdot 2)l$ (substitution and associativity)

$d\cdot 2$ is a divisor of $a$ (definition of divisor)

$d\cdot 2$ is a divisor of $b$ (definition of divisor)

$d\cdot 2$ is a common divisor of $a$ and $b$ (definition of common divisor)

$d=d\cdot 1 < d \cdot 2$ (properties of $<$)

$d$ is not the greatest common divisor of $a,b$ (definition of greatest common divisor)

$d$ is the greatest common divisor of $a,b$ (definition of $d$)

$d$ is the greatest common divisor of $a,b$ and $d$ is not the greatest common divisor of $a,b$ (combining the previous two statements)

Contradiction

Hence the initial assumption that $a,b$ are integers such that $a^2=2b^2$ is false.

The equation $a^2=2b^2$ has no integer solutions.

We will consider divisors, greatest common divisors, inequalities etc. in greater detail in a later chapter.