Lecture 1 (Feb 1)
What does a mathematician do? What's the purpose of this course? What's the purpose of a proof? We saw some examples of problems where the data suggests a natural conjecture, but the natural conjecture is wrong.
Lecture 2 (Feb 4)
We discussed a problem solved by 10-year-old Gauss, and how to generalize it. Then we talked about the Pythagoreans, and the discovery that √2 cannot be expressed as a fraction.
Lecture 3 (Feb 6)
We defined and discussed rational and irrational numbers (among other things, stating two open problems about them). We then turned to the topic of prime numbers. After working really hard, we managed to put together a precise definition of prime... which we then scrapped in favor of a better definition. We concluded with a fundamental question: what's the largest prime number? We'll take this up next class.
Lecture 4 (Feb 8)
What's the largest prime number? Today we proved there isn't any. Along the way we invented an algorithm for generating more and more primes from a given one, and also proved that every integer that's at least 2 has a prime factor.
Lecture 5 (Feb 11)
We started discussing logic, in particular rigorously defining the notions of proposition and mathematical proof and getting into boolean algebra.
Lecture 6 (Feb 13)
We discussed logical connectives, in particular writing down the formal definition of ⇒ (using a truth table) and studying some other related logical connectives. We also discussed the converse of P ⇒ Q (which is logically independent of P ⇒ Q) and the contrapositive of P ⇒ Q (which is logically equivalent to P ⇒ Q).
Lecture 7 (Feb 18)
We began by showing how to turn boolean algebra into ordinary arithmetic. We then motivated and introduced the biconditional (aka if and only if), and gave an example of how to prove an iff claim.
Lecture 8 (Feb 20)
Today we discussed predicates, in particular rewriting most of our previous theorems in a form that made clear that they are, secretly, predicates. This motivated us to introduce notation for the quantifiers (for all and there exists) and relations (belongs to). We then discussed what a mathematical theory is, and gave some famous examples. We concluded with a foundational (and world-shaking) result in logic: Gödel's First Incompleteness theorem.
Lecture 9 (Feb 22)
We introduced notation for a few sets we've seen a lot of, and discussed the adventures of Io Tichy and the Hilbert Hotel.
Lecture 10 (Feb 25)
We started with a brief discussion of the subtleties involved in logic involving predicates; see these notes for more information. We then finished discussing the Hilbert Hotel by coming up with a way of housing all the guests from all the Hilbert Hotels in the original one, in such a way that every room is occupied. Next, we turned to the problem of comparing different infinite sets. Inspired by the simpler version of this with finite sets, we formulated the notion of one-to-one correspondences.
Lecture 11 (Feb 27)
We continued discussing countability, in particular giving a more intuitive way to think about it. We then proved that the positive rational numbers were countable, while the open interval (0,1) is not.
Lecture 12 (Mar 1)
Thus far we've described sets in a fairly haphazard way, using lots of inventive combinations of symbols and words. Today we created a uniform notation for sets, and discussed ways to combine sets (including set-minus, union, intersection, cartesian product, and power set).
Lecture 13 (Mar 4)
Today we discussed a general approach for proving that two sets A and B have the same cardinality: (1) produce a function f : A → B, and verify that it is indeed a function; (2) prove that f is injective; and (3) prove that f is surjective.
Lecture 14 (Mar 6)
After clarifying the meaning of countable, we resumed our discussion of functions. We showed, in particular, that a function may be neither injective nor surjective, injective but not surjective, surjective but not injective, or both surjective and injective. We also introduced some nice notation for surjective and injective functions. We concluded by showing that not all uncountable sets have the same cardinality. More precisely, we proved that given a set S, its power set P(S) has strictly larger cardinality than S. We concluded with a discussion of the Generalized Continuum Hypothesis.
Lecture 15 (Mar 8)
We intoduced the term bijective. We then produced a bijection between the open intervals (0,1) and (-1,1), as well as one between (0,1) and all of R.
Lecture 16 (Mar 11)
We started by stating the Cantor-Schröder-Bernstein theorem, and demonstrating its power by handling with ease a tricky one-to-one matching problem. (Click here for a proof.) We then turned to the pigeonhole principle (originally named the Schubfachprinzip, or drawer principle, by Dirichlet in the 1830s), applying it to the important real-world problem of finding a matching pair of socks, as well as to problems about numbers and geometry.
Lecture 17 (Mar 13)
Today we discussed induction. We motivated the idea by a demonstration involving dominoes, and then stated induction as a formal theorem. We next proved two propositions (one familiar, one new) using induction. Finally, we proved induction itself; implicit in our proof was an axiom called the Well-Ordering Principle.
Lecture 18 (Apr 1)
After a brief interlude on triangular numbers, we reviewed induction, in particular giving a false example of a proof by induction. We also gave an example of a claim which couldn't be proved by induction directly, but when stated slightly more precisely could be proved by induction.
Lecture 19 (Apr 3)
Today we went over the midterm exam. See the grading guide (linked below) and try to grade your own exam before looking at the scores I gave!
Lecture 20 (Apr 5)
Today we stated and proved Strong Induction. We also used Strong Induction to prove that every positive integer can be written in binary.
Lecture 21 (Apr 8)
We discussed the relationship between the well-ordering principle, induction, and strong induction. We then restated the two proofs of the irrationality of root 2 in such a way that the similarities between them became apparent. Finally we turned to the Fibonacci sequence, which we'll explore more in depth next time.
Lecture 22 (Apr 10)
Today we continued discussing the Fibonacci sequence, in particular stating Kepler's conjecture and employing the machinery of generating functions to conjecture an explicit formula for the sequence.
Lecture 23 (Apr 12)
Today we proved our conjectured explicit formula for the Fibonacci numbers, then deduced Kepler's conjecture. We also stated Zeckendorf's theorem.
Lecture 24 (Apr 15)
Today we introduced modular arithmetic by discussing computations modulo 7 with days of the week. In particular, we practiced using John Conway's doomsday algorithm.
Lecture 25 (Apr 17)
After briefly discussing Zeckendorf decomposition some more, we played with a trick to use it in converting between miles and kilometers. Next, again inspired by the Zeckendorf decomposition, we proved that every positive integer has a unique binary expansion. The we turned to modular arithmetic, stating a formal definition of a (mod n). For this definition to be well-defined, we needed to prove an important result: the quotient-remainder theorem. This concluded the class.
Lecture 26 (Apr 19)
After discussing some changes to grading policy, we returned to modular arithmetic. We discussed two different notations, and worked out some examples. We concluded by writing out the multiplication table for (mod 7) arithmetic, and observing a bunch of remarkable structure.
Lecture 27 (Apr 22)
After a brief discussion of Fermat's Last Theorem, we returned to modular arithmetic explorations. We restated the patterns we'd observed last class, and found that they hold for other prime moduli as well (although they don't necessarily hold for composite moduli). We then proved one of the patterns.
Lecture 28 (Apr 24)
We observed that the Sudoku Rule (concerning the multiplication table modulo p) is equivalent to some nice properties of modular congruences, for example the cancellation rule and the property that if two numbers multiply to 0 then one of them must be 0. All of this, in turn, is equivalent to a property of prime numbers: if a product ab is divisible by a prime p, then one of a or b must be divisible by p. We proved this using Bezout's theorem, thus proving all the properties above (including the Sudoku Rule). Finally, we deduced from the Sudoku Rule a nice consequence: Fermat's Little Theorem.
Lecture 29 (Apr 26)
We started by using Fermat's Little Theorem to prove that a given number is composite... without at any time finding a factor of the number! Along the way, we developed a neat trick (repeated squaring) for efficiently evaluating a large exponent (mod n). We then shifted gears to discuss cryptography: the Diffie-Hellman Key Exchange protocol. The only reason this is considered to be secure is that the discrete log problem is still unsolved!
Lecture 30 (Apr 29)
We started discussing combinatorics today. Occupying the bulk of our class today was playing around with Pascal's triangle and observing patterns in it, some of which we were able to prove. We concluded with a discussion of how to expand the product of a bunch of sums.
Lecture 31 (May 1)
We continued our discussion from last time, eventually proving Newton's binomial theorem. This motivated us to explore the binomial coefficients more carefully; by viewing the problem of how to sort n objects into n boxes in two different ways, we were able to deduce an explicit formula for an arbitrary binomial coefficient. We then used the binomial coefficients to solve two problems which they aren't explicitly related to. The first was to compute the size of the power set of a given set. Then second was to compute the number of optimal paths from one point to another in a grid.
Lecture 32 (May 3)
Today we discussed graph theory, motivating the subject by the Königsberg bridge problem. We also discussed the four-color theorem and the scheduling problem.
Lecture 33 (May 6)
We continued discussing graph theory, motivating much of our discussing by social networks. In particular, we ended up coming up with concepts like the degree of a vertex, paths on graphs, the distance between two vertices, the diameter of a graph, and the adjacency matrix of a graph. We concluded by proving that the sum of the degrees of each vertex in a graph is twice the number of edges.
Lecture 34 (May 8)
We started by using our previous work to deduce the handshake lemma: in any graph, there must be an even number of vertices of odd degree. We next briefly discussed minimal spanning trees, and trees more generally. Thinking about the relationship between vertices and edges in a tree led us to ask for such a relationship in a general graph. A beautiful answer to this is Euler's theorem, which we concluded with.
Lecture 35 (May 10)
After discussing the Euler characteristic (for polyhedra, as well as for graphs), we turned to an awesome application of the idea: we proved that any simple planar graph must have a vertex of small degree. This relied on a result relating faces and edges; this is the dual of our sum of degrees formula. Finally, we sketched a proof of the Six-Color Theorem.
