Properties of Relations. In many applications to computer science and appliedmathematics, we deal with relations on a set A ratherthan relations fromAto BArelation R on a set A is reflexive if (a,a)eRfor allaeA; it's irreflexive if (a,a)Rfor all aeALet △=f(a,a)l aeAi, △ is the relation of equality on theset A. and△ is reflexiveThe matrix of a reflexive relation must have all 1's onits main diagonal, while irreflexive must have all O's onits main diagonal.A reflexive relation has a cycle of length 1 at everyvertex, while irreflexive has no cycles of length 1.: R is reflexive if and only if △cR, and R is irreflexive ifand only if △oR=dIf Ris reflexive on a set A, then Dom(R)=Ran(R)=A
Properties of Relations • In many applications to computer science and applied mathematics, we deal with relations on a set A rather than relations from A to B • A relation R on a set A is reflexive if (a,a)R for all aA; it’s irreflexive if (a,a)R for all aA • Let ={(a,a)| aA}, is the relation of equality on the set A, and is reflexive • The matrix of a reflexive relation must have all 1’s on its main diagonal, while irreflexive must have all 0’s on its main diagonal. • A reflexive relation has a cycle of length 1 at every vertex, while irreflexive has no cycles of length 1. • R is reflexive if and only if R, and R is irreflexive if and only if R= • If R is reflexive on a set A, then Dom(R)=Ran(R)=A
Symmetric, Asymmetric andAntisymmetric Relations: A relation R on a set A is symmetric if wheneveraRb,then bRa- Ris not symmetric if there are some a and beA withaRb,/but bRa: A relation R on a set A is asymmetric ifwhenever aRb,then bRa- Ris not asymmetric if there are some a and beAwithbothaRband bRa. A relation R on a set Ais antisymmetric ifwhenever aRb and bRa, then a=b;- The contrapositive of this definition: R isantisymmetric if whenever a=b, then aRb or bRa- Ris not antisymmetric if there are some a and beAa+b, and both aRb and bRa
Symmetric, Asymmetric and Antisymmetric Relations • A relation R on a set A is symmetric if whenever aRb, then bRa – R is not symmetric if there are some a and bA with aRb, but bRa • A relation R on a set A is asymmetric if whenever aRb, then bRa – R is not asymmetric if there are some a and bA with both aRb and bRa • A relation R on a set A is antisymmetric if whenever aRb and bRa, then a=b; – The contrapositive of this definition: R is antisymmetric if whenever ab, then aRb or bRa – R is not antisymmetric if there are some a and bA, ab, and both aRb and bRa
Symmetric, Asymmetric andAntisymmetric Relations: Mr =[mil of a symmetric relation satisfies theproperty that if mi=1, then mi=1 and if mi=0then m=0; it's a symmetric matrix- mi can be either 0 or 1 for all i: Mr =[mi] of an asymmetric relation satisfiesthe property that if mi=1, then mi=0 and mi=0for all i- If mi=0, then mj; can be either 0 or 1: Mr =[mi] of an antisymmetric relation satisfiesthe property that if i*j, then mi=0, or mi=0- mi can be either 0 or 1 for all i
Symmetric, Asymmetric and Antisymmetric Relations • MR =[mij] of a symmetric relation satisfies the property that if mij=1, then mji=1 and if mij=0, then mji=0; it’s a symmetric matrix – mii can be either 0 or 1 for all i • MR =[mij] of an asymmetric relation satisfies the property that if mij=1, then mji=0 and mii=0 for all i – If mij=0, then mji can be either 0 or 1 • MR =[mij] of an antisymmetric relation satisfies the property that if ij, then mij=0, or mji=0 – mii can be either 0 or 1 for all i
Symmetric, Asymmetric andAntisymmetric Relations: If relation R is asymmetric, then the digraphof R cannot simultaneously have an edgefrom vertex ito j and an edge from jto i; andthere can be no cycles of length 1: all edgesare one-way: If relation R is antisymmetric, then fordifferent vertices i and jthere cannot not bean edge from ito jand an edge from jto iwhen i=j, no condition is imposed, thus theremay be cycles of length 1: still all edges areone-way: If relation R is symmetric, then wheneverthere is an edge from vertex ito j, then thereis an edge from vertex jto i
Symmetric, Asymmetric and Antisymmetric Relations • If relation R is asymmetric, then the digraph of R cannot simultaneously have an edge from vertex i to j and an edge from j to i; and there can be no cycles of length 1: all edges are one-way • If relation R is antisymmetric, then for different vertices i and j there cannot not be an edge from i to j and an edge from j to i; when i=j, no condition is imposed, thus there may be cycles of length 1: still all edges are one-way • If relation R is symmetric, then whenever there is an edge from vertex i to j, then there is an edge from vertex j to i
Transitive RelationsArelation R on a set A is transitive if whenever aRbandbRc,thenaRc.A relation R on A is not transitive if there exists a, b,and c in A so that aRb and bRc, but aRcIf such a, b, and c do not exist, then Ris transitiveR is transitive if and only if its matrix M =[mil has theproperty if mi=1 and mik=1, then mik=1.If MoM has a 1 in any position, then M must have a1 in the same position, i.e. if MpOMp = Mr, then R istransitiveThe converse is not true, i.e. if MoMr + Mr, thenR may be transitive or may not be transitive
Transitive Relations • A relation R on a set A is transitive if whenever aRb and bRc, then aRc. • A relation R on A is not transitive if there exists a, b, and c in A so that aRb and bRc, but aRc. – If such a, b, and c do not exist, then R is transitive • R is transitive if and only if its matrix MR =[mij] has the property if mij=1 and mjk=1, then mik=1. • If MRMR has a 1 in any position, then MR must have a 1 in the same position, i.e. if MRMR = MR, then R is transitive – The converse is not true, i.e. if MRMR MR, then R may be transitive or may not be transitive