CS 173: Skills list for Examlet 4

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 id_A on a set 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.

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 formulas to count the numbers of possible functions or one-to-one functions between sets of specific sizes.
• 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.