b and c please! 1 Let X be a set. A binary relation ~ is called an equivalence r

Question

b and c please!

1 Let X be a set. A binary relation ~ is called an equivalence relation if: i) r~T; ll) x ~ y implies y~ i1) x ~ y and y~ Z limpliesT~. A function f with domain X is called a representing function for ~ if x ~ y exactly when f(x) = f(y) a) Let n 1 be an integer. Find a representing function when x ~ y iff x-y is a multiple of n. b) Show that every equivalence relation has a representing function. c) Suppose X has n elements. Consider two methods for storing an equivalence relation on a computer: a) a 0-1 array indicating, for each pair, whether the relation holds between them or not; b) a succinct tabulation of the representing function. Which uses less space?

Explanation / Answer

a) f(x) = x mod n

This can also be written as,

f(x) = x % n where % is remainder.

b) Every equivalence relationship creates a partition on a set X. This Parition PX will contain sets of form S, where for x, y elements of S, x ~ y. Now we define representative functions in such a way that for every x in S, f(x) has same value.

To summarize, representative function can be defined based on parition created on Set, where for every parition, value taken by elements within a parition are same.

As an example, when x - y = n, a representative function is f(x) = x % n such that f(x) = f(y)

(c) (a)(0, 1) array will mean, for a given set containing N elements, space requirement for array will be of order N^2. As equivalence relation ship is symmetric, we can consider only those pairs (i, j) for which i <=j. This will lead to N^2/2 pairs at the minimum.

(b) An another approach will be a Tabulation scheme. Where we can partition all elements where each partition will contain elements having equivalence relationship. A simplified approach will be labelling elements in such a way that elements within a parition have same label, while elements in different paritions have different label.

So consider an array of 10 elements = { 1, 11, 23, 4, 78, 9, 5, 89, 90, 119}

Assume they have an equivalence relationship, admitting following parition:

{{1, 4, 78}, {11}, {23, 9, 5, 119}, {89, 90}}

We can label elements of each partition with same value, as such:

{1, 4, 78} -> 'A'

{11} -> 'B'

{23, 9, 5, 119} -> 'C'

{89, 90} -> 'D'

This will need extra space of 2*n, n for each element and n for values taken by each element. Here space requirement is much less than 0-1 array which would have taken 3*n^2/2 space ( for every pair space of 2, and 1 corresponding to 0-1).

Hence tabulation takes less space.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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