1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Cancellation law multiplication natural numbers

  1. Sep 22, 2016 #1

    Math_QED

    User Avatar
    Homework Helper

    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. jcsd
  3. Sep 22, 2016 #2

    fresh_42

    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##.
     
  4. Sep 22, 2016 #3

    Math_QED

    User Avatar
    Homework Helper

    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)?
     
  5. Sep 22, 2016 #4

    fresh_42

    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.
     
  6. Sep 22, 2016 #5

    Math_QED

    User Avatar
    Homework Helper

    Missing quantifiers? And my axioms don't consider ##0## as natural number, so that wouldn't be a problem.
     
  7. Sep 22, 2016 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
  8. Sep 22, 2016 #7

    fresh_42

    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.
     
  9. Sep 22, 2016 #8

    Math_QED

    User Avatar
    Homework Helper

    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\}##
     
  10. Sep 22, 2016 #9

    fresh_42

    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
  11. Sep 22, 2016 #10

    Math_QED

    User Avatar
    Homework Helper

    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.
     
  12. Sep 22, 2016 #11

    fresh_42

    Staff: Mentor

    Thanks, because I'm not quite sure whether ##g \in G \Rightarrow s(g) \in G## is formally an induction.
     
  13. Sep 22, 2016 #12

    Math_QED

    User Avatar
    Homework Helper

    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}##
     
  14. Sep 22, 2016 #13

    fresh_42

    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.
     
  15. Sep 22, 2016 #14

    Math_QED

    User Avatar
    Homework Helper

    Thanks a lot!
     
  16. Sep 23, 2016 #15

    Math_QED

    User Avatar
    Homework Helper

    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?
     
  17. Sep 23, 2016 #16

    fresh_42

    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".
     
  18. Sep 23, 2016 #17

    Math_QED

    User Avatar
    Homework Helper

    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?
     
  19. Sep 23, 2016 #18

    fresh_42

    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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Cancellation law multiplication natural numbers
  1. Cancellation Law (Replies: 5)

  2. Natural Numbers (Replies: 7)

  3. Natural Numbers (Replies: 3)

  4. Natural Numbers (Replies: 11)

Loading...