-
Definition of two sets having the same cardinality.
Both are empty, or there is a bijection from one to the other.
-
Equivalence Relation
- Reflexive
- Symmetric
- Transitive
-
-
-
Transitive
(a,b),(b,c),(a,c)
-
If there is a bijection from A to B, what do we know about the relation?
It is an equivalence relation.
-
Countable
Finite or denumerable
-
Countably infinite
Denumerable
-
Uncountable
Infinite and not denumerable
-
Denumerable
Has the same cardinality as N
-
Prove Z is denumerable.
(1+(-1)^n(2n-1))/4
-
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
-
If A⊆B, and A is infinite and B is denumerable.
Then A is denumerable.
-
If A and B are denumerable, then AxB...
is denumerable.
-
Prove R is uncountable.
- (0,1) is uncountable.
- (0,1)⊆R.
-
Let A⊆B, and A is uncountable.
Then B is uncountable.
-
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.
-
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.
-
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.
-
Schoder-Bernstein Theorem
If f:A→B and g:B→A are injective functions, then ∃ h:A→B which is a bijection.
-
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
-
For SB Theorem, define h(x)
-
Definition of a bijection
- Defined
- Well-Defined
- Injective
- Surjective
-
-
-
Prime
An integer whose only positive integer divisors are 1 and p.
-
Composite
A number that is not prime.
-
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).
-
Division algorithm
For positive integers a and b, there exist unique integers q and r such that b=aq+r and 0≤r<a.
-
Common divisor
An integer c is a common divisor of a and b if c|a and c|b.
-
GCD
The greatest positive integer that is a common divisor.
-
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
-
If b=aq+r, then GCD(a,b)=?
GCD(r,a)
-
Relatively Prime
GCD(a,b)=1
-
Euclid's Lemma
If a|bc and GCD(a,b)=1, then a|c.
-
Euclid's Corollary
If p|bc, then either p|b or p|c.
-
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.
-
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
-
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.
-
√n is rational iff
√n is an integer
-
How many primes are there?
Infinite
|
|
