Methods of Proof

proof

mathematical statement is a clear,logical argument to establish the staement is true

theorem vs proposition

A Theorem is an important statement for which a proof exists. • A Proposition is a (less important) statement for which a proof exists

lemma

roven statement that is not usually of interest in its own right but does a lot of the work required to prove a theorem.

corollary

is a statement that can be easily proved using a Theorem or Proposition

conjecture

is a statement which is believed to be true but no proof has been found yet

direct proof

A direct proof establishes that a statement is true by reasoning from some given assumptions, definitions, and known results to prove the statement directly in the form it is stated.

prove a statement of the form ‘For all x ∈ A, P(x)’ is true

we have to produce a general argument that shows that P(x) is true for every x in the set A. We assume x ∈ A or an arbitrary element x and show that P(x) is true using properties of the set A, definitions, axioms, and known results.

how do we disprove a statement of the form ‘For all x ∈A, P(x)

show it is false, it is enough to find one value of x for which P(x) is false. This is known as a counterexample.

how to prove a statement of the form ‘There exists x ∈ A, P(x)’ is true

We start by choosing the value x∈ A and then show that x ∈ A (if this isn’t obvious) and that P(x) holds.

how To disprove a statement of the form ‘There exists x ∈ A, P(x)’

we have to show that for every x in A, P(x) is false (ie. the negation of P(x) is true).

how to prove ‘P ⟹ Q

We do this by assuming P is true and then deducing that Q is also true.

when do we say that a divides b

We say that a divides b if and only if there is an integer c with b = ac. We say that a is a factor of b or b is a multiple of a.

when is an integer a even

n integer a is even if and only if 2 divides a. ie. there exists an integer k such that a =2k.

when is an integer odd

An integer is odd if and only if it is not even. If a is an odd integer, then it can be written as 2k +1 for some integer k.

how to write a divides b

a|b

how to prove a statement P ⇔ Q

we have to prove that P ⇒ Q and Q ⇒ P .

⇔ meaning

if and only if

proof by contrapositive

We know that P ⇒ Q and its contrapositive ¬Q ⇒ ¬P are logically equivalent. Therefore

we can prove P ⇒ Q is true by proving the contrapositive is true.

how to prove by contradiction

To prove a statement P is true using proof by contradiction:

(i) Assume P is false. or not p is true

(ii) Deduce from this assumption a statement that we know is false or that contradicts

one of our assumptions.

(iii) Conclude that the assumption in (i) is false ie. the statement P must be true.

when are 2 integers coprime

if and only if their only

common factors are ±1

simple proof by induction

Let P (n) be a statement about the natural number n. Suppose we can show that

(i) P (1) is true (called the Base Case), and

(ii) for each natural number k, if P (k) is true, then P (k + 1) is true (called the Inductive

Step).

Then P (n) is true for all natural numbers n

strong induction

n this case we need to assume more

than P (k) is true to show that P (k + 1) is true.