Q:

Proving that if $\bar{R}$ transitive (where $R$ equivalence relation), $|A/R|=1$

Let $A\neq\emptyset$ a set and $R\subseteq A\times A$ equivalence relation s.t the complementary relation $\bar{R}=(A\times A)\setminus R$ is transitive. Prove that $|A/R|=1$ (cardinality of quotient set is 1).

There has to be a contradiction if the cardinality is bigger then 1 but I haven't found it yet. I'll be glad for any hint. 

A:

Hint: Let $a$ and $b$ be different elements of $A/_R$. Then $a\overline{R}b$ and $b\overline{R}a$.

A:

If I am not mistaken, the quotient set is the set of equivalence classes under $R$.  Thus the assumption $\vert A / R \vert =1$ means there is exactly one such class, i.e. any two elements $a, b \in A$ satisfy $(a, b) \in R$.  So that's what we need to prove.  Now, I will write $aRb$ for $(a, b) \in R$ from here on out.  Suppose then that there are more than one class.  Then there exists $c \in A$ such that $aRc$ is false.  Thus $(a, c) \in \bar R$, or $a \bar{R} c$.  I claim that we then have $c \bar{R} a$ as well.  For if not, then $cRa$, and by the symmetry of $R$, $aRc$, a contradiction.  So now the transitivity of $\bar R$ implies both $a \bar{R}a$ and $c \bar{R} c$, contradicting the reflexitivity of $R$, I.e. that $xRx$ for all $x \in A$.  Thus there is but one equivalence class under $R$.  QED.

