CS 173: Skills list for Second Written Test

• Sets
  • Know basic set operations.
  • Be able to prove that one set is contained in the other by picking an arbitrary element of one set, and showing that it belongs to the other set
  • Be able to prove that two sets are equal by showing each set is contained in the other
• Functions
  • Know definitions of functions that are injective/1-to-1, surjective/onto, and bijective
  • Be able to prove that a given function is injective/surjective/bijective
• Relations
  • Understand relations that defined through sets or using other mathematical forms.
  • Know the relationship between relations and Cartesian Products
• (Easy) Induction
  • Given a claim, identify/state the key parts of an inductive proof: the induction variable, the claim P(n), base case, inductive step, inductive hypothesis, conclusion of the inductive step.
  • Be able to state a (strong) inductive hypothesis. (We always use strong hypotheses in this class, but some of you may have used weak hypotheses in other classes.)
  • Use induction to prove a formula (equality or inequality) is correct for all integers starting at some base case.
  • Use induction to prove that a non-formula claim (e.g. a divisibility relation) holds for all integers starting at some base case.