I. Sets in General:
A. Subset: A is a subset of B iff every element of A is also an element of B
B. Equality: A = B iff A is a subset of B and B is a subset of A
C. Power Set : The power set of A is the set whose elements are subsets of A,
i.e.
{B:B is a subset of A}
D. Union: The union of A and B is {x:x is an element of A or x is an element of
B}
E. Intersection: The intersection of A and B is {x:x is an element of A and x is
an
element of B}
F. Difference: The difference of A and B is the set A – B = {x:x is an element
of
A and x is not an element of B}
G. Disjoint: A and B are disjoint iff their intersection is the empty set
H. Complement: If U is the universe and B is a subset of U, then we define the
complement of B to be U – B
I. Union over A: The union over A is {x:x is an element of A for some set A
which is an element of A}
J. Inductive: A set S which is a subset of the set of all natural numbers is
inductive iff for every natural number n, n is element of S implies that n+1 is
an element of S
The PMI/WOP:
II. Definition of the Principle of Mathematical Induction :
A. Definition One:
1. Let P(n) be a statement about a natural number n
2. If:
i. P(1) is true
ii. For every natural number n, P(n) implies P(n+1)
3. Then: For every natural number n, P(n)
B. Definition Two :
1. Let S be a set
2. If:
i. S is a subset of the set of all natural numbers
ii. S is inductive
iii. 1 is an element of S
3. Then: S is the set of all natural numbers
III. Using the PMI:
A. The theorem describes a property that every natural number has
B. So, say, “let P(n) be the statement (the property from the theorem states)”
C. Show that P(1) is true
D. Let nbar be arbitrary
E. Assume P(nbar) and arrive at P(nbar+1)
F. So P(nbar) implies P(nbar+1)
G. So for every n, P(n) implies P(n+1)
H. Since P(1) and for every n, P(n) implies P(n+1), the PMI says, for every n,
P(n)
IV. The Well- Ordering Principle (WOP):
A. If set S is a nonempty subset of the natural numbers, then S has a smallest
element.
B. The WOP is a consequence of the PMI
V. Proving the WOP from the PMI:
A. Assume PMI is true
B. Suppose T is an arbitrary nonempty subset of the natural numbers
C. Let S = the set of natural numbers – T
D. Since T is not empty, S is not equal to the set of natural numbers
E. Suppose T has no smallest element
F. 1 is the smallest natural number, so 1 cannot be in T. So 1 is in S.
G. Suppose n is an element of S
H. No number less than n is in T because one of them would have to be the
smallest element of T
I. n is not an element of T because n is an element of S
J. So n+1 is not an element of T because it would be the smallest member of T.
So n+1 is in S
K. Since 1 is in S and n in S implies n+1 in S, every natural number is in S (by
the PMI)
L. This contradicts the fact that S is not the set of natural numbers
M. So T has a smallest element. So every nonempty subset of the natural numbers
has a smallest element
VI. Using the WOP for Fibonacci number proofs:
A. The proof will be some statement F(n) about Fibonacci numbers
B. Make a set of “Bad” numbers, i.e., natural numbers that do not meet this
property
C. Assume that it is not empty
D. Apply the WOP to get a smallest element b
E. Test by case b = 1 and b = 2. So you know that b is greater than 2.
F. Then you know that anything smaller than b is not is B, so the property is
true
for b - 1 and b – 2, which are both natural numbers. Use this to arrive at a
contradiction.
G. So B is empty
H. So every natural number is not in B
I. So every natural number has property F(n)
Relations:
VII. Relations in General:
A. Ordered Pair : a pair of coordinates , (a.b)
1. Alternate definition: (a,b) = {{a},{a,b}}
B. Equality of Ordered Pairs: (a,b) = (c,d) iff a = c and b = d
C. Cartesian Product: The Cartesian Product of A and B is written as AxB and is
given by AxB = {(a,b):a is an element of A and b is an element of B}
D. Relation: R is a relation from A to B iff R is a subset of AxB
E. R-Related: If (a,b) is an element of R, we write aRb and say that a and b are
R-related
F. Relation on A: A relation R from A to A is called a relation on A
G. Inverse: If R is a relation from A to B, then the inverse of R is R-1 =
{(y,x):(x,y) is an element of R}
H. Composite: If R is a relation from A to B and S is a relation from B to C,
then
the composite of R and S is 
= {(a,c): there
exists an element b of B such
that aRb and bSc}
I. Domain: If R is any relation, then {x: there exists a y such that xRy} is the
domain of R
VIII. Equivalence Relations:
A. Equivalence Relation on A: A relation R is an equivalence relation on A iff R
is reflexive on A, symmetric, and transitive.
B. Reflexive: R is reflexive on A iff for every x in A, xRx
C. Symmetric: R is symmetric iff for every x and y, xRy implies yRx
D. Transitive: R is transitive iff for every x, y, and z, xRy and yRz imply xRz
E. Equivalence Class: Let R be an equivalence relation on A. For x which are in
A, the equivalence class of x determined by R is the set x/R = {y which is an
element of A:xRy}
F. x modulo R: x/R is read as “x modulo R”
G. A modulo R: The set of all equivalence classes is called A modulo R and is
denoted by A/R = {x/R:x is an element of A}
IX. Congruence modulo m:
A. Definition 1: for any natural number m, and for any integers (x,y), x is
congruent modulo m to y iff they have the same remainder when divided by m
B . Definition 2: For any natural number m, and for any integers (x,y), x is
congruent modulo m to y iff m divides x – y.
X. Outline for proving that Definition 1 is equivalent to Definition 2:
A. Use the division algorithm to divide x and y by m
B. Part 1: Assume Definition 1. So set the remainders equal and subtract y from
x . show that m divides x – y.
C. Part 2: Assume Definition 2. So m divides x – y. So x = y + km. Replace y
with its division algorithm form, and then get a second equation for x by
setting it equal to its division algorithm form. Show that the remainders are
equal. (Because DA remainders are unique for each divisor.)
XI. Trick for proving that “(m,n)R(m`,n`) iff mn` = m`n” is transitive: Multiply
the
equation from the first assumed relation by the second coordinate in the third
ordered
pair
Partitions:
XII. Partition: A partition of a nonempty set A is a set A such that:
1. A is a subset of the power set of A
2. Every element of A is not the empty set
3. If X and Y are elements of A, then either X = Y or X and Y are disjoint
4. Every element of A is a member of some element of A
XIII. Outline of proving that for an equivalence relation
R on A, A modulo R is a
partition on A:
A. Let:
1. A be an arbitrary nonempty set
2. R be an arbitrary equivalence relation on A
3. x/R = {y in A:yRx}, for x in A
4. A = A/R = {x/R:x is an element of A}
B. Step One : Prove that A is a subset of the power set of A
1. Make an arbitrary set B, and assume that it is an element of A
2. Pick a b such that B = b/R. So B is not empty because b is in B.
3. Make an arbitrary z and assume it is an element of B
4. So bRz, so (b,z) is an element of R. R is a subset of AxA, so (b,z) is
element of AxA, so z is an element of A.
5. Since z in B implies z in A, B is a subset of A, i.e., B is an element of
the power set of A
6. Since B in A implies B in the power set of A, A is a subset of the
power set of A
C. Step Two : Proving that no element of A is empty
1. Make an arbitrary set B, and assume that it is an element of A
2. Pick a b such that B = b/R. So B is not empty because b is in B.
3. Since B was arbitrary, ever element of A is not empty
D. Step Three: Proving that any two elements of A are either equal or disjoint
1. Make arbitrary sets F and G and assume that they are elements of A.
Assume their intersection is not empty.
2. So then pick a z that is an element of the intersection of F and G
3. Pick f and g such that F = f/R and G = g/R
4. Since z is in both sets, fRz and gRz. Using symmetry and transitivity,
show that fRg and gRf
5. Make an arbitrary s and assume it is an element of F. Show that it is an
element of G.
6. Since s in F implies s in G, F is a subset of G
7. Make an arbitrary s and assume it is an element of G. Show that it is
an element of F.
8. Since s in G implies s in F, G is a subset of F
9. Since F and G are subsets of each other, they are equal.
10. So the intersection of F and G being not empty implies F = G, i.e., the
intersection is empty or they are equal
11. So F and G being in A implies either F and G are equal or disjoint. So
then generalize to all sets F and G
E. Step Four: Proving that every element of A is in some element of A
1. Make an arbitrary x in A
2. So xRx, by reflexivity
3. So x is an element of X = x/R
4. X is an element of A, by definition
5. So x is in an element of A
6. Since x was arbitrary, every x in A is in a member of an element of A
F. Since all four conditions for a partition have been met, A is a partition on
A
