SP19:Prelim 1 guide

Updates: I've added a note to the list of all proofs below, and to the number theory section.

Update: Here are the board notes from the first review session. Review 2 board. The video is here.

Prelim 1 will cover material all material covered in lecture and the homework up to and including material covered on Friday 3/1. 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.

Here are some questions from past prelims. These questions are 10-15 minute questions; I would expect 4-7 of them on an exam. (Solutions)

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 list of all claims on the wiki; of course this includes things we haven't proved yet, you you can still see how the proof techniques are being used)
  • Be able to find the logical negation of a proposition
  • Be able to write proof by contradiction.
  • Understand diagonalization proofs.
  • Be comfortable with proofs by weak induction and strong induction

• Know and be able to apply definitions (both formal and informal):
  • Set definitions: union, intersection, power set, cartesian product, empty set, [math]\href{/cs2800/wiki/index.php?title=Set_of_all_functions&action=edit&redlink=1}{[X \to Y]} [/math].
  • Functions: function, partial function, left inverse, right inverse, two-sided inverse, injectivity, surjectivity, and bijectivity [math]\href{/cs2800/wiki/index.php/%5Cleq}{|A| \leq |B|} [/math], [math]\href{/cs2800/wiki/index.php/%5Cgeq}{|A| \geq |B|} [/math], [math]\href{/cs2800/wiki/index.php/Equality_(cardinality)}{|A| = |B|} [/math], countable
  • Relations: relation, reflexive, symmetric, transitive, equivalence relation, equivalence class, A/R, well-defined functions from A/R. (Note: these will be covered Monday and Wednesday in lecture).

• Know and be able to apply basic results
  • Relationship between 'jectivity and inverses
  • Countability or uncountability of [math]\mathbb{Z}, \mathbb{N} \times \mathbb{N}, \mathbb{R}, 2^\mathbb{N}, [\mathbb{N} \to \{0,1\}] [/math].

• Be able to prove and apply the following basic results from number theory
  • Euclidean division algorithm
  • Base b representation (be able to represent a number in base b and interpret a sequence of digits as a number)
  • Update: GCD algorithm (Update: don't worry about memorizing the gcd algorithm; however the proofs of correctness are a good example of strong induction proof, so you can treat them as good practice problems)
  • Update: (depending how far we get Friday: computing Bézout coefficients; we didn't cover this)