Prove property involving successor function

53 Views Asked by At

Let $a \in \mathbb{N} $ and $s: \mathbb{N} \longrightarrow \mathbb{N} $ be the successor function defined in Peano postulates. Then, prove the following

$$ 1 + a = s(a) = a + 1 $$

Now, there is a theorem, which says that there is a unique binary operation $+: \mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N} $ that satisfies the following two properties for all $n, m \in \mathbb{N} $.

$$ n + 1 = s(n)$$ $$ n + s(m) = s(n + m) $$

So, using this theorem, its trivial that $ a + 1 = s(a)$. I can not assume Commutative Law for Addition. But I can assume Cancellation Law for Addition and Associative Law for Addition. So, how can I proceed ?

1

There are 1 best solutions below

0
On BEST ANSWER

Doing induction on the natural numbers means exploiting the fact, that any subset $A\subseteq\mathbb N$, which contains $0$ and is closed under successors, is already the whole of $\mathbb N$.

So let us consider the subset $A = \{a \in \mathbb{N} \mid 1+a = s(a) = a+1\}$.

For $a=0$ you find by the definition of the maps $1+\bullet:\mathbb{N}\rightarrow\mathbb{N}$ and $0+\bullet:\mathbb{N}\rightarrow\mathbb{N}$ that $$1+0 = 1 = s(0) = 0+1,$$ hence $0 \in A$.

The second condition on $+$ gives you $$1+s(a) = s(1+a) \overset{ind}{=}s(s(a)) = s(a)+1.$$ This shows $s(a) \in A$ for any $a\in A$.

This shows $A=\mathbb{N}$.