Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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. – 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.

share|cite|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|cite|improve this answer

Your Answer


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