Math 290

Card Set Information

Author:
Robertfoster
ID:
269096
Filename:
Math 290
Updated:
2014-04-03 16:22:47
Tags:
math proofs
Folders:

Description:
Math 290
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user Robertfoster on FreezingBlue Flashcards. What would you like to do?


  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
    (a,a)
  4. Symmetric
    (a,b),(b,a)
  5. Transitive
    (a,b),(b,c),(a,c)
  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
    Denumerable
  9. Uncountable
    Infinite and not denumerable
  10. Denumerable
    Has the same cardinality as N
  11. Prove Z is denumerable.
    (1+(-1)^n(2n-1))/4
  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
    BUD=A
  25. Well-Defined
    B∩D=∅
  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)=?
    GCD(r,a)
  34. Relatively Prime
    GCD(a,b)=1
  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?
    Infinite

What would you like to do?

Home > Flashcards > Print Preview