Card Set Information
Definition of two sets having the same cardinality.
Both are empty, or there is a bijection from one to the other.
If there is a bijection from A to B, what do we know about the relation?
It is an equivalence relation.
Finite or denumerable
Infinite and not denumerable
Has the same cardinality as
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...
(0,1) is uncountable.
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.
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).
: x∈f(x). Then by definition, x∉B. So f(x)≠B.
: x∉f(x). Then x∈B. So f(x)≠B.
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
D is A-B
For SB Theorem, define h(x)
f(x) if x∈B
(x) if x∈D
Definition of a bijection
An integer whose only positive integer divisors are 1 and p.
A number that is not prime.
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).
For positive integers a and b, there exist unique integers q and r such that b=aq+r and 0≤r<a.
An integer c is a common divisor of a and b if c|a and c|b.
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)=?
If a|bc and GCD(a,b)=1, then a|c.
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.
Prove that if GCD(a,b)=1, a|c, and b|c, then ab|c.
Since GCD(a,b)=1, 1=as+bt
Prove that every number is prime or composite.
True for n=2
Assume true for 2≤i≤k.
: k+1 is prime.
: 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?