REFLEXIVE RELATION:IRREFLEXIVE RELATION, ANTISYMMETRIC RELATION

<< REFLEXIVE RELATION:SYMMETRIC RELATION, TRANSITIVE RELATION

RELATIONS AND FUNCTIONS:FUNCTIONS AND NONFUNCTIONS >>

MTH001 Elementary Mathematics

R2 is symmetric

R1 is symmetric

R3 is not symmetric since there

R4 is not symmetric since

are arrows from 2 to 3 and from

there is an arrow from 4 to 3

3 to 4 but not conversely

but no arrow from 3 to 4

MATRIX REPRESENTATION OF A SYMMETRIC RELATION

Let

A = {a1, a2, ..., an}.

A relation R on A is symmetric if and only if for all

ai, aj ∈ A, if (ai, aj) ∈R then (aj, ai)∈R.

Page 45

MTH001 Elementary Mathematics

Accordingly, R is

symmetric if the

elements in the ith row are the same as the elements in the ith column of the

matrix M representing R. More precisely, M is a symmetric matrix.i.e. M = M

EXAMPLE

The relation R = {(1,3), (2,2), (3,1), (3,3)}

on A = {1,2,3} represented by the following matrix M is symmetric.

123

1 ⎡0 0 1⎤

M = 2 ⎢0 1 0⎥

⎢

⎥

3 ⎢1 0 1⎥

⎣

⎦

TRANSITIVE RELATION

Let R be a relation on a set A.R is transitive if and only if for all a, b, c ∈A,

if (a, b) ∈R and (b, c) ∈R then (a, c) ∈R.

That is, if aRb and bRc then aRc.

In words, if any one element is related to a second

and that second element is related to a third, then the first is related to the third.

Note that the "first", "second" and "third" elements need not to be distinct.

REMARK

R is not transitive iff there are elements a, b, c in A such that

If (a,b) ∈R and (b,c) ∈R but (a,c) ∉R.

EXAMPLE

Let A = {1, 2, 3, 4} and define relations R1, R2 and R3 on A

as follows:

R1 = {(1, 1), (1, 2), (1, 3), (2, 3)}

R2 = {(1, 2), (1, 4), (2, 3), (3, 4)}

R3 = {(2, 1), (2, 4), (2, 3), (3,4)}

Then R1 is transitive because (1, 1), (1, 2) are in R then to be transitive relation

(1,2) must be there and it belongs to R Similarly for other order pairs.

R2 is not transitive since (1,2) and (2,3) ∈ R2 but (1,3) ∉ R2.

R3 is transitive.

DIRECTED GRAPH OF A TRANSITIVE RELATION

For a transitive directed graph, whenever there is an arrow going from one point to

the second, and from the second to the third, there is an arrow going

directly from the

first to the

third.

EXAMPLE

Let A = {1, 2, 3, 4} and define relations R1, R2 and R3 on A by the

directed graphs:

R1 = {(1, 1), (1, 2), (1, 3), (2, 3)}

R2 = {(1, 2), (1, 4), (2, 3), (3, 4)}

R3 = {(2, 1), (2, 4), (2, 3), (3,4)}

Page 46

MTH001 Elementary Mathematics

R1 is transitive

R2 is not transitive since there is

an arrow from 1 to 2 and from 2

to 3 but no arrow from 1 to 3

directly

R3 is transitive

EXERCISE:

Let A = {1, 2, 3, 4} and define the null relation φ and universal

relation A ×A on A. Test these relations for reflexive, symmetric and

transitive

properties.

SOLUTION:

Reflexive:

∅ is not reflexive since (1,1), (2,2), (3,3), (4,4) ∉ ∅.

(i)

A × A is reflexive since (a,a) ∈ A × A for all a ∈ A.

(ii)

Symmetric

For the null relation ∅ on A to be symmetric, it must

(i)

satisfy the implication:

if (a,b) ∈ ∅ then (a, b) ∈ ∅.

Since (a, b) ∈ ∅ is never true, the implication is vacuously true or true by default.

Hence ∅ is symmetric.

The universal relation A × A is symmetric, for it contains

(ii)

all

ordered pairs of elements of A. Thus,

if (a, b) ∈ A × A then (b, a) ∈ A × A for all a, b in A.

Transitive

Page 47

MTH001 Elementary Mathematics

The null relation ∅ on A is transitive, because the

(i)

implication.

if (a, b) ∈ ∅ and (b, c) ∈ ∅ then (a, c) ∈ ∅ is true by default,

since the condition (a, b) ∈ ∅ is always false.

The universal relation A × A is transitive for it contains all ordered pairs of

(i)

elements of A.

Accordingly, if (a, b) ∈ A × A and (b, c) ∈ A × A then (a, c) ∈ A × A as well.

EXERCISE:

Let

A = {0, 1, 2} and

R = {(0,2), (1,1), (2,0)} be a relation on A.

1. Is R reflexive? Symmetric? Transitive?

2. Which ordered pairs are needed in R to make it a reflexive and transitive

relation.

SOLUTION:

1. R is not reflexive, since 0 ∈ A but (0, 0) ∉R and also 2 ∈ A but (2, 2)

∉R.

R is clearly symmetric.

R is not transitive, since (0, 2) & (2, 0) ∈ R but (0, 0) ∉R.

For R to be reflexive, it must contain ordered pairs (0,0) and (2,2).

For R to be transitive,

we note (0,2) and (2,0) ∈ but (0,0) ∉R.

Also (2,0) and (0,2) ∈R but (2,2)∉R.

Hence (0,0) and (2,2). Are needed in R to make it a transitive relation.

EXERCISE:

Define a relation L on the set of real numbers R be defined as follows:

for all x, y ∈R, x L y ⇔ x < y.

a. Is L reflexive?

b. Is L symmetric?

c. Is L transitive?

SOLUTION:

a. L is not reflexive, because x < x for any real number x.

(e.g. 1 < 1)

L is not symmetric, because for all x, y ∈R, if

x < y then y < x

(e.g. 0 < 1 but 1 < 0)

L is transitive, because for all, x, y, z ∈R, if x < y

and y < z, then x < z.

(by transitive law of order of real numbers).

EXERCISE:

Define a relation R on the set of positive integers Z as follows:

for all a, b ∈Z+, a R b iff a × b is odd.

Determine whether the relation is

a. reflexive

b. symmetric c. transitive

SOLUTION:

Firstly, recall that the product of two positive integers is

odd if and only if both of them are odd.

a. reflexive

R is not reflexive, because 2 ∈ Z+ but 2 R 2

for 2 × 2 = 4 which is not odd.

b. symmetric

R is symmetric, because

if a R b then a × b is odd or equivalently b × a is odd

Page 48

MTH001 Elementary Mathematics

( b × a = a × b) ⇒ b R a.

c. transitive

R is transitive, because if a R b then a × b is

odd

⇒ both "a" and "b" are odd. Also bRc means b × c is odd

⇒ both "b" and "c" are odd.

Now if aRb and bRc, then all of a, b, c are odd and so a × c

is odd.

Consequently aRc.

EXERCISE:

Let "D" be the "divides" relation on Z defined as:

for all m, n ∈Z, m D n⇔ m|n

Determine whether D is reflexive, symmetric or transitive. Justify your answer.

SOLUTION:

Reflexive

Let m ∈Z, since every integer divides

itself so

m|m ∀ m ∈Z therefore m D m ∀ m ∈Z

Accordingly D is reflexive

Symmetric

Let m, n ∈ Z and suppose m D n.

By definition of D, this means m|n (i.e.= an integer)

Clearly, then it is not necessary that = an integer.

Accordingly, if m D n then n D m, ∀ m, n ∈Z

Hence D is not symmetric.

Transitive

Let m, n, p ∈Z and suppose m D n and n D p.

Now m D n ⇒ m|n ⇒ = an integer.

Also n D p ⇒ n|p ⇒ = an integer.

* ⎛ p ⎞ (an in⎛) n ⎞an int)

We note

t *(

⎜ ⎟

m = an i⎝ tn ⎠

⎝ m⎠

⇒ m|p and so mDp

Thus if mDn and nDp then mDp ∀ m, n, p ∈Z

Hence D is transitive.

EXERCISE:

Let A be the set of people living in the world today. A

binary relation R is defined on A as follows:

for all p, q ∈A, pRq ⇔ p has the same first name as q.

Determine whether the relation R is reflexive, symmetric and/or transitive.

SOLUTION:

a. Reflexive

Since every person has the same first name as his/her self.

Hence for all p ∈ A, pRp. Thus, R is reflexive.

b. Symmetric:

Let p, q ∈A and suppose pRq.

⇔ p has the same first name as q.

⇔ q has the same first name as p.

⇔ qRp

Thus if pRq then qRp ∀ p,q ∈A.

⇒ R is symmetric.

a. Transitive

Let p, q, s ∈A and suppose p R q and qRr.

Page 49

MTH001 Elementary Mathematics

Now pRq ⇔p has the same first name as q

and qRr ⇔ q has the same first name as r.

Consequently, p has the same first name as r.

⇔ pRr

Thus, if pRq and qRs then pRr, ∀ p, q, r ∈A.

Hence R is transitive.

EQUIVALENCE RELATION:

Let A be a non-empty set and R a binary relation on A. R is an equivalence

relation if, and only if, R is reflexive, symmetric, and transitive.

EXAMPLE:

Let A = {1, 2, 3, 4} and

R = {(1,1), (2,2), (2,4), (3,3), (4,2), (4,4)}

be a binary relation on A.

Note that R is reflexive, symmetric and transitive, hence an

equivalence

relation.

CONGRUENCES:

Let m and n be integers and d be a positive integer. The notation

m ≡ n (mod d) means that

d | (m n) {d divides m minus n}.There exists an integer k such that

(m n) = d ⋅ k

EXAMPLE:

c. Is 22 ≡ 1(mod 3)?

Is 5 ≡ +10 (mod 3)?

d. Is 7 ≡ 7 (mod 3)?

Is 14 ≡ 4 (mod 3)?

SOLUTION

a. Since 22-1 = 21 = 3×7.

Hence 3|(22-1), and so 22 ≡ 1 (mod 3)

b. Since 5 10 = - 15 = 3 × (-5),

Hence 3|((-5)-10), and so - 5 ≡ 10 (mod 3)

c. Since 7 7 = 0 = 3 × 0

Hence 3|(7-7), and so 7 ≡ 7 (mod 3)

d. Since 14 4 = 10, and 3 / 10 because 10 ≠ 3⋅ k for any integer

k. Hence 14 ≡ 4 (mod 3).

EXERCISE:

Define a relation R on the set of all integers Z as follows:

for all integers m and n, m R n ⇔ m ≡ n (mod 3)

Prove that R is an equivalence relation.

SOLUTION:

1. R is reflexive.

R is reflexive iff for all m ∈Z, m R m.

By definition of R, this means that

For all m ∈Z, m ≡ m (mod 3)

Since m m = 0 = 3 ×0.

Hence 3|(m-m), and so m ≡ m (mod 3)

⇔ mRm

⇒ R is reflexive.

2. R is symmetric.

R is symmetric iff for all m, n ∈Z

if m R n then n R m.

⇒

m≡n (mod 3)

Now mRn

⇒

3|(m-n)

⇒

m-n = 3k, for some integer k.

⇒

n m = 3(-k), -k ∈Z

Page 50

MTH001 Elementary Mathematics

⇒

3|(n-m)

⇒

n ≡ m (mod 3)

⇒

nRm

Hence R is symmetric.

1. R is transitive

R is transitive iff for all m, n, p ∈Z,

if mRn and nRp then mRp

Now mRn and nRp means m ≡ n (mod 3) and n ≡ p (mod 3)

⇒ 3|(m-n)

and

3|(n-p)

⇒ (m-n) = 3r

for some r, s ∈Z

and

(n-p) = 3s

Adding these two equations, we get,

(m n) + (n p) = 3 r + 3 s

⇒ m p = 3 (r + s),where r + s ∈Z

⇒ 3|(m p)

⇒ m ≡ p (mod 3) ⇔ m Rp

Hence R is transitive. R being reflexive, symmetric and transitive, is an

equivalence relation.

Page 51

MTH001 Elementary Mathematics

LECTURE # 10

EXERCISE:

Suppose R and S are binary relations on a set A.

a. If R and S are reflexive, is R ∩ S reflexive?

b. If R and S are symmetric, is R ∩ S symmetric?

c. If R and S are transitive, is R ∩ S transitive?

SOLUTION:

a. R ∩ S is reflexive:

Suppose R and S are reflexive.

Then by definition of reflexive relation

∀ a ∈A (a,a) ∈R and (a,a) ∈S

⇒

∀ a ∈ A (a,a) ∈ R ∩ S

(by definition of intersection)

Accordingly, R ∩ S is reflexive.

b. R ∩ S is symmetric.

Suppose R and S are symmetric.

To prove R ∩ S is symmetric we need to show that

∀ a, b ∈ A, if (a,b) ∈ R ∩ S then (b,a) ∈ R ∩ S.

Suppose (a,b) ∈ R ∩ S.

⇒ (a,b) ∈ R and (a,b) ∈ S

( by the definition of Intersection of two sets )

Since R is symmetric, therefore if (a,b) ∈ R then

(b,a) ∈ R. Similarly S is symmetric, so if (a,b) ∈ S then (b,a) ∈ S.

Thus (b,a) ∈ R and (b,a) ∈ S

⇒ (b,a) ∈ R ∩ S

(by definition of intersection)

Accordingly, R ∩ S is symmetric.

c. R∩S is transitive.

Suppose R and S are transitive.

To prove R∩S is transitive we must show that

∀ a,b,c, ∈A, if (a,b) ∈ R∩S and (b,c) ∈ R∩S

then (a,c) ∈R∩S.

Suppose (a,b) ∈R∩S and (b,c) ∈R∩S

⇒

(a,b) ∈R and (a,b) ∈S and (b,c) ∈R and (b,c) ∈S

Since R is transitive, therefore

if (a,b) ∈R and (b,c) ∈R then (a,c) ∈R.

Also S is transitive, so (a,c) ∈S

Hence we conclude that (a,c) ∈R and (a,c) ∈S

and so (a,c) ∈R∩S (by definition of intersection)

Accordingly, R∩S is transitive.

EXAMPLE:

Let A = {1,2,3,4}

and let R and S be transitive binary relations on A defined as:

R = {(1,2), (1,3), (2,2), (3,3), (4,2), (4,3)}

and

S = {(2,1), (2,4),(3,3)}

Then R ∪ S = {(1,2), (1,3), (2,1), (2,2), (2,4), (3,3), (4,2), (4,3)}

We note (1,2) and (2,1) ∈R∪S, but (1,1) ∉ R∪S

Page 52

MTH001 Elementary Mathematics

Hence R∪S is not transitive.

IRREFLEXIVE RELATION:

Let R be a binary relation on a set A. R is irreflexive iff for all a∈A,(a,a) ∉R.

That is, R is irreflexive if no element in A is related to itself by R.

REMARK:

R is not irreflexive iff there is an element a∈A such that (a,a) ∈R.

EXAMPLE:

Let A = {1,2,3,4} and define the following

relations on A:

R1 = {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)}

R2 = {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)}

R3 = {(1,2), (2,3), (3,3), (3,4)}

Then R1 is irreflexive since no element of A is related to itself in R1. i.e.

(1,1)∉ R1, (2,2) ∉ R1, (3,3) ∉ R1,(4,4) ∉ R1

R2 is not irreflexive, since all elements of A are related to themselves in R2

R3 is not irreflexive since (3,3) ∈R3. Note that R3 is not reflexive.

NOTE:

A relation may be neither reflexive nor irreflexive.

DIRECTED GRAPH OF AN IRREFLEXIVE RELATION:

Let R be an irreflexive relation on a set A. Then by

definition, no element of

A is

related to itself by R. Accordingly, there is no loop at each point of A in the

directed graph of R.

EXAMPLE:

Let A = {1,2,3}

and R = {(1,3), (2,1), (2,3), (3,2)} be represented by the

directed graph.

MATRIX REPRESENTATION OF AN IRREFLEXIVE RELATION

Let R be an irreflexive relation on a set A. Then by definition, no element of A is

related to itself by R.

Since the self related elements are represented by 1's on the main diagonal of the

matrix representation of the relation, so for irreflexive relation R, the matrix will

contain all 0's in its main diagonal.

It means that a relation is irreflexive if in its matrix representation the diagonal

elements are all zero, if one of them is not zero the we will say that the

relation is

not

irreflexive.

EXAMPLE:

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

be represented

by the matrix

1 2 3

1 ⎡0 0 1⎤

M = 2 ⎢1 0 1⎥

⎢

⎥

3 ⎢0 1 0⎥

⎣

⎦

Page 53

MTH001 Elementary Mathematics

Then R is irreflexive, since all elements in the main diagonal are 0's.

EXERCISE:

Let R be the relation on the set of integers Z

defined as:

for all a,b ∈Z, (a,b) ∈R ⇔ a > b.

Is R irreflexive?

SOLUTION:

R is irreflexive if for all a ∈Z, (a,a) ∉R.

Now by the definition of given relation R,

for all a ∈Z, (a,a) ∉R since a > a.

Hence R is irreflexive.

ANTISYMMETRIC RELATION:

Let R be a binary relation on a set A.R is anti-symmetric iff

∀a, b ∈A if (a,b) ∈R and (b,a) ∈R then a = b.

REMARK:

1. R is not anti-symmetric iff there are elements a and b in A such

that (a,b) ∈R and (b,a) ∈R but a ≠ b.

2. The properties of being symmetric and being

anti-symmetric are not negative of each other.

EXAMPLE:

Let A = {1,2,3,4} and define the following relations on A.

R1 = {(1,1),(2,2),(3,3)}

R2 = {(1,2),(2,2), (2,3), (3,4), (4,1)}

R3={(1,3),(2,2), (2,4), (3,1), (4,2)}

R4={(1,3),(2,4), (3,1), (4,3)}

R1 is anti-symmetric and symmetric .

R2 is anti-symmetric but not symmetric because (1,2) ∈ R2but (2,1) ∉ R2.

R3 is not anti-symmetric since (1,3) & (3,1) ∈ R3 but 1 ≠ 3.

Note that R3 is symmetric.

(1,3) & (3,1) ∈ R4 but 1 ≠ 3 nor

R4is neither anti-symmetric because

because (2,4) ∈ R4 but (4,2) ∉R4

symmetric

DIRECTED GRAPH OF AN ANTISYMMETRIC RELATION:

Let R be an anti-symmetric relation on a set A. Then by definition, no two distinct

elements of A are related to each other.

Accordingly, there is no pair of arrows between two distinct elements of A in the

directed graph of R.

EXAMPLE:

Let A = {1,2,3} And R be the relation defined on

A is

R ={(1,1), (1,2), (2,3), (3,1)}.Thus R is represented by the directed graph as

R is anti-symmetric, since there is no pair of arrows between two distinct points in

MATRIX REPRESENTATION OF AN ANTISYMMETRIC RELATION:

Page 54

MTH001 Elementary Mathematics

Let R be an anti-symmetric relation on a set

if (ai, aj) ∈R for i ≠ j then (ai, aj) ∉R.

A = {a1, a2, ..., an}. Then

Thus in the matrix representation of R there is a 1 in the ith row and jth column iff

the jth row and ith column contains 0 vice versa.

EXAMPLE:

Let A = {1,2,3} and a relation

R = {(1,1), (1,2), (2,3), (3,1)}on A be represented by the matrix.

1 2 3

1 ⎡1 1 0⎤

M = 2 ⎢0 0 1⎥

⎢

⎥

3 ⎢1 0 0⎥

⎣

⎦

Then R is anti-symmetric as clear by the form of matrix M

PARTIAL ORDER RELATION:

Let R be a binary relation defined on a set A. R is a partial order relation,if and

only if, R is reflexive, antisymmetric, and transitive. The set A together with a

partial ordering R is called a partially ordered set or poset.

EXAMPLE:

Let R be the set of real numbers and define the"less than or

equal to" , on R as follows:

for all real numbers x and y in R.x ≤y ⇔ x < y or x = y

Show that ≤ is a partial order relation.

SOLUTION:

≤ is reflexive

For ≤ to be reflexive means that x ≤ x for all x ∈R

But x ≤ x means that x < x or x = x and x = x is always true.

Hence under this relation every element is related to itself.

≤ is anti-symmetric.

For ≤ to be anti-symmetric means that

∀ x,y ∈R, if x ≤ y and y ≤ x, then x = y.

This follows from the definition of ≤ and the trichotomy

property, which says

that

"given any real numbers x and y, exactly one of thefollowing holds:

x < y or x = y or x > y"

≤ is transitive

For ≤ to be transitive means that

∀ x,y,z ∈R, if x≤ y and y ≤ z then x ≤ z.

This follows from the definition of ≤ and the transitive property of order of real

numbers, which says that "given any real numbers x, y and z,

if x < y and y < z then x < z"

Thus ≤ being reflexive, anti-symmetric and transitive is a partial order relation on

EXERCISE:

Let A be a non-empty set and P(A) the power set of A.

Define the "subset" relation, ⊆, as follows:

for all X,Y ∈ P(A), X ⊆ Y ⇔ ∀ x, iff x ∈X then x ∈Y.

Show that ⊆ is a partial order relation.

SOLUTION:

1. ⊆ is reflexive

Let X ∈ P(A). Since every set is a subset of itself, therefore

X ⊆ X, ∀ X ∈P(A).

Accordingly ⊆ is reflexive.

Page 55

MTH001 Elementary Mathematics

2. ⊆ is anti-symmetric

Let X, Y ∈P(A) and suppose X ⊆ Y and Y ⊆ X.Then by definition of equality of

two

sets it follows that X = Y.

Accordingly, ⊆ is anti-symmetric.

3. ⊆ is transitive

Let X, Y, Z ∈P(A) and suppose X ⊆ Y and Y ⊆ Z. Then by the transitive

property of subsets "if U ⊆ V and V ⊆ W then U ⊆ W"it follows X ⊆ Z.

Accordingly ⊆ is transitive.

EXERCISE:

Let "|" be the "divides" relation on a set A of positive

integers.

That is, for all a, b ∈A, a|b ⇔ b = k ⋅a for

some integer k.

Prove that | is a partial order relation on A.

SOLUTION:

1. "|" is reflexive. [We must show that, ∀ a ∈A, a|a]

Suppose a ∈A. Then a = 1⋅a and so a|a by definition of

divisibility.

2. "|" is anti-symmetric

[We must show that for all a, b ∈A, if a|b and b|a then a=b]

Suppose a|b and b|a

By definition of divides there are integers k1, and k2 such that

b = k1 ⋅a

a = k2 ⋅b

and

Now b = k1 ⋅a

= k1⋅(k2 ⋅ b)

(by substitution)

= (k1 ⋅k2) ⋅b

Dividing both sides by b gives

1 = k1 ⋅k2

Since a, b ∈A, where A is the set of positive integers, so the

equations

b = k1⋅a

a = k2 ⋅b

and

implies that k1 and k2 are both positive integers. Now the

equation

k1⋅k2 =1

can hold only when k1 = k2 = 1

Thus a = k2⋅b=1 ⋅b=b

i.e., a = b

3. "|" is transitive

[We must show that ∀a,b,c∈A if a|b and b|c than a|c]

Suppose a|b and b|c

By definition of divides, there are integers k1 and k2 such that

b = k1 ⋅a

c = k2 ⋅b

and

Now c = k2 ⋅b

= k2 ⋅(k1 ⋅a) (by substitution)

= (k2 ⋅k1) ⋅a (by associative law under

multiplication)

= k3 ⋅a

where k3= k2⋅k1 is an integer

⇒ a|c

by definition of divides

Thus "|" is a partial order relation on A.

EXERCISE:

Let "R" be the relation defined on the set of integers Z as follows:

for all a, b ∈Z, aRb iff b=a for some positive integer r.

Show that R is a partial order on Z.

Page 56

MTH001 Elementary Mathematics

SOLUTION:

Let a, b ∈Z and suppose aRb and bRa. Then there are positive

integers r and s such that

b = a and

a=b

Now,

a=b

r s

= (a )

by substitution

⇒ rs =1

Since r and s are positive integers, so this equation can hold if, and only if,

=1 and s = 1

and then a = bs = b = b

i.e., a = b

Thus R is anti-symmetric.

3. Let a, b, c ∈Z and suppose aRb and bRc.

Then there are positive integers r and s such that

b = a and

c=b

Now c = b

r s

= (a )

(by substitution)

=a =a

(where t = rs is also a positive integer)

Hence by definition of R, aRc. Therefore, R is transitive.

Accordingly, R is a partial order relation on Z.

Page 57

Table of Contents: