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