# SP18:Prelim 1 guide

Prelim 1 will cover material all material covered in lecture and the homework up to and including material covered on Friday 3/2. Material that you've had homework problems on will be stressed more heavily. The exam will be closed book, closed notes, and will be 90 minutes long.

The first part of the course is somewhat different from past semesters; for questions on set theory and basic proof techniques, I would review homework 1. Most of the questions in part 1 are good prelim questions. For problems on functions and induction, see the corresponding sections of File:P1-sample.pdf (File:P1-sample-sol.pdf). I expect the exam to be about as long as 4-6 of these questions.

Here is a brief summary of what we've covered; for an exhaustive list see the Main page.

- Proof techniques
- be able to write good proofs. Know how to use and prove various kinds of propositions
- Be able to do the proofs we've done in lecture or on the homework. (here is a partial list)
- Be able to write inductive proofs, including strong induction
- Understand diagonalization proofs.

- Know and be able to apply definitions (both formal and informal):
- Set definitions: union, intersection, power set, cartesian product, empty set, .
- Functions: function, partial function, left inverse, right inverse, two-sided inverse, injectivity, surjectivity, and bijectivity , , , countable
- Relations: relation, reflexive, symmetric, transitive, equivalence relation, equivalence class, A / R, well-defined functions from A/R.
- Number theory: Euclidean division algorithm, quotient, remainder, base b representation, Euclidean gcd algorithm, , equivalence mod m, , modular number, arithmetic operations on modular numbers.

- Know and be able to apply basic results
- Relationship between 'jectivity and inverses
- Countability or uncountability of .
- Properties of GCD algorithm, existence and uniqueness of quotient and remainder, existence of base b representation, set relationships, etc.