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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Max and Min are Associative - ProofWiki $\endgroup$– Martin SleziakOct 28, 2012 at 13:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
answered Oct 28, 2012 at 12:37
-
$\begingroup$ So you are saying that I need to prove for all choices? You mean I have to write all of them? $\endgroup$– FazlanOct 28, 2012 at 12:45
-
$\begingroup$ 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$. $\endgroup$ Oct 28, 2012 at 15:06