CS 173: Skills list for Examlet 2
- Set Theory
- 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.
- 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,
- 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.
- 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.