[SOLVED] Binary Operations

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
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
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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\)
 
  • Like
Reactions: dwsmith

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
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.
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
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\)

...
 

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
\(\displaystyle nx=(n-1+1)x=(n-1)x\oplus x=(n-2+1)x\oplus x=(n-2)x\oplus x \oplus x.....\)
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
\(\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.
 

dwsmith

MHF Hall of Honor
Mar 2010
3,093
582
Florida
\(\displaystyle x^{k+1}=x^k\odot x\)

This is why 3 is obvious.