CS 173: Skills list for "Examlet B"

• Logic
  • Know what it means for a statement to be "vacuously true."
• Modular arithmetic
  • For congruence mod k, know which integers are in the equivalence class of x. Know the shorthand notation [x]_k (and the shorthand [x] for when k is clear from context).
  • Know when [x]_k and [y]_k are equal as elements of Z_k.
  • Do arithmetic in Z_k (e.g. addition, multiplication, taking integer powers), keeping intermediate results small.
• Set Theory
  • Notation
    • set builder notation for defining sets
    • set membership (∈) and subset/inclusion (⊆)
    • 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 cardinality of a set
    • The complement of a set (given some specified universe).
    • The union, intersection, and difference of two sets.
  • Know the meaning of the term disjoint.
  • 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.
  • Cardinality
    • Know the inclusion-exclusion formula relating the cardinality of sets A and B to that of their union and intersection.
    • Given the cardinality of two sets A and B, compute the cardinality of their Cartesian product.
    • Apply these two formulas to real-world counting problems.
• Set Theory Proofs
  • Prove a set inclusion by choosing an element from the smaller set (while keeping it arbitrary!) and showing it's in the larger set.

• Relations
  • Define a relation R on a set A, using the notation xRy.
  • Represent a relation as a directed graph.
  • Define reflexive, irreflexive, symmetric, anti-symmetric, transitive. For any of these problems, determine if a specific relation has the property. In particular, be sure you know
    • When one of these properties is vacuously true (e.g. what are the properties of a relation with no arrows at all?)
    • Know that symmetric and antisymmetric are not opposites, and recognize or construct a relation that is neither or both. Same for irreflexive and reflexive (except we can't have both at the same time since we're assuming the base set is nonempty).
  • Define equivalence relation.
• Equivalence Classes
  • For an equivalence relation R and an element x, define the equivalence class [x]_R (or just [x] for short) and determine what's in it.
    • (Common mistake to avoid: even though congruence mod k ([x]_k) was the first kind of equivalence class you learned about and it is often written using shorthand as [x], in general the notation [x] can refer to the equivalence class for any relation and does not automatically mean congruence mod k.)
  • List or describe all of R's equivalence classes.
• Relation proofs
  • Prove that a relation does or doesn't have one of the standard properties (reflexive, irreflexive, symmetric, anti-symmetric, transitive).
  • Prove that a relation is, or isn't, an equivalence relation, a partial order, or a strict partial order. (The definitions of partial order and strict partial order in terms of the properties above will be provided for you when relevant.)