The Wikipedia article on Euclidean relation reads:

A transitive relation is Euclidean only if it is also symmetric. Only a symmetric Euclidean relation is transitive.

It seems to be claimed that every transitive and Euclidean relation is symmetric. However, consider the following relation, where $a$, $b$, and $c$ are distinct elements:

$R = \{\langle a, b \rangle, \langle a, c \rangle, \langle b, b \rangle, \langle b, c \rangle, \langle c, b \rangle, \langle c, c \rangle\}.$

I think $R$ is transitive and Euclidean but not symmetric, so the claim appears to be wrong to me. This version of the Wikipedia article is due to the edit done on March 8, 2016, and the version before the edit seems correct and precise.

Am I correct or mistaken?

  • 5
    $\begingroup$ It seems to me that you are right; both versions of Wiki's entry ref to Fagin, Ronald (2003), Reasoning About Knowledge, page 60, where we have : "If $\mathcal K$ is symmetric and transitive, then $\mathcal K$ is Euclidean". $\endgroup$ – Mauro ALLEGRANZA Oct 5 '16 at 11:34
  • $\begingroup$ Thank you, Mauro. I had checked that reference before I posted my question here. It is indeed straightforward to show that every symmetric and transitive relation is Euclidean, but whether every transitive and Euclidean relation is symmetric is another matter. It looks like whoever did the edit thought he was just simplifying the explanation, not realizing that he was incorrectly altering the content. I felt like reverting the article to the old version, but I didn't do so since I am not an expert and could be mistaken. So I decided to post a question here. $\endgroup$ – Usagi Oct 7 '16 at 9:26

My simpler counterexample for "Is a transitive and Euclidean relation necessarily symmetric?" is {⟨a,b⟩⟨b,b⟩}. So, no.

Euclidian relation is right Euclidian and left Euclidian relation, as I learnt. Wiki isn't agree with me. I guess, the right form is here. Or, maybe, they meant "If it's Euclidian and reflexive it's an equivalence."


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.