# [SOLVED] Binary Operations

• May 10th 2010, 01:47 PM
dwsmith
[SOLVED] Binary Operations
Suppose that two binary operations, denoted by $\displaystyle \oplus$ and $\displaystyle \odot$, are defined on a nonempty set S, and that the following conditions are satisfied $\displaystyle \forall x,y,z\in S$.

(1) $\displaystyle x\oplus y$ and $\displaystyle x\odot y$ are in S
(2) $\displaystyle x\oplus (y\oplus z)=(x\oplus y) \oplus z$ and $\displaystyle x\odot (y\odot z)=(x\odot y) \odot z$
(3) $\displaystyle x\oplus y=y\oplus x$

Also, $\displaystyle \forall x\in S$ and $\displaystyle \forall n\in \mathbb{Z}^+$, the elements $\displaystyle nx$ and $\displaystyle x^n$ are defined recursively as follows:

$\displaystyle 1x=x^1=x$
if $\displaystyle kx$ and $\displaystyle x^k$ have been defined, then $\displaystyle (k+1)x=kx\oplus x$ and $\displaystyle x^{k+1}=x^k\odot x$

Which of the following must be true?

(i) $\displaystyle (x\odot y)^n=x^n\odot y^n$ $\displaystyle \forall x,y\in S$ and $\displaystyle \forall n\in\mathbb{Z}^+$

(ii) $\displaystyle n(x\oplus y)=nx\oplus ny$ $\displaystyle \forall x,y\in S$ and $\displaystyle \forall n\in\mathbb{Z}^+$

(ii) $\displaystyle x^m\odot x^n=x^{m+n}$ $\displaystyle \forall x\in S$ and $\displaystyle \forall m,n\in\mathbb{Z}^+$
This is one obviously true.

I am struggling with proving or disproving 1 and 2
• May 10th 2010, 02:10 PM
undefined
Quote:

Originally Posted by dwsmith
Suppose that two binary operations, denoted by $\displaystyle \oplus$ and $\displaystyle \odot$, are defined on a nonempty set S, and that the following conditions are satisfied $\displaystyle \forall x,y,z\in S$.

(1) $\displaystyle x\oplus y$ and $\displaystyle x\odot y$ are in S
(2) $\displaystyle x\oplus (y\oplus z)=(x\oplus y) \oplus z$ and $\displaystyle x\odot (y\odot z)=(x\odot y) \odot z$
(3) $\displaystyle x\oplus y=y\oplus x$

Also, $\displaystyle \forall x\in S$ and $\displaystyle \forall n\in \mathbb{Z}^+$, the elements $\displaystyle nx$ and $\displaystyle x^n$ are defined recursively as follows:

$\displaystyle 1x=x^1=x$
if $\displaystyle kx$ and $\displaystyle x^k$ have been defined, then $\displaystyle (k+1)x=kx\oplus x$ and $\displaystyle x^{k+1}=x^k\odot x$

Which of the following must be true?

(i) $\displaystyle (x\odot y)^n=x^n\odot y^n$ $\displaystyle \forall x,y\in S$ and $\displaystyle \forall n\in\mathbb{Z}^+$

(ii) $\displaystyle n(x\oplus y)=nx\oplus ny$ $\displaystyle \forall x,y\in S$ and $\displaystyle \forall n\in\mathbb{Z}^+$

(ii) $\displaystyle x^m\odot x^n=x^{m+n}$ $\displaystyle \forall x\in S$ and $\displaystyle \forall m,n\in\mathbb{Z}^+$
This is one obviously true.

I am struggling with proving or disproving 1 and 2

I think (i) is false, but I don't think my demonstration constitutes a rigorous proof.

We can rewrite

$\displaystyle (x\odot y)^n=\underbrace{(x\odot y)\odot (x\odot y) \odot ... \odot (x\odot y)}_{n \text{ instances of }(x\odot y)}$

Since $\displaystyle \odot$ is not commutative, we cannot rearrange terms.

I think (ii) is true and can be proven from the definition of multiplication and conditions (2) and (3).

We can rewrite

$\displaystyle n(x\oplus y)=\underbrace{(x\oplus y) \oplus (x\oplus y) \oplus \cdots \oplus (x\oplus y)}_{n \text{ instances of }(x\oplus y)}$

Now with commutativity and associativity we can simply rearrange terms to get

$\displaystyle n(x\oplus y)=\underbrace{x \oplus x \oplus \cdots \oplus x}_{n \text{ instances of } x} \oplus \underbrace{y \oplus y \oplus \cdots \oplus y}_{n \text{ instances of } y}$

$\displaystyle = nx\oplus ny$
• May 10th 2010, 02:17 PM
dwsmith
Why does $\displaystyle n(x\oplus y)$ mean $\displaystyle (x\oplus y)\oplus (x\oplus y)....$? I don't see how you deciphered that from what was giving.
• May 10th 2010, 02:26 PM
undefined
Quote:

Originally Posted by dwsmith
Why does $\displaystyle n(x\oplus y)$ mean $\displaystyle (x\oplus y)\oplus (x\oplus y)....$? I don't see how you deciphered that from what was giving.

Well $\displaystyle 1x = x$

$\displaystyle 2x = 1x \oplus x = x \oplus x$

$\displaystyle 3x = 2x \oplus x = (x \oplus x) \oplus x = x \oplus x \oplus x$

...
• May 10th 2010, 02:32 PM
dwsmith
$\displaystyle nx=(n-1+1)x=(n-1)x\oplus x=(n-2+1)x\oplus x=(n-2)x\oplus x \oplus x.....$
• May 10th 2010, 03:14 PM
undefined
Quote:

Originally Posted by dwsmith
$\displaystyle nx=(n-1+1)x=(n-1)x\oplus x=(n-2+1)x\oplus x=(n-2)x\oplus x \oplus x.....$

This relies on

$\displaystyle (n_1+n_2)x = n_1x \oplus n_2x$

which I suppose is obvious since it's just the $\displaystyle \oplus$ version of (iii), nevertheless it still requires proof.

The way I wrote it down, weak induction could be used for a formal proof.

I'm curious as to your obvious proof of (iii), since I would have used

$\displaystyle x^n = \underbrace{x \odot x \odot \cdots \odot x}_{n \text{ instances of } x}$

from which (iii) follows trivially.
• May 10th 2010, 03:17 PM
dwsmith
$\displaystyle x^{k+1}=x^k\odot x$

This is why 3 is obvious.