Writing Mathematical Proofs

This is a beginner's course to writing mathematical proofs. There are many different ways to prove mathematical statements. This course will show you how to write a proof, four types of proofs, and the logic in proofs.

Logical Form

Statements and Truth Values

Statements and Truth Values

A statement is a sentence that is either true, or false, but not both. In a logical form statement, p stands for the first variable, and q stands for the second variable. The truth value is whether the statement is true, or false.

The negation of p, denoted ∼p, is the statement "it is not the case that p." ∼p is read as "not p." The conjunction of p and q, denoted p∧q, is read as "p and q." p∧q is only true if both p and q are true. In logical form,  "p but q" means the same as "p and q." The dis-junction of p and q, denoted p∨q, is read as "p or q." p∨q is true if either p is true, q is true, or both are true. p∨q is only false if both p, and q are false. To use the symbol ≡  is to say something is logically equivalent to something else.

An example of ∼ p ∧ q in plain English would be "Bob does not have a watch, and he missed the bus." If there is a negation in the statement, always use the word "not" for the negation.

The symbols and their meanings:

≡ means "logically equivalent"

∧ means "and"

∨ means "or"

∼ means "not"

The following is an example of a truth table. Use truth tables to help you figure out the truth values of statements.

p q p ∧ q p ∨ q ∼ p ∼ q
T T T T F F
T F F T F T
F T F T T F
F F F F T

T

Sometimes there is more than two variables. Such as ∼ p ∧ (q ∨ r). This would be read as "not p, and q or r." Use parenthesis the same way as you would a normal mathematical equation. Use parenthesis to separate the variables into groups.

To write a statement, start with the first variable. Then write the relation to the second variable, or variables. Finally, write the last variable.

Test Yourself

  • T
  • F

Choose the correct truth value for the missing value.

p q ∼ p p ∧ q ∼ p ∧ q
T T F T  
T F F F F
F T T F T
F F T F F

 

Conditional Statements

Conditional Statements

A conditional statement is either an "if-then," or an "if and only if statement." The first element is the hypothesis and the second element is the conclusion.

⇒ ≡ if-then

⇔ ≡ if and only if

To write a conditional statement, simply write the first element, then the matching arrow, then the second element.

In an if-then statement, if the first element is false, then it doesn't matter what the truth value of the second element is. If the truth value of the first statement is false, then the truth value of a if-then statement will always be true by fallacy. In an if and only if statement, both elements must be true for a true truth value.

Examples:

Tom takes a walk if and only if it is not raining. This can be written as: Tom takes a walk ⇔ it is not raining. So Tom will only take a walk if it is not raining.

Tom does not take a walk if it is raining. This can be written as: Tom does not take a walk ⇒ it is raining. So Tom may not take a walk even if it is not raining, but Tom will not take a walk if it is raining.

p q p ⇒ q p⇔q
T T T T
T F F F
F T T F
F F T

F

Original Statement

p ⇒ q

Converse Statement

q ⇒ p

Simply reverse the order of the two elements to write a converse statement. A converse statement will not have the same truth value of the original statement.

Contrapositive Statement

∼ q ⇒ ∼ p

Take the negation of both elements, and reverse the order to write a contrapositive statement. A contrapositive statement always has the same truth value as the original statement. Therefore, they are logically equivalent.

Original Statement ≡ Contrapositive Statement

Inverse Statement

∼ p⇒ ∼ q

Take the negation of both elements to write an inverse statement. An inverse statement will not have the same truth value of the original statement. Since the inverse of the original statement is the contrapositive of the converse of the original statement, the inverse and converse will always have the same truth value. The inverse and converse are logically equivalent.

Converse Statement ≡ Inverse Statement

p q ∼p ∼q p ⇒ q q ⇒ p ∼q⇒∼p ∼p⇒∼q
T T F F T T T T
T F F T F T F T
F T T F T F T F
F F T T T T T T

Test Yourself

  • If Sally cannot buy milk, then she cannot go to the store.
  • If Sally cannot go to the store, then she cannot buy milk.
  • If Sally can buy milk, then she can go to the store.

Choose the contrapositve of the statement:

If Sally can go to the store, then she can buy milk.

Universal and Existential Statements

Universal and Existential Statements

For both universal and existential statements, the first set you use in the statement always affects the second set. Use ∈, and the symbol for whatever set is being used, to denote that the variable is part of a given set.

∈ ≡ is an element of

A universal statement is a statement that says that something is true for everything in the set.

To write a universal statement, you must start out with the symbol ∀, (which looks like an upside-down A). Put a comma after the set, then write the rest of the statement as normal.

∀ ≡ for all

An existential statement is a statement that says that there is at least one thing that exists for which the property is true.

To write an existential statement, you must start out with the symbol ∃, (which looks like a backward E). You then must write "such that," "so that," or use an abbreviation such as "s.t." Then you write the rest of the statement as normal.

∃ ≡ there exists, there is at least one, there is a

Universal Statement:

∀ r ∈ P, ∃ q ∈ P such that r loves q

In plain English:

Everyone loves someone.

Existential Statement:

∃ x ∈ P such that ∀ y ∈ P, x loves y

In plain English:

There is someone who loves everyone.

Test Yourself

  • ∀ p ∈ Q, ∃ r ∈ Q such that p⇒r
  • ∃ p ∈ Q, ∀ r ∈ Q, p ∧ r
  • ∃ p ∈ Q such that ∃ r ∈ Q such that p ∧ r
  • ∃ p ∈ Q such that ∃ r ∈ Q, p ⇔ r
Choose the correct format for writing an existential statement.

Writing Form

Getting Started

How to Write a Proper Proof

There are steps to writing a proper proof.

  1. Statement you are proving
  2. Basis Step
  3. Induction Step (if writing an induction or strong induction proof)
  4. Induction Hypothesis (if writing an induction or strong induction proof)
  5. Concluding Statement
  6. Q.E.D. or equivalent

You first start out by writing the statement you are going to prove. If you are writing an indirect proof, you should put the negation, or contrapostive statement after the original statement. Make sure you label that it is a negation or contrapositive statement, because the negation or contrapostive statement is what you are using in the proof.

Then you start your basis step. This is the where you prove a statement in direct and indirect proofs. The basis step shows the statement is true for one or more values in induction and strong induction proofs.

A handy tip is to first work on your proof on a scratch piece of paper. Sometimes a proof is easier to figure out by working backwards. When you are finished, you can copy the correct information in the correct order onto the actual proof.

If you are writing a direct, or indirect proof,  you can skip the induction step and induction hypothesis.

The induction step is where you prove the statement for induction, and strong induction proofs. The proof for "k+1," which shows that the statement is true, or false, for the value after k. The induction hypothesis goes in the beginning of induction step.

Next you write the concluding statement. This states whether the statement is true or false, and by what means it is true or false.

The final step is to show that you are finished with the proof. You put this at the very bottom of the proof, under the concluding statement. Q.E.D. is an abbreviation for the Latin phrase "quod erat demonstrandum," which translates as "that which was to be demonstrated." Q.E.D. is one of the most common ways to show you are finished with a proof. Another common way is to draw a little box, and shade the box in.

Test Yourself

  • Statement
  • Basis Step
  • Induction Step (If writing an induction or strong induction proof)
  • Induction Hypothesis (if writing an induction or strong induction proof)
  • Concluding Statement
  • Q.E.D.
Place the steps to writing a proof in the correct order.

Direct Proofs

Basic Direct Proofs

Direct Proofs

A direct proof is a way of showing whether a given statement is true or false by a straightforward explanation. You show that every element of a set satisfies a certain property. Suppose x is a particular, but arbitrarily chosen element of a set, and show x satisfies the property.

First, you express the statement as ∀ x ∈ D, P(x) ⇒ Q(x). Then you suppose x ∈ D, and P(x) are true.  The next step is to show Q(x) is true. You may use definitions, previously established results, and rules of logical inference.

In direct proofs, you do not use division. To show something is divisible by b, you show that there is a value, c, that is a multiple of the given value.

Some definitions to know:

If x is even then there exists a y such that x=2y

If x is odd then there exists a y such that x=2y+1

a divides b is written as a|b

If a|b then there exists a c such that b=ac with a≠0

Example

Prove the sum of two even integers is even.

Written in logic form: ∀ m,n ∈ Z, m and n are even ⇒ m+n is even

Proof:

Let m and n be even integers.

So there exist a k and a s such that m=2k and n=2s.

m+n=2k+2s=2(k+s)

and m+n is 2 times an integer, so the sum is even.

Q.E.D.

For an existential statement, if something exists, give it a name, and use it. Find a x that works, or give directions to find a x that works.

Example:

Suppose s and r are integers. ∃ k ∈ Z such that 22r+18s=2k

Proof:

Let s and r be integers.

Let k=11r+9s (so k ∈ Z)

Then 2k=2(11r+9s)=22r+18s

So there exists at least one k ∈ Z such that 22r+18s=2k.

Q.E.D.

Test Yourself

Prove there is an integer the sum of two odd integers is even.

Let n,m ∈ Ζ  be odd.

So ∃ r,k ∈ Ζ such that n=2k+1 and m=

n+m=(2k+1)+(2r+1)==2(k+r+1)

which is even by definition.

Q.E.D.

Proof by Cases

Proof by Cases

A proof by cases is a way to write a direct proof by splitting the statement into cases. Simply write out each case in the basis step.

Example

Prove that given two consecutive integers, one is even and the other is odd.        

Proof:

Case One: n is even

There is a k such that n=2k        

Then n+1=2k+1 and is odd.             

Case Two: n is odd        

There is a s such that n=2s+1        

Then n+1=2s+1+1=2s+2=2(s+1) and is even.

Q.E.D.

Test Yourself

∀ n ∈ Ζ, 2n^2+1 is odd.

Proof:

Case One: n is even

So ∃ k ∈ Ζ such that n=

Then 2n^2+1=2(2k)^2+1=2(4k^2)+1

which is  by definition.

Case Two: n is 

So ∃ k ∈ Ζ such that n=2k+1

Then 2n^2+1==2(4k^2+4k+1)+1

which is odd by definition.

Q.E.D.

Proof by Exhaustion

Proof by Exhaustion

A proof by exhaustion is commonly referred to as a brute force method. To write a proof by exhaustion, you write the statement with each value in the given domain, and show it is true for each value.

Example

Prove that (n+1)^3 ≥ 3n if n ∈ Ζ with n ≤ 4.        

Proof:

 Let n be 1

(1+1)^3=8>3∗1=3 

 Let n be 2

(2+1)^3=27>3∗2=9 

 Let n be 3

(3+1)^3=64>3∗3=27 

 Let n be 4

(4+1)^3=125>3∗4=81. 

In each of these four cases, we see that (n+1)^3 ≥ 3n

Q.E.D.

Test Yourself

Every even integer n greater than 2 and less than 16 can be expressed as the sum of two prime numbers.

Proof by exhaustion:

Let n=4

Let n=6

6=3+3

8=5+3

Let n=10

12=7+5

Let n=14

14=7+7

Q.E.D.

Indirect Proofs

Indirect Proofs

Indirect Proofs

Sometimes the statement you want to prove is not easy to prove with a direct proof.

There are two ways of writing an indirect proof.

A proof by contradiction is a proof that shows the original statement is true, or false, by showing the negation of the original statement in the proof. You should end up with a contradiction to the original statement as the result.

A proof by contrapositive is a proof that shows the original statement is true, or false, by showing the contrapositive of the original statement in the proof. You should end up with the same truth value as the original statement, therefore proving the original statement.

Proof by Contradiction

Proof by Contradiction

To write a proof by contradiction, first take the negation of the statement. Then you try to prove that the negation is true. The negation should have the opposite truth value of the original statement. So, if you are proving some statement to be true, the contradiction proof should show a contradiction, and be false. Therefore, the original statement is true.

Be sure to write that it is the contradiction of the original statement.

Example

Prove there is no greatest integer.        

The negation of the statement is there is a greatest integer.

Proof by contradiction:

Assume n ∈ Ζ is the largest integer.

So ∀ m ∈ Ζ, m ≤ n

Since 1 ∈ Ζ, and the integers are closed under addition, n+1 ∈ Ζ

So n+1 ≤ n < n+1

which gives a contradiction, so there is no greatest integer.

Q.E.D.

Test Yourself

There is no greatest even integer.

Proof by contradiction:

Assume there is a greatest integer n.

So So ∀ a ∈ Ζ, .

Now suppose there is a m so that m=n+2, so m is even. So  because n+2>n and m=n+2.

Therefore m≤ n<m

which gives a , so there is no greatest even integer.

Q.E.D.

Proof by Contrapositive

Proof by Contrapositive

Sometimes the original statement is hard to prove directly. If you take the contrapostive of the statement, which holds the same truth value as the original statement, the proof might be easier to write.

To write a contrapositive proof, first take the contrapositive of the original statement. Then, you treat the contrapositive statement the same as you would a direct proof. 

Be sure to write that it is the contrapositive of the original statement.

Example

For all m,n ∈ Ζ if mn is even, the m is even or n is even.

The contrapostive of the above statement is ∀ m,n ∈ Ζ, if m is odd and n is odd, then mn is odd.

Proof by Contrapositive:

Let m,n ∈ Ζ be odd.

So ∃ k,r ∈ Ζ such that m=2k+1 and n=2r+1

mn=(2k+1)(2r+1)=4kr+2k+2r+1=2(2kr+k+r)+1

So mn is odd, and the contrapostive has the same truth value as the original statement.

Q.E.D.

Test Yourself

Prove ∀ n ∈ Z, if n^2 is even then n is even.

Contrapositive:

Proof:

Let n ∈ Z be

So ∃  k ∈ Z such that n=2k+1

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

which is by definition.

Q.E.D.

Induction Proofs

Induction Proofs

Induction

An induction proof is a lot like a direct proof, except you are showing it is true for the value after n. Induction is sometimes referred to as weak induction, as opposed to strong induction.

Let P(n) be a property that is defined for integers n. Let a be a fixed integer. Suppose both are true, so P(a) is true. For all integers k≥a, if P(k) is true, then P(k+1) is true. Then, for all integers n≥a, P(n) is true.

Consider a statement of the form "for all integers n≥a, a property P(n) is true." To prove it, you need two steps.

  1. Basis Step - Show P(a) is true.
  2. Induction Step - Show that for all integers n≥a, P(n) is true then P(n+1) is also true.


First write the statement you are proving. Then you move on to the basis step. This is where you prove the statement is true for a given value. This is where induction starts to differ from a direct proof. Next is the induction step. In this step you will write your induction hypothesis, and then prove for n+1. After you have proven k+1, you write your concluding statement, and Q.E.D. as normal.

Example

Prove for all integers n ≥ 0,  2^(2n) − 1 is divisible by 3.

Basis Step

Let P(n) be the statement 2^(2n) − 1

P(0):  2^(2(0)) − 1=2^(0)-1=1-1=0

3∗0=0 so 0 is a multiple of 3

and P(0) is true.

Induction Step:

Let k be an integer with k≠0

Assume 2^(2k) − 1 is true.

There is an integer r where  2^(2n) − 1=3r

2^(2(k+1))-1=2^(2k+2)-1=2^(2k)∗2^(2)-1=(3r+1)∗2^(2)-1

=(3r+1)∗4-1=3r4+4∗1-1=3r4+3=3(4r+1)

and we get a multiple of 3.

Q.E.D.

Test Yourself

Choose the correct induction proof.

Strong Induction Proofs

Strong Induction Proofs

Strong Induction

You use strong induction when you need to prove it is true for more than one value n before you start the induction step. If an induction proof is like using a sledgehammer to drive a nail into a board, then a strong induction proof is like using a wrecking ball.

Let P(n) be a property that is defined for integers n and let a and b be fixed integers a≤b. Suppose the folloing are true.

  • P(a), P(a+1)....P(b) are true
  • For any integer k≥b, if P(i) is true for all integers i when a≤i≤k, then P(k+1) is true.
  • Then the statement "P(n) is true for all integers n≥a" is true.

Writing a strong induction proof is a lot like writing an induction proof. Use the same steps as an induction proof to write a strong induction proof. The main difference between strong induction, and induction is the induction hypothesis. In an induction proof, you are assuming P(k) is true. In a strong induction proof, you are assuming P(a), P(a+1)....P(k) are true.

Example

Prove any integer greater than 1 is divisible by a prime number.

Basis Step:

2 is divisible by 2 (2∗1=2)

3 is divisible by 3 (3∗1=3)

4 is divisible by 2 (2∗2=4)

5 is divisible by 5 (5∗1=5)

6 is divisible by 2 (2∗3=6)

Induction Step:

Let k ≥ 6

Assume that all integers from 2 up to, and including k, are divisible by a prime number.

Then either k+1 is prime or not.

Case One: k+1 is prime

If k+1 is prime then k+1 is divisible by k+1

Case Two: k+1 is not prime

If k+1 is not prime then there exists integers a and b with 1<a<k+1 and 1<b<k+1

(2≤a≤k and 2≤b≤k) so that k+1=ab

since 2≤a≤k, by the induction hypothesis a is divisible by a prime number.

So there are integers p and r, where p is prime, so that a=pr

thus k+1=ab=prb=p(br) and k+1 is divisible by a prime number, namely p.

Q.E.D.

Test Yourself

Choose the correct proof.