This post continues my effort to write solutions to the problems on this year’s Putnam competition. I previously posted a solution to problem A1. Problem A2 seems like it should have been reasonable for students familiar with abstract algebra, but it could have been tricky for students without much exposure to axiomatic theories.
My (slight) rephrasing of the question is as follows: Let be a set with a binary operation that is commutative and associative. Suppose that, for every and in , there exists in such that . (This may depend on and .) Show that, if are in and , then .
Don’t read anything below Nyan Cat if you don’t want to see the solution.
This is like when you start learning group theory and you have some axioms, and you try to prove things using those axioms. In this case, there are three given axioms: commutativity, associativity, and what I’ll call “transitivity” (for every and , there exists such that ). And you’re asked to prove that the “cancellation law” holds: if , then . It’s an exercise in being very careful that every step of your proof is justified, either by the axioms themselves or by results you have already established.
There may be a more direct approach, but it turns out that in this case, you can actually prove that is a group. We already know that is well-defined and associative, so we need to prove the existence of an identity and inverses.
Pick any element . The transitivity property implies that there exists an element such that . We need to be careful with this equation, since, as far as we know, might depend on . However, for any there is a such that , so
so really is an identity element. [Note: there can’t be more than one identity, so it turns out that doesn’t depend on after all.]
The existence of inverses directly follows from the transitivity property: For every , there is an element (which we’ll call such that . This concludes the proof that is a group, and the cancellation law will therefore hold: if , then we can multiply both sides of the equation by to get .
As I said, there may be a slightly more direct approach that avoids completely proving that is a group, but the observation that it is actually a group seems to be important and probably explains why the problem was considered “interesting enough” to be on the exam.
I’ll point out that, even though group operations aren’t required to be commutative, the commutativity axiom was crucial for this problem. Consider a set with an operation that simply “takes the term on the right”, so that for all and . This is a perfectly good associative operation, and it satisfies the transitivity property. But (as long as the set has more than one element) you won’t have a group.
Can you pinpoint where commutativity was used in the above solution?