• Definition: Let R be a binary relation on A.
• R is reflexive if for all x ∈ A, (x,x) ∈ R.
(Equivalently, for all x e A, x R x.)
• R is symmetric if for all x,y ∈ A, (x,y) ∈ R
implies (y,x) ∈ R. (Equivalently, for all x,y ∈ A,
x R y implies that y R x.)
• R is transitive if for all x,y,z ∈ A, (x,y) ∈ R and
(y,z) ∈ R implies (x,z) ∈ R. (Equivalently, for all
x,y,z ∈ A, x R y and y R z implies x R z.)10.2.2
Examples
• Reflexive: The relation R on {1,2,3} given by
R = {(1,1), (2,2), (2,3), (3,3)} is reflexive. (All
loops are present.)
• Symmetric: The relation R on {1,2,3} given by
R = {(1,1), (1,2), (2,1), (1,3), (3,1)} is symmetric.
(All paths are 2-way.)
• Transitive: The relation R on {1,2,3} given by
R = {(1,1), (1,2), (2,1), (2,2), (2,3), (1,3)} is
transitive. (If I can get from one point to another
in 2 steps, then I can get there in 1 step.)10.2.3
Violations of the Properties
• Why is R = {(1,1), (2,2), (3,3)} not reflexive on
{1,2,3,4}?
Because (4,4) is missing.
• Why is R = {(1,2), (2,1), (3,1)} not symmetric?
Because (1,3) is missing.
• Why is R = {(1,2), (2,3), (1,3), (2,1)} not
transitive?
Because (1,1) and (2,2) are missing.
• Is {(1,1), (2,2), (3,3)} symmetric? transitive?
Yes! Yes!10.2.4
The Transitive Closure
• Definition: Let R be a binary relation on a set A.
The transitive closure of R is the binary relation
R t on A satisfying the following three properties:
1. R t is transitive;
2. R is a subset of R t ;
3. If S is any other transitive relation that
contains R, then S contains R t .
• In other words, the transitive closure of R is the
smallest transitive relation containing R.10.2.5
Example of the Transitive Closure
• Given the relation R on {1,2,3,4},
1 2
4 3
its transitive closure is:
1 2
4 310.2.6
Properties of Equality
• Consider the Equality (=) relation on R:
Equality is reflexive since for each x ∈ R, x = x.
Equality is symmetric since for each x,y ∈ R, if
x = y, then y = x.
Equality is transitive since for each x,y,z ∈ R, if
x = y and y = z, then x = z.
• As a graph, the relation contains only loops, so
symmetry and transitivity are vacuously satisfied!10.2.7
Properties of Congruence Mod p
• Let p be an integer greater than 1, and consider
the relation on Z given by:
R = {(x,y) | x,y ∈ Z and x ≡ y mod p}.
• When we say x ≡ y mod p, this means (x − y) = kp
for some integer k.
• Now, R is reflexive since (x − x) = 0 = 0p, for all
integers x.
• Moreover, R is symmetric, since if x ≡ y mod p,
then (x − y) = kp, thus (y − x) = (−k)p, implying
that y ≡ x mod p.10.2.8
Congruence Mod p (cont’d.)
• Finally, R is transitive. Why?
• Let x ≡ y mod p and y ≡ z mod p. This means
there are integers k and j such that (x − y) = kp
and (y − z) = jp. Hence, (x − z) = (x − y) + (y − z)
= kp + jp = (k + j)p. Therefore, x ≡ z mod p.10.2.9
Properties of Inequality
• Consider the Inequality (< or >) relation on R:
Inequality is not reflexive since for no x ∈ R is it
true that x < x.
Inequality is not symmetric since for each
x,y ∈ R, if x < y is true, then y < x is false.
Inequality is transitive since for each x,y,z ∈ R, if
x < y and y < z, then x < z.
• Inequality is so pathelogically unsymmetric, that
we define a special property to describe it.10.2.10
The Anti-symmetry Property
• Definition: A relation R on a set A is called anti-
symmetric if (x,y) ∈ R and (y,x) ∈ R implies x = y.
• This is equivalent to requiring that if x ≠ y and
(x,y) ∈ R, then (y,x) ∉ R. (All streets are one-
way.)
• Example: R = {(1,1), (1,2), (3,2), (3,3)} is anti-
symmetric.
• Is every relation symmetric or anti-symmetric?
• No! Consider R = {(1,2), (2,1), (1,3)}.