0
$\begingroup$

Is this a true statement for binary relations defines an equivalence relation on S:

S is the set of all n-digit binary sequences. We say that two binary sequences are in a relation if and only if they have the same number of 1s.

$\endgroup$
3
  • $\begingroup$ As equality is an equivalence, this seems pretty obvious, don't you think? $\endgroup$
    – Bernard
    Commented Oct 21, 2015 at 18:34
  • $\begingroup$ Is there a proof or a theorem or something to go with this? $\endgroup$
    – Micky
    Commented Oct 21, 2015 at 18:35
  • $\begingroup$ You just have to say that, if $s$ and $t$ are $n$-digit binary sequences, if $x$ has the same number of $1$s as $t$, the $t$ has the same number of $1$s as $s$, for instance. It's really obvious, unless I didn't understand well what's your relation. $\endgroup$
    – Bernard
    Commented Oct 21, 2015 at 18:50

1 Answer 1

0
$\begingroup$

If $f:S\to X$ is some function then the relation $\sim$ on $S$ prescribed by: $$s\sim s'\iff f(s)=f(s')$$ is an equivalence relation. This simply because for all $s,t,r\in S$:

  • $f(s)=f(s)$ (reflexivity)
  • $f(s)=f(t)\implies f(t)=f(s)$ (symmetry)
  • $f(s)=f(t)\wedge f(t)=f(r)\implies f(s)=f(r)$ (transitivity)

In your question let $f$ be the function that sends each sequence to its number of $1$'s.

$\endgroup$
2
  • $\begingroup$ I see thank you very much! $\endgroup$
    – Micky
    Commented Oct 21, 2015 at 19:16
  • $\begingroup$ You are welcome. $\endgroup$
    – drhab
    Commented Oct 21, 2015 at 19:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .