# High School Mathematics Extensions/Mathematical Proofs

*"It is by logic that we prove, but by intuition that we discover."*

## Introduction

Mathematicians have been, for the past five hundred years or so, obsessed with proofs. They want to prove everything, and in the process proved that they can't prove everything (see this). This chapter will introduce the axiomatic approach to mathematics, and several types of proofs.

## Direct proof

The direct proof is relatively simple — by logically applying previous knowledge, we *directly prove* what is required.

**Example 1**

Prove that the sum of any two even integers and is even.

**Solution 1**

We know that since and are even, they must have 2 as a factor. Then, we can write the following:

- Let , , for some integers

Then:

by the distributive property of integers

The number clearly has 2 as a factor, which implies it is even. Therefore, is even.

**Example 2**

Prove the following statement for non-zero integers :

If divides and divides , then divides .

**Solution 2**

If an integer divides an integer , then we can write , for some non-zero integer . So let's say that and , for some non-zero integers and . Then:

by the associative property of integer multiplication.

But since and are integers, their product must also be an integer. Therefore, is the product of some integer multiplied by , so we get that divides .

## Mathematical induction

Deductive reasoning is the process of reaching a conclusion that is guaranteed to follow. For example, if we know

- All ravens are black birds, and
- For every action, there is an equal and opposite reaction

then we can conclude:

- This bird is a raven, therefore it is black.
- This billiard ball will move when struck with a cue.

Induction is the opposite of deduction. To induce, we observe how things behave in specific cases and from that we draw conclusions as to how things behave in the general case.

Suppose we want to show that a statement (let us call it for easier notation) is true for all natural numbers. This is how induction a proof by induction works:

- First, we show that is true for the natural number 1. This is usually called the
*basis*or the*base case*. - Then, we show that is true for natural number whenever it is true for natural number .
- By mathematical induction, is true for all natural numbers.

To understand how the last step works, notice the following

- is true for 1 (due to step 1)
- is true for 2 because it is true for 1 (due to step 2)
- is true for 3 because it is true for 2 (due to previous)
- is true for 4 because it is true for 3 (due to previous)
- is true for 5 because it is true for 4 (due to previous)
- and so on...

**Example 1**
Show that the identity

holds for all positive integers.

**Solution**
Firstly, we show that it holds for 1

Suppose the identity holds for some natural number *k*:

This supposition is known as the induction hypothesis. We assume it is true, and aim to show that,

is also true.

We proceed

which is what we have set out to show. Since the identity holds for 3, it also holds for 4, and since it holds for 4 it also holds for 5, and 6, and 7, and so on.

There are two types of mathematical induction: strong and weak. In weak induction, you assume the identity holds for certain value k, and prove it for k+1. In strong induction, the identity must be true for any value lesser or equal to k, and then prove it for k+1.

**Example 2**
Show that n! > 2^{n} for n ≥ 4.

**Solution**
The claim is true for n = 4. As 4! > 2^{4}, i.e. 24 > 16.
Now suppose it's true for n = k, k ≥ 4, i.e.

- k! > 2
^{k}

it follows that

- (k+1)k! > (k+1)2
^{k}> 2^{k+1} - (k+1)! > 2
^{k+1}

We have shown that if for n = k then it's also true for n = k + 1. Since it's true for n = 4, it's true for n = 5, 6, 7, 8 and so on for all n.

**Example 3**
Show that

**Solution**
Suppose it's true for n = k, i.e.

it follows that

We have shown that if it's true for n = k then it's also true for n = k + 1. Now it's true for n = 1 (clear). Therefore it's true for all integers.

### Exercises

1. Prove that

2. Prove that for n ≥ 1,

where x_{n} and y_{n} are integers.

3. Note that

Prove that there exists an explicit formula for

- for all integer
*m*. E.g.

4. The sum of all of the interior angles of a triangle is ; the sum of all the angles of a rectangle is . Prove that the sum of all the angles of a polygon with *n* sides, is .

## Proof by contradiction

*"When you have eliminated the impossible, what ever remains, however improbable must be the truth." Sir Arthur Conan Doyle*

The idea of a proof by contradiction is to:

- First, we assume that the
*opposite*of what we wish to prove is true. - Then, we show that the logical consequences of the assumption include a contradiction.
- Finally, we conclude that the assumption must have been false.

### √2 is irrational

As an example, we shall prove that is not a rational number. Recall that a rational number is a number which can be expressed in the form of p/q, where p and q are integers and q does not equal 0 (see the 'categorizing numbers' section here).

First, assume that is *rational*:

where *a* and *b* are coprime (i.e. integers with no common factors, with greatest common divisor 1). If *a* and *b* are not coprime, we remove all common factors. In other words, *a/b* is in simplest form. Now, continuing:

We have now found that *a ^{2}* is some integer multiplied by 2. Therefore,

*a*must be divisible by two. If

^{2}*a*is even, then

^{2}*a*must also be even, for an odd number squared yields an odd number. Therefore we can write

*a = 2c*, where

*c*is another integer.

We have discovered that *b ^{2}* is also an integer multiplied by two. It follows that

*b*must be even. We have a contradiction! Both

*a*and

*b*are even integers. In other words, both have the common factor of 2. But we already said that

*a/b*is in simplest form, with no common factors. Since such a contradiction has been established, we must conclude that our original assumption was false. Therefore, √2 is irrational.

### Contrapositive

Some propositions that take the form of *if xxx then yyy* can be hard to prove. It is sometimes useful to consider the *contrapositive* of the statement. Before I explain what contrapositive is let us see an example

- "If
*x*^{2}is odd then*x*is also odd"

is harder to prove than

- "if
*x*is even then*x*^{2}is also even"

although they mean the same thing. So instead of proving the first proposition directly, we prove the second proposition instead.

If *A* and *B* are two propositions, and we aim to prove

- If
*A*is true then*B*is true

we may prove the equivalent statement

- If
*B*is false then*A*is false

instead. This technique is called proof by contrapositive.

To see why those two statements are equivalent, we show the following boolean algebra expressions is true (see Logic)

(to be done by the reader).

### Exercises

1. Prove that there is no perfect square number for 11,111,1111,11111......

2. Prove that there are infinitely number of *k'*s such that, 4*k* + 3, is prime. (Hint: consider N = p_{1}p_{2}...p_{m} + 3)

## Reading higher mathematics

This is some basic information to help with reading other higher mathematical literature.
*... to be expanded*

### Quantifiers

Sometimes we need propositions that involve some description of rough quantity, e.g. "For *all* odd integers x, x^{2} is also odd". The word *all* is a description of quantity. The word "some" is also used to describe quantity.

Two special symbols are used to describe the quanties "all" and "some"

- means "for all" or "for any"
- means "there are some" or "there exists"

**Example 1**

The proposition:

*For all even integers*x*, x*^{2}is also even.

can be expressed symbolically as:

**Example 2**

The proposition:

*There are some odd integers*x*, such that x*^{2}is even.

can be expressed symbolically as:

This proposition is false.

**Example 3**

Consider the proposition concerning (z = x'y' + xy):

*For any value of*x*, there exist a value for*y*, such that z = 1.*

can be expressed symbolically as:

This proposition is true. Note that the order of the quantifiers is important. While the above statement is true, the statement

is false. It asserts that there is one value of y which is the same for all x for which z=1. The first statement only asserts that there is a y for each x, but different values of x may have different values of y.

#### Negation

Negation is just a fancy word for the opposite, e.g. The *negation* of "All named Britney can sing" is "Some named Britney can't sing". What this says is that to disprove that all people named Britney can sing, we only need to find one named Britney who can't sing. To express symbolically:

- Let
*p*represent a person named Britney

Similarly, to disprove

we only need to find one odd number that doesn't satisfy the condition. Three is odd, but 3×3 = 9 is also odd, therefore the proposition is FALSE and

is TRUE

In summary, to obtain the *negation* of a proposition involving a quantifier, you replace the quantifier by its opposite (e.g. with ) and the *quantified proposition* (e.g. "x is even") by its negation (e.g. "x is odd").

**Example 1**

is a true statement. Its negation is

## Axioms and Inference

If today's mathematicians were to describe the greatest achievement in mathematics in the 20th century in one word, that word will be **abstraction**. True to its name, abstraction is a very abstract concept (see Abstraction).

In this chapter we shall discuss the *essence* of some of the number systems we are familiar with. For example, the real numbers and the rational numbers. We look at the most fundamental properties that, in some sense, *define* those number systems.

We begin our discussion by looking at some of the more obscure results we were told to be true

- 0 times any number gives you 0
- a negative number multiplied by a negative number gives you a positive number

Most people simply accept that they are true (and they are), but the two results above are simple consequences of what we believe to be true in a number system like the real numbers!

To understand this we introduce the idea of axiomatic mathematics (mathematics with simple assumptions). An axiom is a statement about a number system that we assume to be true. Each number system has a few axioms, from these axioms we can draw conclusions (inferences).

Let's consider the Real numbers, it has axioms
Let *a*, *b* and *c* be real numbers

- For
*a*,*b*, and*c*taken from the real numbers **A1:***a*+*b*is a real number also (*closure*)**A2:**There exist 0, such that 0 +*a*=*a*for all*a*(existence of zero - an*identity*)**A3:**For every*a*, there exist*b*(written -*a*), such that a + b = 0 (existence of an additive inverse)**A4:**(*a*+*b*) +*c*=*a*+ (*b*+*c*) (associativity of addition)**A5:***a*+*b*=*b*+*a*(commutativity of addition)

- For
*a*,*b*, and*c*taken from the real numbers excluding zero **M1:***ab*is a real number also (*closure*)**M2:**There exist an element, 1, such that 1*a*=*a*for all*a*(existence of one - an*identity*)**M3:**For every*a*there exists a*b*such that*ab*= 1**M4:**(*ab*)*c*=*a*(*bc*) (associativity of multiplication)**M5:***ab*=*ba*(commutativity of multiplication)

**D1:***a*(*b*+*c*) =*ab*+*ac*(distributivity)

These are the *minimums* we assume to be true in this system. These are *minimum* in the sense that everything else that is true about this number system can be derived from those axioms!

Let's consider the following true identity

- (x + y)z = xz + yz

which is not included in the axioms, but we can prove it using the axioms. We proceed:

Before we proceed any further, you will have notice that the real numbers are not the only numbers that satisfies those axioms! For example the rational numbers also satisfy all the axioms. This leads to the abstract concept of a *field*. In simple terms, a *field* is a number system that satisfies all those axiom. Let's define a *field* more carefully:

A number system,

F, is afieldif it supports + and × operations such that:

- For
a,b, andctaken fromFA1:a+bis inFalso (closure)A2:There exist 0, such that 0 +a=afor alla(existence of zero - anidentity)A3:For everya, there existb(written -a), such that a + b = 0 (existence of an additive inverse)A4:(a+b) +c=a+ (b+c) (associativity of addition)A5:a+b=b+a(commutativity of addition)

- For
a,b, andctaken fromFwith the zero removed (sometimes writtenF^{*})M1:abis inF(closure)M2:There exist an element, 1, such that 1a=afor alla(existence of one - theidentity)M3:For everyathere exists absuch thatab= 1 (inverses)M4:(ab)c=a(bc) (associativity of multiplication)M5:ab=ba(commutativity of multiplication)

D1:a(b+c) =ab+ac(distributivity)

Now, for **M3**, we do not let *b* be zero, since 1/0 has no meaning. However for the *M* axioms, we have excluded zero anyway.

For interested students, the requirements of *closure*, *identity*, having *inverses* and *associativity* on an operation and a set are known as a group. If *F* is a group with addition and *F*^{*} is a group with multiplication, plus the distributivity requirement, *F* is a field. The above axioms merely state this fact in full.

Note that the natural numbers are not a field, as **M3** is generally not satisfied, i.e. not every natural number has an inverse that is also a natural number.

Please note also that (-*a*) denotes the additive inverse of *a*, it doesn't say that (-a) = (-1)(a), although we can prove that they are equivalent.

**Example 1**

Prove using only the axioms that 0 = -0, where -0 is the additive inverse of 0.

**Solution 1**

- 0 = 0 + (-0) by
**A3:**existence of inverse - 0 = (-0) by
**A2:**0 + a = a

**Example 2**

Let F be a field and *a* an element of F. Prove using nothing more than the axioms that 0*a* = 0 for all *a*.

**Solution**

- 0 = 0a + (-0a) by
**A3**existence of inverse - 0 = (0 + 0)a + (-0a) by Example 1
- 0 = (0a + 0a) + (-0a) by distributivity and commutativity of multiplication
- 0 = 0a + (0a + (-0a)) by associativity of addition
- 0 = 0a + 0 by
**A3** - 0 = 0a by
**A2**.

**Example 3**

Prove that (-*a*) = (-1)*a*.

**Solution 3**

- (-a) = (-a) + 0
- (-a) = (-a) + 0a by Example 2
- (-a) = (-a) + (1 + (-1))a
- (-a) = (-a) + (1a + (-1)a)
- (-a) = (-a) + (a + (-1)a)
- (-a) = ((-a) + a) + (-1)a
- (-a) = 0 + (-1)a
- (-a) = (-1)a

One wonders why we need to prove such obvious things (obvious since primary school). But the idea is not to prove that they are true, but to practise inferencing, how to logically join up arguments to prove a point. That is a vital skill in mathematics.

### Exercises

1. Describe a field in which 1 = 0

2. Prove using only the axioms if u + v = u + w then v = w (subtracting u from both sides is not accepted as a solution)

3. Prove that if xy = 0 then either x = 0 or y = 0

4. In F_{-}, the operation + is defined to be the difference of two numbers and the × operation is defined to be the ratio of two numbers. E.g. 1 + 2 = -1, 5 + 3 = 2 and 9×3 = 3, 5×2; = 2.5. Is F_{-} a field?

5. Explain why Z_{6} (modular arithmetic modular 6) is not a field.

## Problem Set

1. Prove

for

2. Prove by induction that

3. Prove by induction

where

- and
- and 0! = 1 by definition.

4. Prove by induction

5. Prove that if x and y are integers and n an odd integer then is an integer.

6. Prove that (n~m) = n!/((n-m)!m!) is an integer. Where n! = n(n-1)(n-2)...1. E.g. 3! = 3×2×1 = 6, and (5~3) = (5!/3!)/2! = 10.

*Many questions in other chapters require you to prove things. Be sure to try the techniques discussed in this chapter.*

# Feedback

**What do you think?** Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.