MATH 240 Fall 2024 — Section 002



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.