CS 173: Skills list for Examlet 3
- 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.
- 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).
- 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 on a set A and know its shorthand name
(idA)
- One-to-one and Onto
- Define what it means for a function function to be one-to-one,
onto, bijective, increasing, strictly increasing.
- 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. a strictly increasing function is
one-to-one, composition of two one-to-one functions is one-to-one.
- Know that a strictly increasing function is always one-to-one.
- Logic and proofs
- Understand how to simplify proofs using
"without loss of generality"
- Negate a statement containing multiple quantifiers.
- Understand the difference in meaning between
the statement ∀ x, ∃ y P(x,y)
and the statement ∃ y, ∀ x, P(x,y).
- Counting
- Know the formulas for counting permutations, and
permutations with indistinguishable objects.
- Apply permutation formulas to count the
numbers of possible functions or one-to-one functions
between sets of specific sizes, and count
the number of graphs on a set of a specific size.
- Know how a function being onto or one-to-one constrains the
size of its domain relative to its co-domain. (Finite sets only.)
- Apply these formulas to solve simple concrete word problems.
- Be able to state the Pigeonhole Principle and apply it to simple
concrete examples.
- Apply the pigeonhole principle in writing proofs.
Straightforward examples only.