# CS 173, Fall 2014: 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 (idA)
• 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.