# I Cancellation law multiplication natural numbers

Tags:
1. Sep 22, 2016

### Math_QED

Hello everyone. I wanted to prove the following theorem, using the axioms of Peano.

Let $a,b,c \in \mathbb{N}$. If $ac = bc$, then $a = b$.

I thought, this was a pretty straightforward proof, but I think I might be doing something wrong.

Proof:

Let $G := \{c \in \mathbb{N}|$ if $a,b \in \mathbb{N}$ and $ac = bc$, then $a = b\}$
Obviously, $G \subset \mathbb{N}$. Since $a.1 = b.1$ implies that $a = b, 1 \in G$.
Now, suppose $g \in G$. Then $ag = bg$. Thus, $a.s(g) = b.s(g) \Rightarrow a(g+1) = b(g+1) \Rightarrow ag+a = bg + b \Rightarrow ag + a = ag + b \Rightarrow a = b$ Thus, $s(g) \in G$ and we deduce that $G = \mathbb{N}$. QED.

Also, I used some properties that I already proved:

$a.1 = a = 1.a$
$a + c = b + c \Rightarrow a = b$

The proof in my book however, defines $G := \{a \in \mathbb{N}|$ if $b,c \in \mathbb{N}$ and $ac = bc$, then $a = b\}$ and then uses some contradictions and other stuff to show that $G = \mathbb{N}$. Am I overseeing something or is my proof correct as well? This page shows a similar proof to the one in my book: https://www.math.upenn.edu/~ted/203S10/References/Peano.pdf , theorem B.13.

2. Sep 22, 2016

### Staff: Mentor

The main difference is that your definition of $G$ seems to be ambiguous because it depends on the choice of $a$ and $b$ so it is rather a collection of $G_{ab}$ which you are defining. What if you get different $G$ for every pair $(a,b)$? How do you handle this possibility?
The textbook on the other hand places a condition on the selected $a$.

3. Sep 22, 2016

### Math_QED

Hm, I'm not sure whether I fully understand you. But, to set a precedent, the book proves that $a + c = b + c \Rightarrow a = b$ by defining $G := \{c \in \mathbb{N}|$ if $a,b \in \mathbb{N}$ and $a + b = a + c$, then $a = b\}$.Thus, I did something analogue... Anyway, was my proof correct? What do you mean by getting a different G for every pair (a,b)?

4. Sep 22, 2016

### Staff: Mentor

This is probably because it's been more of a feeling, that there is something wrong with $G$. I had trouble to get it properly.
I mean what if one $c$ can be used to cancel $a=2 \cdot 2 \, , \, b= 4$ but not $a=3 \cdot 3 \, , \, b=9$?
It's been the missing quantifiers that irritated me and the case of a (a priori) possible $0$.

The rest looks like an ordinary induction, which is correct.

5. Sep 22, 2016

### Math_QED

Missing quantifiers? And my axioms don't consider $0$ as natural number, so that wouldn't be a problem.

6. Sep 22, 2016

### micromass

Staff Emeritus
No, his proof does not have a different $G$ for different $a$ and $b$. But you're right that his $G$ (and the books) has missing quantifiers. But many books don't put in these quantifiers for some reason.

7. Sep 22, 2016

### Staff: Mentor

Yes, that it is required for all pairs $(a,b)$, not that $c=2$ works for one pair and $c=3$ for another. The definition of $G$ must not depend on the choice of for which $(ac=bc \Rightarrow a=b)$ holds. Or is it clear that if $c$ cancels $(ac,bc)$ then it cancels $(a'c,b'c)$, too? It is difficult to stay properly by the rules when dealing with stuff we're used to on a daily basis. At least to me.

And although $0$ is not contained in $\mathbb{N}$, how do you know beforehand that there is no element $c$ with $ac=bc$ AND $a \neq b$? But it isn't required, since the implication would be wrong. I just said the possibility irritated me.

8. Sep 22, 2016

### Math_QED

Do you have any idea why the book's proof is different then? Mine (if it would be correct) seems to be easier

So, would this be correct?

$G := \{c \in \mathbb{N}| \forall (a,b) \in \mathbb{N} \times \mathbb{N}: ac = bc \Rightarrow a = b\}$

9. Sep 22, 2016

### Staff: Mentor

No (idea), yes (correct), maybe (easier) and yes (quantifier)

You used a proof by induction. Perhaps it's not part of the book at the current stage.
Then you used $s(g) = g+1$ and you used the distributive law by $a(g+1)=ag +a$. Perhaps this hasn't been proven, yet.

As I said. When dealing with every day stuff, the art is to keep apart what is already known, and what has yet to be shown, because everything usual has to be proven first.

Edit: No induction. I forgot you only use $ag=bg$ and additive cancellation..

Last edited: Sep 22, 2016
10. Sep 22, 2016

### Math_QED

Induction is an axiom, so that's okay. The book proved that there are unique binary operations that satisfy these properties (s(g) = g+1) and we work with those operations so that's not a problem either. Distributivity was proved too. I'm just wondering why the proof is different than mine, but I'll just accept this and move on. Thanks for your helpful replies.

11. Sep 22, 2016

### Staff: Mentor

Thanks, because I'm not quite sure whether $g \in G \Rightarrow s(g) \in G$ is formally an induction.

12. Sep 22, 2016

### Math_QED

The induction axiom, according to my book:

Let $G \subset \mathbb{N}$ be a set. Suppose that $1 \in G$, and that if $g \in G$, then $s(g) \in G$. Then $G = \mathbb{N}$

13. Sep 22, 2016

### Staff: Mentor

The book's proof says "All natural numbers can be canceled." and you showed "All natural numbers can be cancellation factors."
Good to have both but not exactly and formally the same.

14. Sep 22, 2016

### Math_QED

Thanks a lot!

15. Sep 23, 2016

### Math_QED

Hm, this made me think. The book proves the cancellation law of addition by defining $G := \{c \in \mathbb{N}|$ if $a,b \in \mathbb{N}$ and $a + c = b + c$, then $a = b\}$ Doesn't this also mean that the book proves that all natural numbers can be cancellation terms, instead of showing that all natural numbers can be cancelled by addition?

16. Sep 23, 2016

### Staff: Mentor

Let me first consider the additional part. Therefore I define
$G_0 := \{c \in \mathbb{N} \, \vert \, \forall_{a,b} \;\; a+c = b+c \Rightarrow a=b\}$ and
$G_1 := \{a \in \mathbb{N} \, \vert \, \forall_{b,c} \;\; a+c = b+c \Rightarrow a=b\}$

Now let $G_0 = \mathbb{N}$.
If $G_1 \subsetneq \mathbb{N}$ then there is an $a \in \mathbb{N}$ and a $c \in \mathbb{N}$ with $a+c=b+c$ and $a \neq b$.
This means $c \notin G_0$, a contradiction.

If conversely $G_1 = \mathbb{N}$,
and $G_0 \subsetneq \mathbb{N}$ then there is a $c \in \mathbb{N}$ and $a,b \in \mathbb{N}$ with $a+c=b+c$ and $a \neq b$.
This means $a \notin G_1$, a contradiction.

Thus both statements are equivalent.

Now let us see, whether this proof can be used in the multiplicative case. too. Therefore I define
$G_0 := \{c \in \mathbb{N} \, \vert \, \forall_{a,b} \;\; a \,\cdot\, c = b \,\cdot\, c \Rightarrow a=b\}$ and
$G_1 := \{a \in \mathbb{N} \, \vert \, \forall_{b,c} \;\; a \,\cdot\, c = b \,\cdot\, c \Rightarrow a=b\}$

Now let $G_1 = \mathbb{N}$. (textbook)
If $G_0 \subsetneq \mathbb{N}$ then there is a $c \in \mathbb{N}$ and $a,b \in \mathbb{N}$ with $ac=bc$ and $a \neq b$.
This means $a \notin G_1$, a contradiction and the textbook's statement implies yours.

Finally let $G_0 = \mathbb{N}$. (proven by you)
If $G_1 \subsetneq \mathbb{N}$ then there is an $a \in \mathbb{N}$ and a $c \in \mathbb{N}$ with $ac=bc$ and $a \neq b$.
This means $c \notin G_0$, a contradiction. *)

Thus both statements are also equivalent.

*) I am not a 100% sure, since one has to be very careful with the quantifiers and both versions are distinct in the case of $a$ and / or $c$ being possibly $0$, which makes a difference in the multiplicative case. Whether you define $\mathbb{N}$ with or without a zero doesn't matter, as long as you haven't ruled out that there might be an element that behaves like zero with respect to multiplication. Taking the piece off the board by definition is not enough. There still could be another.

So have a close look. Perhaps you can find a pit I've been fallen into. However, I still find the definitions of $G_1$ more transparent, as it goes "all a such that + property of a" instead of "all c such that + property with c".

17. Sep 23, 2016

### Math_QED

So, both statements are most likely equivalent. Thanks for the proof. I will look at it soon (don't have too much time right now, but it looks quite good on first sight). And, if we prove that the cancellation law for multiplication works for every number in $\mathbb{N} \backslash \{0\}$, why aren't we sure then there is no such element that behaves like zero?

18. Sep 23, 2016

### Staff: Mentor

I think we can.

If we have $\forall_{a,b,c} \;\; (ac=bc \Rightarrow a=b)$ then $\forall_{a,b} \; \; (a\,\cdot\,z = b\,\cdot\, z = z \Rightarrow a=b)\;$ cannot happen for $a \neq b$. Thus a cancellation factor $z=0$ is impossible as long as we have at least two different elements.

But $\forall_{b,c} \; \; ( z\,\cdot\,c = b\,\cdot\, c = z \Rightarrow b = z )$ is still possible except for $c=z=0$ which brings us back to the case of the cancellation factor. Since it has to be true for all $c$, especially for $c=z$, then $z$ is ruled out again, since it doesn't follow in this case for $b=1$.