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

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(2n1))/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.

SchoderBernstein 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 Ag(p) (these are undefined by g^{1}(x))
 D is AB

For SB Theorem, define h(x)
 f(x) if x∈B
 g^{1}(x) if x∈D

Definition of a bijection
 Defined
 WellDefined
 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 ab, then abc.
 2. If ab and bc, then ac.
 3. If ab and ac, 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 ca and cb.

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 cd

If b=aq+r, then GCD(a,b)=?
GCD(r,a)

Relatively Prime
GCD(a,b)=1

Euclid's Lemma
If abc and GCD(a,b)=1, then ac.

Euclid's Corollary
If pbc, then either pb or pc.

Prove Euclid's Lemma
 Since abc, bc=aq.
 Since GCD(a,b)=1, 1=as+bt.
 c=c(as+bt)=a(cs)+(bc)t=acs+aqt=a(cs+qt).
 So ac.

Prove that if GCD(a,b)=1, ac, and bc, then abc.
 Since GCD(a,b)=1, 1=as+bt
 c=ax, c=by
 c=c(as+bt)=(by)(as)+(ax)(bt)=ab(ys+xt)
 So abc

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

