1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 5
Текст из файла (страница 5)
Note that thecomposition of two functions I : A f--t Band g : B f--t C is a function h from Ato C such that h(a) = g(f(a)) for each a E A. For example, if I is the functionthat assigns to each dog its owner and g assigns to each person his or her age,then log assigns to each dog the age of its owner.<>Problems for Sectior 1.21.2.1. Write each of the following explicitly.(a) {I} x {1,2} x {1,2,3}(b) 0 x {1,2}(c) 2{1,2} x {I, 2}1.2.2. Let R = {(a, b), (a, c), (c, d), (a, a), (b, a)}. What is R 0 R, the compositionof R with itself? What is R- 1 , the inverse of R? Is R, R 0 R, or R- 1 afunction?1.2.3. Let I : A f--t Band g : B f--t C. Let h : A f--t C be their composition.
Ineach of the following cases state necessary and sufficient conditions on Iand g for h to be as specified.(a) Onto.(b) One-to-one.(c) A bijection.1.2.4. If A and B are any sets, we write BA for the set of all functions from A toB. Describe a natural isomorphism between {O, l}A and 2A.liiJSPECIAL TYPES OF BINARY RELATIONSBinary relations will be found over and over again in these pages; it will behelpful to have convenient ways of representing them and some terminologyfor discussing their properties.
A completely "random" binary relation has nosignificant internal structure; but many relations we shall encounter arise out14Chapter 1: SETS, RELATIONS, AND LANGUAGESof specific contexts and therefore have important regularities. For example,the relation that holds between two cities if they belong to the same state hascertain "symmetries" and other properties that are worth noting, discussing,and exploiting.In this section we study relattons that exhibit these and similar regularities.We shall deal only with binary relations on a set and itself.
Thus, let A be aset, and R t::;: A x A be a relation bn A. The relation R can be represented by adirected graph. Each element of A is represented by a small circle-what wecall a node of the directed graph~ and an arrow is drawn from a to b if and onlyif (a, b) E R. The arrows are the edges of the directed graph. For example, therelation R = {(a,b),(b,a), (a,d),(d,c),(c,c),(c,a)} is represented by the graphin Figure 1-1.
Note in particular the loop from c to itself, corresponding to thepair (c, c) E R. From a node of a graph to another there is either no edge, orone edge ~we do not allow "parallel arrows."a~--~bdFigure 1-1There is no formal distinction between binary relations on a set A and directed graphs with nodes from A. We use the term directed graph when we wantto emphasize that the set on which the relation is defined is of no independentinterest to us, outside the context of this particular relation. Directed graphs,as well as the undirected graphs soon to be introduced, are useful as models andabstractions of complex systems (traffic and communication networks, computational structures and processes, etc.).
In Section 1.6, and in much more detailin Chapters 6 and 7, we shall discuss many interesting computational problemsarising in connection with directed graphs.For another example of a binary relation/directed graph, the less-than-orequal-to relation::; defined on the natural numbers is illustrated in Figure 1-2.Of course, the entire directed graph cannot be drawn, since it would be infinite.A relation R t::;: A x A is reflexive if (a, a) E R for each a E A. The directedgraph representing a reflexive relation has a loop from each node to itself. Forexample, the directed graph of Figure 1-2 represents a reflexive relation, butthat of Figure 1-1 does not.A relation R t::;: A x A is symmetric if (b, a) E R whenever (a, b) E R.151.3: Special Types of Binary RelationsFigure 1-2In the corresponding directed graph, whenever there is an arrow between twonodes, there are arrows between those nodes in both directions.
For example, the directed graph of Figure 1-3 represents a symmetric relation. Thisdirected graph might depict the relation of "friendship" among six people,since whenever x is a friend of y, y is also a friend of x. The relation offriendship is not reflexive, since we do not regard a person as his or her ownfriend.
Of course, a relation could be both symmetric and reflexive; for example, {(a, b) : a and b are persons with the same father} is such a relation.a~:fFigure 1-3A symmetric relation without pairs of the form (a, a) is represented as anundirected graph, or simply a graph. Graphs are drawn without arrowheads,combining pairs of arrows going back' and forth between the same nodes. Forexample, the relation shown in Figure 1-3 could also be represented by the graphin Figure 1-4.A relation R is antisymmetric if whenever (a, b) E R and a and baredistinct, then (b, a) ~ R. For example, let P be the set of all persons. Then{(a,b) : a,b E P and a is the father of b}16ao-rChapter 1: SETS, RELATIONS, AND LANGUAGES10--1ICdFigure 1-4is antisymmetric.
A relation may be neither symmetric nor antisymmetric; forexample, the relation{( a, b) ; a, b E P and a is the brother of b}and the relation represelrted in Figure 1-1 are neither.A binary relation R is transitive if whenever (a, b) E Rand (b, c) E R,then (a, c) E R. The relation{(a, b) ; a, b E P and a is an ancestor of b}is transitive, since if a is an ancestor of band b is an ancestor of c, then a isan ancestor of c. So is the less-than-or-equal relation. In terms of the directedgraph representation, transitivity is equivalent to the requirement that wheneverthere is a sequence of arrows leading from an element a to an element z, thereis an arrow directly from a to z.
For example, the relation illustrated in Figure1-5 is transitive.aK77(b~CFigure 1-5A relation that is reflexive, symmetric, and transitive is called an equivalence relation. The representation of an equivalence relation by an undirectedgraph consists of a number of clusters; within each cluster, each pair of nodes isconnected by a line (see Figure 1-6). The "clusters" of an equivalence relationare called its equivalence classes. We normally write [aJ for the equivalenceclass containing an element a, provided the equivalence relation R is understood by the context. That is, [aJ = {b ; (a, b) E R}, or, since R is symmetric,[aJ = {b ; (b, a) E R}.
For example, the equivalence relation in Figure 1-6 hasthree equivalence classes, one with four elements, one with three elements, andone with one element.171.3: Special Types of Binary RelationsQFigure 1-6Theorem 1.3.1: Let R be an equivalence relation on a nonempty set A. Thenthe equivalence classes of R constitute a partition of A.Proof: Let II = {raj : a E A}. We must show that the sets in II are non empty,disjoint, and together exhaust A.
All equivalence classes are nonempty, sincea E [aJ for all a E A, by reflexivity. To show that they are disjoint, considerany two distinct equivalence classes [aJ and [bJ, and suppose that [aJ n [bJ f::. 0.Thus there is an element c such that c E [aJ and c E [bJ. Hence (a, c) E Rand(c, b) E R; since R is transitive, (a, b) E R; and since R is symmetric, (b, a) E R.But now take any element dE raj; then (d, a) E R and, by transitivity, (d, b) E R.Hence d E [b], so that [aJ <:;;; [bJ. Likewise [bJ <:;;; raj. Therefore [aJ = [bJ. But thiscontradicts the assumption that [aJ and [bJ are distinct.To see that UII = A, simply notice that each element a of A is in some setin II -namely, a E [aJ, by reflexivity.•Thus starting from an equivalence relation R, we can always construct acorresponding partition II.
For example, ifR = {( a, b) : a and b are persons and a and b have the same parents},then the equivalence classes of R are all groups of siblings. Note that the construction of Theorem 1.3.1 can be reversed: from any partition, we can constructa corresponding equivalence relation. Namely, if II is a partition of A, thenR= {( a, b) : a and b belong in the same set of II}is an equivalence relation. Thus there is a natural isomorphism between the setof equivalence relations on a set A and the set of partitions of A.A relation that is reflexive, antisymmetric, and transitive is called a partialorder.
For example,{ (a, b) : a, b are persons and a is an ancestor of b}18Chapter 1: SETS, RELATIONS, AND LANGUAGESis a partial order (provided we consider eaeh person to be an ancestor of himselfor herself). If R ~ A x A is a partial order, an element a E A is called minimalif the following is true: (b, a) E R only if a = b. For example, in the ancestorrelation defined above, Adam and Eve are the only minimal elements.
A finitepartial order must have at least one minimal element, but an infinite partialorder need not have one.A partial order R ~ A x A is a total order if, for all a, b E A, either(a, b) E R or (b, a) E R. Thus the ancestor relation is not a total order since notany two people are ancestrally related (for example, siblings are not); but theless-than-or-equal-to relation on numbers is a total order. A total order cannothave two or more minimal elements.A path in a binary relation R is a sequence (al, ... , an) for some n ;::: 1such that (ai, ai+l) E R for i = 1, ... , n - 1; this path is said to be from al toan.
The length of a path (al, ... , an) is n. The path (al, ... , an) is a cycle ifthe ai's are all distinct and also (an' al) E R.Problems for Section 1.31.3.1. Let R = {(a, c), (c,e), (e, e), (e, b), (d, b), (d, d)}. Draw directed graphs representing each of the following.(a) R(b) R- I(c) RUR- I(d) Rn R- I1.3.2. Let Rand S be the binary relations on A = {I, ... , 7} with the graphicalrepresentations shown in the next page.(a) Indicate whether each of Rand S is (i) symmetric, (ii) reflexive, and(iii) transitive.(b) Repeat (a) for the relation R U S.1.3.3. Draw directed graphs representing relations of the following types.(a) Reflexive, transitive, and antisymmetric.(b) Reflexive, transitive, and neither symmetric nor antisymmetric.1.3.4. Let A be a nonempty set and let Rproperties does R have?(a) Reflexi vi ty.(b) Symmetry.(c) Antisymmetry.(d) Transitivity.~A x A be the empty set.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
