Definition: “A relation R on a set A is called reflexive if (a,a) ∈ R for every element a ∈ A.”
Definition: “A relation R on a set A is called symmetric if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A. A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric.”
Definition: “A relation R on a set A is called transitive if whenever (a,b)∈R and (b,c)∈R, then (a,c) ∈ R, for all a,b,c ∈ A.”
The definitions above are from the textbook “Discrete Mathematics and its Applications” by Rosen.
Table of Contents
- a)a is taller than b
- b) a and b were born on the same day
- c) a has the same first name as b
- d) a and b have a common grandparent
a)a is taller than b
A person is not taller than himself. Therefore, the relation is not reflexive.
If a is taller than b, then b is not taller than a. Therefore, the relation is not symmetric.
The relation is antisymmetric because it never shows symmetry between two different elements.
If a is taller than b, and b is taller than c, then a is taller than c. Therefore, the relation is transitive.
b) a and b were born on the same day
it is reflexive as anyone is born on the same day as himself/herself.
It is symmetric because if a person a was born on the same day than person b, then person b was born on the same day than person a.
It is not antisymmetric as two different people can be born on the same day.
It is transitive, if a was born on the same day as b, and b was born on the same day as c, then a was born on the same day as c.
c) a has the same first name as b
The relation is reflexive. Any person has the same name as him/herself.
The relation is symmetric. If person a has the same name as person b, then person b has the same name as a person a.
The relation is not antisymmetric as two different people can have the same name.
The relation is transitive. If person a has the same name as person b, and person b has the same name as person c, then person a has the same name as person c.
d) a and b have a common grandparent
It is reflexive as everyone has a common grandparent with him/herself.
It is symmetric because if person a has a common grandparent with person b, then person b has a common grandparent with person a.
It is not antisymmetric as two different people can have common grandparents.
It is not transitive. Far relatives usually don’t share common grandparents. But close relatives do. Think about you and your cousin, and your cousin and his/her cousin.
Related exercises:
- Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric, and/or transitive, where (x,y) ∈ R if and only if
- For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive.
- List the ordered pairs in the relation R from A = {0,1,2,3,4} to B = {0,1,2,3}, where (a,b) ∈ R if and only if