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.

Let $N$ be a set of non-negative integers. Of course we know that $a+b=0$ implies that $a=b=0$ for $a, b \in N$.

How do (or can) we prove this fact if we don't know the subtraction or order?

In other words, we can only use the addition and multiplication.

Please give me advise.

EDIT

The addition law mean that for $a, b \in N$, there is an element $a+b$ in $N$ and this operation is associative. The multiplication law means that for $a, b \in N$, there is an element $ab$ in $N$ and this operation is associative. Also the distribution laws hold.


EDIT2

Let me rephrase the question since I don't want arguments on orders.

Let $N$ be a set with operation $+$ and $\times$.

$N$ is a monoid with the operation $+$ and $\times$ respectively. There is an unit element $0\in N$.

The distribution laws hold as in the case of the set of integers.

Can we prove the fact above with this assumption?

share|improve this question
3  
Why would you assume you could do it with these laws, since they are true for $\mathbb Z$ as well, and the theorem is not true in $\mathbb Z$? You have a set of axioms that have both $\mathbb N$ and $\mathbb Z$ as "models," and you certainly can't prove something from these axioms alone if it isn't true in $\mathbb Z$ –  Thomas Andrews Mar 20 '13 at 4:45
    
@ThomasAndrews Thanks. Yes, that's true. I think I missed some axiom to distinguish them. –  Snow Mar 20 '13 at 4:47
    
@Snow: Then please either modify your question to make clear you know the answer, or answer it yourself, or delete it. –  Marc van Leeuwen Mar 20 '13 at 6:20
add comment

5 Answers

up vote 2 down vote accepted

Use the Mazur swindle! Namely, if $a+b=0$ then

\begin{align*} 0 &= 0 + 0 + 0 + \cdots\\ &= (a+b)+(a+b)+(a+b)+\cdots\\ &= a+(b+a)+(b+a)+\cdots \\ &= a + 0 + 0 + \cdots\\ &= a. \end{align*}

Regrouping the infinite sum is justified because everything is nonnegative. I leave it as an exercise to identify exactly which axioms of arithmetic we've used.

share|improve this answer
    
The associativity axiom says that ((a+b)+c)=(a+(b+c)). When you write (a+b)+(a+b)+(a+b)+⋯=a+(b+a)+(b+a)+⋯ haven't you used associativity an infinite number of times? Doesn't that make this argument impossible to formalize, since any formal proof (in the sense of a formal proof of mathematical logic) has to come as finite? Also, haven't you used that (b+a)=0 and that (a+0)=a an infinite number of times also? –  Doug Spoonwood Apr 5 '13 at 4:03
    
Also, I don't see how nonnegativity implies the regrouping as justified. Consider the integers under addition (Z, +) and a map F:0->1, x->2x if x>0, x->((-2x)+1) if x<0. F is a bijection between Z and the natural numbers N such that it induces an operation % on the naturals (making (N, %) into a commutative group). Consider, 2%3%2%3&... Here all the numbers come as nonnegative, but we can't regroup such an infinite sum, because it comes as equivalent to regrouping 1+(-1)+1+(-1)+... So, how does nonnegativity imply such regrouping as you did above as permissible? –  Doug Spoonwood Apr 5 '13 at 4:17
add comment

Please set out what you mean by the addition law. You need the axiom that there is no number whose successor is $0$ or this fails. That is what distinguishes the integers from the naturals. It allows you to define order as $x \le y \leftrightarrow \exists (z) x+z=y$

share|improve this answer
    
Is there any way to prove this fact without introducing the order? –  Snow Mar 20 '13 at 4:26
    
@Snow: the reason you can get $a=b=0$ from $a+b=0$ is because you don't have negative numbers available. You need a 'bottom', which gives an order. –  Ross Millikan Mar 20 '13 at 4:30
add comment

What is the addition law?

If it the one from Peano arithmetic, it is $x+0=x$ and $x+S(y) = S(x+y)$, where $S(x)$ is the successor of $x$.

If $x+y=0$, suppose $y$ was not zero. Then there is a $z$ such that $S(z) = y$.

Then $0 = x+y = x+S(z) = S(x+z)$ which is a contradiction, since $0$ is not the successor of anything.

Therefore $y=0$. Substituting this in $x+y=0$ and using $x+0=x$, we get $x=0$.

Is this what you wanted?

share|improve this answer
    
I prefer not to use the successor. –  Snow Mar 20 '13 at 4:28
1  
That's nice. (get 15 characters for a comment) –  marty cohen Mar 20 '13 at 4:31
    
@Snow n+1 is the successor, so you can just replace every occurrence of $S(m)$ with $m+1$. –  Thomas Andrews Mar 20 '13 at 4:33
    
I edited the question. I'm sorry that I didn't write the reason why I don't want to have the successor. –  Snow Mar 20 '13 at 4:44
1  
You can actually prove from Peano that either $y=0$ or $y=S(z)$ for some $z$. It's my favorite induction proof because you prove the case $P(0)$ as obvious and $P(S(n))$ is true whether $P(n)$ is true or not :) –  Thomas Andrews Mar 20 '13 at 5:08
add comment

There are three axioms that you need to prove this:

  1. For all non-negative integers $n$, $n+1\neq 0$
  2. For all non-negative integers $a,b$, $a+(b+1)= (a+b)+1$
  3. Induction

Theorem: For all $b$, either $b=0$ or $a+b\neq 0$.

Proof by induction: If $b=0$ we are done.

Now assume it is true for $b$. Then $a+(b+1)=(a+b)+1$ by (2). But by $1$, $(a+b)+1\neq 0$. So we get our result.

Now, if $a+b=0$ then $b=0$ and then $a+b=a+0=a$ so $a=0$ as well.

You can't do it just from addition law and multiplication law because those laws are true for all the integers, and it is not true for all the integers.

share|improve this answer
    
Induction presupposes order. –  Doug Spoonwood Mar 20 '13 at 4:31
    
No, it doesn't. Induction is an axiom, from which you prove order. @DougSpoonwood –  Thomas Andrews Mar 20 '13 at 4:32
    
The axiom of induction presupposes the ordering of the natural numbers, in that natural number (k+1) immediately succeeds natural number k, and that each natural number has an immediate successor. –  Doug Spoonwood Mar 20 '13 at 4:36
    
There is no such thing as "immediately succeeding" until you prove it. You do have a successor, but it needs proof that there is no natural number between $n$ and $n+1$. And the set is still not ordered, because without the axiom that $n+1\neq 0$, for example, you might have a cycle, in which case there is no natural order. Order in this sense usually means having a useful "<" relation. @DougSpoonwood –  Thomas Andrews Mar 20 '13 at 4:38
1  
You don't, it is an axiom for $\mathbb N$, at least under Peano postulates, that $f(n)\neq 0$ for all $n$. @leo –  Thomas Andrews Mar 20 '13 at 19:44
show 11 more comments

You don't need $+$ or $\times$ as forming monoids on the natural numbers, nor the distributive property. You can get by with less as follows:

Addition has the property that $(0+b)\leq(a+b)$ and $(a+0)\leq(a+b)$. This is NOT presupposing the order of the natural numbers, or that no number of the naturals has 0 as a successor, but only a monotonicity property of addition.

We'll also assume the existence of an additive identity.

Consequently, if $(a+b)=0$, then $b=(0+b)\leq(a+b)=0.$ So, $b\leq 0.$ Also, $0=(0+0)\leq (0+b)=b$ by substitution of 0 for a in $(a+0)\leq (a+b)$ and the identity rule. Thus, $0\leq b.$ So, $0 \leq b\leq 0.$ Consequently, $b=0.$

Similarly, $a=(a+0)\leq(a+b)=0.$ Thus, $a\leq 0$. Also, $0=(0+0)\leq(a+0)=a.$ So, $0\leq a.$ Thus, $0 \leq a\leq 0.$ Consequently, $a=0.$

Therefore, for an algebraic structure with an identity element "$0$", binary operation "$+$" and where $(0+b)\leq (a+b),$ and $(a+0)\leq (a+b),$ and $a \leq x \leq a \implies x=a,$ it holds that "if $(a+b)=0,$ then $a=b=0$".

As an example of an algebriac structure where this holds, and "$+$" is not natural number addition, let "$+$" denote the maximum of two numbers, and consider $(\{0, 1\}, +)$. Both suppositions used in the proof above can get verified.

share|improve this answer
    
Bijections are entirely irrelevant to this question - you could use $\mathbb R$ to show it is impossible to prove this with these axioms. All you need is one example which obeys these axioms but doesn't satisfy the proposition to prove that the proposition is not provable from the axioms. Bijections are irrelevant. –  Thomas Andrews Mar 20 '13 at 6:13
1  
Also, you've posted over 100 answers and you still are not in the habit of entering in LaTeX? –  Thomas Andrews Mar 20 '13 at 6:16
add comment

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.