3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm just curious: if you say you've proven that 0 has no predecessor, how did you do this? As far as I know, this usually is one of the Peano axioms and isn't something you can prove. In case you can read dutch, I'd recommend math.ru.nl/~keune/Getallen/Getallench2.xht#x10-150002 to answer your questions. I think all answers are in there. $\endgroup$ – HSN Jun 21 '13 at 8:12
  • $\begingroup$ I;m afraid I don't read dutch. This is how I prove that $0$ has no predecessor: The Peaono Axioms I'm using say that $0$ isn't a successor of any natural number, so if $0$ has a predecessor $x \in \mathbb{N}$, then $\sigma(x)=0$, which contradicts the axiom above. $\endgroup$ – Bilbo Jun 21 '13 at 8:21
  • $\begingroup$ @Bilbo I would be very surprised if most of this material could not be found via google, coming up with various free sources in English, such as at Wikipedia. Have you tried web search and could not find these topics? $\endgroup$ – coffeemath Jun 21 '13 at 11:55
  • $\begingroup$ I've just tried searching for it in google and all I got was wikipedia, an article where the propositions mentioned above are left without proofs, and my post. $\endgroup$ – Bilbo Jun 21 '13 at 15:45
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your help. I like your answer a lot. I think there's a typo in the definition of addition . Shouldn't there always be $+'$ instead of $k'$? $\\$ As for $4)$ - can I use induction on $p$ ? (but I'm not sure how) $\endgroup$ – Bilbo Jun 25 '13 at 6:29
  • 1
    $\begingroup$ For 4), you're right about induction on $p$. Showing that $n \leq m$ implies $n+p \leq m+p$ can be done by inducting on $p$. For $p=0$, this is easy and if the inequality holds for $p$, then for some $p'$, $n+p+p'=m+p$ and so $\sigma(n+p+p')=\sigma(m+p)$ which is just $n+ \sigma(p)+p'=m+\sigma(p)$ so that $n+ \sigma(p) \leq m+ \sigma(p)$. For the other direction, you get something like $(n+p)+p'=(m+p)$. If $p=0$, we are done. Suppose we have $(n+\sigma(p))+ p'=(m+\sigma(p))$. Then this is just $\sigma((n+p)+p')=\sigma(m+p)$ and so $(n+p)+p'=m+p$. Then by inductive assumption, $n \leq m$. $\endgroup$ – Alexander Jun 25 '13 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.