Cancellation law multiplication natural numbers

[member 587159]

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.

 

[fresh_42]

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

 

[member 587159]

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

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)?

 

[fresh_42]

Hm, I'm not sure whether I fully understand you.

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.

 

[member 587159]

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.

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

 

[micromass]

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

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.

 

[fresh_42]

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

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.

 

[member 587159]

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.

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

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.

So, would this be correct?

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

 

[fresh_42]

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

 

[member 587159]

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.

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.

 

[fresh_42]

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.

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

 

[member 587159]

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

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}$

 

[fresh_42]

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.

 

[member 587159]

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.

Thanks a lot!

 

[member 587159]

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.

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 canceled by addition?

 

[fresh_42]

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".

 

[member 587159]

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?

 

[fresh_42]

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?

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