CS 173: Skills list for third examlet

​I accidentally deleted this skillset over the weekend -- it is not accurate but I don't have time to fix it yet! You will need to also know nested quantifiers and some other function related things. Sorry!

• 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 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 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?)
    • How to recognize or construct a relation that is neither irreflexive nor reflexive, or neither symmetric nor antisymmetric.
  • Know what it means for two elements in a relation to be comparable.
  • Define equivalence relation, partial order, strict partial order, linear order.
• Equivalence Classes
  • For an equivalence relation R and an element x, define the equivalence class [x].
  • For a specific value of x, determine what's in [x]
  • 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, an partial order, a strict partial order, or linear order.