Prove Addition is Associative Given Peano Axioms

[AvgStudent]

Hi, I was tasked with proving that addition is associative, assuming the Peano Axioms and followings are true: Can someone check if the proof is valid?
Given:
[imath]S:\N\to\N[/imath], [imath]s(n)=n+1[/imath], where [imath]s(n)[/imath] is the successor function.

1. [imath]s(n)=n+1[/imath]
2. [imath]m+s(n)=s(m+n)[/imath]

Claim: Addtion is associative
Proof by induction:
Let [imath]S=\{l,m,n \in \N|(l+m)=n = l+(m+n)\}[/imath]
Base case:
[imath](l+m)+1=s(l+m)=l+s(m)=l+(m+1)\implies1\in S[/imath]

Induction:
[math](l+m)+(n+1)=(l+m)+s(n)\\ =s((l+m)+n)\\ =s(l+(m+n))\\ =l+s(m+n)\\ =l+(m+s(n))\\ =l+(m+(n+1))\\ \implies n+1 \in S [/math]Therefore, addition is associative for all [imath]n \in\N \quad \blacksquare[/imath]

 

[Zermelo]

Hi, I was tasked with proving that addition is associative, assuming the Peano Axioms and followings are true: Can someone check if the proof is valid?
Given:
[imath]S:\N\to\N[/imath], [imath]s(n)=n+1[/imath], where [imath]s(n)[/imath] is the successor function.

1. [imath]s(n)=n+1[/imath]
2. [imath]m+s(n)=s(m+n)[/imath]

Claim: Addtion is associative
Proof by induction:
Let [imath]S=\{l,m,n \in \N|(l+m)=n = l+(m+n)\}[/imath]
Base case:
[imath](l+m)+1=s(l+m)=l+s(m)=l+(m+1)\implies1\in S[/imath]

Induction:
[math](l+m)+(n+1)=(l+m)+s(n)\\ =s((l+m)+n)\\ =s(l+(m+n))\\ =l+s(m+n)\\ =l+(m+s(n))\\ =l+(m+(n+1))\\ \implies n+1 \in S [/math]Therefore, addition is associative for all [imath]n \in\N \quad \blacksquare[/imath]

This seems ok. One little thing that caught my eye is the formulation of S, I would have maybe put “ Let L and m be arbitrary but fixed natural numbers. S = { n € N | … }. Someone correct me if I’m wrong ?

 

[AvgStudent]

This seems ok. One little thing that caught my eye is the formulation of S, I would have maybe put “ Let L and m be arbitrary but fixed natural numbers. S = { n € N | … }. Someone correct me if I’m wrong ?

Ok, thanks for feedback Appreciate it.

 

[JeffM]

I’d cavil a bit about the presentation.

[imath](\ell + m) + n = \ell + (m + n)[/imath] rather than [imath](\ell + m) = n = \ell+ (m + n).[/imath]

The latter statement is not generally true. For example, 3 + 5 = 8, but 8 does not equal 3 + (5 + 8).

Ignoring what is almost certainly a typo, I find the presentation weird. You develop a base case of [imath](\ell + m) + 1 = \ell + (m + 1).[/imath] But then you seemingly ignore it.

[math](\ell + m) + (n + 1) = (\ell + m) + s(n) = s\{(\ell + m) + n\}.[/math]
Good so far.

But then you go [imath]s\{(\ell + m) + n\} = s\{\ell + (m + n)\}[/imath], WHICH IS ASSUMING THAT WHICH IS TO BE PROVED.

This is partly a presentation issue of letting variable names jump around. So we show that

[math](a + b) + 1 = a + (b + 1). \text {\ Then, we let}\\ k \text { be an arbitrary natural number such that }\\ (\ell + m) + k = \ell + (m + k).\\ (\ell + m) + (k + 1) = (\ell + m) + s(k) \text { by definition of successor.}\\ \therefore (\ell + m) + (k + 1) = s\{(\ell + m) + k)\} \text { by Axiom 2.}\\ \therefore (\ell + m) + (k + 1) = s\{ \ell + ( m + k)\} \text { by definition of } k.\\ \therefore (\ell + m) + (k + 1) = \{\ell + (m + k)\} + 1 \text { by definition of successor.}\\ \therefore (\ell + m) + (k + 1) = \ell + \{(m + k) + 1\} \ \because \ (a + b) + 1 = a + (b + 1).\\ \therefore (\ell + m) + (k + 1) = \ell + \{m + (k + 1)\} \ \because \ (a + b) + 1 = a + (b + 1).\\ \text {Thus, by induction, } (\ell + m) + n = \ell + (m + n) \text { for all natural numbers } \ell, \ m, \text { and } m.[/math]
It has been well over 50 years since I studied the use of the Peano Postulates, but my recollection is that you needed to be beyond meticulous. I believe you had the proof in your mind, but I am not satisfied that your presentation will pass muster. But maybe I am just an old fuss-budget.

 

[AvgStudent]

I’d cavil a bit about the presentation.

[imath](\ell + m) + n = \ell + (m + n)[/imath] rather than [imath](\ell + m) = n = \ell+ (m + n).[/imath]

The latter statement is not generally true. For example, 3 + 5 = 8, but 8 does not equal 3 + (5 + 8).

Ignoring what is almost certainly a typo, I find the presentation weird. You develop a base case of [imath](\ell + m) + 1 = \ell + (m + 1).[/imath] But then you seemingly ignore it.

[math](\ell + m) + (n + 1) = (\ell + m) + s(n) = s\{(\ell + m) + n\}.[/math]
Good so far.

But then you go [imath]s\{(\ell + m) + n\} = s\{\ell + (m + n)\}[/imath], WHICH IS ASSUMING THAT WHICH IS TO BE PROVED.

This is partly a presentation issue of letting variable names jump around. So we show that

[math](a + b) + 1 = a + (b + 1). \text {\ Then, we let}\\ k \text { be an arbitrary natural number such that }\\ (\ell + m) + k = \ell + (m + k).\\ (\ell + m) + (k + 1) = (\ell + m) + s(k) \text { by definition of successor.}\\ \therefore (\ell + m) + (k + 1) = s\{(\ell + m) + k)\} \text { by Axiom 2.}\\ \therefore (\ell + m) + (k + 1) = s\{ \ell + ( m + k)\} \text { by definition of } k.\\ \therefore (\ell + m) + (k + 1) = \{\ell + (m + k)\} + 1 \text { by definition of successor.}\\ \therefore (\ell + m) + (k + 1) = \ell + \{(m + k) + 1\} \ \because \ (a + b) + 1 = a + (b + 1).\\ \therefore (\ell + m) + (k + 1) = \ell + \{m + (k + 1)\} \ \because \ (a + b) + 1 = a + (b + 1).\\ \text {Thus, by induction, } (\ell + m) + n = \ell + (m + n) \text { for all natural numbers } \ell, \ m, \text { and } m.[/math]
It has been well over 50 years since I studied the use of the Peano Postulates, but my recollection is that you needed to be beyond meticulous. I believe you had the proof in your mind, but I am not satisfied that your presentation will pass muster. But maybe I am just an old fuss-budget.

Thanks, this is good feedback. This is my first proof class, so still inexperienced at rigorous proofs. Not exactly sure what's sufficient.

 

[Steven G]

Yeah, I agree with Jeff that your proof is assuming what you want to prove. Do you see that?
It has been just over 30 years since I studied this material. Having said that it seems that Jeff nailed the proof (as always)

 

[AvgStudent]

Yeah, I agree with Jeff that your proof is assuming what you want to prove. Do you see that?
It has been just over 30 years since I studied this material. Having said that it seems that Jeff nailed the proof (as always)

Yes, thanks for the feedback.

 

[JeffM]

My recollection about these proofs is that they involve things so intuitive that it is very easy to assume as true what you are trying to prove is true. That is why I like detailed two-column proofs for this work. (Do they still teach two-column proofs? I studied geometry before they decided that Hilbert's sophistication was suitable for 14 year olds. I think Euclid was better for teaching proofs to kids.) For more sophisticated proofs, skipping steps is not likely to cause that particular error (although it may cause errors of a different type.)

Also I think my way of doing induction proofs is less likely to fry your brain. We are trying to prove a proposition about all n [imath]\ge[/imath] m. We first show the proposition to be true if n = m. Then we are justified in saying that there is a non-empty set of numbers that are [imath]\ge[/imath] m and for which the proposition is true. We choose an arbitrary one of those numbers and call it k. Now prove the proposition is true for k + 1. It keeps which variable is which from falling into a jumble. I do not say that other formats are wrong (and of course in class you must use your teacher's method of presentation), but when you are doing your own work, try my method.

 

[AvgStudent]

My recollection about these proofs is that they involve things so intuitive that it is very easy to assume as true what you are trying to prove is true. That is why I like detailed two-column proofs for this work. (Do they still teach two-column proofs? I studied geometry before they decided that Hilbert's sophistication was suitable for 14 year olds. I think Euclid was better for teaching proofs to kids.) For more sophisticated proofs, skipping steps is not likely to cause that particular error (although it may cause errors of a different type.)

Also I think my way of doing induction proofs is less likely to fry your brain. We are trying to prove a proposition about all n [imath]\ge[/imath] m. We first show the proposition to be true if n = m. Then we are justified in saying that there is a non-empty set of numbers that are [imath]\ge[/imath] m and for which the proposition is true. We choose an arbitrary one of those numbers and call it k. Now prove the proposition is true for k + 1. It keeps which variable is which from falling into a jumble. I do not say that other formats are wrong (and of course in class you must use your teacher's method of presentation), but when you are doing your own work, try my method.

The proof was in geometry the last time I did two columns, and I've never seen it again. I didn't think that would consider as "formal". As stated before, this is my first proof course, and I don't really know what to expect. Furthermore, the professor didn't give us any format or guidelines to follow, so this was shot in the dark. With that being said, your proof is well written and formatted. I'd use it as a guide for my future works. Thanks

 

[JeffM]

The proof was in geometry the last time I did two columns, and I've never seen it again. I didn't think that would consider as "formal". As stated before, this is my first proof course, and I don't really know what to expect. Furthermore, the professor didn't give us any format or guidelines to follow, so this was shot in the dark. With that being said, your proof is well written and formatted. I'd use it as a guide for my future works. Thanks

Do not provide proofs in a format your teacher does not like. If you want, show him this thread (on paper or computer) and ask him if the format I use is ok with him. If not, learn to use what he wants. I am not a mathematician, and my style is intended to be clear even if prolix. I remember some comment about proofs: like miniskirts, they should be short enough to be interesting rather than so short as to be scandalous. My style is not in that mode.

 

[AvgStudent]

Do not provide proofs in a format your teacher does not like. If you want, show him this thread (on paper or computer) and ask him if the format I use is ok with him. If not, learn to use what he wants. I am not a mathematician, and my style is intended to be clear even if prolix. I remember some comment about proofs: like miniskirts, they should be short enough to be interesting rather than so short as to be scandalous. My style is not in that mode.

I don't think he has a preference; otherwise, he would've shown us already.
PS: Love that comment. I'm stealing it

 

[JeffM]

Wasn’t mine so steal away.

By the way, I see I missed two details in my proposed proof. I should have imposed an extra condition on k, namely [imath]k \ge m.[/imath]

And of course zermelo’s comment on l and m was pertinent.

 

[chrislav]

I’d cavil a bit about the presentation.

[imath](\ell + m) + n = \ell + (m + n)[/imath] rather than [imath](\ell + m) = n = \ell+ (m + n).[/imath]

The latter statement is not generally true. For example, 3 + 5 = 8, but 8 does not equal 3 + (5 + 8).

Ignoring what is almost certainly a typo, I find the presentation weird. You develop a base case of [imath](\ell + m) + 1 = \ell + (m + 1).[/imath] But then you seemingly ignore it.

[math](\ell + m) + (n + 1) = (\ell + m) + s(n) = s\{(\ell + m) + n\}.[/math]
Good so far.

But then you go [imath]s\{(\ell + m) + n\} = s\{\ell + (m + n)\}[/imath], WHICH IS ASSUMING THAT WHICH IS TO BE PROVED.

This is partly a presentation issue of letting variable names jump around. So we show that

[math](a + b) + 1 = a + (b + 1). \text {\ Then, we let}\\ k \text { be an arbitrary natural number such that }\\ (\ell + m) + k = \ell + (m + k).\\ (\ell + m) + (k + 1) = (\ell + m) + s(k) \text { by definition of successor.}\\ \therefore (\ell + m) + (k + 1) = s\{(\ell + m) + k)\} \text { by Axiom 2.}\\ \therefore (\ell + m) + (k + 1) = s\{ \ell + ( m + k)\} \text { by definition of } k.\\ \therefore (\ell + m) + (k + 1) = \{\ell + (m + k)\} + 1 \text { by definition of successor.}\\ \therefore (\ell + m) + (k + 1) = \ell + \{(m + k) + 1\} \ \because \ (a + b) + 1 = a + (b + 1).\\ \therefore (\ell + m) + (k + 1) = \ell + \{m + (k + 1)\} \ \because \ (a + b) + 1 = a + (b + 1).\\ \text {Thus, by induction, } (\ell + m) + n = \ell + (m + n) \text { for all natural numbers } \ell, \ m, \text { and } m.[/math]
It has been well over 50 years since I studied the use of the Peano Postulates, but my recollection is that you needed to be beyond meticulous. I believe you had the proof in your mind, but I am not satisfied that your presentation will pass muster. But maybe I am just an old fuss-budget.

to show that [math]1\in S[/math]WE must show not only that: [math] (a+b)+1= a+(b+1) [/math].
But also that : [math]1\in N[/math]Because:
[math] S=\{l,m,n\in N|(l+m)+n=l+(m+n)\}[/math]And
For [math]n=1\in S[/math]WE must have:
[math]l,m\in N[/math]And [math] 1\in N[/math]And [math] (l+m)+1=l+(m+1)[/math]Ather wise the whole proof is unfounded

 

[JeffM]

to show that [math]1\in S[/math]WE must show not only that: [math] (a+b)+1= a+(b+1) [/math].
But also that : [math]1\in N[/math]Because:
[math] S=\{l,m,n\in N|(l+m)+n=l+(m+n)\}[/math]And
For [math]n=1\in S[/math]WE must have:
[math]l,m\in N[/math]And [math] 1\in N[/math]And [math] (l+m)+1=l+(m+1)[/math]Ather wise the whole proof is unfounded

I am not quite sure what the purpose of this post is. The point about [imath]l[/imath] and [imath]m[/imath] was specified by Zermelo in the very first response of this thread (post 2) and acknowledged as pertinent in my post 12, the one immediately preceding the quoted post.

The point about the membership of one in the natural numbers needing to be proved verges on the absurd. The fundamental difficulty of answering questions posed here about proofs is that we have at best partial, and usually no, knowledge of the exact axioms and previously proved theorems that the original poster must work with. You seem to be saying that we must reconstruct all that before we can legitimately answer any question about a proof, which would mean in practice that we cannot answer questions about proofs. And it is particularly silly to cavil about whether one is a natural number.

First, this student told us what theorems were expected to be relevant, and those clearly imply that one is a natural number.

Second, we have no idea which formulation of the Peano postulates the student is expected to use. If I remember correctly, that one is a member of the set of natural numbers is an axiom in Peano’s original formulation of his postulates. The whole point of an axiom is that proving it is unnecessary: it is assumed to be true.

Third, my understanding is that most modern formulations of the Peano postulates have as axioms that zero (symbolized as 0) is a member of the set of natural numbers and that every member of the set of natural numbers has a successor, which is also a member of the set. In that ”one” (symbolized as 1) is defined to be the successor of zero and thus is a member of the set of natural numbers.

In other words, the membership of one in the natural numbers is either an axiom or a trivially obvious theorem that the original poster would know already.

 

[chrislav]

You do not cavil , by leaving out one important axiom that:

[math]1\in N[/math]
You cannot prove associativity without that axiom.
Because as i pointed out before:

for [math] n=1\in S\Leftrightarrow [l,m\in N\wedge 1\in N\wedge (l+m)+1=l+(m+1)][/math]Since
[math] S=\{l,m,n\in N|(l+m)+n=l+(m+n)\}[/math]As the OP suggested