1
$\begingroup$

Find total number of relations that are equivalence as well as partial order set. Assume set contains total $n$ elements.


My attempt:

As equivalence relation has property reflexive, symmetric and transitive and POSET has property reflexive, antisymmetric and transitive.

Symmetric and antisymmetric will cancle each other except reflexive relation and transitive relation can case antisymmetric, so it's also absent on resultant relation.

Therefore, all diagonal element should be present to satisfy conditions of equivalence as well as POSET.

So, it's independent of number of total number of element of set and answer will be $1$.

Can you explain in formal way, please?

$\endgroup$
2
$\begingroup$

I will denote $\sim$ such a relation.

If $a\sim b$, then $b\sim a$ (symmetry), and then $a=b$ (antisymmetry).

The order is partial, but each time you can compare two elements with each other, they must be the same.

So the only element you can compare with $a$ (for any $a$) is $a$ itself.

Therefor there is only one such relation, which is trivial:

$$\forall a,b\quad a\sim b \iff a=b.$$

$\endgroup$
  • $\begingroup$ Thanks for nice explanation. $\endgroup$ – 1 0 May 28 '16 at 13:47
1
$\begingroup$

We want to find the total number of relations on an $n$ element set which are both equivalence relations and partial orders. Suppose the Hasse diagram of a poset contains two distinct elements $a$ and $b$, with element $a$ below $b$ and joined to $b$ (so that $a \le b$ in the poset). Then $(a,b)$ is in the relation but $(b,a)$ cannot be in the relation since a partial order is antisymmetric. An equivalence relation requires that if $(a,b)$ is in the relation then $(b,a)$ is also in the relation. Thus, any chain containing two elements of a poset violates a property of the equivalence relation. It follows that the only partial order which is also an equivalence relation is one where all chains are of length 1, which is the diagonal relation. Hence, the number of relations in question is 1.

$\endgroup$
  • $\begingroup$ Thanks for nice explanation. $\endgroup$ – 1 0 May 29 '16 at 6:16

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.