1

2.2 Properties of Relations

--Digraph representation

--Boolean matrix representation

2.3 Properties of Relations

• Reflexive or Irreflexive
• Symmetric
• Asymmetric
• Antisymmetric
• Transitive

2

Properties of Relations

• Properties of relations can be identified through three characteristics:
• relation statement
• matrix representation
• digraph representation

3

Reflexive and Irreflexive Relations

Relation statement

Reflexive: For all a ∈ A, one has a R a.

Irreflexive: For every a ∈ A, a a

Example:

Let A={1,2,3}, and let R={(1,1),(1,2)}.

Then,

R is not reflexive since (2,2) R and (3,3) R

R is not irreflexive since (1,1) R

4

Reflexive and Irreflexive Relations

Matrix representation

Reflexive: have all 1’s on its main diagonal

Irreflexive: have all 0’s on its main diagonal

Example

Let A={1,2,3,4}. Determine whether the relation R whose matrix M_R is given is reflexive or irreflexive?

​

Solution: M_R have all 1’s in its main diagonal, so R is reflexive

5

Reflexive and Irreflexive Relations

Digraphs representation

Reflexive: has a cycle of length 1 at every vertex

Irreflexive: has no cycles of length 1

Example

Let A={1,2,3,4}. determine whether the relation R whose digraph is given is reflexive or irreflexive?

Solution: Not reflexive, since vertex 3 and 4 has no cycle of length 1.

Not irreflexive, since vertex 1 and 2 has cycle of length 1

6

Symmetric Relations

Relation statement

Symmetric: Whenever a R b then b R a.

Not Symmetric:

For some a and b A, with a R b but b a.

​

Example

Let A={1,2,3,4}, and let R={(1,2),(2,2),(3,4),(4,1)}.

Then,

R is not symmetric since (1,2) R but (2,1) R

7

Symmetric Relations

Matrix representation

Let M_R=M_ij,

Symmetric: M_ij =1 then M_ji =1, or M_ij =0 then M_ji =0

Not symmetric: vice versa

Example

Let A={1,2,3,4}. Determine whether the relation R whose matrix M_R is given is symmetric or not?

8

Symmetric Relations

Solution:

Since,

M₁₂ =1 then M₂₁ = 1 or

M₁₃ =0 then M₃₁ = 0 or

M₁₄ =0 then M₄₁ = 0 or

M₂₃ =0 then M₃₂ = 0 or

M₂₄ =0 then M₄₂ = 0 or

M₃₄ =0 then M₄₃ = 0

R is symmetric

9

Symmetric Relations

Digraph representation

Symmetric: if there is an edge from vertex i to vertex j, then there is an edge from vertex j to vertex i

Not Symmetric: vice versa

Example

Let A={1,2,3,4}. determine whether the relation R whose digraph is given is symmetric or not?

Solution:Not symmetric, since there is an edge from vertex 2 to 3, but there is no an edge from vertex 3 to 2.

10

Asymmetric Relations

Relation statement

Asymmetric: Whenever a R b then b a.

Not Asymmetric:

For some a and b A, with both a R b and b R a.

Example

Let A={1, 2, 3, 4}, and let R = {(1,2), (2,2), (3,4), (4,1)}.

Then, R is not asymmetric since (2,2) R.

11

Asymmetric Relations

Matrix representation

Let M_R=M_ij,

Asymmetric: M_ij =1 then M_ji =0, followed by 0’s in the main diagonal

Not symmetric: vice versa

Example

Let A={1,2,3,4}. Determine whether the relation R whose matrix M_R is given is asymmetric or not?

12

Asymmetric Relations

Solution:

Since,

M₁₂ =0 , M₂₁ = 0

M₁₃ =1 then M₃₁ = 0

M₁₄ =1 then M₄₁ = 1

M₂₃ =1 then M₃₂ = 0

M₂₄ =0, M₄₂ = 0 or

M₃₄ =1 then M₄₃ = 0

R is not asymmetric

13

violates

Asymmetric Relations

Digraph representation

Asymmetric: cannot simultaneously have an edge from vertex i to vertex j and an edge from vertex j to vertex i and also there can be no cycles of length 1.

Not Asymmetric: vice versa

Example

Let A={1,2,3,4,5}. Determine whether the relation R whose digraph is given is asymmetric or not?

Solution:Asymmetric, since there all edges are “one way” and there is no cycles of length 1.

14

Antisymmetric Relations

Relation statement

Antisymmetric: Whenever a R b and b R a, then a=b or

Whenever

Not Antisymmetric:

there is a and b in A, , and both a R b and b R a.

Examp le

Let A={1, 2, 3, 4}, and let R={(1,2), (2,2), (3,4), (4,1)}.

Then, R is antisymmetric since

15

Antisymmetric Relations

Matrix representation

Let M_R=M_ij,

Antisymmetric: If , then M_ij =0 or M_ji =0.

Not antisymmetric: Ǝ i and j with such that ???.

Example

Let A={1,2,3,4}. Determine whether the relation R whose= matrix M_R is given is antisymmetric or not?

16

Antisymmetric Relations

Solution:

Since,

M₁₂ =0 or M₂₁ = 0

M₁₃ =0 or M₃₁ = 0

M₁₄ =1 or M₄₁ = 0

M₂₃ =1 or M₃₂ = 0

M₂₄ =1 or M₄₂ = 0

M₃₄ =0 or M₄₃ = 0

R is antisymmetric

17

Antisymmetric Relations

Digraph representation

Antisymmetric: for different vertices i and j there cannot simultaneously have an edge from vertex i to vertex j and an edge from vertex j to vertex i, however there may be cycles of length 1.

Not Antisymmetric: vice versa

Example

Let A={1,2,3,4,5}. Determine whether the relation R whose digraph is given is antisymmetric or not?

Solution: Antisymmetric, since all edges are “one way”.

18

Transitive Relations

Relation statement

Transitive: Whenever a R b and b R c, then a R c.

​

Not transitive :

If there exist a, b and c in A so that a R b and b R c, but a c

Example

Let A={1,2,3,4}, and let R={(1,2),(1,3),(4,2)}.

Then,

R is transitive since

(a, b, and c do not exist)

19

Transitive Relations

Matrix representation

Let M_R=M_ij,

Transitive: If M_ij =1 then M²_ji =1 or (M_R )²_⊙ = M_R

Not transitive : vice versa

Example

Let A={1,2,3} and let R be the relation on A whose matrix is

​

​

​

Show that R is transitive.

20

Transitive Relations

(M_R )²_⊙ = = M_R

​

​

​

therefore R is transitive.

21

Transitive Relations

Digraph representation

Transitive: If a and b are connected by a path of length 2, they must be connected by a path of length 1.

Not Transitive : ???

Example

Let A={1,2,3,4,5}. Determine whether the relation R whose digraph is given is transitive or not?

Solution: Transitive, since vertex 1 and 2 are connected by vertex 4, i.e. path of length 2, vertex 1 and 2 are also connected by a path of length 1.

22