Reflexivity, Symmetry, and Transitivity
Reflexivity, Symmetry, and Transitivity
Let
A
= {2, 3, 4, 6, 7, 9} and define a relation R
on
A
as
follows: For all
x
,
y
A
,
Then
2
R
2 because 2 – 2 = 0, and 3 | 0.
and similarly
3
R
3, 4
R
4, 6
R
6, 7
R
7, and 9
R
9.
Also
6
R
3 because 6 – 3 = 3, and 3 | 3.
3
R
6 because 3 – 6 = –(6 – 3) = –3, and 3 | (–3).
Similarly, 3
R
9, 9
R
3, 6
R
9, 9
R
6, 4
R
7, and 7
R
4.
Reflexivity, Symmetry, and Transitivity
Thus the directed graph for
R
has
the appearance shown at the right.
This graph has three important
properties:
1. Each point of the graph has an arrow looping around
from it back to itself.
2. In each case where there is an arrow going from one
point to a second, there is an arrow going from the
second point back to the first.
Reflexivity, Symmetry, and Transitivity
3. In each case where there is an arrow going from one
point to a second and from the second point to a third,
there is an arrow going from the first point to the third.
Properties (1), (2), and (3) correspond to properties of
general relations called
reflexivity
,
symmetry
, and
transitivity
.
Reflexivity, Symmetry, and Transitivity
Because of the equivalence of the expressions
x
R
y
and
(
x
,
y
)
R
for all
x
and
y
in
A
, the reflexive, symmetric, and
transitive properties can also be written as follows:
Reflexivity, Symmetry, and Transitivity
In informal terms, properties (1)–(3) say the following:
1
.
R
e
f
l
e
x
i
v
e
:
E
a
c
h
e
l
e
m
e
n
t
i
s
r
e
l
a
t
e
d
t
o
i
t
s
e
l
f
.
2
.
S
y
m
m
e
t
r
i
c
:
I
f
a
n
y
o
n
e
e
l
e
m
e
n
t
i
s
r
e
l
a
t
e
d
t
o
a
n
y
o
t
h
e
r
e
l
e
m
e
n
t
,
t
h
e
n
t
h
e
s
e
c
o
n
d
e
l
e
m
e
n
t
i
s
r
e
l
a
t
e
d
t
o
t
h
e
f
i
r
s
t
.
3
.
T
r
a
n
s
i
t
i
v
e
:
I
f
a
n
y
o
n
e
e
l
e
m
e
n
t
i
s
r
e
l
a
t
e
d
t
o
a
s
e
c
o
n
d
a
n
d
t
h
a
t
s
e
c
o
n
d
e
l
e
m
e
n
t
i
s
r
e
l
a
t
e
d
t
o
a
t
h
i
r
d
,
t
h
e
n
t
h
e
f
i
r
s
t
e
l
e
m
e
n
t
i
s
r
e
l
a
t
e
d
t
o
t
h
e
t
h
i
r
d
.
Note that the definitions of reflexivity, symmetry, and
transitivity are universal statements.
Reflexivity, Symmetry, and Transitivity
This means that to prove a relation has one of the
properties, you use either the method of exhaustion or the
method of generalizing from the generic particular.
Now consider what it means for a relation
not
to have one
of the properties defined previously. We have known that
the negation of a universal statement is existential.
Hence if
R
is a relation on a set
A
, then
1
.
R
i
s
n
o
t
r
e
f
l
e
x
i
v
e
⇔
t
h
e
r
e
i
s
a
n
e
l
e
m
e
n
t
x
i
n
A
s
u
c
h
t
h
a
t
[
t
h
a
t
i
s
,
s
u
c
h
t
h
a
t
(
x
,
x
)
R
]
.
Reflexivity, Symmetry, and Transitivity
2
.
R
i
s
n
o
t
s
y
m
m
e
t
r
i
c
⇔
t
h
e
r
e
a
r
e
e
l
e
m
e
n
t
s
x
a
n
d
y
i
n
A
s
u
c
h
t
h
a
t
x
R
y
b
u
t
[
t
h
a
t
i
s
,
s
u
c
h
t
h
a
t
(
x
,
y
)
R
b
u
t
(
y
,
x
)
R
]
.
3
.
R
i
s
n
o
t
t
r
a
n
s
i
t
i
v
e
⇔
t
h
e
r
e
a
r
e
e
l
e
m
e
n
t
s
x
,
y
a
n
d
z
i
n
A
s
u
c
h
t
h
a
t
x
R
y
a
n
d
y
R
z
b
u
t
[
t
h
a
t
i
s
,
s
u
c
h
t
h
a
t
(
x
,
y
)
R
a
n
d
(
y
,
z
)
R
b
u
t
(
x
,
z
)
R
]
.
It follows that you can show that a relation does
not
have
one of the properties by finding a counterexample.
Example 1 –
Properties of Relations on Finite Sets
Let
A
= {0, 1, 2, 3} and define relation R
on
A
as follows:
R
= {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)},Is
R
reflexive? symmetric? transitive?
Solution:
The directed graph of
R
is
Reflexive?
Yes
Symmetric?
Yes
Transitive?
No
Example 1 –
Properties of Relations on Finite Sets
Let
A
= {0, 1, 2, 3} and define relation S
on
A
as follows:
S
= {(0, 0), (0, 2), (0, 3), (2, 3)}Is
S
reflexive? symmetric? transitive?
Solution:
The directed graph of
S
is
Reflexive?
No
Symmetric?
No
Transitive?
Yes
Example 1 –
Properties of Relations on Finite Sets
Let
A
= {0, 1, 2, 3} and define relation T
on
A
as follows:
T
= {(0, 1), (2, 3)}Is
T
reflexive? symmetric? transitive?
Solution:
The directed graph of
T
is
Reflexive?
No
Symmetric?
No
Transitive?
Yes (vacuously)
Properties of Relations on Infinite Sets
Suppose a relation
R
is defined on an infinite set
A
. To
prove the relation is reflexive, symmetric, or transitive, first
write down what is to be proved. For instance, for
symmetry you need to prove that
x
,
y
A
, if
x R y
then
y R x
.
Then use the definitions of
A
and
R
to rewrite the statement
for the particular case in question. For instance, for the
“equality” relation on the set of real numbers, the rewritten
statement is
x
,
y
R
, if
x
=
y
then
y
=
x
.
Example 2 –
Properties of Equality
D
e
f
i
n
e
a
r
e
l
a
t
i
o
n
R
o
n
R
(
t
h
e
s
e
t
o
f
a
l
l
r
e
a
l
n
u
m
b
e
r
s
)
a
s
f
o
l
l
o
w
s
:
F
o
r
a
l
l
r
e
a
l
n
u
m
b
e
r
s
x
a
n
d
y
.
Is
R
reflexive? symmetric? transitive?
Reflexive?
Yes
Symmetric?
Yes
Transitive?
Yes
Example 4 –
Properties of Congruence Modulo 3
D
e
f
i
n
e
a
r
e
l
a
t
i
o
n
T
o
n
Z
(
t
h
e
s
e
t
o
f
a
l
l
i
n
t
e
g
e
r
s
)
a
s
f
o
l
l
o
w
s
:
F
o
r
a
l
l
i
n
t
e
g
e
r
s
m
a
n
d
n
,
T
h
i
s
r
e
l
a
t
i
o
n
i
s
c
a
l
l
e
d
c
o
n
g
r
u
e
n
c
e
m
o
d
u
l
o
3
.
Is
T
reflexive?
S
o
l
u
t
i
o
n
:
T
i
s
r
e
f
l
e
x
i
v
e
i
f
a
n
d
o
n
l
y
i
f
m
T
m
f
o
r
a
n
y
m
i
n
Z
.
B
u
t
m
–
m
=
0
a
n
d
3
|
0
s
i
n
c
e
3
0
=
0
.
T
h
a
t
i
s
,
m
T
m
a
n
d
s
o
T
i
s
r
e
f
l
e
x
i
v
e
.
Example 4 –
Properties of Congruence Modulo 3
D
e
f
i
n
e
a
r
e
l
a
t
i
o
n
T
o
n
Z
(
t
h
e
s
e
t
o
f
a
l
l
i
n
t
e
g
e
r
s
)
a
s
f
o
l
l
o
w
s
:
F
o
r
a
l
l
i
n
t
e
g
e
r
s
m
a
n
d
n
,
T
h
i
s
r
e
l
a
t
i
o
n
i
s
c
a
l
l
e
d
c
o
n
g
r
u
e
n
c
e
m
o
d
u
l
o
3
.
Is
T
symmetric?
S
o
l
u
t
i
o
n
:
T
o
s
h
o
w
t
h
a
t
T
i
s
s
y
m
m
e
t
r
i
c
,
w
e
n
e
e
d
t
o
s
h
o
w
t
h
a
t
f
o
r
a
l
l
m
,
n
Z
,
i
f
m
T
n
t
h
e
n
n
T
m
.
Suppose
m
and
n
are particular but arbitrarily chosen
integers such that 3 | (
m
–
n
).
Example 4(b) –
Solution
By definition of “divides,” since
3 | (
m
–
n
),
then
m
–
n
= 3
k
for some integer
k
–(
m
–
n
)
= –3
k
n
–
m
= 3(–
k
)
Since –
k
is an integer, this equation shows that
3 | (
n
–
m
).
It follows that
T
is symmetric.
cont’d
Example 4 –
Properties of Congruence Modulo 3
D
e
f
i
n
e
a
r
e
l
a
t
i
o
n
T
o
n
Z
(
t
h
e
s
e
t
o
f
a
l
l
i
n
t
e
g
e
r
s
)
a
s
f
o
l
l
o
w
s
:
F
o
r
a
l
l
i
n
t
e
g
e
r
s
m
a
n
d
n
,
T
h
i
s
r
e
l
a
t
i
o
n
i
s
c
a
l
l
e
d
c
o
n
g
r
u
e
n
c
e
m
o
d
u
l
o
3
.
Is
T
transitive?
S
o
l
u
t
i
o
n
:
T
o
s
h
o
w
t
h
a
t
T
i
s
t
r
a
n
s
i
t
i
v
e
,
w
e
n
e
e
d
t
o
s
h
o
w
t
h
a
t
f
o
r
a
l
l
m
,
n
,
p
Z
,
i
f
m
T
n
a
n
d
n
T
p
t
h
e
n
m
T
p
.
Example 4(c) –
Solution
By definition of “divides,” since
3 | (
m
–
n
) and 3 | (
n
–
p
),
then
m
–
n
= 3
r
for some integer
r
,
and
n
–
p
= 3
s
for some integer
s
.
Add these two equations together to obtain
(
m
–
n
) + (
n
–
p
) = 3
r
+ 3
s
,
which is equivalent to
m
–
p
= 3(
r
+
s
). Since
r
and
s
are
integers,
r
+
s
is an integer. So this equation shows that
3 | (
m
–
p
).
It follows that
T
is transitive.
cont’d
The Transitive Closure of a Relation
The transitive closure of a relation is the smallest transitive
relation that contains the relation.
Example 5 –
Transitive Closure of a Relation
Let
A
= {0, 1, 2, 3} and consider the relation R
defined on
A
as follows:
R
= {(0, 1), (1, 2), (2, 3)}.Find the transitive closure of
R
.
Solution:
Every ordered pair in
R
is in
R
t
, so
{(0, 1), (1, 2), (2, 3)} ⊆
R
t
.
Thus the directed graph of
R
contains
the arrows shown at the right.
Example 5 –
Solution
Since there are arrows going from 0 to 1 and from 1 to 2,
R
t
must have an arrow going from 0 to 2.
Hence (0, 2)
R
t
. Then (0, 2)
R
t
and (2, 3)
R
t
, so
since
R
t
is transitive, (0, 3)
R
t
.
Also, since (1, 2)
R
t
and (2, 3)
R
t
, then (1, 3)
R
t
.
Thus
R
t
contains at least the following ordered pairs:
{(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}.But this relation is transitive; hence it
equals
R
t
. Note that the directed graph
of
R
t
is as shown at the right.
cont’d
A relation R defined on a set A showcases properties of reflexivity, symmetry, and transitivity using a directed graph representation. These properties define how elements relate to themselves and each other, forming foundational principles in mathematics and logic. Understanding these concepts is crucial in analyzing relationships between elements within a set.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Reflexivity, Symmetry, and Transitivity Let A = {2, 3, 4, 6, 7, 9} and define a relation R on A as follows: For all x, y A, Then 2 R 2 because 2 2 = 0, and 3 | 0. and similarly 3 R 3, 4 R 4, 6 R 6, 7 R 7, and 9 R 9. Also 6 R 3 because 6 3 = 3, and 3 | 3. 3 R 6 because 3 6 = (6 3) = 3, and 3 | ( 3). Similarly, 3 R 9, 9 R 3, 6 R 9, 9 R 6, 4 R 7, and 7 R 4. 1
Reflexivity, Symmetry, and Transitivity Thus the directed graph for R has the appearance shown at the right. This graph has three important properties: 1. Each point of the graph has an arrow looping around from it back to itself. 2. In each case where there is an arrow going from one point to a second, there is an arrow going from the second point back to the first. 2
Reflexivity, Symmetry, and Transitivity 3. In each case where there is an arrow going from one point to a second and from the second point to a third, there is an arrow going from the first point to the third. Properties (1), (2), and (3) correspond to properties of general relations called reflexivity, symmetry, and transitivity. 3
Reflexivity, Symmetry, and Transitivity Because of the equivalence of the expressions x R y and (x, y) R for all x and y in A, the reflexive, symmetric, and transitive properties can also be written as follows: 4
Reflexivity, Symmetry, and Transitivity In informal terms, properties (1) (3) say the following: 1. Reflexive: Each element is related to itself. 2. Symmetric: If any one element is related to any other element, then the second element is related to the first. 3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third. Note that the definitions of reflexivity, symmetry, and transitivity are universal statements. 5
Reflexivity, Symmetry, and Transitivity This means that to prove a relation has one of the properties, you use either the method of exhaustion or the method of generalizing from the generic particular. Now consider what it means for a relation not to have one of the properties defined previously. We have known that the negation of a universal statement is existential. Hence if R is a relation on a set A, then 1. R is not reflexive there is an element x in A such that [that is, such that (x, x) R]. 6
Reflexivity, Symmetry, and Transitivity 2. R is not symmetric there are elements x and y in A such that x R y but [that is, such that (x, y) R but (y, x) R]. 3. R is not transitive there are elements x, y and z in A such that x R y and y R z but [that is, such that (x, y) R and (y, z) R but (x, z) R]. It follows that you can show that a relation does not have one of the properties by finding a counterexample. 7
Example 1 Properties of Relations on Finite Sets Let A = {0, 1, 2, 3} and define relation R on A as follows: R = {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)}, Is R reflexive? symmetric? transitive? Solution: The directed graph of R is Reflexive? Yes Symmetric? Yes No Transitive? 8
Example 1 Properties of Relations on Finite Sets Let A = {0, 1, 2, 3} and define relation S on A as follows: S = {(0, 0), (0, 2), (0, 3), (2, 3)} Is S reflexive? symmetric? transitive? Solution: The directed graph of S is Reflexive? No Symmetric? No Yes Transitive? 9
Example 1 Properties of Relations on Finite Sets Let A = {0, 1, 2, 3} and define relation T on A as follows: T = {(0, 1), (2, 3)} Is T reflexive? symmetric? transitive? Solution: The directed graph of T is Reflexive? No Symmetric? No Yes (vacuously) Transitive? 10
Properties of Relations on Infinite Sets Suppose a relation R is defined on an infinite set A. To prove the relation is reflexive, symmetric, or transitive, first write down what is to be proved. For instance, for symmetry you need to prove that x, y A, if x R y then y R x. Then use the definitions of A and R to rewrite the statement for the particular case in question. For instance, for the equality relation on the set of real numbers, the rewritten statement is x, y R, if x = y then y = x. 11
Example 2 Properties of Equality Define a relation R on R (the set of all real numbers) as follows: For all real numbers x and y. Is R reflexive? symmetric? transitive? Reflexive? Yes Symmetric? Yes Yes Transitive? 12
Example 4 Properties of Congruence Modulo 3 Define a relation T on Z (the set of all integers) as follows: For all integers m and n, This relation is called congruence modulo 3. Is T reflexive? Solution: T is reflexive if and only if m T m for any m in Z. But m m = 0 and 3 | 0 since 3 0 = 0. That is, m T m and so T is reflexive. 13
Example 4 Properties of Congruence Modulo 3 Define a relation T on Z (the set of all integers) as follows: For all integers m and n, This relation is called congruence modulo 3. Is T symmetric? Solution: To show that T is symmetric, we need to show that for all m, n Z, if m T n then n T m. Suppose m and n are particular but arbitrarily chosen integers such that 3 | (m n). 14
Example 4(b) Solution cont d By definition of divides, since 3 | (m n), then m n (m n) = 3k n m = 3k for some integer k = 3( k) Since k is an integer, this equation shows that 3 | (n m). It follows that T is symmetric. 15
Example 4 Properties of Congruence Modulo 3 Define a relation T on Z (the set of all integers) as follows: For all integers m and n, This relation is called congruence modulo 3. Is T transitive? Solution: To show that T is transitive, we need to show that for all m, n, p Z, if m T n and n T p then m T p. 16
Example 4(c) Solution cont d By definition of divides, since 3 | (m n) and 3 | (n p), then m n = 3r for some integer r, and n p = 3s for some integer s. Add these two equations together to obtain (m n) + (n p) = 3r + 3s, which is equivalent to m p = 3(r + s). Since r and s are integers, r + s is an integer. So this equation shows that 3 | (m p). It follows that T is transitive. 17
The Transitive Closure of a Relation The transitive closure of a relation is the smallest transitive relation that contains the relation. 18
Example 5 Transitive Closure of a Relation Let A = {0, 1, 2, 3} and consider the relation R defined on A as follows: R = {(0, 1), (1, 2), (2, 3)}. Find the transitive closure of R. Solution: Every ordered pair in R is in Rt, so {(0, 1), (1, 2), (2, 3)} Rt. Thus the directed graph of R contains the arrows shown at the right. 19
Example 5 Solution cont d Since there are arrows going from 0 to 1 and from 1 to 2, Rt must have an arrow going from 0 to 2. Hence (0, 2) Rt. Then (0, 2) Rt and (2, 3) Rt, so since Rt is transitive, (0, 3) Rt. Also, since (1, 2) Rt and (2, 3) Rt, then (1, 3) Rt. Thus Rt contains at least the following ordered pairs: {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}. But this relation is transitive; hence it equals Rt. Note that the directed graph of Rt is as shown at the right. 20
