Could you tell me how to prove the following?
$(1)$ There exists the unique operation of addition :
$+ \ : \ \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that $n+0=n$ and $n+ \sigma(m) = \sigma(n+m)$ ($\sigma$ – successor)
I've already proved associativity and commutativity of addition.
$(2) \ \ \forall n,m \in \mathbb{N} \ \ \exists p \in \mathbb{N} : \ m=n+p$ or $n=m+p$
$(3)$ The relation $\le$ defined by $n \le m \iff \exists p\in \mathbb{N}:p+n=m$ is a total order.
(Although I can prove that every positive natural number has a predecessor.)
$(4) \forall m,n,p \in \mathbb{N}:n\le m \iff n+p \le m+p$
(I've proved that $0$ has no precedessor – does that suffice to show that $0$ is the least element in $\mathbb{N}$?)
$(5) \ \ \mathbb{N} $ does not have the greatest element – does that follow from the second Peano axiom saying that every natural number has a successor?
$(6)$ Every nonempty subset of $\mathbb{N}$ has a smallest element.
$(7) \forall n,m \in \mathbb{N} \ \ \ n\le m \Rightarrow \sigma(n) \le \sigma(m)$
(Would this follow from (4) and the little fact I used for proving commutativity of addition: $n+\sigma(m)=\sigma(n)+m$ and putting $n=0$?)
$(8)$ There exists the unique operation of multiplication:
$\bullet: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that $\forall n \in \mathbb{N} n \cdot 0 = 0$ and $\forall n, m \in \mathbb{N}: n \cdot \sigma(m)=n \cdot m + n$
$(9) \ \ \forall n \in \mathbb{N}: 0 \cdot n = 0$
I've already proved associativity, commutativity, etc. of multiplication.
Could you help me?
Thank you.
Best Answer
1) Define $n+0=n$. Assume $n+m$ has been defined. Then define $n+\sigma(m)=\sigma(n+m)$. This defines addition on all ordered pairs of naturals. Suppose there was some alternate addition $+'$ satisfying the above properties. We notice that for pairs $(n, 0)$, $n+0=n+'0$. Assume that for each $n$, we have shown that $n+k=n+'k$ for all $0 \leq k \leq m$. Then $n+\sigma(k)=\sigma(n+k)=\sigma(n+'k)=n+'k$ and so we see that $+, +'$ are the same for all pairs. This gives uniqueness. You will want to prove distributivity of addition for later parts. Try to get this via induction.
2) Pick any $n \in \mathbb{N}$. We proceed by induction on $m$. If $m=0$, then $p=m$. If there exists $p$ so that $n+p=m$, then we observe that $n+ \sigma(p)=\sigma(n+p)=\sigma(m)$. If there exists $p$ so that $n=p+m$, then if $p=0$, we have $n+1=\sigma(m)$. If $p \neq 0$, then the number we need is the natural whose successor is $p$. Try proving that if $p \neq 0$, it has a predecessor. (Hint: induction!)
3) This relation is clearly reflexive. For anti-symmetry, if there exists $p$ so that $a+p=b$ and $p'$ so that $b+p'=a$, then $b+p+p'=b$. You should be able to show this implies $p+p'=0$. If $p \neq 0$ or $p' \neq 0$, this should give you a predecessor of $0$, which is a contradiction and shows that $p=p'=0$ and so $a=a+p=b$. Transitivity is easy, and totality is part 2).
4) This is not hard. Try to work it out for yourself.
5) Your intuition is correct. You can easily show that $\sigma (n) \geq n$ but $n \neq \sigma(n)$.
6) If this were not the case, you would have an infinite descending chain in $\mathbb{N}$. To get a contradiction, you need to show that for each $m \in \mathbb{N}$, there are only finitely many naturals less than $m$. You can do this by induction.
7) You are correct.
8) This is somewhat similar to addition. Define inductively and use your definition to prove what you need.
9) You can do this by induction.