## 04proofs

Previewing page
*1*
of
actual document.

**View the full content.**View Full Document

## 04proofs

0 0 43 views

- Pages:
- 2
- School:
- Dartmouth College
- Course:
- Cosc 030 - Discrete Math Computer Sci

**Unformatted text preview:**

A Direct Proof CS 30 Discrete Mathematics Amit Chakrabarti Styles of Proof Another Direct Proof Using Cases Theorem A B B A A B A B Proof Consider arbitrary x A B B A Then either x A B or x B A Case 1 x A B Then x A so x A B Also x B so x A B Therefore x A B A B Case 2 x B A Then x B so x A B Also x A so x A B Therefore x A B A B Thus in all cases x A B A B QED Theorem Function d Z Z given by d x 2x is injective Recall deDinition f A B is injective means for every x y A if x y then f x f y i e x y A x y f x f y i e x y A f x f y x y Proof Consider arbitrary x y Z Suppose d x d y Then 2x 2y Therefore x y Thus d is injective QED A Proof by Contradiction Theorem Function d Z Z given by d x 2x is injective Recall deDinition f A B is injective means x y A f x f y x y Proof Suppose to the contrary that d is not injective Then x y Z d x d y x y So x y Z d x d y x y So x y Z 2x 2y x y So x y Z x y x y But this is a contradiction QED Proof by Contradiction 2300 yr old Classic Another Classic Proof by Contradiction Theorem There are inDinitely many primes Proof Suppose to the contrary that of primes is Dinite Full list of primes 2 3 5 p Consider the integer n 2 3 5 p 1 Dividing n by 2 leaves remainder 1 so 2 is not a factor of n Dividing n by 3 leaves remainder 1 so 3 is not a factor of n Dividing n by p leaves remainder 1 so p is not a factor of n But n must have some prime factor possibly n itself This factor is a prime greater than p Contradiction QED Theorem 2 is irrational Proof Suppose to the contrary that 2 Q Then p q N s t 2 p q in lowest terms i e gcd p q 1 So p2 2q2 Thus p2 is even Therefore p is even Because if p were odd its square would be odd Exercise Prove this Let p 2r Substituting we get 2r 2 2q2 So 2r2 q2 Thus q2 is even Therefore q is even Since both p and q are even gcd p q 1 Contradiction QED

View Full Document