Answer to Question #148109 in Discrete Mathematics for Promise Omiponle

Question

Let S be a finite non-empty set. How many relations on S are simultaneously an equivalence relation and a partial order? Justify your answer.

Answer 1

Let $R\subset S\times S$ be a relation that is simultaneously an equivalence relation and a partial order, that is $R$ is reflexive, transitive, symmetric and antisymmetric. Since $R$ is reflexive, $(x,x)\in R$ for any $x\in S.$ Let $(x,y)\in R$. Since $R$ is symmetric, we conclude that $(y,x)\in R$. Taking into account that $R$ is antisymmetric and $(x,y)\in R, \ (y,x)\in R$ , we conclude that $y=x.$ Therefore, $R=\{(x,x)\ |\ x\in S\}$ is the unique relation.

Answer: 1