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.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
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
1  
@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.

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

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.