Prove that $\star=min(a,b+2)$ is associative

Question

Prove that $\star=min(a,b+2)$ is associative. I have written program, which says its associative for $1,2,3$. However I wanted to solve this on paper. I have given a try, but not sure if the approach is correct.

$\star$ is associative iff:

$a\star(b\star c)==(a\star b)\star c$ , that is

$min(a,min(b,c+2)+2)==min(min(a,b+2),c+2)$

• Case 1: Assume $a<b<(c+2)$
  $\rightarrow b\star c=b$
  $\rightarrow a\star b=a$
  $\rightarrow a\star(b\star c)=a$
  $\rightarrow a\star b=a$
  $\rightarrow a\star c=a$
  $\rightarrow (a\star b)\star c=a$

• Case 2: Assume $a<(c+2)<b$
  $\rightarrow b\star c=(c+2)$
  $\rightarrow a\star (c+2)=a$
  $\rightarrow a\star(b\star c)=a$
  $\rightarrow a\star b=a$
  $\rightarrow a\star c=a$
  $\rightarrow (a\star b)\star c=a$

• Case 3.1: Assume $(c+2)<(c+4)<a<b$
  $\rightarrow b\star c=(c+2)$
  $\rightarrow a\star (c+2)=(c+4)$?
  $\rightarrow a\star(b\star c)=(c+4)$
  $\rightarrow a\star b=a$
  $\rightarrow a\star c=(c+2)$
  $\rightarrow (a\star b)\star c=(c+2)$
  So this is the case where it fails to be associative, right?

Am going right with this approach? Or such problems involve different approach indeed simpler, smaller non exhaustive one? And is this operation indeed non-associative?

Answer 1

Note $$ \min\{\min\{a,b+2\},c+2\}=\min\{a,b+2,c+2\} $$ whereas $$ \min\{a,\min\{b,c+2\}+2\}=\min\{a,\min\{b+2,c+4\}\}=\min\{a,b+2,c+4\}. $$ So associativity fails, for example, when $c+4<a,b+2$.

Answer 2

So $c = 0, a= 5, b =6$ would be a concrete example of your last case.

In that case $a \star b = 5 \star 6 = 5$ and $b \star c = 5 \star 0 = 2$

So $(a \star b) \star c = 5 \star 0 = 2$ while $a \star (b \star c) = 5 \star 2 = 4$ so indeed associativity fails.

Your program could have confirmed this too.

If an operation isn't "obviously" associative it probably is not (e.g. for matrix multiplication it's obvious once you know it's just composition of maps) and you can go looking for a counterexample, that a program could find, e.g.

The case distinctions quickly find the pain points here.