Let $R_1, R_2 ∈ R(X)$ be equivalence relations on $X$.

Define $R_1$ and $R_2$ to be isomorphic if there exists a bijection $f : X → X$ such that the following holds: For all $y, z ∈ X : (y, z) ∈ R_1$ if and only if $(f(y), f(z)) ∈ R_2$

(a) Define what is means for two partitions $P_1, P_2 ∈ P(X)$ to be isomorphic. (An answer to this is correct if it lets you prove the next part.)

(b) Prove two equivalence relations $R_1$ and $R_2$ are isomorphic if and only if the partitions $φ(R_1)$ and $φ(R_2)$ are isomorphic. (Here φ is the bijection from the previous problem.)

(c) Let X = {1, 2, 3, 4, 5}. Up to isomorphism, how many equivalence relations are there on X?

My main issue is that I do not understand what an isomorphic partition is. Only when I understand this can I begin to even answer part (b) or (c).

NOTE: I do not get why this post was downvoted when all I asked for is direction to be able to solve this question and even commented on what I understand so far.

  • $\begingroup$ Every equivalence relation determines a partition (and vice versa). You have to use the equivalence relation to define the partition, and use the same idea to define what it means for partitions to be isomorphic. $\endgroup$ – user458276 Dec 14 '18 at 6:21
  • $\begingroup$ Yes, but what does it mean for partitions to be isomorphic? $\endgroup$ – childishsadbino Dec 14 '18 at 6:24
  • 1
    $\begingroup$ Also, when they say $(y,z)$ is in $R_1$, does it mean they are in the same equivalence class, which in turn implies that $f(x), f(y)$ are in the same equivalence class in $R_2$? So, assuming that to be true, for partitions to be isomorphic, they would take elements from a fixed subset of $P_1$ only to a fixed unique set of $P_2$, right? $\endgroup$ – childishsadbino Dec 14 '18 at 6:30
  • 1
    $\begingroup$ Wait, is it that the number of subsets in partitions are equal? $\endgroup$ – childishsadbino Dec 14 '18 at 6:53
  • $\begingroup$ Well, finding the definition is exactly what point (a) is about; and it even gives you a way to check your answer by doing point (b). $\endgroup$ – Arnaud D. Dec 14 '18 at 16:07

When P is a partition, the partition part containing
a, a/P = { x : exists A in P with x,a in A }.

Two partitions P,Q are isomorphic when
exists bijection f:X -> X with for all x,y in X,
x/P = y/P iff f(x)/Q = f(y)/Q.


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.