# 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 $\mathbf{a} = a_1 a_2 \cdots a_n$ is sent, but a word $\mathbf{b} = b_1 b_2 \cdots b_n$ is received(where the $a_i$
and $b_j$ are $0s$ or $1s$), then the error pattern is the word $e = e_1 e_2 ... e_n$ where:

$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 $\mathbf{a}$ and $\mathbf{b}$ are both of length
$1$, we add them according to the rules

$0 + 0 = 0$, $1 + 1 = 0$, $0 + 1 = 1$ and $1 + 0 = 1$

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

$(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 $\mathbf{a}$ and $\mathbf{b}$ is the error pattern $\mathbf{e}$.

For example,

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

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

We will prove that the operation of word addition has the following properties on $\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

$(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

\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.