CSLogicpartv7.pptVIP

* * * For more details, see /~krc/numbers/infitude.html /lists/small/1000.txt Or /notes/proofs/infinite/euclids.html * * * * * * * * * * * * * * * * * * * Theorem “If n is an integer, then n2 ≥ n ” Proof by cases Case 1 n=0 02 = 0 Case 2 n 0, i.e., n = 1. We get n2 ≥ n since we can multiply both sides of the inequality by n, which is positive. Case 3 n 0 n2 ≥ 0 since we can multiply both sides of the inequality by n, which is negative (changes the sign of the inequality); we have n2 ≥ 0 n because n is negative. So, n2 ≥ n. Proof by cases: Example Aside: Hmm. Where is disjunction? (p1 ? p2 ?…? pn ) ? q * 7) Existence Proofs Existence Proofs: Constructive existence proofs Example: “there is a positive integer that is the sum of cubes of positive integers in two different ways” By “brute force”: 1729 = 103 + 93 = 123 + 13 Non-constructive existence proofs Example: “?n (integers), ?p so that p is prime, and p n.” Quite subtle in general… We showed it implicitly before. (a corollary from “infinitely many primes”) Uniqueness proofs Involves: Existence proof Show uniqueness * Existence Proofs: Example 1 ?n (integers), ?p so that p is prime, and p n. Proof: Let n be an arbitrary integer, and consider n! + 1. If (n! + 1) is prime, we are done since (n! + 1) n. But what if (n! + 1) is composite? If (n! + 1) is composite then it has a prime factorization, p1p2…pn = (n! + 1) NON-CONSTRUCTIVE Consider the smallest pi, and call it p. How small can it be? Can it be 2? Can it be 3? Can it be 4? Can it be n? So, p n, and we are done. QED But we don’t know what p is!! Thm. There exist irrational numbers x and y such that xy is rational. Proof: ?2 is irrational (see earlier proof). Consider: z = ?2?2 We have two possible cases: z is rational. Then, we’re done (take x = ?2 and y = ?2 ). or z is irrational. Now, let x = z a