# Prelim 1 Topics

This list of topics is not necessarily complete. Everything covered through combinatorics (Friday's lecture) will be in scope. Material covered on the homework will be given heavier emphasis.

You can find a collection of relevant questions from exams from previous semesters here (solutions)

• Definitions, proofs
• Be able to write clear and succinct proofs
• Be able to give examples and counterexamples given a definition
• Be able to prove and disprove "there exists" and "for all" statements
• Avoid backwards proofs and other logical errors
• Determine whether proofs are valid or not, and why
• Sets and functions
• Understand and use set and function notation
• Determine whether a function is well-defined
• Definitions: function, one-to-one/injective, onto/surjective, bijective
• Cardinality
• Definitions of |X|≤|Y|, |X|≥|Y|, |X|=|Y|
• Know examples of countable and uncountable sets
• Prove a set is countable
• Prove a set is uncountable (by diagonalization)
• Induction
• Strong and weak induction
• Common errors in inductive proofs
• Inductively defined functions
• Combinatorics
• Know and be able to apply sum rule, product rule, quotient rule)
• Permutations and combinations
• Combinatorial identities
• Pascal's triangle
• Balls and urns
• Binomial theorem
• Pigeonhole principle