a b - Home | Courses.ICS

1 ICS 241: Discrete Mathematics II (Spring 2015) Relations and Their PropertiesBinary RelationDefinition:LetA,Bbe any sets. Abinary relationRfromAtoB, writtenR:A B, is a subsetof the setA RelationDefinition:LetRbe the binary relation fromAtoB. Then the complement ofRcan be definedbyR={(a, b)|(a, b)6 R}= (A B) RInverse RelationDefinition:LetRbe the binary relation fromAtoB. Then the inverse ofRcan be defined byR 1={(b, a)|(a, b) R}Relations on a SetDefinition:Arelation on a setAis a relation fromAtoA. In other words, a relation on a setAisa subset ofA :Adirected graph, ordigraph, consists of a set V ofvertices(ornodes) together witha setEof ordered pairs of elements ofVcallededges(orarcs). The vertex a is called theinitialvertexof the edge (a, b), and the vertex b is called theterminal vertexof this :A relationRon a setAis calledreflexiveif(a, a) Rfor every elementa vertex has a :A relationRon a setAis calledsymmetricif(b, a) Rwhenever(a, b) R, for alla, b there is an edge from one vertex to another, there is an edge in the opposite :A relationRon a setAsuch that for alla, b A, if(a, b) Rand(b, a) R,thena=bis 241: Discrete Mathematics II (Spring 2015)There is at most one edge between distinct notes on Symmetric and Antisymmetric: A relation can be both symmetric and antisymmetric.

2 A relation can be neither symmetric nor :A relationRon a setAis calledtransitiveif whenever(a, b) Rand(b, c) R, then(a, c) R, for alla, b, c there is a path from one vertex to another, there is an edge from the vertex to RelationsSince relations fromAtoBare subsets ofA B, two relations fromAtoBcan be combined inany way two sets can be combined. Such as union, intersection, and set :LetRbe a relation from a setAto a setBandSa relation fromBto a setC. Thecomposite ofRandSis the relation consisting of ordered pairs(a, c), wherea A, c C, and forwhich there exists an elementb Bsuch that(a, b) Rand(b, c) S. We denote the compositeofRandSbyS of a RelationLetRbe a relation on the setA. The powersRn, n= 1,2,3, .., are defined recursively byR1=RandRn+1=Rn pg. 581 # 3 For each of these relations on the set{1,2,3,4}, decide whether it is reflexive, whether it is sym-metric, whether it is antisymmetric, and whether it is {(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}Not reflexive because we do not have(1,1),(3,3), and(4,4).

3 Not symmetric because while we we have(3,4), we do not have(4,3).Not antisymmetric because we have both(2,3)and(3,2).Transitive because if we have(a, b)in this relation, thenawill be either 2 or 3. Then(2, c)2 ICS 241: Discrete Mathematics II (Spring 2015)and(3, c)are in the relation for allc6= 1. Since whenever we have both(a, b)and(b, c),then we have(a, c)which makes this relation {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}Ref lexive because(a, a)is in the relation for alla= 1,2,3, because for every(a, b), we have a(b, a).Not antisymmetric because we have(1,2)and(2,1).Transitive because while we have(1,2)and(2,1), we also have(1,1)and(2,2)in {(2,4),(4,2)}Not reflexive because we do not have(a, a)for alla= 1,2,3, because for every(a, b), we have a(b, a).Not antisymmetric because we have both(2,4)and(4,2).Not transitive because we are missing(2,2)and(4,4).d{(1,2),(2,3),(3,4) }Not reflexive because we do not have(a, a)for alla= 1,2,3, symmetric because we do not have(2,1),(3,2), and(4,3).

4 Antisymmetric because for every(a, b), we do not have a(b, a).Not transitive because we do not have(1,3)for(1,2)and(2,3).e{(1,1),(2,2), (3,3),(4,4)}Reflexive because we have(a, a)for everya= 1,2,3, because we do not have a case where(a, b)anda6= because we do not have a case where(a, b)anda6= because we can satisfy(a, b)and(b, c)whena=b= {(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)}Not reflexive because we do not have(a, a)for alla= 1,2,3, symmetric because the relation does not contain(4,1),(3,2),(4,2), and(4,3).Not antisymmetric because we have(1,3)and(3,1).Not transitive because we do not have(2,1)for(2,3)and(3,1). pg. 581 # 7 Determine whether the relationRon the set of all integers is reflexive, symmetric, antisymmetric,and/or transitive, where(x, y) Rif and only ifax6= reflexive because it s not the case16= symmetric becausex6=yandy6= antisymmetric because we havex6=yandy6= transitive because we can have16= 2and26= 1but not16= 241: Discrete Mathematics II (Spring 2015)bxy reflexive because we can t have(0,0).

5 Is symmetric because we havexy= antisymmetric because we havexy= transitive because if we have(a, b) Rand that(b, c) R, it follows that(a, c) that in order for the relation to be true,a, b,andcwill have to be all positive or + 1orx=y reflexive because we can t have(1,1)Is symmetric because we havex=y+ 1andy=x 1. They are equivalent antisymmetric because of the same reason transitive because if we have(1,2) and(2,1)in the relation,(1,1)is not in reflexive because(2,2)does not symmetric because although we can have(9,3), we can t have(3,9).Is antisymmetric because each integer will map to another integer but not in reverse (besides0 and 1).Not transitive because if we have(16,4)and(4,2), it s not the case that16 = reflexive because we can t have(2,2).Not symmetric because if we have(9,3), we can t have(3,9).Is antisymmetric, because each integer will map to another integer but not in reverse (besides0 and 1).Is transitive because ifx y2andy z2, thenx pg.

6 582 # 27 LetRbe the relationR={(a, b)|a|b}on the set of positive integers. FindaR 1R 1={(b, a)|a|b}={(a, b)|b|a}bRR={(a, b)|a-|b}.4