# CS 173: Skills list for Examlet 2

• Set Theory
• Notation
• set builder notation for defining sets
• set membership and inclusion notation: ⊆, ∈
• special symbol for the empty set: ∅
• an ordered pair, triple, n-tuple
• Define formally, be familiar with standard notation, compute the values for concrete input sets
• A is a subset of B
• The cartesian product of two sets A and B, of three or more sets
• The complement of a set (given some specified universe).
• The union, intersection, and difference of two sets.
• Know what happens if one of the inputs to these operations is the empty set.
• Given a simple set relationship, recognize whether it's correct or not. If not, show a counter-example.
• Know DeMorgan's laws and the distributive laws for sets.
• Set Theory Proofs
• Prove a set inclusion by choosing an element from the smaller set and showing it's in the larger set.
• Functions
• Know the basic notation f:A→B. Know the meaning of the terms domain, co-domain, range/image (of the function).
• Define the composition of two functions. Compute the composition of two specific functions.
• One-to-one and Onto
• Define what it means for a function function to be injective/one-to-one, surjective/onto, bijective.
• 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. composition of two one-to-one functions is one-to-one.
• Relations
• Define a k-ary relation, a relation R from A to B, using the notation xRy.
• Know the relationship between functions, relations, and Cartesian products.