See below the relevant definitions that we need to know 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 answer the exercise.
To prove that a relation is an equivalence relation, we need to prove that the relation is reflexive, symmetric, and transitive (see definition of equivalence relation above).
R{(S,T)| |S|=|T|}
Reflexive: Every set has the same cardinality as itself. Therefore, this relation is reflexive.
Symmetric: If S has the same cardinality as T, then T has the same cardinality as S. Therefore, this relation is symmetric.
Transitive: If S has the same cardinality as T, and T has the same cardinality as R, then S has the same cardinality as R. Therefore, this relation is transitive.
The relation R is an equivalence relation because is reflexive, symmetric, and transitive.
What are the equivalence classes of the sets {0, 1, 2} and Z?
Let S={0,1,2},
[S]R={T, where |T|=3}
[Z]R={T, where |T|=|Z|}
Related posts:
- Suppose that A is a nonempty set and R is an equivalence relation on A. Show that there is a function f with A as its domain such that (x,y) ∈ R if and only if f(x) = f(y)
- Define three equivalence relations on the set of students in your discrete mathematics class different from the relations discussed in the text. Determine the equivalence classes for each of these equivalence relations
- Define three equivalence relations on the set of classes offered at your school. Determine the equivalence classes for each of these equivalence relations
- Define three equivalence relations on the set of buildings on a college campus. Determine the equivalence classes for each of these equivalence relations.
- Which of these relations on the set of all functions from Z to Z are equivalence relations? Determine the properties of an equivalence relation that the others lack
