1

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}} .

(Source: How many different equivalent relations can you define on set of three elements?)

And the answer was 5 equivalent relations.

Dal
  • 11
  • 4
    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.) – Ethan Bolker Dec 14 '23 at 22:19
  • 1
    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. – Arturo Magidin Dec 14 '23 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 Dec 14 '23 at 22:41

1 Answers1

0

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.

Arturo Magidin
  • 398,050