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.