Math 245 Exam 2

Card Set Information

Math 245 Exam 2
2014-03-18 01:31:34
math proofs

Definitions and study notes for exam 2
Show Answers:

  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
  7. Explain proof by contradiction
    • 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
    • 1. Start with two of them
    • 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 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,
    • 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