MATH 135 - Algebra for Honours Math
De▯nition: An impication is a statement S such that a hypothesis (or assumption) H ensures
the validity of the conclusion C, and may either be true or false. An implication is only false
if a hypothesis is true and the conclusion is false (ie a counter-example exists). In other
words, for S: P =) Q (P implies Q), S is true unless P is true and Q is false.
Note that this can give confusing results such as
▯ If 1 = 2, then 2 = 2
▯ If 1 = 2, then 2 = 3
Because 1 = 2 is a false hypothesis, both of these implications are true, regardless of the
vailidty of their conclusion.
For a direct proof, we start by assuming the hypothesis, and derive the conclusion.
1. Always assume the hypothesis is true.
2. Never assume the conclusion is true.
3. Starting from the hypothesis, think of what can be derived using de▯nitions, theorems,
and logical deductions.
4. Look toward the conclusion, think of what needs to be achieved to prove the conclusion.
Proposition: For S = 0 =) B, S = B =) C1 and S = A =) C, prove 2 2
given S 0nd S . 1
Assume A. Since both A and A =) B are true, B is true. Since B and B =) C are
true, C is true. Thus A =) C is true. QED.
1 Proposition: Given S , S ,0and1S , assum2 S and S are 0rue. Mus2 S be true? 1
B =) C is false if and only if B is true and C is false. If C is false, we have A is false,
so we have both A =) B and A =) C are true, but B =) C is false. Thus S and
S 2o not imply S . Q1D.
De▯nition: An integer m divides an integer n if there exists an integer k such that n = km.
This is denoted as mjn.
Proposition: Transitivity of Divisibility
Let a, b, and c be integers. If a j b and b j c, then a j c.
Since ajb, there exists an integer k such that b = ka.
Since bjc, there exists an integer j such that c = jb.
Then c = jka. Since jk 2 Z, we have ajc. QED.
A set is a collection of objects. We use the notation e 2 S for element e in set S. Sets
can not have duplicate elements and may be de▯ned in any order. ▯hey may be described
in set builder notation S = fx ;x ;:0:;1 g, T n f2k + 1 ▯k 2 Rg
If S and T are sets, the cartesian product of S and T is
S ▯ T = f(a;b) a 2 S;b 2 Tg
The order of elements within each pair does matter.
For a ▯nite set S, the cordinality of S is the number of elements in S, denoted S . Note▯ ▯
▯ ▯ ▯ ▯▯ ▯
that S ▯ T = S T . The empty set is the only one with a cordinality of 0.
Note that we use ^, _, and : to denote "and", "or", and "not".
1. Union: S [ T = fx ▯ x 2 S _ x 2 Tg
2. Intersection: S \ T = fx ▯ x 2 S ^ x 2 Tg
3. Complement: S = fx ▯x 2= Sg. Note that S cc = S.
▯ Complements are transitive, ie (A \ B) = A \ B . c c
4. Di▯erence (relative complement of B in A): S n T = fx ▯x 2 S ^ x 2 = Tg. In other
words, S n T = S \ B .
2 ▯ Relative complements are inversely transitive, ie X n(A\B) = (X nA)[(X nB).
De▯nition: S is a subset of T (S ▯ T) if and only if for every x 2 R, x 2 S =) x 2 T.
Note that S ▯ S and the zero set is a subset of every other set.
For a set S, the power set is the set of all possible subsets of S, denoted by P(S) or 2
Example: for S = f1;2g, P(S) = fg;f1g;f2g▯ ▯;2g thus f2g 2 P(S) but 2 2 = P(S) so
▯ ▯ ▯ ▯ ▯ ▯n▯
f2g ▯ P(S). P(S) = 4, or P(n) = 2 ▯
A = B if and only if for every x 2 R, (x 2 A () x 2 B). From the de▯nitions of a
subset, we also have A = B () A ▯ B and B ▯ A.
Proposition: S \ (T [ U) = (S \ T) [ (S \ U)
Let x 2 S \ (T [ U).
So x 2 S and x 2 T [ U.
We have two cases:
If x 2 T, x 2 S \ T.
If x 2 U, x 2 S \ U.
Therefore, x 2 (S \ T) [ (S \ U). QED.
The universal quanti▯er 8 means "for all" and the existential quanti▯er 9 means "there
8x, x = 3 is false if x 2 Z but true if x 2 f3g
9y, y < 1 is true if y 2 Z but not if y 2 N
We can thus compare these quali▯ers to logical statements. For example
8x;P(x) = P(x )0^ P(x )1^ P(x ):2:
9x;P(x) = P(x )0_ P(x )1_ P(x ):2:
3 Proving Statements Containing Quanti▯ers
Note that some quanti▯ers can be h▯dden in words. For example, the mathematical de▯nition
of divisibility is ajc =) 9k 2 Z ▯c = ka
1. To prove that something exists, construct this thing.
2. To prove a universal property, select an arbitrary member of the universe and prove
the property for this instance.
Proposition: 8x 2 R;9y 2 R y < x
Let x 2 R,
Then y = x ▯ 1 satis▯es y 2 R and y < x. QED.
but Proposition: 9y 2 R;8x 2 R ▯ y < x
If such a y exists, then x = y does not satisfy y < x.
This is a contradiction, thus the proposition is false. QED.
Proposition: 8x 2 P(N);x 2 = fg =) 9y 2 x;8z 2 x ▯y < z
Can be accepted logically. QED.
Let X be a set. A binary relation on X is a two-variable predicate Rde▯ned on X (ie for
f(x;y) 2 X x Xg;R(x;y) may be either true or false). When R(x;y) holds, we say x is
R-related to y and write xRy.
Equality, ordering, and divisibility are all examples of relations. We also have
A ▯ B () 8x 2 S;(x 2 A =) x 2 B)
and for any A;B 2 P(S) the disjointedness relation
A ? B () A \ B = fg
For a binary relation on set X, the relation is
exive if 8x 2 X;xRx
▯ Symmetric if 8x;y 2 X;xRy =) yRx
▯ Transitive if 8x;y;x 2 X;xRy ^ yRz =) xRz
4 Equivalence Relations
Let X be a non-empty set. An equivalence relation on X is a binary relation on X that is
exive, symmetric, and transitive. The most common example of this is for S = f(x;y) 2
R x R x = yg;xRy is an equivalent relation.
The converse of A =) B is B =) A. Note that the converse does not necessarily
have the same truth value as the original implication. If both statements are true, then the
elements within them are equivalent.
Let A, B, and C be statements. Then
1. :(A ^ B) () (:A) _ (:B)
2. :(A _ B) () (:A) ^ (:b)
3. :(A =) B) () A ^ :B
4. :(:A)) () A
Let S be a set, P(x) is a statement dependant on x 2 S. Then
1. :(8x 2 S;P(x)) () 9x 2 S;:P(x))
2. :(9x 2 S;P(x)) () 8x 2 S;:P(x))
To ▯nd the negation of P(x), we can do the following
P(x) = 9y 2 R;8x 2 R ▯ y < x
:P(x) = :(9y 2 R;8x 2 R ▯y < x)
= 8y 2 R;(:(8x 2 R ▯ y < x))
= 8y 2 R;9x 2 R ▯ y ▯ x
De▯nition: The contrapositive of P =) Q is :Q =) :P. A statement and its
contrapositive are equivalent, and it can sometimes be easier to prove the contrapositive.
Proposition: For n 2 Z, if n is even then n is even
Suppose n is odd.
Then n = 2k + 1 for some k 2 Z.
2 2 2
So n = (2k + 1) = 4k + 4k + 1.
Then n is odd. Thus we have n is odd =) n is odd, so n is even =) n is even.
Use a contrapositive when the hypothesis does not give much to work with or when the
negation of the implication is nicer.
Assume the conclusion is false (or the contrapositive is false). If you derive something
impossible, the assumption must be wrong.
To prove the existence of x, suppose there are two of them x and y. Try to prove either it
must be the case that x = y, or assume x 6= y and reach a contradiction.
Methods of deduction:
▯ Direct: assume the hypothesis and ▯nd the conclusion.
▯ Example: especially with quanti▯ers, ▯nd an example which breaks the implication.
▯ Contrapositive: prove the contrapositive.
▯ Absurdity: Assume the implication (or contrapositive) is false, try to ▯nd something
Induction is useful when proving general statements 8x.
Principle of Mathematical Induction
Suppose P(n) is a statement for n ▯ n 0 If
1. P(n0) is true, and
6 2. 8k ▯ n ;P(k) =) P(k + 1).
Then, by induction, P(n) is true 8n ▯ n .0
Weak induction is a general technique based directly on the Principle of Mathematical
Induction (henceforth refered to as POMI), and is suited to proving statements of the form
"8n ▯ n 0P(n)". It consists of two steps:
1. the base case (prove P(n )0, and
2. the induction step (chose an arbitrary k ▯ n fo0 which we assume P(k), then prove
P(k + 1)).
Then we simply invoke the POMI to conclude 8n;P(n).
Proposition: 8n ▯ 2;(1 + x) > 1 + nx
For n = 2 we have
P(2) = (1 + x) 2
= 1 + 2x + x
> 1 + 2x + 0
> 1 + 2x
This proves P(2)
Assume that (1 + x) > 1 + kx. Then
P(k + 1) = (1 + x) k+1
= (1 + x) (1 + x)
> (1 + kx)(1 + x)
> 1 + kx + x + kx 2
> 1 + (k + 1)x + 0
> 1 + (k + 1)x
So 8k ▯ 2;P(k) =) P(k + 1). Thus, by POMI, 8n ▯ 2;(1 + x) > 1 + nx. QED.
Strong induction is an alternative to weak induction which may be used when P(k +1) is
dependant on either multiple past cases or a single past case P(j) where the relative location
of j < k cannot be determined.
7 Principle of Strong Induction, v1
De▯nition: Let P(n) be a property concerning integers n ▯ n . Suppose that the following
1. P(n 0, and
2. 8k ▯ n 08n ▯oj ▯ k;P(j) =) P(k + 1)
Proposition: Every natural number n > 1 can be expressed as a product of
For any n ▯ 2, if n is prime then n is the product of a single prime (itself). Thus n is
prime =) P(n).
Assume n is composite. By de▯nition 9m ▯1 < m < n ^ mjn.
For n = md;d 2 N, we have 1 < d < n.
By induction hypothesis, P(m)^P(d), which means we can express m and d as products
of primes. The we can write
m = p 0 1::p s
d = q0 1:::t
n = md = (p p 0 1p )sq q0 1:q t
is a product of primes. By POSI, 8n ▯ 2;n is a product of primes. QED.
Principle of Strong Induction, v2
The ▯rst version of POSI can fail given certain low values of k (for certain P(n) we may
have P(n) () n ▯ b ^ b ▯ n ). We 0hus modify POSI to seperately verify the multiple
base cases of P(j) for n ▯ j ▯ b.
De▯nition: Let P(n) be a property concerning integers n ▯ n . Supp0se, for some integer
b ▯ n 0 the following are true:
1. P(n 0;P(n +01);:::;P(b), and
2. 8k ▯ b;8n ▯ j ▯ k;P(j)
Proposition: 8n ▯ 60;n = 7x + 11y;n;x;y 2 Z;x;y ▯ 0. Use the following
1 = 7(▯3) + 11(2) (1)
1 = 7(8) + 11(▯5) (2)
60 = 7(7) + 11(1) (3)
Equation (3) clearly veri▯es P(60).
Since we have x is multiplied by 7 and 7 < 11, we take P(j) with 60 ▯ j ▯ 66 as the
base cases, all of which can be veri▯ed with a list of equations (omitted).
Assume that k ▯ 67 is such that P(j) holds for all 60 ▯ j < k.
Since k ▯ 67;k ▯ 7 ▯ 60 and so P(k ▯ 7) is true, thus
k ▯ 7 = 7x + 11y
for some x and y. We can manipulate this equation to have
k = 7(x + 1) + 11y
and since x + 1 2 Z ^ x + 1 ▯ 0;P(k).
Thus we have shown that whenever k ▯ 67;P(60);:::P(k ▯ 1) all true imply P(k). By
POSI, this proposition is true. QED.
Properites of Various Things
Proposition: Divisibility of Integer Combinations
Let a;b;c 2 Z. a j b ^ a j c =) a j bx + cy;8x;y 2 Z
Since ajb ^ ajc, there exists k;l 2 Z such that b = ka and c = la
Then bx + cy = kax + lay = a(kx + ly). Since kx + ly 2 Z;ajbx + cy. QED.
Proposition: Bounds by Divisibili▯ ▯ ▯ ▯
Let a;b 2 Z:a j b ^ b 6= 0 =) a ▯ b▯ ▯ ▯
Since ▯ ▯, t▯er▯ ex▯ ▯▯ ▯2 Z▯ ▯ch that b = ka.
Then b = ka = k a ▯ a . QED.▯ ▯
Proposition: Let a 2 Z ^ b 2 N. Then there exist unique integers q;r such
that a = qb + r where 0 ▯ r < b
Greatest Common Divisors
De▯nition: For any a;b 2 Z not both 0, the greatest common divisor of a and b, denoted
gcd(a;b), is the integer d such that dja ^ djb and cja ^ cjb =) c ▯ d.
9 Proposition: GCD with Remainders
If a;b;q;r 2 Z such that a = qb + r, then gcd(a;b) = gcd(b;r)
Let d = gcd(a;b).
Since d is a common divisor of a;b;djb.
We see that r = a ▯ qb. Since a ▯ qb is an integer combination of a and b, dja ▯ qb, so
Let c be a common divisor of b and r. So cjb ^ cjr.
Since qb + r is an integer combination of b and r, c j qb + r. So c j a. Therefore, c is a
common divisor of a;b. Since d = gcd(a;b);c ▯ d.
Thus d = gcd(b;r) so gcd(a;b) = gcd(b;r). QED.
Proposition: GCD Characterization
For a;b 2 Z, if d j a;d j b;d ▯ 0, and 9x;y 2 Z such that ax + by = d, then
d = gcd(a;b).
If a = b then gcd(a;b) = 1 so then x = 1;y = 0 is an integer solution to ax + by = a.
Without loss of generality, assume a > b. De▯ne function E(a;b) to be the number
of steps required when feeding (a;b) into the Euclidean algorithm. We will prove by
induction on E(a;b).
E(a;b) = 1 so bja. Then gcd(a;b) = b.
Assume for some k ▯ 1 the result holds when E(a;b) = k.
Suppose E(a;b) = k + 1. In the ▯rst step of the alogirthm, we calculate a = qb + r and
gcd(a;b) = gcd(b;r).
Let d = gcd(a;b). Then E(b;r) = k, so there exists x ;y0 0 2 Z such that bx + 0y = 0
gcd(b;r) = d.
Substitute r = a ▯ qb to get d = bx 0 (a ▯ qb)y =0ay + 0(x ▯ q0 ). 0
Then x = y ;0 = x ▯ 0y is 0n integer soution to ax + by = d. QED.
De▯nition: For a;b 2 Z, a and b are coprime if gcd(a;b) = 1.
Proposition: Coprimesness and Divisibility
If a;b;c 2 Z where c j ab and a and c are coprime, then c j b.
Since gcd(a;c) = 1, there exist x;y such that ax + cy = 1. Then bax + bcy = b.
Since cjab ^ cjc, cjbax + bcy (by integer combination) so cjb. QED.
Proposition: Primes and Divisibility
If a;b 2 Z, p is prime and p j ab, then p j a or p j b.
Assume p - a. Since the only positive factors of p are 1 and p and p - a, gcd(p;a) = 1.
Given Coprimeness and Divisibility, pjb. So pja _ pjb. QED.
Proposition: Division by GCD
If a;b 2 Z where d = gcd(a;b > 0 then gcd( d; d = 1
10 Linear Diophantine Equations
De▯nition: An LDE has the form a x + a x0+ 0:: +1a 1 = c wherenan;:::a ;c 2 Z an0 n
x ;:::x are integer variables.
Given the one variable case ax = c, there exists a solution if and only if a j c. If there is a
solution, that solution ▯s unique. For the two variable case ax+by = c the set of all solutions
is f(x0;y 0 2 Z x Z ax 0 by = 0g.
Generally, ax + by = c has an integer solution whenever gcd(a;b)jc.
Proposition: LDE 1
Let a;b;c 2 Z;d = gcd(a;b). Then ax+by = c has an integer solution if and only
if d j c.
Proposition: LDE 2
Let a;b;c 2 Z;d = gcd(a;b) > 0. If (x ;y▯▯ is a0 in0eger solu▯i▯n to ax + by = c,
b a ▯
the complete set of integers is x0+ d n;y 0 n d n 2 Z .
Euclid’s Theorem hols that there are in▯ntiely many primes. Note that every integer