# Show that $c = \max(a, b)$ on $\mathbb{Z}_2$ is not a binary operation

Let $*: \mathbb{Z}_2\times\mathbb{Z}_2 \to \mathbb{Z}_2$, be defined as $[a] * [b] = [c]$, where $c = \max\{a, b\}$, for all $[a], [b] \in \mathbb{Z}_2$. Prove that $*$ is not a binary operation on $\mathbb{Z}_2$. Hint: is it well defined?

--

I don't want someone to solve the problem for me, but just help clear up my misunderstanding or point me in the right direction.

I don't see how $*$ is not a binary operation, nor how it isn't well defined.

A binary operation is a function on a set $S$ that associates every ordered pair of elements in $S$ to another element of $S$.

Here, $*$ associated ordered pairs of elements $\mathbb{Z}_2$ to another element $\mathbb{Z}_2$, through the max function. It has four possible inputs:

\begin{align} (0, 0) & \mapsto 0 \\ (0, 1) & \mapsto 1 \\ (1, 0) & \mapsto 1 \\ (1, 1) & \mapsto 1 \end{align}

So it associates every unique input to one output, and meets the definition of a function. Every possible input returns an output that is in $S$ ($\mathbb{Z}_2$).

How is it not well-defined?

-

The definition of $[a]\ast[b]$ is defined using representatives of the congruence classes $[a],[b]$. In order for it to be well-defined, it must work the same on all pairs of representatives of $[a]$ and $[b]$. For instance, it must satisfy $[0]\ast[1]=[2]\ast[1]$ since $[0]=[2]$.

-
But there are only two congruence classes, $[0]$. and $[1]$. So when we call max(2,1), wouldn't that just get reduced to max(0,1), since we are operating in $\mathbb{Z}_2$? – Samuel Sep 7 '13 at 21:57
@Samuel You have to be careful about the domain of definition of $\max$; it is a function $\mathbb Z\times\mathbb Z\to\mathbb Z$. It does not care whether we are trying to use it to define a function on congruence classes. In other words, $\max(3,4)=4$ regardless of whether $[3]=[1]$ and $[4]=[0]$. – Karl Kronenfeld Sep 7 '13 at 22:15
@KarlKronenfield Thank you for the help. So, the reason * is not a binary op-n is an example of the importance of the preciseness of mathematics. If we had defined some other function that took two congruence classes and returned the 'maximum', then * would be a binary operation. But because max operates on integers, rather than congruence classes, that allows for situations to arise in which equivalent congruence classes have different maximums. Is all that correct? – Samuel Sep 7 '13 at 22:22
@Samuel That is exactly correct. It just goes to show how nice it is that addition and multiplication actually do work on congruence classes. – Karl Kronenfeld Sep 7 '13 at 22:23
@KarlKronenfield Actually, I'm back to being confused again. [a] * [b] = [c], where c = max(a,b). So when we do [2] * [1] = [c], c = max(2,1) = 2, so [2] * [1] = [2], and [2] = [0]. [2] and [0] are the same congruence class. So I don't see how [2] * [1] and [0] * [1] aren't mapping to the same place. They both map to the same congruence class. – Samuel Sep 7 '13 at 22:35

Note that $[1]=[3]$. But whe have $[2]*[1]=[\max\{2,1\}]=[2]=[0]$, but $[2]*[3]=[\max\{2,3\}]=[3]=[1]$, so if you operate $[2]$ with $[1]$, and $[2]$ with $[3]$, you get two different elements, so this operation is not well defined.

-
So the problem is that max(a,b) takes two integers, rather than the representative congruence classes? – Samuel Sep 7 '13 at 21:53
Yes, for the operation to be well defined one must require that it doesn't depend on the representative of a congruence class. – user93658 Sep 7 '13 at 21:57