Let’s start with the relevant definitions that will help us to solve this exercise.
Definition: “A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.”
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.”
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.
Let’s solve the exercises.
Table of Contents
- a) {(a,b) | a and b are the same age}
- b) {(a, b) | a and b have the same parents}
- c) {(a,b)|a and b share a common parent}
- d) {(a,b) | a and b have met}
- e) {(a,b)|a and b speak a common language}
a) {(a,b) | a and b are the same age}
Reflexive: a person has the same age as himself. Therefore, the relation is reflexive.
Symmetric: if person a has the same age as b, then person b has the same age as a. Therefore, the relation is symmetric.
Transitive: if a and b have the same age, and b and c have the same age, then a and c have the same age. Therefore, it is transitive.
It is an equivalence relation because it is reflexive, symmetric, and transitive.
b) {(a, b) | a and b have the same parents}
Reflexive: a person has the same parents as himself. Therefore, it is reflexive.
Symmetric: If a has the same parents as b, then b has the same parents as a. Therefore, it is symmetric.
Transitive: If a has the same parents as b, and b has the same parents as c, then a has the same parents as c. Therefore, is transitive.
It is an equivalence relation because it is reflexive, symmetric, and transitive.
c) {(a,b)|a and b share a common parent}
Reflexive: a shares a common parent with himself. So, it is reflexive.
Symmetric: If a shares a common parent with b, then b also shares a common parent with a. Therefore, the relation is symmetric.
Transitive: a share the father with b, and b share the mother with c. a don’t share a common parent with c. Therefore, the relation is not transitive.
It is not an equivalence relation because is not transitive.
d) {(a,b) | a and b have met}
Reflexive: a met with himself. Therefore, it is reflexive.
Symmetric: if a met with b, then b met with a. Therefore, it is symmetric.
Transitive: if a met with b, and b met with c, doesn’t mean that a met with c. Therefore, it is not transitive.
It is not an equivalence relation because is not transitive.
e) {(a,b)|a and b speak a common language}
Reflexive: a speak the same language as himself. Therefore, it is reflexive.
Symmetric: if a speaks a common language with b, then b also speaks a common language with a. Therefore, it is symmetric.
Transitive: a speaks Spanish, b speaks Spanish and English, and c speaks English. a and c don’t speak a common language. Therefore, it is not transitive.
It is not an equivalence relation because is not transitive.
Related exercises:
- Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) ∈ R if and only if a + d = b + c. Show that R is an equivalence relation
- Suppose that A is a nonempty set, and f is a function that has A as its domain. Let R be the relation on A consisting of all ordered pairs (x, y) such that f (x) = f (y)
- Show that the relation of logical equivalence on the set of all compound propositions is an equivalence relation. What are the equivalence classes of F and of T?
- Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack.