Proof by DefinitionTheorem: Every even number is divisible by 2.Proof: That’s the definition of ‘even’! Proof by Logical EquivalenceAxiom 1. Everyone sane is my friend.∀x (Sane(x) → Friend(x)) Theorem: Everyone who is not my friend is insane.∀x (¬Friend(x) → ¬Sane(x)) Proof: Contrapositive of Axiom 1. 1Universal InstantiationTheorem: ∀x ∈ X : P (x)Proof: Let x be an arbitrary element of X.— Insert proof of P (x) here —Thus, P (x) is true.Since x ∈ X implies P (x), we conclude that ∀x ∈ X : P (x). This template is often applied implicitly. We will insist that you include atleast the first line.2Direct ProofTheorem: p → qProof: Assume p is true.— Insert proof of q here —Thus, our assumption implies q.We conclude that p → q is true. Theorem: For any integer n, if n is even, then n2is even.Proof: Let n be an arbitrary integer.Suppose n is even.Let k = n/2.Because n is even, k must be an integer.Routine algebra gives us n2= (2k)2= 4k2= 2(2k2).Because k is an integer, 2k2is also an integer.Thus, n2= 2k2is even.Thus, our assumption that n is even implies that n2is even. 3Indirect Proof = Direct proof + EquivalenceTheorem: p → qProof: Assume q is false.— Insert proof of ¬p here —Thus, our assumption implies ¬q.We conclude that ¬q → ¬p, which is equivalent to p → q. Theorem: For any integer n, if n2is even, then n is even.Proof: Let n be an arbitrary integer.Suppose n is odd.Then n = 2k + 1 for some integer k.We have n2= (2k + 1)2= 4k2+ 4k + 1 = 2(2k2+ 2k) + 1.Because k is an integer, 2k2+ 2k is also an integer.Thus, n2= 2(2k2+ 2k) + 1 is odd.Thus, our assumption that n is odd implies that n2is odd.Equivalently, if n2is even, then n must also be even. 4Proof of EquivalenceTheorem: p ↔ qProof:— Insert proof of p → q here —— Insert proof of q → p here —Thus, (p → q) ∧ (q → p) ≡ p ↔ q must be true. Theorem: For any integer n, n is even if and only if n2is even.Proof: Let n be an arbitrary integer.By our earlier argument, if n is even, then n2is even.By our earlier argument, if n2is even, then n is even. 5Proof of Equivalence (2)Theorem: p ↔ qProof:— Insert proof of p → q here —— Insert proof of ¬p → ¬q here —Thus, (p → q) ∧ (¬p → ¬q) ≡ p ↔ q must be true. Theorem: For any integer n, n is even if and only if n2is even.Proof: Let n be an arbitrary integer.By our earlier argument, if n is even, then n2is even.By our earlier argument, if n is odd, then n2is odd. 6Trivial ProofTheorem: p → qProof:— Insert proof of q here —Thus, q is true.We conclude that p → q is trivially true. Theorem: For all integers x, if x is prime, then 2x is even.Proof: Let x be an arbitrary integer.By definition, 2x is even.Thus, trivially, if x is prime, then 2x is even. 7Vacuous ProofTheorem: p → qProof:— Insert proof of ¬p here —Thus, p is false.We conclude that p → q is vacuously true. Theorem: For all positive integers x, if 2xis odd, then x2is prime.Proof: Let x be an arbitrary positive integer.We have 2x= 2 · 2x−1.Because x is positive, 2x−1is an integer.So 2xis even.Thus, vacuously, if 2xis odd, then x2is prime. 8Proof by AdditionTheorem: p ∨ qProof:— Insert proof of p here —Thus, p is true.We conclude that p ∨ q is also true. Proof by ConjunctionTheorem: p ∧ qProof:— Insert proof of p here —— Insert proof of q here —Thus, both p and q are true.We conclude that p ∧ q is also true. 9Proof by CasesTheorem: (p ∨ q) → rProof: There are two cases to consider.Case 1:— Insert proof of p → r here —Case 2:— Insert proof of q → r here —We conclude that (p → r) ∧(q → r), which is equivalent to (p ∨q) → r. Theorem: For all integers x, the expression x2− x is even.Proof: Let x be an arbitrary integer.There are two cases to consider: Either x is even or x is odd.Case 1: Suppose x is even.Then by our earlier argument, x2is even.The difference between two even numbers is even.Thus, x2− x is even.Case 2: Suppose x is odd.Then by our earlier argument, x2is odd.The difference between two odd numbers is even.Thus, x2− x is even.In either case, x2− x is even. 10Proof by ContradictionTheorem: pProof: For purposes of deriving a contradiction, assume p is false.— Insert proof of F here —Thus, our assumption implies a contradiction. (Formally: ¬p → F )We conclude that p must be true. Theorem: There are no positive integers x and y such that x2− y2= 1.Proof: For purposes of deriving a contradiction, assume that there are pos-itive integers x and y such that x2− y2= 1.Let x and y be positive integers such that x2− y2= 1.We can write x2− y2= (x + y)(x −y).Because x and y are integers, x + y and x − y are also integers.Thus, either x + y = x − y = 1, or x + y = x − y = −1.In either case, we have x + y = x − y, which implies that y = 0.But this contradicts the fact that y is positive!Our assumption led to a contradiction, so the theorem must be true. 11Every Proof by Contradiction Can Be ReversedReplace every step in your argument with its contrapositive.Instead of proving ¬p → F , prove T → p!Theorem: There are no positive integers x and y such that x2− y2= 1.Proof: Let x and y be arbitrary positive integers.We can write x2− y2= (x + y)(x −y).Because y is positive, we have x + y 6= x − y.Because x and y are positive integers, we have x + y ≥ 1.x − y is either positive, zero, or negative.If x − y > 0, then x − y ≥ 2,and therefore (x + y)(x −y) ≥ 2.If x − y = 0, then (x + y)(x − y) = 0 .If x − y < 0, then (x + y)(x − y) ≤ 0.In all cases, (x + y)(x −y) 6= 1. 12Theorem:√2 is irrational.Proof: For purposes of deriving a contradiction, assume that√2 is rational.Lemma: Any rational number can be expressed as the fraction a/b,where a is an integer, b is a positive integer, and a and b have nocommon factors.Let a be an integer and let b be a positive integersuch that a/b =√2 and a and b have no common factors.Routine algebra implies that a2= 2b2.Since b2is an integer, a2is even.Thus, by our earlier argument, a is even.Let k be an integer such that a = 2k.Then a2= 2b2= 4k2, so b2= 2k2.Since k2is an integer, b2is even.Thus, by our earlier argument, b is even.Thus, both a and b are even.But this contradicts the fact that a and b have no common factors!Our assumption that√2 is rational led to a contradiction, so√2 must beirrational. 13Constructive ProofTheorem: There is a prime