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 3-4 pm, Wednesday 10-11 am

### Schedule

Numbers refer to sections in Hammack, Book of Proof.
1. 01/13: Gauss formula for 1+2+...+n, Euclid's proof for infinitely many primes
2. 01/15: sets and elements, equality by Axiom of Extensionality (1.1), subsets (1.3), set builder notation (Axiom of Specification) (1.1)
3. 01/17: Russell's paradox (1.10), Axiom of Replacement, cardinality (size) of sets (1.1)
4. 01/22: unordered and ordered pairs (Axiom of Pairing), Cartesian products of 2 and more sets (1.2)
5. 01/24: union (Axiom of Unions), intersection, difference, (1.5) complements (1.6), Venn diagrams (1.7)
6. 01/27: proving inclusion and identities between sets, distributive law, de Morgan
7. 01/31: indexed unions and intersections (1.8), power set (Axiom of Power Set), size of power set of a finite set (1.4)
8. 02/03: logic statements, and, or, not (2.1), truthtables and logical equivalence (2.5)
9. 02/05: implication, different formulations and negation (2.3)
10. 02/07: if and only if (2.4), truthtables and Boolean functions
11. 02/10: introduction to LaTeX, OverLeaf, first documents [tex], [pdf]
12. 02/12: universal and existential quantifiers and their negations (2.7)
13. 02/14: lists with and without repetition of elements, permutations, factorial (3.1, 3.2),
14. 02/17: review for midterm [pdf]
15. 02/19: MIDTERM
16. 02/21: counting k-element subsets, binomial coefficients (3.5), Poison
17. 02/24: Pascal's triangle (3.6), combinatorial proof (3.10)
18. 02/26: Binomial Theorem (3.6), inclusion-exclusion (3.7)
19. 02/28: integer solutions of x1+x2+...+xn = k, counting k-element multisets (3.8)
20. 03/02: divisibility for integers (4.2), direct proof
21. 03/04: greatest common divisor, least common multiple, Euclidean algorithm (4.2)
22. 03/06: Bezout's identity, Die Hard, weighing coins
23. 03/09: division algorithm, proof by contradiction
24. 03/11: primes, Euclid's lemma, contrapositive proof
25. 03/13: proof strategies (direct, contrapositive, contradiction, see handout `Proof strategies'), irrationality of the square root of 2 (Section 6 of handout `Integers')
26. 03/16: integers modulo n, Diffie-Hellman key exchange (Section 7 of handout `Integers', [mp4])
27. 03/18: induction proofs: sum 1+3+...+(2n-1), Binomial Theorem, Bernoulli's inequality (10.1) [pdf], [mp4]
28. 03/20: strong induction, minimal counterexample: prime factorization of integers (10.1 and Section 8 of handout `Integers') [pdf], [mp4]
29. 03/30: gcd and lcm via prime factorization (10, Section 8 of handout `Integers', last 2 slides on [pdf]), unstacking boxes[pdf], [mp4]
30. 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]
31. 04/03: equivalence classes and partitions (11.3 and Section 2 of handout `Relations') [pdf], [mp4]
32. 04/06: integers modulo n, addition, multiplication well-defined (11.4) [pdf], functions, domain, codomain, range (12.1), injective functions (Section 1 of handout `Functions') [pdf], [mp4]
33. 04/08: surjective, bijective functions (12.2), pigeonhole principle (12.3), composition (12.4), inverse functions (12.5) (Sections 2-4 of handout `Functions') [pdf], [mp4]
34. 04/10: inverse functions (12.5) (Sections 4 of handout `Functions'), counting (injective) functions on finite sets [pdf], [mp4]
35. 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]
36. 04/15: counting surjective functions [pdf] [png], cardinality of sets via bijections, |N| = |Z| (14.1) [pdf] [mp4]
37. 04/17: |R| = |[0,1]|, countably and uncountably infinite, Cantor's diagonal argument, |N| = |Q| (14.2) [pdf] [mp4]
38. 04/20: |A|<|B| if there is a injection from A to B, Schroeder-Bernstein Thm (14.3) [pdf] [mp4]
39. 04/22: |P(N)| = |R|, |A| < |P(A)|, Continuum Hypothesis (14.4) [pdf] [mp4]
40. 04/24: Review: Zermelo-Fraenkel Set Theory, Inclusion-Exclusion Principle [pdf] [mp4]
41. 04/27: Review: proving and disproving quantified statements [pdf] [mp4]
42. 04/29: Review: Integers mod n, invertible elements, Euler's phi function, Euler's Theorem [pdf] [mp4]

### Homework

1. due 01/15 [pdf] [tex]
2. due 01/24 [pdf] [tex]
3. due 01/31 [pdf] [tex]
4. due 02/07 [pdf] [tex]
5. due 02/14 [pdf] [tex]
6. due 02/21 [pdf] [tex] part preparation for midterm 1
7. due 02/28 [pdf] [tex]
8. due 03/06 [pdf] [tex]
9. due 03/13 [pdf] [tex]
10. due 03/20 [pdf] [tex]
11. due 04/03 [pdf] [tex]
12. due 04/10 [pdf] [tex]
13. due 04/17 [pdf] [tex]
14. due 04/24 [pdf] [tex]

### Writing assignments

1. due Monday 02/17 [pdf]
2. first draft due 02/28 [pdf] [tex], final draft due 03/04, see comments [pdf]
3. first draft due 03/16 [pdf] [tex], final draft due 03/20, 6 pm, see comments [pdf]
4. first draft due 04/06 [pdf] [tex], final draft due 04/10
5. 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

### Handouts

1. Axioms of Zermelo-Fraenkel set theory [pdf] [tex]
2. How to show two sets are equal [pdf] [tex]
3. Sets vs Logic [pdf] [tex]
4. Combinatorics [pdf] [tex]
5. Integers [pdf]
6. Proof strategies [pdf] [tex]
7. Relations [pdf] [tex]
8. Functions [pdf] [tex]

### Scientific writing

There is a variety of word-processing software for writing Mathematics. LaTeX is the most widespread. You can use it with many text editors or via some cloud-based service, like OverLeaf.

### How to succeed in this class

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.