Math 290

Card Set Information

Math 290
2014-04-03 16:22:47
math proofs

Math 290
Show Answers:

  1. Definition of two sets having the same cardinality.
    Both are empty, or there is a bijection from one to the other.
  2. Equivalence Relation
    • Reflexive
    • Symmetric
    • Transitive
  3. Reflexive
  4. Symmetric
  5. Transitive
  6. If there is a bijection from A to B, what do we know about the relation?
    It is an equivalence relation.
  7. Countable
    Finite or denumerable
  8. Countably infinite
  9. Uncountable
    Infinite and not denumerable
  10. Denumerable
    Has the same cardinality as N
  11. Prove Z is denumerable.
  12. Prove Q is denumerable.
    • q={1/1,1/2,2/1,1/3,2/2,...}
    • q-=-q
    • 0={0}
    • Q=q U q- U 0
  13. If A⊆B, and A is infinite and B is denumerable.
    Then A is denumerable.
  14. If A and B are denumerable, then AxB...
    is denumerable.
  15. Prove R is uncountable.
    • (0,1) is uncountable.
    • (0,1)⊆R.
  16. Let A⊆B, and A is uncountable.
    Then B is uncountable.
  17. Prove that if A⊆B, and A is uncountable, then B is uncountable.
    • To the contrary, let B be denumerable.
    • Then A is a subset of a denumerable set, and so is denumerable.
    • Contradiction.
  18. Cantor's Theorem
    • The power set is always larger than the set.
    • If A is a set and f:A→P(A), then f is not surjective.
  19. Prove Cantor's Theorem
    • For a set A, let f:A→P(A).
    • Define B={x∈A:x∉f(x)}.
    • Case 1: x∈f(x). Then by definition, x∉B. So f(x)≠B.
    • Case 2: x∉f(x). Then x∈B. So f(x)≠B.
  20. Schoder-Bernstein Theorem
    If f:A→B and g:B→A are injective functions, then ∃ h:A→B which is a bijection.
  21. For SB Theorem, define A,B,C,D
    • A is the set
    • B is C U g(f(C)) U ...
    • C is A-g(p) (these are undefined by g-1(x))
    • D is A-B
  22. For SB Theorem, define h(x)
    • f(x) if x∈B
    • g-1(x) if x∈D
  23. Definition of a bijection
    • Defined
    • Well-Defined
    • Injective
    • Surjective
  24. Defined
  25. Well-Defined
  26. Prime
    An integer whose only positive integer divisors are 1 and p.
  27. Composite
    A number that is not prime.
  28. Division properties
    • 1. If a|b, then a|bc.
    • 2. If a|b and b|c, then a|c.
    • 3. If a|b and a|c, then a|(bx+cy).
  29. Division algorithm
    For positive integers a and b, there exist unique integers q and r such that b=aq+r and 0≤r<a.
  30. Common divisor
    An integer c is a common divisor of a and b if c|a and c|b.
  31. GCD
    The greatest positive integer that is a common divisor.
  32. If d=GCD(a,b) then d satisfies what conditions?
    • d is a common divisor of a and b
    • if c is a common divisor of a and b, then c|d
  33. If b=aq+r, then GCD(a,b)=?
  34. Relatively Prime
  35. Euclid's Lemma
    If a|bc and GCD(a,b)=1, then a|c.
  36. Euclid's Corollary
    If p|bc, then either p|b or p|c.
  37. Prove Euclid's Lemma
    • Since a|bc, bc=aq.
    • Since GCD(a,b)=1, 1=as+bt.
    • c=c(as+bt)=a(cs)+(bc)t=acs+aqt=a(cs+qt).
    • So a|c.
  38. Prove that if GCD(a,b)=1, a|c, and b|c, then ab|c.
    • Since GCD(a,b)=1, 1=as+bt
    • c=ax, c=by
    • c=c(as+bt)=(by)(as)+(ax)(bt)=ab(ys+xt)
    • So ab|c
  39. Prove that every number is prime or composite.
    • True for n=2
    • Assume true for 2≤i≤k.
    • Case 1: k+1 is prime.
    • Case 2: k+1 is not prime. Then k+1=ab, where 2≤a≤k and 2≤b≤k. So, a and b are prime or a product of primes.
  40. √n is rational iff
    √n is an integer
  41. How many primes are there?