Let’s start by reviewing the relevant definitions needed to solve this type of exercise.
Definition: “Let A and B be sets. A binary relation from A to B is a subset of A × B.”
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.
Now, we need to use the definitions above to decide whether each of the relations below is reflexive, symmetric, antisymmetric, and/or transitive.
A common mistake students make is to find 1 pair that holds the definition and classify the relation accordingly. Please notice that the definitions clearly state “for all” pairs. It is not enough to find 1 pair. I’ll come back to this in each example.
Also, the easiest way to decide on a specific property is to find a counterexample. If you cannot find it, then probably the relation has a specific property, but you still have to prove it.
Table of Contents
- a) {(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)}
- b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
- c) {(2, 4), (4, 2)}
- d) {(1, 2), (2, 3), (3, 4)}
- e) {(1, 1), (2, 2), (3, 3), (4, 4)}
- f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
a) {(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)}
Let’s start by deciding if the relation is reflexive. According to the definition (a, a) ∈ R for every element a ∈ A.
A= {1, 2, 3, 4}
(4,4) does not belong to this relation. Therefore, is not reflexive.
Notice that even though (2,2) and (3,3) belong to the relation, we cannot say that the relation is reflexive because according to the definition, all pairs (a, a) must belong to the relation for us to classify it as reflexive.
Symmetric: (2,4) belongs to the relation, but (4,2) does not belong to the relation. Therefore, the relation is not symmetric.
Antisymmetric: (2,3) and (3,2) belong to the relation, but 2≠3. Therefore, the relation is not antisymmetric.
Transitive: (2,3) and (3,2) belong to the relation, and also (2,2) belongs to the relation.
Because there are no two pairs such that (a,b)∈R and (b,c)∈R, and (a,c) ∉R, we can conclude that this relation is transitive.
b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
A= {1, 2, 3, 4}
Reflexive: All the pairs of the form (a,a) belong to the relation – (1,1), (2,2), (3,3), and (4,4) -. Therefore, the relation is reflexive.
Symmetric: For all pairs (a,b) that belong to the relation, (b,a) also belong to the relation. Therefore, the relation is symmetric.
Antisymmetric: (1,2) and (2,1) belong to the relation but 1≠2. Therefore, the relation is not antisymmetric.
Transitive: (1,2) and (2,1) belong to the relation, and also (1,1) belongs to the relation. Because there are no two pairs such that (a,b)∈R and (b,c)∈R, and (a,c) ∉R, we can conclude that this relation is transitive.
c) {(2, 4), (4, 2)}
A= {1, 2, 3, 4}
Notice that I always write again the set that is part of the relation definition. This is important because, in some cases, we need to check all the elements of that set. Therefore, we need to have clarity on what elements are in that specific set.
Reflexive: (1,1) does not belong to the relation. Therefore, the relation is not reflexive.
Symmetric: (2,4) and (4,2) belong to the relation and there are no other pairs. Therefore, the relation is symmetric. Notice again that the definition state that for all pair (a,b) that belong to the relation, (b,a) also must belong to the relation.
Antisymmetric: (2,4) and (4,2) belong to the relation, but 2≠4. Therefore, the relation is not antisymmetric.
Transitive: (2,4) and (4,2) belong to the relation, but (2,2) does not belong to the relation. Therefore, this relation is not transitive.
d) {(1, 2), (2, 3), (3, 4)}
Reflexive: (1, 1) does not belong to the relation. Therefore, the relation is not reflexive.
Symmetric: (2,3) belongs to the relation, but (3,2) does not belong to the relation. Therefore, this relation is not symmetric.
Definition: “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.”
Antisymmetric: If you follow the definition above, you can see that it applies to this case. Therefore, the relation is antisymmetric. You could think about this as a trivial proof. In a conditional p->q, if you know that p is false, then p->q is true.
Transitive: (1,2) and (2,3) belong to the relation, but (1,3) does not belong to the relation. Therefore, this relation is not transitive.
e) {(1, 1), (2, 2), (3, 3), (4, 4)}
This relation is reflexive, symmetric, antisymmetric, and transitive.
f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
Reflexive: (1,1) does not belong to the relation. Therefore, the relation is not reflexive.
Symmetric: (1,4) belongs to the relation but (4,1) does not belong to the relation. Therefore, the relation is not symmetric.
Antisymmetric: (1,3) and (3,1) belong to the relation, but 1≠3. Therefore, the relation is not antisymmetric.
Transitive: (2,3) and (3,1) belong to the relation, but (2,1) does not belong to the relation. Therefore, this relation is not transitive.
Related exercises:
- Determine whether the relation R on the set of all people is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)∈R if and only if
- 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
- 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
