MATH-UA 120 Study Guide - Bijection, Contraposition, Natural Number
30 Nov 2013
School
Department
Course
Professor
Document Summary
Proof by contrapositive of if , then : assume . Proof by contradiction of if , then combines direct proof and proof by contrapositive: assume . Let * +, i. e. be the set of counterexamples to . By the well-ordering principle, contains a least element (i. e. is the smallest counterexample to ). We know that because is true for (rule out being the very smallest possibility). Since , we see that is a natural number and smaller than and therefore is (consider an just smaller than , i. e. , and show that is ). Manipulate the expression for so that is in there, e. g. add one to the result or substitute like in induction, and show that is also so that there is a contradiction . We find that is also true for although we supposed earlier that is true for . Inductive step: if then (by substituting identity for in ).
