Let A = {1,2,3} and B = {4,5}, and let S = BA be the set of all functions from {

Question

Let A = {1,2,3} and B = {4,5}, and let S = BA be the set of all functions from {1,2,3} to {4,5}. Define a relation ? on S as follows: for f,g ? S, we define f ? g to mean that f(A) ? g(A) (in words, the images of f and g are in bijection). (a) Prove that ? is an equivalence relation. (b) Write down the equivalence classes of this equivalence relation. (Hints: In order to represent the equivalence classes neatly, remember that a function can be represented as a set of ordered pairs. To help check your answer, you may wish to compute #S.)

Explanation / Answer

An equivalence relation is a binary relation ~ satisfying three properties: For every element a in X, a ~ a (reflexivity), For every two elements a and b in X, if a ~ b, then b ~ a (symmetry) For every three elements a, b, and c in X, if a ~ b and b ~ c, then a ~ c (transitivity). The equivalence class of an element a is denoted [a] and may be defined as the set of elements that are related to a by ~. The alternative notation [a]R can be used to denote the equivalence class of the element a specifically with respect to the equivalence relation R. This is said to be the R-equivalence class of a. The set of all equivalence classes in X given an equivalence relation ~ is denoted as X/~ and called the quotient set of X by ~. Each equivalence relation has a canonical projection map that maps each element to its equivalence class, the surjective function p from X to X/~ given by p(x) = [x]. [edit]Analogy with division This operation can be thought of (very informally) as the act of dividing the input set by the equivalence relation, hence both the name "quotient", and the notation, which are both reminiscent of division. One way in which the quotient set resembles division is that if X is finite and the equivalence classes are all equinumerous, then the number of equivalence classes in X/~ can be calculated by dividing the number of elements in X by the number of elements in each equivalence class. The quotient set X/~ may be thought of as the set X with all the equivalent points identified. [edit]Examples If X is the set of all cars, and ~ is the equivalence relation "has the same color as", then one particular equivalence class consists of all green cars. X/~ could be naturally identified with the set of all car colors (cardinality of X/~ would be the number of all car colors) Consider the modulo 2 equivalence relation on the set Z of integers: x ~ y if and only if their difference x - y is an even number. This relation gives rise to exactly two equivalence classes: one class consisting of all even numbers, and the other consisting of all odd numbers. Under this relation [7], [9], and [1] all represent the same element of Z/~. Let X be the set of ordered pairs of integers (a,b) with b not zero, and define an equivalence relation ~ on X according to which (a,b) ~ (c,d) if and only if ad = bc. Then the equivalence class of the pair (a,b) can be identified with the rational number a/b, and this equivalence relation and its equivalence classes can be used to give a formal definition of the set of rational numbers. The same construction can be generalized to the field of fractions of any integral domain. [edit]Properties Every element x of X is a member of the equivalence class [x]. Every two equivalence classes [x] and [y] are either equal or disjoint. Therefore, the set of all equivalence classes of X forms a partition of X: every element of X belongs to one and only one equivalence class. Conversely every partition of X comes from an equivalence relation in this way, according to which x ~ y if and only if x and y belong to the same set of the partition. It follows from the properties of an equivalence relation that x ~ y if and only if [x] = [y]. In other words, if ~ is an equivalence relation on a set X, and x and y are two elements of X, then these statements are equivalent: .

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.