The original question at hand was:

Suppose α and β are equivalence relations on the set S. Suppose further that the relation γ is defined as follows: For x,y∈S, xγy means xαy and xβy. Prove that γ is also an equivalence relation on S.

I'm not quite sure where I should start on this, but I think it has something to do with both α and β being equivalence relations, and then proving that γ is also an equivalence relation through the use of reflexive, symmetric, and transitive properties. Any ideas?

(already answered in another thread)

The followup to this question is: Suppose, in the preceding problem, S = {1, 2, 3, 4, 5, 6}, the equivalence classes of α are {1, 2, 3} and {4, 5, 6} and the equivalence classes of β are {1, 4}, {2, 5}, and {3, 6}. What are the equivalence classes of γ?

Any ideas on this one? I have no idea how to approach this.

  • $\begingroup$ Just go through the axioms one by one. For example we have $x\gamma x$ if and only if $x \alpha x$ and $x\beta x$. But we know... $\endgroup$ – leibnewtz Nov 17 '18 at 18:53
  • $\begingroup$ Could you give an example of this? $\endgroup$ – NKP Nov 17 '18 at 19:30

For the first question, check the axioms one by one. For example (i) reflexive: Take any $x\in S$. $x\alpha x$ and $x\beta x$, thus... (continue)

For the second part, start with one element in $S$, e.g. with $1$ and then add all elements which are equivelant to $1$. If you have all of them, continue and do the same thing again. This is a valid strategy, since $S$ is finite. Make sure that you understand why an equivalence relation partitions its set into classes.

Btw, you will learn more from your problem sheets, if you don't ask for solutions online. So be strong next time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.