# Math 245 Exam 2

The flashcards below were created by user nisab44 on FreezingBlue Flashcards.

1. Inductive
A set S (subset of) natural numbers is called INDUCTIVE if 1. there is a minimal k (element of) natural numbers s.t. k (element of) S. 2. If n (element of) S, then n+1 (element of) S.
2. Greatest Common Divisor
Let a,b (element of) natural numbers. The GREATEST COMMON DIVISOR, denoted gcd(a,b) is the unique natural number d s.t. 1. d (divides) a and d (divides) b. 2. If e (divides) a and e (divides) b => e (divides) d
3. Relatively Prime
If gcd(a,b) = 1, then a and b are said to be RELATIVELY PRIME.
4. Least Common Multiple
The LEAST COMMON MULTIPLE of a,b denoted lcm(a,b) is the unique natural number s.t. 1. a (divides) lcm(a,b) and b (divides) lcm(a,b). 2. If M is any natural number s.t. a (divides) M and b (divides) M => lcm(a,b) (divides) M.
5. Explain direct proofs
• Say P => Q
• 1. Backward-Forward method: consider what will make Q to be true. What has to be established to show Q?
• 2. Backward: Assume Q is true.
• 3. Forward: Assume P is true.
• 4. Hopefully, the logically chains meet
6. Explain proof by contrapositive
• Given P => Q, prove ~Q => ~P instead
• 1. Indirectly proves P => Q
• 2. ~Q => ~P is proven directly
• 3. Replaces one conditional with another
• Want to prove a proposition that is always false.
• Assume P (and) ~Q => derive R (and) ~R
• P=>P2=>P3=>...=>R
• ~Q=>Q1=>Q2=>...~R
• Two things to word with: P and ~Q
8. Explain proof by induction
• Given a propositional function
• Pn with domain natural numbers,
• 1. Verify base case: P(1) must be true
• 2. Assume P(n) is true.
• Derive P(n+1) is true
9. How to prove an "Either-Or" statement
10. How to prove an object is unique
• 2. Either derive a contradiction or show two objects are equal
11. How to prove a set is empty
12. Helpful hints for: If X is a set with [X] = n, then [P] = 2n
• Assume Induction Hypothesis
• Let [X] = n+1 and X={x1,x2,...xn}U{xn+1}
• Let Y = {x1,x2,...xn}
• By IH, [P(Y)] = 2n
13. Fundamental Theorem of Arithmetic
Let n (element of) natural numbers..., then n is a product of prime numbers. There exist primes p1...pm and exponents e1...em s.t. n=p1e1p2e2...pmem
14. Euclid's Lemma: if p is a prime and p (divides) ab, then p (divides) a or p (divides) b
• If P then Q or R. P => Q v R
• Assume ~Q. Q is false; prove P => R
• Assume P (~divides) a
• gcd(p,a)=1 => there exist integers s,t (element of) integers s.t. 1=as+pt
• Multiply equation by b...
15. There are infinitely many prime numbers
• Assume otherwise
• Let N equal p1, p2,...pn+1
• If N has a prime factor N is prime itself...but it's not
• There's at least one pi s.t. pi (divides) N
• End up with pi (divides) 1 => contradiction 1 isn't divisible by primes
16. Prove Sqrt(2) is irrational
• Assume it is rational
• Sqrt(2) = a/b, assuming that a and b have no common factors other than 1
• Square both sides
• 2b2=a2
• Even, odd, both have factors of 2 => contradiction
 Author: nisab44 ID: 266862 Card Set: Math 245 Exam 2 Updated: 2014-03-18 05:31:34 Tags: math proofs Folders: Description: Definitions and study notes for exam 2 Show Answers: