0
$\begingroup$

I'm considering a set $ G = \{0,1\}$ under addition modulo 2. I.e. $$ a*b = a + b\bmod 2, \quad \quad \forall \ a,b \in G. $$ I am able to show that there exists an identity element, $0$.

Showing that $*$ is assosiative and that there exists an inverse, is more difficult to me.

Can someone help me to show this?

$\endgroup$
  • 2
    $\begingroup$ Concerning inverse, compute $a\ast a$. What is the inverse of $a$ ? $\endgroup$ – Dietrich Burde Jan 7 '15 at 21:41
1
$\begingroup$

Showing that the identity $e \in G$ exists means showing $a= a\star e = e \star a$ for all $a \in G$, and as you correctly pointed out $e = 0$. Next I would prove every element has an identity, since you only have one non-identity element left in $G$ to consider. By definition, $$1 \star 1 = 1+1\bmod 2 \\ = 2\bmod 2 \\ = 0$$ So $1$ is its own identity (making it an idempotent element, if that matters much to you). Now for associativity, let $a,b,c \in G$ and consider $a \star b \star c$. Since you have three elements $(a,b,c)$ that can be valued as either $1$ or $0$, you could run through by hand all $2^3=8$ possible operations of the form $a\star b \star c$ and show $(a \star b) \star c = a \star (b \star c)$ in all eight cases. Otherwise you can take the more general approach and try: $$(a \star b) \star c = (a+b\bmod 2) \star c \\ = (a+b\bmod 2)+c\bmod 2$$ compared to $$a \star (b \star c) = a\star (b+c\bmod 2) \\ = a+ (b+c\bmod 2)\bmod 2$$ Now can you show that $$(a+b\bmod 2)+c\bmod 2 = a+ (b+c\bmod 2)\bmod 2$$ ?

$\endgroup$
1
$\begingroup$

Since $G=\{0,1\}$, you have just eight identities to check for associativity:

$$ 0*(0*0)=(0*0)*0\\ 0*(0*1)=(0*0)*1\\ 0*(1*0)=(0*1)*0\\ 0*(1*1)=(0*1)*1\\ 1*(0*0)=(1*0)*0\\ 1*(0*1)=(1*0)*1\\ 1*(1*0)=(1*1)*0\\ 1*(1*1)=(1*1)*1 $$

The inverse of $0$ is of course $0$. What can the inverse of $1$ be? Is it?

$\endgroup$
  • $\begingroup$ Also, the operation is commutative, so you need to check only half of the cases. $\endgroup$ – sas Jan 7 '15 at 22:37
  • $\begingroup$ @sas Not really. $\endgroup$ – egreg Jan 7 '15 at 22:39
  • $\begingroup$ In your list you need check cases number $2, 4, 5, 7$. $\endgroup$ – sas Jan 7 '15 at 22:41
  • $\begingroup$ @sas Choosing the ones to check takes longer than the complete check. But in more complex cases it can help. $\endgroup$ – egreg Jan 7 '15 at 22:42
0
$\begingroup$

For all $a,b \in G$
$$(a*0)*b=a*b,\quad a*(0*b)=a*b$$
and
$$(a*1)*b=(1-a)*b=1-a+b \bmod 2 = \begin{cases} 1, \quad\text{if}\quad a=b \\ 0,\quad\text{if}\quad a\neq b \end{cases}$$
$$a*(1*b)=a*(1-b)=a+1-b \bmod 2 = \begin{cases} 1, \quad\text{if}\quad a=b \\ 0,\quad\text{if}\quad a\neq b \end{cases}$$

So, for all $a,b,c\in G$ it is true that $$(a*c)*b=a*(c*b).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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