CS 173: Skills list for "Examlet B"

• 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.
• 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); and identify/list elements of these sets.
  • 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, or 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.
  • Understand the difference in meaning between the statement ∀ x, ∃ y P(x,y) and the statement ∃ y, ∀ x, P(x,y) (i.e., nested quantifiers).