Proofs of Mathematical Statements • A proof is a valid argument that establishes the truth of a statement. • In math, CS, and other disciplines, informal proofs which are generally shorter, are generally used. ○ More than one rule of inference are often used in a step. ○ Steps may be skipped. ○ The rules of inference used are not explicitly stated. ○ Easier for to understand and to explain to people. ○ But it is also easier to introduce errors. Definitions • A theorem is a statement that can be shown to be true using: ○ definitions ○ other theorems ○ axioms (statements which are given as true) ○ rules of inference • A lemma is a ‘helping theorem’ or a result which is needed to prove a theorem. • A corollary is a result which follows directly from a theorem. • Less important theorems are sometimes called propositions. • A conjecture is a statement that is being proposed to be true. • Once a proof of a conjecture is found, it becomes a theorem, it may turn out to be false. Forms of Theorems • Many theorems assert that a property holds for all elements in a domain, such as the integers, the real numbers, or some of the discrete structures that we will study in this class. • Often the universal quantifier (needed for a precise statement of a theorem) is omitted by standard mathematical convention. • For example, the statement: ○ “If xy, where x and y are positive real numbers, then x2y2” ○ really means ○ “For all positive real numbers x and y, if xy, then x2y2.” Proving Theorems • Many theorems have the form: ∀x(P(x)→Q(x)) • To prove them, we show that P(c)→Q(c) where c is an arbitrary element of the domain, • By universal generalization the truth of the original formula follows. • So, we must prove something of the form: p→q Proving Conditional Statements: p→q • Trivial Proof ○ If we know q is true, then p→q is true as well. ○ “If it is raining then 1=1. • Vacuous Proof ○ If we know p is false then p→q is true as well. ○ “If I am both rich and poor then 2 + 2 = 5.” • Even though these examples seem silly, both trivial and vacuous proofs are often used in mathematical induction, as we will see in Chapter 5 • Direct Proof Assume that p is true. Use rules of inference, axioms, and logical equivalences to show that q must also be true. • Example 1 of Direct Proof ○ Give a direct proof of the theorem “If n is an odd integer, then n^2 is odd.” ○ Assume that n is odd. Then n=2k+1 for an integer k. ○ Squaring both sides of the equation, we get: § n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1=2r+1, § where r=2k^2+2k , an integer. ○ We have proved that if n is an odd integer, then n^2 is an odd integer. • Example 2 of Direct Proof ○ Prove that the sum of two rational numbers is rational. ○ Assume x and y are two rational numbers. ○ Then there must be integers p,q,r,s such that x=p/q, y=r/s and s≠0, p≠0 ○ x+y=p/q+r/s=(ps+qr)/qs, where q,s≠0, and (ps+qr),qs are integers ○ Hence, x+y is rational • Proof by Contraposition ○ Assume ¬q and show ¬p is true also. ○ This is sometimes called an indirect proof method. ○ If we give a direct proof of ¬q→¬p then we have a proof of p→q. • Example of Proof by Contraposition ○ Prove that for an integer n, if n^2 is odd, then n is odd. ○ Use proof by contraposition. ○ Assume n is even (i.e., not odd). ○ Therefore, there exists an integer k such that n=2k. ○ Hence, n2=4k2=2(2k^2), and n^2 is even(i.e., not odd). ○ We have shown that if n is an even integer, then n^2 is even. ○ Therefore by contraposition, for an integer n, if n^2 is odd, then n is odd. • Proof by Contradiction: (AKA reductio ad absurdum). ○ To prove p, assume ¬p and derive a contradiction such as p∧¬p. (an indirect form of proof). ○ Since we have shown that ¬p→F is true, ○ it follows that the contrapositive T→p also holds. • Example of Proof by Contradiction ○ Use a proof by contradiction to give a proof that √2 is irrational. ○ Towards a contradiction assume that √2 is rational ○ Let a,b be such that √2=a/b, b≠0, and a,b have no common factors ○ 2=a2/b2 ⇒2b2=a2, so a^2 is even and a is even ○ Let a≔2k for some k∈Z, then a2=4k2 ○ Then 2b2=4k2⇒b^2=2k, so b^2 is even, and b is also even ○ So 2 divides a and b, which makes a contradiction ∎ Theorems that are Biconditional Statements • To prove a theorem that is a biconditional statement, that is, a statement of the form p↔︎q, we show that p→q and q→p are both true. • Example ○ Prove the theorem: “If n is an integer, then n is odd if and only if n^2 is odd.” ○ We have already shown (previous slides) that both p→q and q→p. ○ Therefore we can conclude p ↔︎ q. • Note ○ Sometimes iff is used as an abbreviation for “if an only if,” as in “If n is an integer, then n is odd iif n^2 is odd.” Looking Ahead • If direct methods of proof do not work: • We may need a clever use of a proof by contraposition. • Or a proof by contradiction. • In the next section, we will see strategies that can be used when straightforward approaches do not work. • In Chapter 5, we will see mathematical induction and related techniques. • In Chapter 6, we will see combinatorial proofs
