# Proof of commutativity and associativity for binary error pattern

• Oct 31st 2012, 12:35 PM
x3bnm
Proof of commutativity and associativity for binary error pattern
There's a math problem on page-34 of Pinter's "A Book of Abstract Algebra" book which is(Problem F):

If a word is $\displaystyle \mathbf{a} = a_1 a_2 \cdots a_n$ is sent, but a word $\displaystyle \mathbf{b} = b_1 b_2 \cdots b_n$ is received(where the $\displaystyle a_i$
and $\displaystyle b_j$ are $\displaystyle 0s$ or $\displaystyle 1s$), then the error pattern is the word $\displaystyle e = e_1 e_2 ... e_n$ where:

$\displaystyle e_i = \begin{cases} 0 & \text{ if } a_i = b_i \\ 1 & \text{ if } a_i \neq b_i \end{cases}$

With this motivation, we define an operation of adding words, as follows: If $\displaystyle \mathbf{a}$ and $\displaystyle \mathbf{b}$ are both of length
$\displaystyle 1$, we add them according to the rules

$\displaystyle 0 + 0 = 0$, $\displaystyle 1 + 1 = 0$, $\displaystyle 0 + 1 = 1$ and $\displaystyle 1 + 0 = 1$

If $\displaystyle \mathbf{a}$ and $\displaystyle \mathbf{b}$ are both of length $\displaystyle n$, we add them by adding corresponding digits. That is(let us
introduce commas for convenience),

$\displaystyle (a_1, a_2, \cdots, a_n) + (b_1, b_2, \cdots, b_n) = (a_1 + b_1, a_2 + b_2, \cdots, a_n + b_n)$

Thus the sum of $\displaystyle \mathbf{a}$ and $\displaystyle \mathbf{b}$ is the error pattern $\displaystyle \mathbf{e}$.

For example,

$\displaystyle 0010110 + 0011010 = 0001100$ and $\displaystyle 10100111 + 11110111 = 01010000$

The symbol $\displaystyle \mathbb{B}^n$ will designate the set of all the binary words of length $\displaystyle n$.

We will prove that the operation of word addition has the following properties on $\displaystyle \mathbb{B}^n$:

1. It is commutative.
2. It is associative.
3. There is an identity element for word addition.
4. Every word has an inverse under word addition.

.....

1) Show that

$\displaystyle (a_1, a_2, \cdots, a_n) + (b_1, b_2, \cdots b_n) = (b_1, b_2, \cdots, b_n) + (a_1, a_2, \cdots, a_n)$

3) Show that

\displaystyle \begin{align*}(a_1, a_2, \cdots, a_n) + [(b_1, b_2, \cdots, b_n) + (c_1, c_2, \cdots, c_n)] =& [ (a_1, a_2, \cdots, a_n) + (b_1, b_2, \cdots, b_n) ] \\ + & (c_1, c_2, \cdots, c_n) \end{align*}.

How can I prove that the commutativity and associativity holds in this case?
• Oct 31st 2012, 01:58 PM
emakarov
Re: Proof of commutativity and associativity for binary error pattern
For each digit, this is addition modulo 2. It;s a well-known fact that addition modulo n is commutative and associative.
• Oct 31st 2012, 02:36 PM
x3bnm
Re: Proof of commutativity and associativity for binary error pattern
Quote:

Originally Posted by emakarov
For each digit, this is addition modulo 2. It;s a well-known fact that addition modulo n is commutative and associative.

Thanks emakarov for help.