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

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

