Math 290

Home > Preview

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

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.
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

Card Set Information

 Author: Robertfoster ID: 269096 Filename: Math 290 Updated: 2014-04-03 20:22:47 Tags: math proofs Folders: Description: Math 290 Show Answers:

Home > Flashcards > Print Preview