0
$\begingroup$

I am trying to show that if $|A| = m$ and $0\neq n \le m $ then exists equivalence relation $r$ in set $A$ such that $ |A \setminus r| = n$. Could someone help me deal with it?

$\endgroup$
  • 1
    $\begingroup$ Can't you just arbitrarily glue points together? $\endgroup$ – Klaus Jan 21 at 1:15
  • $\begingroup$ I don't understand, could you explain it? $\endgroup$ – René Accardo Jan 21 at 1:18
  • 1
    $\begingroup$ Draw your $m$ points on a sheet of paper. Now draw lines between the points until there are exactly $n$ connected components. This defines an equivalence relation. $\endgroup$ – Klaus Jan 21 at 1:21
  • $\begingroup$ Is it reflexive? $\endgroup$ – René Accardo Jan 21 at 1:33
  • 1
    $\begingroup$ Added some details as an answer. $\endgroup$ – Klaus Jan 21 at 1:48
4
$\begingroup$

Without loss of generality let $A = \{1, \ldots, m\}$. Choose $A_1 = \{1\}$, $A_2 = \{2\}$, ..., $A_{n-1} = \{n-1\}$, $A_n = \{n, \ldots, m\}$. This defines a partition of $A$ and hence and equivalence relation.

$\endgroup$
  • 2
    $\begingroup$ Correct, so +1. But I prefer your "draw a picture" comment. It's just as correct and much easier to read and understand. $\endgroup$ – Ethan Bolker Jan 21 at 1:52
  • $\begingroup$ I agree, but OP wanted a more formal answer. $\endgroup$ – Klaus Jan 21 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.