Prove ##(a+b) + c = a + (b+c)## using Peano postulates

issacnewton
Messages
1,035
Reaction score
37
Homework Statement
Prove ##(a+b) + c = a + (b+c)## using Peano postulates
Relevant Equations
Peano postulates
I have to prove the associative law for addition ##(a+b) + c = a + (b+c)## using Peano postulates, given that ##a, b, c \in \mathbb{N}##. Now define the set

$$ G = \{ z \in \mathbb{N} |\forall\; x, y \in \mathbb{N} \quad (x + y) + z = x + (y + z) \} $$

Obviously, ## G \subseteq \mathbb{N} ##. Now ## 1 \in \mathbb{N} ## according to Peano postulates. Let ##x, y \in \mathbb{N} ## be arbitrary.
Using the way addition function is defined using the successor function, we have ## (x + y) + 1 = s(x + y) ##. But ##s(x + y) = x + s(y) ## and ## s(y) = y + 1##. So, we have ##(x + y) + 1 = x + s(y) = x + (y + 1)##. This means that ## 1 \in G##.

Now, suppose ##r \in G##. This means that ##r \in \mathbb{N} ## and

$$ \forall\; x, y \in \mathbb{N} \quad (x + y) + r = x + (y + r) $$

Suppose ##x, y \in \mathbb{N} ## be arbitrary. Since, ##r \in G##, we have

$$ (x + y) + r = x + (y + r) $$
$$ \therefore s((x + y) + r) = s( x + (y + r) ) $$

Using definition of addition function, we have

$$ \therefore (x + y) + s(r) = x + s(y + r) = x + (y + s(r)) $$
$$ \therefore (x + y) + s(r) = x + (y + s(r)) $$

From definition of successor function, ## s(r) \in \mathbb{N} ##. Hence ##s(r) \in G##. So, using Peano postulates, ## G = \mathbb{N}##.

Since ##a, b, c \in \mathbb{N}##, we have ## c \in G##. It follows that ##(a+b) + c = a + (b+c)##. Is this proof correct ?
 
Physics news on Phys.org
Do you define ##\mathbb{N}## such that 0 is an element? If so, you didn't show ##0 \in G##, so you can't conclude ##G = \mathbb{N}##.
 
No, I define ##\mathbb{N}## such that ##1 \in \mathbb{N}##. Following is a set of Peano postulates I am using.

There exists a set ##\mathbb{N}## with an element ##1 \in \mathbb{N}## and a function ##s: \mathbb{N} \rightarrow \mathbb{N} ## that satisfy the following three properties.

1) There is no ##n \in \mathbb{N}## such that ##s(n) = 1##

2) The function ##s## is injective.

3) Let ##G \subseteq \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} ##

I just got in reply for my post. Is this because this is a physics forum and very few mathematicians visit this forum ?
 
There are a number of mathematicians around here. I don’t know why none replied to your question earlier.
 
So vela, is the proof correct ? Can you please comment ?
 
Looks good to me.
 
  • Like
Likes issacnewton
issacnewton said:
No, I define ##\mathbb{N}## such that ##1 \in \mathbb{N}##. Following is a set of Peano postulates I am using.

There exists a set ##\mathbb{N}## with an element ##1 \in \mathbb{N}## and a function ##s: \mathbb{N} \rightarrow \mathbb{N} ## that satisfy the following three properties.

1) There is no ##n \in \mathbb{N}## such that ##s(n) = 1##

2) The function ##s## is injective.

3) Let ##G \subseteq \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} ##

I just got in reply for my post. Is this because this is a physics forum and very few mathematicians visit this forum ?
It was helpful to me that you posted the set of Peano postulates that you were using.

I agree with @vela: Your proof looks good.
 
issacnewton said:
So vela, is the proof correct ? Can you please comment ?
I tried to follow your proof, but I couldn't figure out what is the definition of the binary operation ##+##?
 
PeroK, sorry for late reply. I am not getting email notifications. I will have to check settings. I am using the book "The real numbers and real analysis" by Ethan Bloch . He uses the following theorem as the definition of +.

There is a unique binary operation ##+: \mathbb{N} \times \mathbb{N} \to \mathbb{N} ## that satisfies the following two properties for all ##n, m \in \mathbb{N} ##

a. ## n + 1 = s(n) ##
b. ## n + s(m) = s(n + m) ##
 
  • #10
issacnewton said:
Homework Statement: Prove ##(a+b) + c = a + (b+c)## using Peano postulates
Relevant Equations: Peano postulates

I have to prove the associative law for addition ##(a+b) + c = a + (b+c)## using Peano postulates, given that ##a, b, c \in \mathbb{N}##. Now define the set

$$ G = \{ z \in \mathbb{N} |\forall\; x, y \in \mathbb{N} \quad (x + y) + z = x + (y + z) \} $$

Obviously, ## G \subseteq \mathbb{N} ##. Now ## 1 \in \mathbb{N} ## according to Peano postulates. Let ##x, y \in \mathbb{N} ## be arbitrary.
Using the way addition function is defined using the successor function, we have ## (x + y) + 1 = s(x + y) ##. But ##s(x + y) = x + s(y) ## and ## s(y) = y + 1##. So, we have ##(x + y) + 1 = x + s(y) = x + (y + 1)##. This means that ## 1 \in G##.

Now, suppose ##r \in G##. This means that ##r \in \mathbb{N} ## and

$$ \forall\; x, y \in \mathbb{N} \quad (x + y) + r = x + (y + r) $$

Suppose ##x, y \in \mathbb{N} ## be arbitrary. Since, ##r \in G##, we have

$$ (x + y) + r = x + (y + r) $$
$$ \therefore s((x + y) + r) = s( x + (y + r) ) $$

Using definition of addition function, we have

$$ \therefore (x + y) + s(r) = x + s(y + r) = x + (y + s(r)) $$
$$ \therefore (x + y) + s(r) = x + (y + s(r)) $$

From definition of successor function, ## s(r) \in \mathbb{N} ##. Hence ##s(r) \in G##. So, using Peano postulates, ## G = \mathbb{N}##.

Since ##a, b, c \in \mathbb{N}##, we have ## c \in G##. It follows that ##(a+b) + c = a + (b+c)##. Is this proof correct ?
Algebraically this is much simpler, you just have to prove that every non-zero natural is an nth successor of 1. Prove that 1 under the recurrence definition of addition is associative with itself, prove that the successor of a number is just it + 1 (which is either trivial or definition). As a bonus you can also conclude commutativity which is nice.
(This argument involves some additional things, but I'm just mentioning the main ideas, it'll probably be simple to know how to proceed knowing this).

Essentially you're just proving that the naturals are the free monoid with 1 generator (up to isomorphism).
 
Back
Top