Online meetings via Zoom

• 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)

• 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.

Office hours:

Schedule

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'
27. 03/18: induction proofs: sum 1+3+...+(2n-1), Binomial Theorem, Bernoulli's inequality (10.1) [pdf]
28. 03/20: strong induction, minimal counterexample: prime factorization of integers (10.1 and Section 8 of handout `Integers') [pdf]
29. 03/30: gcd and lcm via prime factorization (10, Section 8 of handout `Integers', last 2 slides on [pdf]), unstacking boxes[pdf]
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]
31. 04/03: equivalence classes and partitions (11.3 and Section 2 of handout `Relations') [pdf]
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]
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]
34. 04/10: inverse functions (12.5) (Sections 4 of handout `Functions'), counting (injective) functions on finite sets [pdf]
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)
36. 04/15: counting surjective functions [pdf] [png], cardinality of sets via bijections, |N| = |Z| (14.1) [pdf]
37. 04/17: |R| = |[0,1]|, countably and uncountably infinite, Cantor's diagonal argument, |N| = |Q| (14.2) [pdf]
38. 04/20: |A|<|B| if there is a injection from A to B, Schroeder-Bernstein Thm (14.3) [pdf]
39. 04/22: |P(N)| = |R|, |A| < |P(A)|, Continuum Hypothesis (14.4) [pdf]
40. 04/24: Review: Zermelo-Fraenkel Set Theory, Inclusion-Exclusion Principle [pdf]
41. 04/27: Review: proving and disproving quantified statements [pdf]
42. 04/29: Review: Integers mod n, invertible elements, Euler's phi function, Euler's Theorem [pdf]

Homework

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

Writing assignments

0. due Monday 02/17 [pdf]
1. first draft due 02/28 [pdf] [tex], final draft due 03/04, see comments [pdf]
2. first draft due 03/16 [pdf] [tex], final draft due 03/20, 6 pm, see comments [pdf]
3. first draft due 04/06 [pdf] [tex], final draft due 04/10
4. first draft due 04/20 [pdf] [tex], final draft due 04/27

Texts

• Paul Halmos. Naive Set Theory. Springer, 1974. Available via CU library link

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

• Installing LaTeX on your own computer
• Math symbols
• LaTeX template [tex]

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.