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.