4
$\begingroup$

Can a relation be a partial order AND an equivalence at the same time? For instance, if we have a set $A = \{1, 2, 3, 4, 5\}$ and a relation $R$ on $A$ defined as $R = \{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)\}$: this relation is reflexive, anti-symmetric, symmetric, and would it be considered transitive as well? If it is considered transitive, I suppose that it is an equivalence and a partial order at the same time.

$\endgroup$
  • $\begingroup$ Yes it can be. Your example is correct. $\endgroup$ – Anurag A Oct 19 '14 at 16:22
  • $\begingroup$ Simpler is $\varnothing$. $\endgroup$ – Git Gud Oct 19 '14 at 16:39
3
$\begingroup$

Two remarks:

(1) Equality is an equivalence relation which is also a partial order ($\leq$).

(2) An equivalence relation is never a strict partial order ($<$).

$\endgroup$
  • $\begingroup$ I don't think the equivalence relation on a set of size $1$ is a strict partial order either... $\endgroup$ – Nishant Oct 19 '14 at 16:30
  • $\begingroup$ Thanks, You are right. I edited. $\endgroup$ – arithmetic Oct 19 '14 at 16:31
  • $\begingroup$ What do you mean, that every equivalence relation is a partial order? For instance, on a set B = {0, 1, 2}, the relation R = {(0, 1), (1, 0), (0, 0), (1, 1), (2, 2), (2, 1), (1, 2), (2, 0), (0, 2)} is an equivalence relation, because it is reflexive, symmetric and transitive, but it is not a partial order, because it is not anti-symmetric, I think. $\endgroup$ – ProfessorMoriarty Oct 19 '14 at 16:37
  • $\begingroup$ Sorry, I was thinking of quasi-orders. I have edited. $\endgroup$ – arithmetic Oct 19 '14 at 16:40
  • $\begingroup$ Thanks for editing, I was getting confused. $\endgroup$ – ProfessorMoriarty Oct 19 '14 at 16:44
2
$\begingroup$

Yes, but it must be exactly like the one you propoes, that is all the equivalence classes must be of size one.

For if we had an equivalence class with at least two elements a,b we would $(a,b),(b,a)\in R$

so it would not satisfy antisymmetry

$\endgroup$

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.