0
$\begingroup$

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?

  • 0
    [Max and Min are Associative](http://www.proofwiki.org/wiki/Max_and_Min_are_Associative) - ProofWiki2012-10-28

1 Answers 1

1

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$.

  • 0
    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$.2012-10-28