proof by induction that every non-zero natural number has a predecessor

Question

I am trying to prove by induction that every non-zero natural number has at least one predecessor. However, I don't know what to use as a base case, since 0 is not non-zero and I haven't yet established that 1 is the number following zero.

My axioms are:

1. $0$ is a natural number.
2. if $b$ is a natural number then $S(b)$ is also a natural number.
3. $0$ is not a successor of any natural number.
4. different numbers have different successors.

Any advice?

Answer 1

The fact that every number is either 0 or a successor follows almost embarrassingly quickly from induction on the predicate $$P(x) \equiv (x = 0 ) \lor (\exists y)[x = S(y)].$$

Clearly $P(0)$ holds. Also $P(S(y))$ holds for all $y$, so $(\forall y)[P(y) \to P(S(y))]$ also holds. Now apply induction.

As you can see, the only axiom that is required here is the induction axiom for $P(x)$, along with usual first-order logic. The numerical axioms of $PA^{-}$ are entirely irrelevant.

Answer 2

Hint: Let $P(n) ={}$ "all numbers $<n$ have a predecessor". Then $P(0)$ is true (as there are no numbers $< 0$. I'm sure you can do the induction step.

Answer 3

Proof of Existence: Let us assume that it was already shown that $(\forall n)((n\ \in\ \omega)\ \ \rightarrow\ \ (n^+\ \neq\ 0))$ which is another way of saying that the natural number $0$ has no immediate predecessor in $\omega$. So,

     what about the nonzero natural numbers---Do they have an immediate predecessor?  

Hence, it suffices only to show that:

Each nonzero natural number has an immediate predecessor in $\omega$.

To this end, we conduct induction as follows.

We define a set $M\ \subseteq\ \omega$ consisting of only those nonzero natural numbers which has an immediate predecessor, i.e, $$x\ \in\ M\ \ \leftrightarrow\ \ (x\ \in\ \omega)\ \land\ ((\exists y)(y\ \in\ \omega)\ \ \land\ \ (x\ =\ y^+)\ \land\ (x\ \neq\ \varnothing)).$$Next, define the set $N\ \subseteq\ \omega$ by $N\ =\ M\ \cup\ \{\varnothing\}$. Clearly, by definition of $N$ we have $\varnothing\ \in\ N$. Let $n$ be any non-empty element of $N$ (i.e., $n\ \in\ M$). Then $(n\ \in\ \omega)\ \land\ ((\exists m)(m\ \in\ \omega)\ \land\ (n\ =\ m^+)\ \land\ \ (n\ \neq\ 0))$ holds. But then it follows immediately that: $$(n^+\ \in\ \omega)\ \ \land\ \ ((\exists (m^+)^+)((m^+)^+\ \in\ \omega)\ \ \land\ \ (n^+\ =\ (m^+)^+)\ \ \land\ \ (n^+\ \neq\ 0))$$also holds. This tells us precisely, that $n^+\ \in\ N$ whenever $n\ \in\ N$. Thus, we have shown that the set $N\ =\ M\ \cup\ \{0\}$ is an inductive subset of $\omega$. Therefore, by the Principle of Finite Induction, $N\ =\ \omega$. This complete the Existence part of non-zero natural numbers having an immediate predecessor (or just predecessor).

Predecessors are unique too! This follows from the uniqueness of successors.