4
$\begingroup$

I have a question about a GRE practice problem relating to Rings. The question is as follows:

Suppose that two binary operations, denoted by $\oplus$ and $\odot$ , are defined on a nonempty set $S$, and that the following conditions are satisfied for all $x, y$, and $z$ in $S$:

(1) $(x\oplus y)$ and $x \odot y$ are in S.

(2) $x\oplus (y \oplus z) = (x \oplus y) \oplus z$ and $x \odot (y \odot z) = (x \odot y) \odot z$.

(3) $x \oplus y = y \oplus x$

Also, for each $x$ in $S$ and for each positive integer $n$, the elements $nx$ and $xn$ are defined recursively as follows:

$1x = x^1 = x$ and

if $kx$ and $x^k$ have been defined, then $(k + 1) x = kx \oplus x$ and $x^{k+1} = x^k \odot x$. Which of the following must be true?

I) $(x \odot y)^n = x^n \odot y^n$ for all $x,y \in S$ and all positive integers $n$.

II) $n(x \oplus y) = nx \oplus ny$ for all $x,y \in S$ and all positive integers $n$.

III) $x^m \odot x^n = x^{m+n}$ for all $x \in S$ and all positive integers $n,m$.

A) I only, B) II only, C) III only, D) II and III, E) I, II and III

I recognize that the description given is the description of a ring. So I was pretty sure that the answer was E) I, II, III. It is pretty easy to show II and III, and I couldn't think of a counterexample for I. However, the solutions manual I purchased says the answer is D) II and III, claiming that the ring of integers does not have property I.

So my question is, what is the darn counterexample? I can't think of any. I tried $x=1$ and $y=-1$ with both odd and even powers, and even tried $x=1$, $y=2$ and $x=-1$, $y=2$, still nothing. Any suggestions? Thanks in advance.

$\endgroup$
  • $\begingroup$ I am stunned to see such a question in a GRE $\endgroup$ – imranfat Sep 11 '14 at 21:03
  • 2
    $\begingroup$ You do not necessarily have a ring. In particular there are no identity elements, you have no additive inverses, and you aren't told that multiplication distributes over addition. 1 is going to be false because you aren't told that multiplication is commutative. $\endgroup$ – James Sep 11 '14 at 21:09
  • $\begingroup$ It's not a ring - there is no hint that there are additive inverses or an identity in either operator. For example, the positive integers with the usual operators satisfies the above. $\endgroup$ – Thomas Andrews Sep 11 '14 at 21:11
  • $\begingroup$ This question is simpler that it appears at first glance. The key is (3) implies $\odot$ may not be commutative which breaks the induction step when trying to show I $\endgroup$ – illysial Sep 11 '14 at 21:14
  • 2
    $\begingroup$ @CarlMummert Imagine if this question did appear on the math portion of the ordinary GRE...you would hear the collective sound of heads exploding across the country. $\endgroup$ – heropup Sep 11 '14 at 21:27
2
$\begingroup$

Here's a counterexample for (I). $\mathrm{Mat}_{2 \times 2}(\mathbb{R})$ equipped with matrix addition and multiplication satisfies all of the above criteria, and we consider the matrices $$A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \: \: B = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$$ For $n = 2$, we have that $$(AB)^2 = \left(\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\right)^2 = \begin{pmatrix} 1 & -1 \\ 0 & -1 \end{pmatrix}^2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$

but $$A^2 B^2 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^2 \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}^2 = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$$

So, $A^2B^2 \ne (AB)^2$, and therefore this is a counterexample for (I).

$\endgroup$
1
$\begingroup$

Claims II and III are necessarily true from the given conditions. Proof by induction: Suppose $(n-1)x \oplus (n-1)y = (n-1) z$, where $z = x \oplus y$. Then by definition, $$nx \oplus ny = ((n-1)x \oplus x) \oplus ((n-1)y \oplus y).$$ But property (3) indicates that $\oplus$ is commutative, so the above can be arranged at will: $$nx \oplus ny = ((n-1) x \oplus (n-1) y) \oplus (x \oplus y) = (n-1)z \oplus z = nz.$$ Claim III is an obvious and direct consequence of the associativity of $\odot$.

The only claim that is not necessarily true is I, because this requires $\odot$ to be commutative, which is not postulated. This also suggests a choice of set $S$ for which properties (1-3) hold true, yet claim I is false; e.g., try a set of $2 \times 2$ matrices.

$\endgroup$
1
$\begingroup$

Your solution manual is incorrect that the integers are a counterexample, because the integers are a commutative ring.

For a true counterexample to I, take the $2\times 2$ matrices over the integers with addition as matrix addition and multiplication as matrix multiplication, with $x = \begin{pmatrix} 1 & 1 \\ 1 & 1\end{pmatrix}$ and $y = \begin{pmatrix} 1 & 2 \\ 1 & 1\end{pmatrix}$.

$\endgroup$
0
$\begingroup$

The questioner is trying to deceive you. What you have are two independent operations on the set $S$; both are associative, but only one is commutative.

Under either operation, $S$ is a semigroup. Let's use the common notation for semigroups, that is, simple juxtaposition denotes the result of the operation; associativity is expressed by $$ x(yz)=(xy)z \quad\text{for all $x,y,z$} $$ Powers are defined recursively by $$ x^1=x,\quad x^{n+1}=x^nx. $$ Proving that $$ x^{m+n}=x^mx^n $$ is standard: it's true by definition when $n=1$; suppose it holds for $n$: then \begin{align} x^{m+n+1}&=x^{m+n}&&\text{definition}\\ &=(x^mx^n)x&&\text{induction hypothesis}\\ &=x^m(x^nx)&&\text{associativity}\\ &=x^mx^{n+1}&&\text{definition} \end{align}

This proves III.

If the semigroup is commutative, that is $xy=yx$ for all $x,y$, then also $$ (xy)^n=x^ny^n $$ holds. This can be proved by a double induction: first show that $y^nx=xy^n$ and then $(xy)^n=x^ny^n$. This proves II, because placing the exponent on the left instead as a superscript is just a matter of notation.

For a counterexample to I, consider the group $S_3$ under composition; let $x$ be the permutation that swaps $2$ and $3$ and $y$ the permutation that swaps $1$ and $2$. Then $(xy)^2$ is not the identity, while $x^2y^2$ is the identity. This can be the $\odot$ operation; for $\oplus$ consider the operation that composes any two objects producing the identity: this is associative and commutative.

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