0

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?

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
Fazlan
  • 297

1 Answers1

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

Hagen von Eitzen
  • 374,180
  • So you are saying that I need to prove for all choices? You mean I have to write all of them? – Fazlan Oct 28 '12 at 12:45
  • 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