Instructor: Marcel Goh
Email address: marcel[dot]goh[snail]mail[dot]mcgill[dot]ca
Classes: Tuesdays and Thursdays 16:05 to 17:25 in Leacock 26.
Office hours: Tuesdays 13:00 to 15:00 at a bench under the western slab of Burnside Hall.
(I will be wearing a large black hat for visibility purposes.) In case of inclement weather, I will
hold office hours in Burnside 1117 instead. Summer is over. Starting 22 October, my office hours
will be held in Burnside 1117. Time remains the same (13:00 to 15:00 Tuesdays).
Notes: A PDF of the course notes can be found here. These will
be updated shortly after each class with the new material covered. They are intended to be much more
comprehensive than what actually appeared on the board: a combination of everything I planned to
say, did say, and wished I'd said.
Midterm exam: Wednesday, 23 October 2024, from 18:10 to 20:10.
Final exam: Wednesday, 18 December 2024, from 14:00 to 17:00.
29 August
Today we introduced ourselves to each other and made some new friends. Then we talked about sets,
set-builder notation, special sets of numbers, and set inclusion. We did our first proof, a proof
by double-inclusion. Next we learned about set operations and laws thereof.
3 September
We learned about De Morgan's laws, defined the Cartesian product and power set, and talked a bit about
using counterexamples to prove that statements are false.
5 September
We began the lecture by discussing Russell's paradox, then embarked on a new section—propositional logic.
We defined
the AND, OR, NOT, and XOR operations, then learned some properties thereof. We ended the class by pondering the truth
table of the conditional operator. This was quite tricky, so we'll pick up next week by revising it.
10 September
We kicked off by going over the conditional and biconditional operators again, then
we defined the terms tautology,
contradiction, contingency, satisfiable, and falsifiable. We then launched into a long example about using
propositional logic to encode a Sudoku game. Then we briefly touched upon the boolean satisfiability
problem, which is outside the scope of the course, but you can read more about its importance to
computer science by searching it up on Wikipedia, etc.
12 September
Today we started a new section on predicate logic, learning how to translate between English sentences
and formulas in this logic. We also learned how to negate statements. Then we moved on to yet another
new section on proofs. We learned what constitutes proofs of "for all" and "there exists" statements.
It is at this junction where we had our first fearsome encounter with the Adversary.
17 September
We continued to expand our toolkit this lecture, learning how to prove conditional statements, and introducing
three further techniques used in proofs: contraposition, contradiction, and case analysis.
We did lots of examples along the way.
19 September
Today we did one more (interesting) case analysis proof, then proved the principle of mathematical induction.
This proof used the well-ordering principle, a statement whose proof is outside the scope of the course,
but which you can learn more about on Wikipedia.
Mathematical induction is quite a difficult principle to digest;
this image might clarify
the situation for you. We did two examples of proofs by induction (we'll see many more in the coming weeks),
then embarked on a new section: functions.
24 September
We learned about injective, surjective, and bijective functions, and also learned what it means for a function
to be invertible. To prove properties of these various types of functions required us to make a brief
digression and study the nesting patterns of pigeons.
26 September
This lecture was all about the cardinalities of infinite sets. We defined the terms countable and uncountable,
and proved that the set of integers and the
set of rationals are both countable.
To do so, we used the Schröder–Bernstein theorem (whose proof is a bit too long and difficult for this
course). We also showed that the half-open interval [0,1) is not countable,
using a diagonal argument due to Cantor.
1 October
We started a new section on relations, defining the terms reflexive, symmetric, and transitive.
We then defined equivalence relations and their equivalence classes and considered many examples.
Last, we defined what a partition of a set is.
3 October
We proved that equivalence relations give rise to partitions—the last proof
in the foundations unit of the course. Then we moved on to the first section
of the number theory unit, namely, division. We defined what it means for an integer to divide another,
then proved various easy properties of the "divides" relation. Next, we asserted the existence of
a division algorithm (the proof of which was left to the notes), and proved the correctness of an
algorithm for finding greatest common divisors. We saw that with sufficient bookkeeping, the steps
of this algorithm can be followed backwards to express the greatest common divisor as an integer
linear combination of the two starting integers. This is called Bézout's theorem, and we will begin
next class by proving it.
8 October
Today I was sick and there was some amount of political unrest on campus,
so we congregrated on Zoom. We proved Bézout's
theorem and used it to prove a
proposition about frogs on lilypads jumping over lava. After that, we started a new section
on primes, and proved the Fundamental Theorem of Arithmetic: any integer at least 2 can be factored into
a product of primes, and this factorisation is unique up to the order of the primes.
10 October
First we used the Fundamental Theorem of Arithmetic to prove that an integer root of an integer is
either integer or irrational. Then we proved there are infinitely many primes. After that, we briefly
discussed the prime number theorem (its proof is far out of the scope of this class), before
moving on to a new section on modular arithmetic. We proved that congruence modulo n defines
an equivalence relation, then established that the equivalence classes are simply sets of integers
that have the same remainders when divided by n.
22 October
This was our first day back after a week-long restorative break. We defined the ring of integers
modulo n, defined zero divisors,
performed some computations modulo n, and also defined what it means
for an integer to be invertible modulo another. We learned the link between invertibility and the
greatest common divisor, then turned out attention to the case in which the modulus is prime. We
showed that all nonzero elements are invertible modulo a prime, and that there are no zero
divisors modulo a prime. This shows that the ring of integers modulo a prime is a field.
Rings and fields are one of the main topics of MATH 235 (a class that has a significant overlap in
material with this class). If you're interested in learning more about rings and fields,
a good starting point is the Wikipedia
page on rings.
24 October
First we solved a couple congruences modulo n, then proved Fermat's little theorem,
which required us to first derive a little lemma related to Wilson's theorem. From there
we moved on to some applications of number theory: ISBN codes, divisibility tests,
computation of large powers modulo n, and Fermat's primality test. We'll pick up
with some examples of Fermat's primality test in action next time.
29 October
As I promised, we started with some examples of using Fermat's primality test to show that certain
integers are not prime. Then we described two cryptosystems: Vernam's one-time pad and RSA.
This concluded the number theory unit, so we started a new unit on graph theory. We introduced
a whole host of definitions, and drew many small examples of graphs.
31 October
Today we defined the hypercube and drew small examples. Then we talked about degrees and
proved the handshaking lemma before getting into walks, paths, and cycles.
5 November
We kicked off the lecture by defining connectedness of a graph, and showing that complete graphs
and hypergraphs are all connected. We then spent the rest of the class considering the following
extremal graph problem: What is the largest number of edges that a graph can have, assuming
that it does not contain a triangle? In one direction, we proved Mantel's
theorem, namely, that any graph on n vertices and more than
⌊n²/4⌋
edges contains a triangle. Lastly, we introduced the notion of a bipartite
graph and found that it is always possible to create a bipartite graph on n vertices and
⌊n²/4⌋
edges. We left off with this wishful thought: supposing that
we can show that this graph contains no triangle, we will have fully settled our extremal
question regarding the edge-number threshold that forces triangles to appear. Later
in the evening,
the
Calgary Flames bested the Montréal Canadiens in a thrilling 3-2 overtime win.
7 November
We resolved the mystery of last lecture by proving that bipartite graphs cannot contain any
triangles. In fact, a graph is bipartite if and only if it does not contain any cycles of odd length.
Then we moved on to a new section on trees. We proved that they are exactly the connected
graphs in which there is a unique path between any two vertices.
12 November
We started the class by giving another characterisation of trees: a graph is a tree if and only if it is
connected and has n – 1 vertices. This answers the extremal
graph problem: What is the largest number of edges a graph can have, assuming that it does
not contain any cycles? Next we described the famous
Königsberg bridge problem
and defined Eulerian trails and circuits.
We showed that a graph contains an Eulerian circuit if and only if all
vertices have even degree, and a that a graph contains an Eulerian trail but no Eulerian
circuit if and only if exactly two vertices have odd degree.
14 November
Today's lecture was all about planar graphs. We stated and proved Euler's formula,
then used it to show that all graphs on n > 5 vertices
with more than 3n – 6 edges must be nonplanar (this answers
an extremal question that none of you asked because you're bored of such things by now).
We then showed that K5 and K3,3 are nonplanar,
meaning that any graph containing one of these as a subgraph are nonplanar. We then
defined what a graph minor is, hinting towards a characterisation of all nonplanar graphs.
19 November
We mopped up a few lingering tasty bits of graph theory (the theorems of Wagner and Kuratowski)
before starting the final unit of the course: combinatorics. We solved a potpourri
of small problems to practise our counting techniques, then moved on to the main course of
the day, the binomial theorem and the principle of inclusion of exclusion. For dessert,
we used this principle to count the number of positive integers at most 100 that are coprime with
30. This wasn't enough to satisfy us, so we spent the last five minutes of class defining
k-permutations of a set, and counted the number of ways to draft a hockey team.
21 November
We applied combinatorial techniques to bookshelf organisation, walks in Edmonton, marble purchasing,
and card counting at the casino. Then we drew Pascal's triangle and proved various combinatorial
identites regarding binomial coefficients, including the freshman's dream.
26 November
We began by applying the binomial theorem to the sale of milk. This example offers a glimpse at
the might and majesty of generating functions.
I made a small digression by suggesting that one can
derive a formula for the Fibonacci numbers by using generating functions. This is in fact possible, but
I didn't do a good job of explaining how. Here's the roadmap (which requires that you use
what you learned about power series in MATH 141). We define the power series as I did
in class, then find
its formula
as the ratio of two polynomials. Next
we split this expression into a sum of two simpler rational functions using the method
of partial fractions. From here, we use the fact
that the coefficient of xn in the power series
1 / (1 – ax)
is an to get the final formula. (Work this out if you want an advanced exercise. We will
derive the same formula in a different way in the final lecture of this course.)
After the milk example we went over some simple applications of the pigeonhole principle, including the
fact that there does not exist a lossless compression algorithm that reduces some files' sizes but does
not increase any file's size. We finished the class by defining a recurrence relation.
28 November
Today we learned, by means of a couple of examples,
how to translate a counting problem into a recurrence relation. Then we introduced
a ton of definitions regarding general recurrences, and reduced the
problem of solving non-homogeneous recurrences to solving their associated homogeneous recurrences.
3 December
This lecture was all about homogeneous recurrences with constant coefficients. We found the general
solution in the degree-2 case when the roots of the characteristic polynomial are distinct, and used
this to derive a formula for the Fibonacci numbers. Then we dealt with the case where the
quadratic characteristic polynomial has a repeated root. We did one full (non-homogeneous) example
to finish off the course. Then we bade each other farewell.
