Math 2001 Spring 20
MATH 2001: Introduction to Discrete Mathematics (Spring 2020)
Syllabus and details on accomodations, honor code, etc
Online meetings via Zoom
Starting Friday, March 13, all lectures and office hours for the rest of the semester will be held at their regular time via Zoom.
See Canvas for the link.
 Please email as soon as possible if you experience technical problems with streaming.
 Please check the schedule of classes below for recordings, presentations, and references for other reading materials. The topics for each lecture will be listed 2 days in advance so that you can read ahead.
Assignments
 Please upload all homework and writing projects as pdf (no jpgs or other file formats) on Canvas before 9 am on the
respective due date.

Assignments will be graded on Canvas. You can see the corrections as annotations on your pdf at
Assignments > HW** > Submission Details > View Feedback.
Update on grading (as of April 2, 2020)
Because of our change to remote teaching for the remaining semester and in order to avoid complications with taking exams remotely
in fixed time periods, we will make the following changes:
 No more quizzes after Friday, March 13. Hence the contribution of quizzes to the final grade is halfed to 7.5 points.
 Midterm 2 scheduled on April 1 is cancelled. Hence the contribution of midterms to the final grade is halfed to 12.5 points.
 The Final Exam scheduled on 05/05 is cancelled. Hence its contribution to the final grade is reduced to 0 points
 All weekly assignments through the semester still count for 25 points.
 All writing projects through the semester still count for 15 points.
All these contributions add up to 60 points (instead of the original 100) and will then be used to determine the final grade.
Office hours:
Tuesday 34 pm,
Wednesday 1011 am
Schedule
Numbers refer to sections in Hammack, Book of Proof.
 01/13: Gauss formula for 1+2+...+n, Euclid's proof for infinitely many primes
 01/15: sets and elements, equality by Axiom of Extensionality (1.1), subsets (1.3), set builder notation (Axiom of Specification) (1.1)
 01/17: Russell's paradox (1.10), Axiom of Replacement, cardinality (size) of sets (1.1)
 01/22: unordered and ordered pairs (Axiom of Pairing), Cartesian products of 2 and more sets (1.2)
 01/24: union (Axiom of Unions), intersection, difference, (1.5) complements (1.6), Venn diagrams (1.7)
 01/27: proving inclusion and identities between sets, distributive law, de Morgan
 01/31: indexed unions and intersections (1.8), power set (Axiom of Power Set), size of power set of a finite set (1.4)
 02/03: logic statements, and, or, not (2.1), truthtables and logical equivalence (2.5)
 02/05: implication, different formulations and negation (2.3)
 02/07: if and only if (2.4), truthtables and Boolean functions
 02/10: introduction to LaTeX, OverLeaf, first documents [tex], [pdf]
 02/12: universal and existential quantifiers and their negations (2.7)
 02/14: lists with and without repetition of elements, permutations, factorial (3.1, 3.2),
 02/17: review for midterm [pdf]
 02/19: MIDTERM
 02/21: counting kelement subsets, binomial coefficients (3.5), Poison
 02/24: Pascal's triangle (3.6), combinatorial proof (3.10)
 02/26: Binomial Theorem (3.6), inclusionexclusion (3.7)
 02/28: integer solutions of x1+x2+...+xn = k, counting kelement multisets (3.8)
 03/02: divisibility for integers (4.2), direct proof
 03/04: greatest common divisor, least common multiple, Euclidean algorithm (4.2)
 03/06: Bezout's identity, Die Hard, weighing coins
 03/09: division algorithm, proof by contradiction
 03/11: primes, Euclid's lemma, contrapositive proof
 03/13: proof strategies (direct, contrapositive, contradiction, see handout `Proof strategies'), irrationality of the square root of 2 (Section 6 of handout `Integers')
 03/16: integers modulo n, DiffieHellman key exchange (Section 7 of handout `Integers', [mp4])
 03/18: induction proofs: sum 1+3+...+(2n1), Binomial Theorem, Bernoulli's inequality (10.1) [pdf], [mp4]
 03/20: strong induction, minimal counterexample: prime factorization of integers (10.1 and Section 8 of handout `Integers') [pdf], [mp4]
 03/30: gcd and lcm via prime factorization (10, Section 8 of handout `Integers', last 2 slides on [pdf]), unstacking boxes[pdf], [mp4]
 04/01: relations; functions, reflexive, symmetric, antisymmetric, transitive relations; partial orders, equivalence relations (11.2) (11.1, 11.2, 11.5 and Section 1 of handout `Relations')[pdf], [mp4]
 04/03: equivalence classes and partitions (11.3 and Section 2 of handout `Relations') [pdf], [mp4]
 04/06: integers modulo n, addition, multiplication welldefined (11.4) [pdf], functions, domain, codomain, range (12.1), injective functions (Section 1 of handout `Functions') [pdf], [mp4]
 04/08: surjective, bijective functions (12.2), pigeonhole principle (12.3), composition (12.4), inverse functions (12.5) (Sections 24 of handout `Functions') [pdf], [mp4]
 04/10: inverse functions (12.5) (Sections 4 of handout `Functions'), counting (injective) functions on finite sets [pdf], [mp4]
 04/13: review on equivalences (solutions to HW 11), counting surjective and bijective functions on finite sets (see last 2 pages of slides from 04/10), [mp4]
 04/15: counting surjective functions [pdf] [png], cardinality of sets via bijections, N = Z (14.1) [pdf] [mp4]
 04/17: R = [0,1], countably and uncountably infinite, Cantor's diagonal argument, N = Q (14.2) [pdf] [mp4]
 04/20: A<B if there is a injection from A to B, SchroederBernstein Thm (14.3) [pdf] [mp4]
 04/22: P(N) = R, A < P(A), Continuum Hypothesis (14.4) [pdf] [mp4]
 04/24: Review: ZermeloFraenkel Set Theory, InclusionExclusion Principle [pdf] [mp4]
 04/27: Review: proving and disproving quantified statements [pdf] [mp4]
 04/29: Review: Integers mod n, invertible elements, Euler's phi function, Euler's Theorem [pdf] [mp4]
Homework
 due 01/15 [pdf] [tex]
 due 01/24 [pdf] [tex]
 due 01/31 [pdf] [tex]
 due 02/07 [pdf] [tex]
 due 02/14 [pdf] [tex]
 due 02/21 [pdf] [tex] part preparation for midterm 1
 due 02/28 [pdf] [tex]
 due 03/06 [pdf] [tex]
 due 03/13 [pdf] [tex]
 due 03/20 [pdf] [tex]
 due 04/03 [pdf] [tex]
 due 04/10 [pdf] [tex]
 due 04/17 [pdf] [tex]
 due 04/24 [pdf] [tex]
Writing assignments
 due Monday 02/17 [pdf]
 first draft due 02/28 [pdf] [tex], final draft due 03/04, see comments [pdf]
 first draft due 03/16 [pdf] [tex],
final draft due 03/20, 6 pm, see comments [pdf]
 first draft due 04/06 [pdf] [tex], final draft due 04/10
 first draft due 04/20 [pdf] [tex], final draft due 04/27
Texts
Richard Hammack. The Book of Proof. Creative Commons, 3rd edition, 2018.
Available for free
Additional reading:
Handouts
 Axioms of ZermeloFraenkel set theory [pdf] [tex]
 How to show two sets are equal [pdf] [tex]
 Sets vs Logic [pdf] [tex]
 Combinatorics [pdf] [tex]
 Integers [pdf]
 Proof strategies [pdf] [tex]
 Relations [pdf] [tex]
 Functions [pdf] [tex]
Scientific writing
There is a variety of wordprocessing software for writing Mathematics.
LaTeX is the most widespread. You can use it with many text editors or
via some cloudbased service, like
OverLeaf.
How to succeed in this class
 Go to class! It seems obvious, but learning the material in small portions 3 times a week is easier than reading up on it in some book by yourself. Always keep up with the topics. You also get nerdy Math jokes.
 Ask questions early and often! If you are not sure about something, ask about it immediately  no matter whether in class, in office hours, or by mail. Do not assume that you can skip or figure out things later that you do not understand now. If you are missing the basics, you may fall behind and struggle with more complicated concepts later in class.
 Do the work! The only way to learn stuff is to try it yourself. Strive to do all the homework assignments. Some will be more challenging than others. If you are stuck on the hard ones, discuss them with colleagues or ask for possible hints in office hours or by mail.
 Learn from mistakes! Look at all feedback you get on graded homework, quizzes, exams, etc. Make sure you understand where you went wrong and how to get the correct solution. In particular revise all relevant graded work before exams.
 Organize in study groups! Meet with classmates a couple of times a week to discuss lectures and homework. Still write up your solutions to assignments when you are alone, never in a group.
 Take advantage of office hours! If you cannot make it to the official hours, ask to meet at some other time. Office hours are an additional resource for you to discuss stuff for which there is no time during class. Come prepared! Try to solve homework problems alone before you ask for help and be ready to explain your thoughts and where you are stuck.