# The equivalence relation is defined on a set of 9 elements and is negatively transitive relation. How many equivalence classes can be there?

I looked for answers a lot but mostly used the Bell number, which we haven't studied. And I have no idea how to do it with negatively transitive relations..

(Edit) Negatively transitive relation, according to our lecturer:

R is negatively transitive if and only if:

∀x,y,z∈S:¬(xRy)∧¬(yRz)⟹¬(xRz)

By De Morgan's Laws, this can be given the alternative form:

∀x,y,z∈S:(xRz)⟹(xRy)∨(yRz)

(Also a note that we don't study this in English, so there might be some mistakes in the explanation, I'm sorry for this)

I tried to count all possible relations for 9 elements first, which was 2^18, and then tried to find the partitions of a set (the equivalence relations on the set). For 9 elements was hard, but for 3 elements it was:

First possible partition: {{a},{b},{c}}:3 classes, each class with 1 element.

2 nd possible partition: {{a,b},{c}}2 classes, one with elements a,b and the other with c .

Similarly we see three other possible partitions: {{a},{b,c}},{{a,c},{b}} , and {{a,b,c}} .

And the answer was 5 equivalent relations.

• Please edit the question to tell us what "negatively transitive" means, and what you have tried. Can you solve the problem for sets with fewer elements? (Don't respond in a comment.) Commented Dec 14, 2023 at 22:19
• You seem to be counting how many equivalence relations you can have satisfying the given properties, but you also quoted the question as asking how many equivalence classes there are, which would be a question about a specific equivalence relation, something entirely different. Commented Dec 14, 2023 at 22:37
• Oh, yes, it is. I was stuck after counting equivalence relations and couldn't continue from that on.. thank you for pointing it out.
– Dal
Commented Dec 14, 2023 at 22:41

You counted the equivalence relations (which correspond to partitions) but you never took into account the "negatively transitive" property.

For example, consider the equivalence relation corresponding to the partition $$\{\{a,b\},\{c\}\}$$. This is not "negatively transitive": because we have $$aRb$$, so therefore by the definition of negatively transitive, we must have either $$aRc$$ or $$cRb$$, but we have neither.

In fact, if $$R$$ is an equivalence relation that is also "negatively transitive", then it must be the total relation (everything is related to everything)!

Why?

Well, let $$a$$ and $$b$$ be any elements of the set. Because $$R$$ is reflexive, we know that $$aRa$$ holds. Since $$R$$ is negatively transitive, we have $$aRa\implies aRb \vee bRa.$$ But because $$R$$ is symmetric, $$bRa\implies aRb$$ anyway. Therefore, we conclude that $$aRb$$ holds.

Since $$a$$ and $$b$$ were arbitrary elements, it follows that $$R$$ is the total relation.

That means that there is exactly one equivalence class.