Does the relation aRb if (a+b) is not divisible by 4 has transitive property?

79 Views Asked by At

I recently encounter an programming problem in which I was to make subsets of set 'S' as following - { a + b should not be divisibe by 'k' where 'a' and 'b' are elements of S }

Of course I could just brute force through it and get an answer but I got interested in the fact that is this property transitive i.e. if a+b is not divisible by 'k' and if a+c is not divisible by 'k' then b+c is also not divisible by 'k'. I could neither prove it not find an counter-example.

Extra question - this relation is definately not reflective, but would these subsets still make equivalance classes? why or why not?

Edit - thank you for your answers. Even though it seems like a rather dumb question in hindsight, I appreciate your answers.

4

There are 4 best solutions below

0
On BEST ANSWER

Lack of reflexiveness already makes it not an equivalence relation, so they can't be equivalence classes. But note also that $1+2$ is not divisible by $4$, $2+3$ is not divisible by $4$, but $1+3$ is divisible by $4$, so transitivity fails as well.

0
On

In general this relation is not transitive, but it depends on the set $S$. There are trivial sets for which this is true, like

$S=\{1\}$ or $S=\{1,5\}$

0
On

Counter-example :-

Let k = 4, a = 8, b = 6 and c = 10

0
On

"Sum not divisible by $4$" is not an equivalence relation, because it is not reflexive nor transitive. Here is a counterexample to transitivity: $1+2$ is not divisible by $4$ and $2+3$ isn't but $1+3$ is. Therefore this relation does not divide $S$ into equivalence classes.