# equivalence relations and partial ordering

Let $A$ be a set with $6$ elements, $R$ be a relation on $A$ and $n = |\{(x, y) \in A \times A : xRy\}|$.
(a) If $R$ is an equivalence relation on $A$, then what is the maximum value of $n$?
(b) If $R$ is a partial ordering on $A$, then what is the minimum value of $n$?

-
Welcome to math.SE! Please share your thoughts on the problem, and explain what you've tried and what's giving you difficult. This will help responders to give help at an appropriate level and not just repeat material you already know. Also, many find it rude when a question is phrased as a command, so please consider editing. – user61527 Aug 27 '13 at 11:02

Hint: (a) Prove that $xRy \;\forall x,y\in A$ is an equivalence relation. (b) Prove that $xRy \Leftrightarrow x=y$ is a partial ordering.

-

Let $S=\left\{\left(x,y\right)\in A\times A \mid xRy\right\}$.

1) It is obvious that $S\subseteq A\times A$ and the relation for which $\forall x,y\in A, xRy$ is an equivalence relation so since $X\subseteq Y \implies \left|X\right|\le\left|Y\right|$, the maximum value of $n$ is $\left|A\times A\right|=\left|A\right|^2$.

2) Since you need reflexivity, you have $\forall x\in A, xRx$ so $\left\{(x,x)\mid x \in A\right\}\subseteq S$. And you can check easily that the axioms of a partial order are satisfied by the relation so that $\forall x,y \in A, xRy\iff x=y$. So you can take $S=\left\{(x,x)\mid x \in A\right\}$ and you therefore get $\left|\left\{(x,x)\mid x \in A\right\}\right|=\left|A\right|$ as minimum value for $n$.

-