4. Relations and DigraphsBinary RelationGeometric and Algebraic Representation MethodPropertiesEquivalenceRelationsOperations
4. Relations and Digraphs Binary Relation Geometric and Algebraic Representation Method Properties Equivalence Relations Operations
Product Sets An ordered pair (a,b) is a listing of the objects a andb in a prescribed order. If A and B are two nonempty sets, the product setor Cartesian product AxB is the set of all orderedpairs (a,b) with aeA, beB.Theorem 1. For any two finite, nonempty sets A and B[AxB|=|A/B| Cartesian product of the nonempty setsA1,A2,...,Am is the set of all ordered m-tuples(a,a2,...,am) where a;EAj, i=1,2, ...,m.A,xA2 ×... ×Am=(a1,a2,...,am) I a;EAi, i=1,2, ...,m)
Product Sets • An ordered pair (a,b) is a listing of the objects a and b in a prescribed order. • If A and B are two nonempty sets, the product set or Cartesian product AB is the set of all ordered pairs (a,b) with aA, bB. Theorem 1. For any two finite, nonempty sets A and B, |AB|=|A||B| • Cartesian product of the nonempty sets A1 ,A2 ,.,Am is the set of all ordered m-tuples (a1 ,a2 ,.,am) where aiAi , i=1,2, .,m. A1A2 . Am={(a1 ,a2 ,.,am) | aiAi , i=1,2, .,m}
PartitionsA partition or quotient set of a nonemptyset A is a collection Pof nonempty subsetsof A such thatEach element of A belongs to one of the setsin @.If A, and A, are distinct elements of , thenA0A2=Φ.The sets in P are called the blocks or cellsof the partitionThe members of a partition of a set A aresubsets of AA partition is a subset of P(A), the power setofAPartitions can be considered as particularkinds of subsets of P(A)
Partitions • A partition or quotient set of a nonempty set A is a collection P of nonempty subsets of A such that – Each element of A belongs to one of the sets in P. – If A1 and A2 are distinct elements of P, then A1A2=. • The sets in P are called the blocks or cells of the partition • The members of a partition of a set A are subsets of A • A partition is a subset of P(A), the power set of A • Partitions can be considered as particular kinds of subsets of P(A)
Relations: Let A and B be nonempty sets, a relation R fromA to B is a subset of AxB. If (a,b)eR, then a isrelated to b by R and aRb.. If Rc AxA, Ris a relation on A.. The domain of R, Dom(R), is the set of elementsin A that are related to some elements in BThe range of R, Ran(R), is the set of elements inB that are related to some elements in A.: R(x) is defined as the R-relative set of x, whereXeA, R(x)={yeB / xRy ) R(Ay) is defined as the R-relative set of A1where AA, R(A)={y eB I xRy for some x in A)
Relations • Let A and B be nonempty sets, a relation R from A to B is a subset of AB. If (a,b)R, then a is related to b by R and aRb. • If R AA, R is a relation on A. • The domain of R, Dom(R), is the set of elements in A that are related to some elements in B. • The range of R, Ran(R), is the set of elements in B that are related to some elements in A. • R(x) is defined as the R-relative set of x, where xA, R(x)={yB | xRy } • R(A1 ) is defined as the R-relative set of A1 , where A1A, R(A1 )={y B | xRy for some x in A1 }
RelationsTheorem 1. Let R be a relation from A to Band let A and A, be subsets of A. Then(a) If A1CA2, then R(A)CR(A2),(b) R(A,UA2)=R(A)UR(A2)(c) R(AnA)CR(A)nR(A2)Theorem 2. Let R and S be relations form Ato B. If R(a)=S(a) for all a in A, then R=S
Relations Theorem 1. Let R be a relation from A to B, and let A1 and A2 be subsets of A. Then (a) If A1A2 , then R(A1 )R(A2 ). (b) R(A1A2 )=R(A1 )R(A2 ). (c) R(A1A2 )R(A1 )R(A2 ). Theorem 2. Let R and S be relations form A to B. If R(a)=S(a) for all a in A, then R=S