Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to prove that $\nexists\; \beta\in\mathbb N$ such that $\alpha<\beta<\alpha+1$ for all $\alpha\in\mathbb N$. I just want to use the Peano axioms and $+$ and $\cdot$

If $\alpha<\beta$ then there is a $\gamma\in\mathbb N$ such that $\beta=\alpha+\gamma$.

If $\beta<\alpha+1$ then there is a $\delta\in\mathbb N$ such that $\alpha+1=\beta+\delta$.

Now I tried to equalize the two equations and I got $\gamma\le0$ which is contradictory to $\gamma\in\mathbb N$. But I used $\alpha+1-\delta=\beta$ in which the $-$ is problematic because I am not allowed to use it.

Anbody knows a better solution? Thanks a lot!

share|improve this question
    
So you have from the definition of addition that $S(\alpha)=\alpha+1$ and so if $\beta > \alpha$ then $\exists \gamma$ s.t. $\alpha+\gamma=\beta$ so then if $\gamma =1$ then$\beta=\alpha+1$ and if $\gamma > 1$ then $\beta > \alpha+1$ which are both contradictions –  hmmmm Oct 20 '12 at 17:22
add comment

3 Answers

Fix $\alpha\in\Bbb N$; the result will follow almost immediately if you can prove that if $\alpha<\beta$, then $S\alpha\le\beta$.

Let $A=\{\gamma\in\Bbb N:\gamma=0\text{ or }S\alpha\le\alpha+\gamma\}$; clearly $0\in A$. Suppose that $\gamma\in A$. If $\gamma=0$, then $S\gamma=1$, and $S\alpha=\alpha+1=\alpha+S\gamma$, so $S\gamma\in A$. Otherwise, $$S\alpha\le\alpha+\gamma<\alpha+\gamma+1=\alpha+S\gamma\;,$$ and again we conclude that $S\gamma\in A$. The induction axiom now implies that $A=\Bbb N$.

Now suppose that $\alpha<\beta$. Then $\beta=\alpha+\gamma$ for some $\gamma\in\Bbb N\setminus\{0\}$, and it follows from the previous paragraph that $S\alpha\le\alpha+\gamma=\beta$.

share|improve this answer
add comment

I'm not sure if the following is allowed but:

Inserting the first equation in the second we get: $\alpha+1=\alpha+\gamma+\delta$.

Now we can substract $\alpha$ at both sides to get $1=\gamma+\delta$, which is a contradiction.

share|improve this answer
    
I don't think that will be allowed as subtraction is not defined –  hmmmm Oct 20 '12 at 17:31
1  
@hmmmm : In this case subtraction is just injectivity of the successor function. –  Julian Kuelshammer Oct 20 '12 at 17:34
    
Sure, just because the op seemed not to want to use subtraction explicitly –  hmmmm Oct 20 '12 at 17:48
add comment

I assume that $0\notin \mathbb N$ and $x<y:\Leftrightarrow \exists z\colon x+z=y$.

You may already have proved $$\tag1\forall x,y\colon \exists z\colon x+y=S(z)$$ and $$\tag2 \forall x,y,z\colon (x+y=x+z\rightarrow y=z).$$

Now the assumption $\alpha<\beta \land \beta<\alpha+1$ implies that there are $x,y$ such that $\alpha+x=\beta$ and $\beta+y=S(\alpha)$, hence $\alpha+x+y=S(\alpha)$. Using $(1)$, there exists $z$ such that $\alpha+1=\alpha+S(z)=$ and by $(2)$, we conclude $1=S(z)$ contrary to $\neg\exists x\colon S(x)=1$.


In case you don't have $(1)$ or $(2)$ yet, they are readily proved by induction:

  • If $x=1$, then $x+y=S(y)$. For the induction step, $S(x)+y=S(x+y)$ gives us $z=x+y$ as candidate immediately.
  • If $x=1$, then $S(y)=x+y=x+z=S(z)$, i.e. $S(y)=S(z)$, implies $y=z$. Otherwise $S(x+y)=S(x)+y=S(x)+z=S(x+z)$ implies $x+y=x+z$ and thus $x=z$ by induction hypothesis.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.