Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I just started reading An Introduction to Mathematical Analysis by H.S. Bear and problem 1 goes as follows:

Problem 1: Show that + and * are necessarily different operations. That is, for any system (F, +, *) satisfying Axioms I, II, and III, it cannot happen that x + y = x * y for all x, y. Hint: You do not know there are any numbers other than 0 and 1, so that your argument should probably involve only these numbers. Did you use Axiom II? If not, state explicitly the stronger result that you actually proved.

In this book, Axiom I is commutativity of + and *, Axiom II is associativity of + and *, and Axiom III is existence of identities (x+0=x, x*1=x, 0 does not equal 1).

My question: Simply why would the author specifically ask the reader if he/she used Axiom II (associativity) and what exactly do they mean by "If not, state explicitly the stronger result you actually proved"? Why not not include those last two sentences?

FWIW, here is my solution:

To prove: Thing to prove Restated: Thing to prove restated enter image description here

And I justified 5 by citing Axiom III since Axiom III includes the statement that 0 does not equal 1.

share|improve this question
    
Hint: if you didn't use Axiom II, what can you now say about systems where Axioms I And III hold but II possibly does not? –  Steven Stadnicki Jun 5 '12 at 16:13
2  
More succinctly: $\ 1 = 1 + 0 = 1 * 0 = 0.\ $ Note that the proof requires only one of the operations to be commutative, so it will work for noncommutative rings too, i.e. where multiplication is not necessarily commutative. It wouldn't require comutativity at all if Axiom II was $\rm\:1*x = x\:$ vs. $\rm\:x*1 = x.$ Said simply, the hypothesis $\:1\ne 0\:$ forces addition $\ne$ multiplication, because these operations have the value $1,0$ resp. at the same point, viz. $(1,0)$ –  Bill Dubuque Jun 5 '12 at 16:16
1  
Since I didn't use Axiom II (associativity), my answer to the request "State explicitly the stronger result that you actually proved" is "The non-equivalence of + and * is not dependent on associativity holding in the system F." Is that a good answer to the meaning of the very last sentence of the problem? –  Pete Jun 5 '12 at 16:42
1  
@Pete Close, though I would make it clear that it does still require Axioms I and III, e.g. (though this is awkward) '+ and * are non-equivalent in each system with commutativity and existence of identities, regardless of associativity'. –  Steven Stadnicki Jun 5 '12 at 17:04

4 Answers 4

up vote 4 down vote accepted

The basic idea is as follows. From the neutral Axioms III, and commutativity of addition we have

$$\begin{eqnarray}\rm x = 0 + x &\rm \\ \rm y *\: 1 &=\rm y \end{eqnarray}$$

If $\ +\, =\, *\ $ then aligned terms are unified for $\rm\:y = 0,\ x = 1,\:$ yielding

$$\rm\ 1 = 0 + 1 = 0 * 1 = 0 $$

contra hypothesis $\rm\:1 \ne 0.\:$ Thus $\rm\: +\: \ne\: *\:$ because they take different values at the point $\rm\:(0,1)$.

Note that the proof does not use associativity, and doesn't use commutativity if you state the neutral axioms as above. In any case, only one of the commutative axioms is needed, so that the neutral axioms can be ordered so the above unification is possible. In particular, the inference works in noncomutative rings, i.e. rings where multiplication is not necessarily commutative. Further, because the proof did not use associativity, it will also work in nonassociative rings.

Note $\ $ This method of deriving consequences by unifying terms in identities is a basic method in equational reasoning (term rewriting), e.g. google Knuth-Bendix or Grobner basis algorithms.

share|improve this answer

The author probably wants to add that it is not necessary to use Axiom II in order to prove that the laws must be different.

If you then forget about axiom II, and if you suppose that + and * are the same, your axioms become :

axiom 1 : $x+y = y+x$
axiom 3a : $x+0 = x$
axiom 3b : $x+1 = x$
axiom 3c : $0 \neq 1$.

In order to get a contradiction you must use axiom 3c, and the only way to use it is to show that axioms 1,3a,3b implies that $0 = 1$.

So you really are investigating commutative laws with two identity elements, and in fact, you necessarily have to prove that the identity element of a commutative law must be unique :

If 0 and 1 are identity elements of +, then 0 = 0+1 = 1+0 = 1, so they are the same. There, we proved that if a commutative law has an identity element, it is unique.

share|improve this answer

Proven without Associativity:

Given the two different operations, $x+y\neq x*y$ cannot hold $\forall x,y$ even when the order of evaluation matters (the case where Axiom II is false, e.g. subtraction and division).

share|improve this answer

As far as I understand this the author also wants to teach how to understand/write a proof in general. If you are given a proof of a statement a good place to start understanding it, is figuring out where exactly every single assumption was used. The second question is which assumptions didn't we use and whether we actually proved a stronger result.

This is a very useful lesson for your future as a mathematician! The first question is probably more important when it comes to understanding a specific proof, while the second question may help you linking the statement with other similar statements. Obviously in your rather elementary exercise it might not reveal its full importance but as soon as things get more complicaated it is a good idea to keep these two questions in mind.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.