On 2012 Putnam Problem A2

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 $S$ be a set with a binary operation $\ast$ that is commutative and associative. Suppose that, for every $x$ and $y$ in $S$, there exists $z$ in $S$ such that $x \ast z = y$. (This $z$ may depend on $x$ and $y$.) Show that, if $a,b,c$ are in $S$ and $a \ast c = b \ast c$, then $a = b$.

Don’t read anything below Nyan Cat if you don’t want to see the solution.

Initial remarks

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 $x$ and $y$, there exists $z$ such that $x \ast z = y$). And you’re asked to prove that the “cancellation law” holds: if $a \ast c = b \ast c$, then $a = b$. 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 $S$ is a group. We already know that $\ast$ is well-defined and associative, so we need to prove the existence of an identity and inverses.

Solution

Pick any element $x$. The transitivity property implies that there exists an element $e$ such that $x \ast e = x$. We need to be careful with this equation, since, as far as we know, $e$ might depend on $x$. However, for any $y$ there is a $z$ such that $x \ast z = y$, so

$y \ast e = (x \ast z) \ast e = (x \ast e) \ast z = x \ast z = y$,

so $e$ really is an identity element. [Note: there can’t be more than one identity, so it turns out that $e$ doesn’t depend on $x$ after all.]

The existence of inverses directly follows from the transitivity property: For every $c$, there is an element (which we’ll call $c^{-1}$ such that $c \ast c^{-1} = e$. This concludes the proof that $S$ is a group, and the cancellation law will therefore hold:  if $a \ast c = b \ast c$, then we can multiply both sides of the equation by $c^{-1}$ to get $a = b$.

QED

Closing remarks

As I said, there may be a slightly more direct approach that avoids completely proving that $S$ 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 $\diamond$ that simply “takes the term on the right”, so that $x \diamond y = y$ for all $x$ and $y$. 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?