CS 173, Spring 2015: Skills list for fifth examlet

• Functions
  • Know the basic notation f:A→B. Know the meaning of the terms domain, co-domain, image (of the function), pre-image (of a value in B).
  • Define the composition of two functions. Compute the composition of two specific functions.
  • Identify when a formula or diagram defines something that is not a function (e.g. two output values for a single input).
  • Define the identity function on a set A and know its shorthand name (id_A)
• One-to-one and Onto
  • Define what it means for a function function to be one-to-one, onto, bijective, increasing, strictly increasing.
  • Be able to identify whether a function (presented via a formula, diagram, or other method) has one of these properties.
  • Prove that a function has one of these properties.
  • Prove general results about these properties, e.g. a strictly increasing function is one-to-one, composition of two one-to-one functions is one-to-one.
  • Know that a strictly increasing function is always one-to-one.
• Logic and proofs
  • Understand how to simplify proofs using "without loss of generality"
  • Negate a statement containing multiple quantifiers.
  • Understand the difference in meaning between the statement ∀ x, ∃ y P(x,y) and the statement ∃ y, ∀ x, P(x,y).
• Counting
  • Know the formulas for counting permutations, and permutations with indistinguishable objects.
  • Apply permutation formuls to count the numbers of possible functions or one-to-one functions between sets of specific sizes, and count the number of graphs on a set of a specific size.
  • Know how a function being onto or one-to-one constrains the size of its domain relative to its co-domain. (Finite sets only.)
  • Apply these formulas to solve simple concrete word problems.
  • Be able to state the Pigeonhole Principle and apply it to simple concrete examples.
  • Apply the pigeonhole principle in writing proofs. Straightforward examples only.