Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Max and Min are Associative - ProofWiki –  Martin Sleziak Oct 28 '12 at 13:54
add comment

1 Answer

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.