CS 173: Skills list for Oral Review Examlet

While this list covers all possible proof types you might see,
you are expected to be comfortable with other course concepts that
may come up as parts of proofs, including but not limited to:
how to negate quantifiers, the divides relation, congruence mod k, and how set operations work with the empty set.

• Fundamental Logic and Proof Techniques
  • Write a simple direct proof, using familiar concepts, with good mathematical style. Make sure your statements are in logical order, starting with the given information and ending with what you needed to show.
  • Write a proof by cases
  • Convert a claim to its contrapositive and prove that using direct proof.
  • Know the following standard ways to approach parts of a proof:
    • prove a universal claim by choosing a representative object of the appropriate type
    • prove an if/then statement by assuming whatever's in the hypothesis and proving the conclusion,
    • disprove a universal claim by giving a concrete counterexample.
    • prove an existential claim by giving specific values that make the claim true
• Set Theory Proofs
  • Prove a set inclusion by choosing an element from the smaller set and showing it's in the larger set.
• Relation Proofs
  • Prove that a relation does or doesn't have one of the standard properties (reflexive, irreflexive, symmetric, anti-symmetric, transitive).
  • Prove that a relation is, or isn't, an equivalence relation, an partial order, a strict partial order, or linear order.
• One-to-one and Onto Proofs
  • Prove that a function is one-to-one, onto, bijective, increasing, and/or strictly increasing.
  • Prove general results about these properties, e.g., a strictly increasing function is one-to-one, the composition of two one-to-one functions is one-to-one.
• Two-way Bounding Proofs
  • Prove an equality by establishing upper and lower bounds. E.g. prove that the chromatic number of a graph G is k.
  • Prove a set equality by proving inclusion in both directions.
• Induction Proofs
  • Write inductive proofs that need to use the truth of the claim for more than one immediately previous value, e.g. multiple previous values, a previous value several steps back.
  • Use induction to prove facts about a recursively defined function, e.g., that it has some specific closed form.
  • For recursively defined sets of objects (e.g., graphs), use induction to prove that they have some specific property (e.g., number of edges) and/or write a recurrence for the values of some property of the objects (e.g., number of edges).
  • Use induction to prove claims involving inequalities.
• Tree Induction Proofs
  • Prove a claim about labeled or unlabeled trees using induction.
  • Use induction to prove a claim about other sorts of objects, where your induction variable is the size of the object and there may be more than one object of each size.