Prove ##a\cdot b = b \cdot a ##using Peano postulates

[issacnewton]

Homework Statement

Prove $a\cdot b = b \cdot a$ for $a,b \in \mathbb{N}$ using Peano postulates

Relevant Equations

The book I am using ("The real numbers and real analysis" by Ethan Bloch) defines Peano postulates little differently.

Following is a set of Peano postulates I am using. (Axiom 1.2.1 in Bloch's book)

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

And addition operation is given in Theorem 1.2.5 as follows

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

Multiplication operation is given in Theorem 1.2.6 as follows

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

a. $n \cdot 1 = n$
b. $n \cdot s(m) = (n \cdot m) + n$

I am also going to assume following results for this proof.
Identity law for multiplication for $a\in \mathbb{N}$
$$ a \cdot 1 = a = 1 \cdot a $$

Distributive law
$$ (a + b) \cdot c = a \cdot c + b \cdot c $$

with this background, we proceed to the proof. Let us define a set

$$ G = \{ z \in \mathbb{N} | \mbox{ if } y \in \mathbb{N}, y\cdot z = z \cdot y \} $$

We want to prove that $G = \mathbb{N}$. For this purpose, we will use part 3) of Peano postulates given above. Obviously, $G \subseteq \mathbb{N}$. Since $1 \in \mathbb{N}$ from Peano postulates and for arbitrary $y \in \mathbb{N}$, using Identity law for multiplication, we have $y \cdot 1 = 1 \cdot y$. Hence $1\in G$. Now, suppose $r \in G$. So $r \in \mathbb{N}$ and it follows that

$$ \forall y \in \mathbb{N} \; \left[ y \cdot r = r \cdot y \right] \cdots\cdots (1)$$

Now, let $y \in \mathbb{N}$ be arbitrary. Using addition definition part (a), we have $s(r) \cdot y = (r + 1) \cdot y$. Using Distributive law, we get $s(r) \cdot y = r \cdot y + 1 \cdot y$. Using equation 1 for $y$ and Identity law for multiplication for $y$, we have $s(r) \cdot y = y \cdot r + y$. Finally, using multiplication definition part (b), $s(r) \cdot y = y \cdot s(r)$. Since $y \in \mathbb{N}$ be arbitrary, this means that

$$ \forall y \in \mathbb{N} \; \left[ y \cdot s(r) = s(r) \cdot y \right] $$

Since $s(r) \in \mathbb{N}$, this means that $s(r) \in G$ and using part 3) of Peano postulates given above, $G = \mathbb{N}$. Now, if $a, b \in \mathbb{N}$, we have $b \in G$ and it follows that $a\cdot b = b \cdot a$.

Is this proof valid ?

Thanks

 

[fresh_42]

I see that $y\cdot 1=y$ by the definition of multiplication. But why is $1\cdot y=y$ which you need for the conclusion $1\in G\;?$ Looks as if you had proven this earlier so a reference (number of lemma or whatever) would have been nice, i.e. saying why you are allowed to ...

... assume following results for this proof.
Identity law for multiplication for $a\in \mathbb{N}$
$$ a \cdot 1 = a = 1 \cdot a $$

I am a bit confused among those many elements, $a,b,c,x,y,z,1,r$, and the function $s$ so it is hard to keep track of all the assumed qualifiers they carry with them. And you could have somehow named what you use:

$S1\, : \,\not\exists\,n\in\mathbb{N}\, : \,s(n)=1$
$S2\, : \,s(a)=s(b) \Longrightarrow a=b$
$S3\, : \,(1\in G\subseteq \mathbb{N}\wedge [g\in G\Longrightarrow s(g)\in G])\, \Longrightarrow \,G=\mathbb{N}$

$Aa\, : \,n+1=s(n)$
$Ab\, : \,n+s(m)=s(n+m)$

$Ma\, : \,n\cdot 1=n$
$Mb\, : \,n\cdot s(m)=(n\cdot m)+n$

$Lc\, : \,n\cdot 1= n = 1\cdot n$ by theorem ... in the book

$Rd\, : \,(y+x)\cdot z=y\cdot z+x \cdot z$ by theorem ... in the book

A side note: Many proofs about natural numbers are indirect by assuming a minimal counterexample and showing that there is no such number.

Let's see if I can sort your ideas:

$1\in G$ by $(Lc)$ so $G\neq \emptyset.$ Assume $G\subsetneq \mathbb{N}.$ Then there is a $y\in G$ and $s(y)\not\in G.$ It therefore exists a $z\in \mathbb{N}$ such that $s(y)\cdot z\neq z\cdot s(y).$ Now
\begin{align*}
z\cdot s(y)&\stackrel{(Mb)}{=} (z\cdot y)+ z\stackrel{(Ma)}{=}z\cdot y + z\cdot 1\stackrel{(y\in G)}{=}y\cdot z+ z\cdot 1\stackrel{1\in G}{=}y\cdot z +1\cdot z \stackrel{(Rd)}{=}(y+1)\cdot z \stackrel{(Aa)}{=}s(y)\cdot z
\end{align*}
which contradicts $s(y)\not\in G.$

Or positively written without the minimality condition:
\begin{align*}
1&\stackrel{(Lc)}{\in} G\subseteq \mathbb{N}\\
\,y\in G &\Longrightarrow z\cdot s(y)\stackrel{(Mb)}{=}\ldots \stackrel{(Aa)}{=}s(y)\cdot z\\&\Longrightarrow s(y)\stackrel{(def.)}{\in} G \stackrel{(S3)}{\Longrightarrow } G=\mathbb{N}
\end{align*}

 

[issacnewton]

fresh_42, thanks for your input. I am learning this stuff on my own. so, it would be difficult to write as compact proofs as you did. Also, for somebody who is learning this topic on his or her own, detailed explanation would be helpful. All future readers of my post will be able to understand easily.

 

[fresh_42]

fresh_42, thanks for your input. I am learning this stuff on my own. so, it would be difficult to write as compact proofs as you did. Also, for somebody who is learning this topic on his or her own, detailed explanation would be helpful. All future readers of my post will be able to understand easily.

It's a matter of practice and I guess I have practiced a lot over the years. And, it took me quite a while and several edits before it appeared in the version you see now. That's the point: fight yourself through a proof and if you are finished, reconsider it and look at the points you used and those you did not use.

Don't get me wrong. You are doing fine (!) and there are no logical mistakes in what you post. I only wrote a version to show you what it could look like.