## General information

Instructor: Wouter van Limbeek
Office: SEO 511
Email: wouter@uic.edu
Grades: Blackboard.
Syllabus: Download.

Lectures: MWF, 11:00-11:50AM in AH 311.
Office hours: TF 2-3 pm.

## Exams

Midterm 1 will take place 9/28, in class. Material: Lectures 1-10 (see below) and corresponding sections of the book.
Review problems and their solutions.
Midterm 2 will take place 10/26, in class. Material: Lectures 1-23 (see below) and corresponding sections of the book.
Review problems and their solutions.
The Final will be 12/13 (Thursday), 1030 AM - 1230 PM, in AH 311. Material: Lectures 1-41 (see below) and corresponding sections of the book.
Review problems and their solutions.

## Assignments

Homework 1 (due 9/5, beginning of class):   Assignment and Solutions.
Homework 2 (due 9/12, beginning of class): Assignment and Solutions.
Homework 3 (due 9/19, beginning of class): Assignment and Solutions.
Homework 4 (due 9/26, beginning of class): Assignment and Solutions.
Homework 5 (due 10/10, beginning of class): Assignment and Solutions.
Homework 6 (due 10/17, beginning of class): Assignment and Solutions.
Homework 7 (due 10/24, beginning of class): Assignment and Solutions.
Homework 8 (due 11/7, beginning of class): Assignment and Solutions.
Homework 9 (due 11/14, beginning of class): Assignment and Solutions.
Homework 10 (due 11/28, beginning of class): Assignment and Solutions.
Homework 11 (due 12/5, beginning of class): Assignment and Solutions.

## Lectures

1. Definition of statements; logical connectives (and, or, not, implies); equivalence of statements. (Eccles' §1, 2.1)
2. What is a proof, why proofs, direct proofs (§3)
3. Proof by cases, proof by contradiction. (§3, 4)
4. Irrationality of √2 (§13.2), proofs by contraposition (§4.3)
5. Negations of composite statements, proof by induction (§5)
6. Extended and strong principles of induction (§5)
7. Elements and sets, subsets, equality of sets. (§6.1)
8. Operations on sets (intersection, union, complement, product), disjointness (§6.2). Quantifiers (§7.1).
9. Proofs involving sets, Power sets (§6.3).
10. Proving statements with quantifiers (§7.1,7.2,7.3). Negating statements with quantifiers (§7.4)
11. Disproving and quantifiers (§7.4). Informal defn. of functions (§8.1). Defns, exs of in-, sur-, bijectivity (§9.1).
12. Proving and disproving in-,sur-,bijectivity (§9.1). Graphs of functions (§8.5).
13. Midterm 1 review.
14. Midterm 1.
15. Formal definition of functions (p.99 footnote), equality of functions, restriction, (§8.1), composition (§8.2).
16. Image (§8.4), pre-images, invertibility (§9.1).
17. Determining invertibility and constructing the inverse, Invertibility and bijectivity (§9.1,9.2).
18. Finite cardinalities, finiteness (§10.1), addition principle (§10.2).
19. Multiplication and inclusion-exclusion principles (§10.2,10.3).
20. Pigeonhole principle (§11.1).
21. Applications of pigeonhole principle: bijections and injections between finite sets (§11.1).
22. Cardinality of infinite sets; countably infinite sets; examples (§14.1).
23. Hilbert hotel; unions, products, subsets of countably infinite sets (§14).
24. The rationals are countable. The reals are not (Cantor's diagonal argument). (§14).
25. Midterm 2 review.
26. Midterm 2.
27. Definition of divisors. Basic properties.
28. Division with remainder: existence and uniqueness (§15).
29. Definition of congruence modulo m, and examples (§19.1).
30. Modular arithmetic: addition and multiplication modulo m. (§19.1).
31. Greatest common divisors (definition, existence, uniqueness) and the Euclidean algorithm. (§16).
32. Integral linear combinations, gcd is least positive integeral linear combination. (§17.1,2).
33. Coprime pairs, division in modular equations (§17.3, 19.3).
34. Solving linear modular equations, coprime case (§20.1,20.2).
35. Solving linear modular equations, general case (§20.1,20.2).
36. Equivalence relations (§22.2) and congruence classes (§21.1).
37. Congruence classes and their arithmetic (§21.1 and 21.2).
38. Prime and composite numbers. Prime factorization. (§23.1 and 23.2)
39. Fundamental theorem of arithmetic (uniqueness of prime factorization). (§23.3)
40. Description of divisors in terms of prime factorization. Existence of infinitely many primes. (§23.4,5)
41. Fermat's Little Theorem. (§24.1)
42. Private key cryptography: shift and affine ciphers.
42. Public key cryptography: RSA via prime factorization and Fermat's little theorem.