Revision:Proofs

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Proofs

Proofs

Consider the following mathematical statements:

The square of an odd integer is odd.

No real number has square equal to -1

These statements are both true, you can tell this by simply looking at them. However to be totally convincing you have to provide a clear proof to justify your opinions.

Notation

X Implies Y and X if and only if Y

IF X and Y are statements then we write:

To say that X implies Y. For example:

Notice however that does not mean that .

Take a look at the same example:

Since x=-7, or the etc.

However, sometimes it is the case that both:

and .

In such a case we say, X if and only if Y. This is written as:

Some examples:

And so on.

Negation of X

The negation of a statement, X, is the opposite statement, 'Not X' which is written as .

NB: Notice that if then also: . (Since if not Y is true then X cannot be true since ). This little consideration is the basis for Proof by Contradiction, which is a very powerful and simple means of proving a mathematical statement.

Direct Proof

A direct proof is a proof in which you manipulate your algebra to arrive at the desired result. For example if I try to prove the statement shown above:

The square of an odd integer is odd.

Proof: Let be an odd integer. Then 1 more than is an even integer. Therefore can be rewritten as: for some integer k.

Therefore

This is 1 more than which is an even number.

Therefore is odd.

Proof by Contradiction

Definition

Suppose we want to prove the truth of a statement R. A proof by contradiction would first assume that R is false, (assuming not R). From this we would try and deduce another statement which is mathematically impossible based on the constraints of the statement P, or by normal laws of mathematics (ie 0=1). This may sound really complicated but it isnt! Upon doing this we have shown that:

, hence: . Since we have shown that P is false, therefore P not is true and hence so is R.

Examples

Divisbility

Let be an integer such that is a multiple of 3. Then is also a multiple of 3. - Call this statement 1.1.

Proof: Suppose not a multiple of 3. ie. can be rewritten as (when divided by 3 there is a remainder - you could also use

Consider .

This means that is 1 more than a multiple of 3, which is a contradiction to statement 1.1. So we have shown that assuming is not a multiple of 3, we come to a false statement - therefore we have proven that is a multiple of 3.

Will add more later on.

Disproof by Counter Example

Disproof by counter example is probably the easiest form of proving a statement is false. All you simply do is state a value for a variable for which the statement is false.

ie: Prove is a false statement.

Proof: Consider

LHS:

RHS:

So for . The left hand side of the equation does not match up with the right hand side of the equation, and so the statement is clearly false.

Comments