Proof

Question 1

What are the 4 types of proofs?

Answer 1

Proof by:
Deduction
Exhaustion
Counter Example
Contradiction

Question 2

Proof by deduction: common examples

Answer 2

Prove that a quadratic is positive for all values of x - complete the square

Question 3

How to structure proofs

Answer 3

State proposition: the question but condensed
Write proof and then suppose (e.g. x is a member of integer numbers)
There could be different cases (e.g. case 1 could be if x is odd and case 2 could be if x is even)
WRITE proof
End proof with little conclusion (e.g. odd by defintion)
NB: never start a formal proof by the statement

Question 4

Proof by contradiction: root 2 is irrational (METHOD 1)

Answer 4

suppose, for contradiction, root 2 is rational

root 2 = a/b, where a,b EZ, b doesn’t = 0 and a,b are relatively prime

square both sides: 2=a^2/b^2
2b^2 = a^2

a^2 is multiple of 2, so a is multiple of 2
a = 2k for some KEZ

2b^2=(2k)^2=4k^2
b^2=2k^2
b^2 is multiple of 2, so b is multiple of 2

Since a and b are multiples of 2, a/b can be simplified and that means a,b aren’t relatively prime.

Question 5

Proof by contradiction: root 2 is irrational (METHOD 2)

Answer 5

from METHOD 1 continued,

2b^2 = a^2
a^2 and b^2 have even powers of 2 in prime factorisation, but 2b^2 has odd power of 2 in prime factorisation.

Question 6

Proof by contradiction: infinity primes

Answer 6

suppose, for contradiction, finite primes

(P1 x P2 x P3… x Pn) + 1 = k for some kez

K cannot be divided by (), as there is a remainder of 1

Since every integer has prime factor, there is a prime factor greater than Pn