# Review of MATH 300

XIV. Old theorems:

A. Division Algorithm : If a and b are positive integers with b less than or
equal

to a, then there exists a natural number q and a non - negative integer r such

that a = bq + r, where 0 is less than or equal to r, and r is less than b.

B. Euclid’s Algorithm: Let a and b be two positive integers with b less than or

equal to a. Let d be GCD(b,a). Then:

1. Part 1: You can successively apply the division algorithm to a and b to

find a final remainder r such that r = d

2. Part 2: The GCD of a and b may be written as a combination of a and

b , i.e., d = ax + by for some integers x and y

C. The Fundamental Theorem of Arithmetic : Every natural number can be

expressed uniquely as a product of primes

Assorted Proof Outlines:

XV. Proof that the square root of a prime number p is irrational:

A. Assume that the square root of the p is rational , and rewrite as a fraction
of

integers

B. Square both sides, and remove denominator

C. Make a set consisting of all natural numbers which, when multiplied by p ,

equal an integer squared.

D. Show that it is not empty

E. Apply WOP to get a natural number, which, when multiplied by p, yields the

square of an integer

F. Show that p divides that integer squared

G. Subproof: Prove that p divides that integer (not squared)

1. Assume p does not divide it

2. So the GCD of p and that integer is 1

3. Use Euclid’s Algorithm

4. Arrive at the fact that p does divide that integer

5. So p does not divide it implies that p does divide it, i.e., p divides it or

p divides it, i.e., p divides it

H. Apply definition of “divides”

I. Square this, and in doing so, find a new element of the set

J. Show that this element is smaller than the previous smallest element.

K. This is a contradiction, so the square root of p is not rational.

XVI. Proof that every natural number has a prime factor :

A. Let n be an arbitrary natural number

B. Make a set S of all numbers that divide it

C. n is in this set, so it is not empty, so you can apply the WOP to get S’s

smallest member p

D. suppose p is not prime

E. then p has a factor

F. show that there is another natural number, p`, which is in S but smaller than
p

G. this is a contradiction, so p is prime

H. so every natural number has a prime factor

XVII. Proof that there are infinite primes:

A. Let , denote a prime number

B. Assume that there are a finite number of primes

C. So, , where n is some natural number, is
the set of all

prime numbers

D. Let and let m = M+1. So m – M = 1

E. Every natural number greater than 1 has a prime factor

F. So m is divisible by some prime number q

G. Suppose q is an element of S. So q/M. But q/m. m – M = 1. Show that q

divides 1.

H. So t = 1/q for some integer t

I. Arrive at a contradiction (0 = 1)

J. So q is not an element of S

K. So q is a prime number but q is not a member of the set of all prime numbers

L. This is a contradiction, so the set of primes is infinite

Functions:

XVIII. Functions in general:

A. Function: A function f from A to B is a relation f from A to B such that:

1. For every x∈A there is a y∈B such that xfy

2. For every x∈A, if xfy and xfz, then y = z

B. If f is a function from A to B, we write f:A→B

C. If f:A→B and a∈A, then we write f(a) for the unique b∈B such that (a,b)∈f;

i.e., instead of (a,b)∈f, we write f(a) = b

D. Restriction: if f is function from A to B and S is a subset of A, we can
define a

function f/S by letting f/S = the intersection of f and the Cartesian Product of

S and B; i.e., f/S = {(x,y)∈f: x is an element of S}

E. One-to-one: let f be a function from A to B. we say that f is one-to-one iff
f(x)

= f(y) implies x = y

F. Onto: let f be a function from A to B. f is onto B iff for every b∈B, there
is an

a∈A such that f(a) = b

G. Bijection: Let A and B be sets. A bijection from A to B is a function f:A→B

which is one-to-one and onto

H. Equivalent: Two sets A, B are equivalent iff there exists a bijection from A
to

B, and we write A ≈ B.

XIX. Special Properties of Functions (easy to prove):

A. The composite of two functions is a function

B. The composite of two onto functions is onto

C. The composite of two one-to-one functions is one-to-one

D. The composite of two bijections is a bijection

E. The inverse of a function f is a function iff f is a bijection

F. ≈ is an equivalence relation

Cardinality

XX. Cardinality in General:

A. : If k∈N, then
= {n∈ N: n ≤ k}

B. Finite: A set S is finite iff S = Ø or S ≈
for some k∈ N.

C. Infinite: A set S is infinite iff it is not finite

D. Cardinal number: Let S be a finite set. If S ≈
for some k∈ N, then S has

cardinal number k, or cardinality k. If S = Ø then we say that S has cardinal

number 0, or cardinality 0.

E. Denumerable: Let S be a set. S is denumerable iff S ≈ N. For a denumerable

set S, we say S has cardinal number or
cardinality

F. Countable: A set S is countable iff it is finite or denumerable

G. Uncountable: A set S is uncountable iff it is not countable

XXI. Special Properties of Cardinality (proved later):

A. The cardinality of a finite set is unique

B. A finite set is not equivalent to any of its proper subsets

C. Every subset of a finite set is finite

D. Every proper subset of a finite set has smaller cardinality

E. The union of two finite sets is finite

Consequences of Functions and Cardinality:

XXII. Pigeon Hole Principle: for every n∈N, if r∈N and n > r and
, then f is

not one-to-one

A. Lemma for proving the Pigeon Hole Principle: If r ∈N and r > 1 and x ∈,

then .

B. Proving Pigeon Hole Principle:

1. Use induction on “if r∈N and n > r and ,
then f is not one-to-

one” starting with n = 2

2. P(2) is true because if f:{1,2}→{1}, then f(1) = 1 and f(2) = 1, so f(1)

= f(2) but 1 ≠ 2, so f is not one-to-one

3. Assume P(n) for arbitrary n∈ N

4. Suppose r∈N and n+1 > r and F:

5. Suppose F is one-to-one

6. Let g be the restriction of F to .

7. So g:

8. Let x∈ be arbitrary

9. Suppose g(x) = F(n+1). Get a contradiction because then F(x) =

F(n+1), but x ≠ n+1, so F is not one-to-one

10. So g(x) ≠ F(n+1) for any x∈

11. So g: – {F(n+1)}

12. Suppose g is not one-to-one. Then there exist a,b∈
such that g(a) =

g(b) and a ≠ b. Get a contradiction because F is not one-to-one.

13. So g is one-to-one

14. By the Lemma, –
{F(n+1)} ≈

15. So there exists a bijection h:
– {F(n+1)}→

16. So

17. Since g is one-to-one and h is one-to-one,
is one-to-one

18. Since r < n+1, r-1<n

19. So and r-1<n, which contradicts the
hypothesis of

induction

20. So F is not one-to-one. So r∈N and n+1 > r and F:
imply F

is not one-to-one. So for every r, r∈N and n+1 > r and F:

imply F is not one-to-one, i.e., P(n+1).

21. Finish out PMI proof

XXIII. Proof Outlines for Special Properties of Cardinality:

A. Proving that the cardinality of a finite set is unique:

1. Make an arbitrary set with cardinality k and cardinality m

2. Suppose k ≠ m. So one is larger. Pick k to be larger.

3. Show that there is a bijection from to

4. The Pigeon Hole Principle says this is impossible

5. So k = m

B. Proving that a finite set is not equivalent to any of its proper subsets:

1. Let A be an arbitrary finite set and let B be a proper subset of A

2. So A ≈ for some k∈N or A = Ø, and B is a
subset of A, and B ≠ A

3. Suppose A = Ø. So A has no elements, so B does not exist. So ~A ≈ B

4. Suppose A ≈ for arbitrary k∈N. From B ≠ A
and B is a subset of

A, show that A is not a subset of B

5. So there is an x that is in A but not in B

6. Make a bijection f:A→ and make g its
restriction to B

7. Show by contradiction that g(b) ≠ f(x) for any x

8. So g:B→–{f(x)}

9. Apply Lemma to show that –{f(x)} ≈

10. Use it to make a bijection h

11. So there is now (by composite) a bijection from B to

12. So B ≈ , but ~
≈ because the Pigeon Hole Principle says

that this is impossible. So ~B ≈ A.

C. Proving that any subset of a finite set is finite:

1. Let A be an arbitrary finite set. So A ≈
for some k∈ N or A = Ø.

2. Let B be a subset of A

3. Suppose A = Ø. Then B = Ø, so B is finite

4. Suppose A ≈ for some k∈ N

5. Then there is a bijection f:A→

6. Suppose A = B. Then g:B→ is a bijection.
So B ≈ . So B is

finite.

7. Suppose A ≠ B. Then there is an x in A but not in B.

8. Let h be the restriction of f to B

9. Show that h(b) ≠ f(x) for any b∈B

10. So h:B→ -{f(x)}

11. Show that h is one-to-one and onto by contradiction

12. So h is a bijection and B ≈ -{f(x)}

13. By the Lemma, B ≈

14. So B is finite

15. So in all cases, B is finite, and so any subset of a finite set is finite

XXIV. Other Assorted Proofs:

A. Proving that N is infinite:

1. Suppose N is finite

2. Then N ≈ for some k∈
or N = Ø

3. N ≠ Ø because 1∈ N

4. So N ≈ for some k∈

5. So there exists a bijection f:→N

6. Let n = f(1) + f(2) + … + f(k) + 1

7. Then n∈N but ~n∈ because n is larger than
any element of

8. So f is not onto. But f is onto because it is a bijection. This is a

contradiction. So N is not finite. So N is infinite.

B. Proving that (0,1) is uncountable:

1. Suppose (0,1) is finite

2. Then (0,1) ≈ for some k∈N or (0,1) ≈ Ø

3. (0,1) ≈ Ø because 0.5∈(0,1)

4. So (0,1) ≈ for some k∈N

5. So there exists a bijection f:→(0,1)

6. Let a be the largest of f(1), f(2), f(3), … f(k)

7. Let b = (a+1)/2. Then b∈(0,1) but f(j) ≠ b for any j∈
because b >

the greatest f (k)

8. So f is not onto, contradicting the fact that f is a bijection.

9. So (0,1) is infinite

10. Suppose (0,1) is denumerable

11. So N ≈ (0,1)

12. So there exists a bijection g: N→(0,1)

13. So f(1) =

(i) f(2) =

(ii) f(3) =

14. etc, where ∈{0,1,2,3,4,5,6,7,8,9} and
all decimals are in

normalized form

15. let b = where
= 5, if
≠ 5 and = 3, if
= 3

16. then b∈(0,1) but b ≠ f(j) for any j∈N, so f is not onto, contradicting

the fact that f is a bijection. So (0,1) is not denumerable

17. Since (0,1) is not finite or denumerable, it is uncountable

Prev | Next |