Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?
Explain your answers.

share|improve this question
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. –  T. Bongers Aug 27 '13 at 11:02

2 Answers 2

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.

share|improve this answer

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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.