# How to prove associativity

I have been given set $M=\{0,1,2,3\}$ and a binary operation $a\circ b=\max\{a,b\}$. I need to prove that this set is a monoid. So In order to prove that I need to prove that $M$ is associative under that operation. How am I supposed to prove it? Is it fine if I take $3$ elements and just prove that it works for that set, or do I need to prove for each possible element selection?

-
Max and Min are Associative - ProofWiki –  Martin Sleziak Oct 28 '12 at 13:54

You need to prove $$\max\{a,\max\{b,c\}\}=\max\{\max\{a,b\},c\}$$ it for all choices of $a,b,c\in M$ (including duplicates). Before you actually test all 64 choices, note that it only matters whether $a\ge b\ge c$ or $a\ge c\ge b$ or $b\ge a\ge c$ or $b\ge c\ge a$ or $c\ge a\ge b$ or $c\ge b\ge a$.
Indeed, the statement is about all choices. However, you can reduce the amount of work, by reducing the number of cases by valid arguments. Hagen showed, how one could argue that 6 cases are enough. Then, for example, in case $b \geq a \geq c$ you get that $\max(a,\max(b,c)) = \max(a,b) = \max(\max(a,b), c)$ just by the definition of the maximum and the assumption on $a, b, c$. –  cubic lettuce Oct 28 '12 at 15:06