August 27

* Functions

  A function f is a mapping from one set to another
  f <= AxB
  A function from set A to set B can also be defined as a binary relation R
  on A and B with the property that for each element a in A, there is
  exactly one ordered pair in R with the first component a.

  The first component of each pair is mapped onto the second component.
  One function f<= NxN could be (n, n+1), or f = {(1,2), (2,3), (0,1), ...)}

     +-----+
     |     |          +---+   When a function maps elements of set A onto
     |     |  ===>    |   |   elements of set B, then
     |     |          |   |
     |     |          +---+   A is the "domain" of the function
     |     |                  B is the "range" of the function
     +-----+                  If a in A, then f(a) is element b in B s.t.
			      (a,b) in f
			      If f is a function, then one and only one b in B
			      with this property.
			      f(a) is the "image of a under f", or "f of a"

  Sometimes a function can be applied to an n-tuple.  The components of the
  tuple are the "arguments" of f and b is the corresponding "value" of f.

  f: A1 x A2 x ... x An ->B  is such a function, f(a1, a2, ..., an) = b.


  - If each element in the range is paired with only one element from the
    domain, then then function is "one-to-one".

    For any two distinct elements a, a' in A, f(a) neq f(a')

  - If every element of B is included in the range of f, then the
    function is "onto".

    Each element of B is the image under f of some element of A.

  - A functions is a "bijection between A and B" if it is one-to-one and onto.


  Consider the following relations.  Are they functions?
  One-to-one?  Onto?  Bijections?

  - A = students in this class, B = days of the year
    f(a) = {b: b = birthday(a)}

    Function, not onto (less than 365 students), have to check to see if
    one-to-one

  - A = students in this class, B = CSE classes
    f(a) = {b: enrolled_in_class(a)} 

    Not a function, at least one student enrolled in more than one class

  - A = graduate students in CSE, B = cse accounts
    Function, one-to-one, onto, bijection


* Special Types of Binary Relations

   These relations will map a set to itself
   We can view these relations with a directed graph.
   Each element of the set is a node in the graph, an arrow is drawn from
   node a to node b if and only if (iff) (a,b) in R.

   Sample graph
   A = {a,b,c,d}
   R = {(a,b), (b,a), (a,d), (d,c), (c,c), (c,a)}

   By viewing the relation as a directed graph we can sometimes see
   interesting structure in the relation.

   Note in this case the loop from c to itself (c,c) in R.

   Consider less-than-or-equal-to relation
   (show on values 0 through 5)

   Once again, all nodes have loops to themselves.

   This self-loop shows the "reflexive" relation.
   - A relation R <= AxA is "reflexive" if (a,a) in R for all a in A.

   For example, {(a,b): a has the same parity as b} is reflexive.

   - A relation R <= AxA is "symmetric" if (b,a) in R whenever (a,b) in R.
   Can see this in graphs if loop between two nodes.
   Show graph.

   For example, {(a,b): a is in the same class as b} is symmetric.
   The previous example is also symmetric.

   - A relation R is "antisymmetric" if whenever (a,b) in R, a, b distinct,
   then (b,a) is NOT in R.
   There are NO two-node loops in graph.

   For example, "a is less than b" is antisymmetric.

   A relation can sometimes be neither symmetric nor antisymmetric - in this
   case, there can be two-node loops but sometimes there will just be an arrow
   in one direction (not both directions) between two nodes.

   For example, {(a,b):  a is the brother of b} is neither symmetric
   nor antisymmetric.

   - A relation R is "transitive" if, whenever (a,b) in R and (b,c) in R,
   then (a,c) in R.

   {(a,b) a is less than b} is transitive.

   In the graph, you see a path from a to c going through b.

   - A relation is an "equivalence relation" if it is reflexive, symmetric,
   and transitive.

   If you draw an equivalence relation with an "undirected graph" (remove
   the arrows), you will see connected clusters.  Each separate cluster in this
   case represents an "equivalence class".

   The equivalence class of an element a in A defined by the equivalence
   relation R is the set [a], where [a] = {b in A: (a,b) in R}.

   The set of equivalence classes of R, where R is an equivalence relation,
   constitute a partition of A.

   Show graph for
   R = {(a,b):  a and b are people and a and b have the same parents}

   If Q and R are binary relations, then their "composition" Q.R, or QR, is
   {(a,b): for some c, (a,c) in Q and (c,b) in R}.  The composition of two
   functions f:A->B and g:B->C is a function h from A to C s.t.
   h(a) = g(f(a)) for each a in A.

   If f assigns to each student a number grade and g maps a number grade onto
   a letter grade, then f.g assigns to each student a letter grade.

   If Q = {(a,b) (b,c), (c,d)} and R = {(a,e), (b,f) (c,g), (d,h)}, then
   QR = {(a,f), (b,g), (c,h)}.


* Partial Order

  A relation R is a "partial order" if it is reflexive, antisymmetric,
  and transitive.

  A partial order R is also a "total order" if for all a,b in A, either
  (a,b) in R or (b,a) in R.  In other words, for any two elements exactly one
  ordering must exist between the two.

  One way to identify a partial ordering is to prove that a relation
  is reflexive, transitive, and has no "nontrivial cycles".

  A "chain" in a binary relation R is a sequence (a1, ..., an) such that
  each (ai, ai+1) in R.  If all ai are distinct and (an, a1) in R, the
  chain is also a "cycle".  If n=1 the cycle is "trivial", otherwise the
  cycle is "nontrivial".

  Problem 1.4.8

  a) Prove that if S is any collection of sets, then R_S = {(A,B): A,B in S
  and A<=B} is a partial order.

     To prove that R_S is a partial order it is sufficient to show that R_S is
  reflexive, transitive, and has no nontrivial cycles.

  Reflexive:  A includes all of the elements of itself, so by definition of
  subset, A<=A.

  Transitive: Show that if A<=B and B<=C, then A<=C.  If B<=C, then every
  element of B is also an element of C.  Because A<=B, every element of A
  is an element of B which is also an element of C, so A<=C.

  No nontrivial cycles:  for (a1, ..., an) to form a nontrivial cycle all ai
  must be distinct, (ai, ai+1) must be in R_S, and (an, a1) must be in R_S.
  Note that for ai<=ai+1, either ai must equal ai+1 or ai has fewer elements
  than ai+1.  Since all of the ai components are distinct, we know that
  ai neq ai+1 so |a1| < |a2| < ... < |an|.  By the transitive property of "<",
  |a1| < |an|, and thus (an, a1) cannot be in R_S.  Thus R_S has no nontrivial
  cycles.


  b) Let S = 2**{1,2,3}.  Draw directed graph representing the partial
  order defined in (a).  What element or elements are minimal?

  A "minimal" element of a partial order R is an element a such that
  (b,a) in R only if b = a.

  We can spot minimal elements in the directed graph if there are no
  arrows pointing to a node or nodes in the graph except from themselves
  (these are minimal elements).

  Every finite partial order has at least one minimal element.

  One final note on binary relations:  we can use the notation
  (a,b) in R or the "infix notation" aRb.