3

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?

Asaf Karagila
  • 393,674
Adam
  • 3,422
  • 1
  • 33
  • 50
  • 2
    What are your axioms? What is your structure? You can't prove things out of thin air. – Asaf Karagila Jun 23 '14 at 17:05
  • 1
    I am using Peano axioms. – Adam Jun 23 '14 at 17:06
  • 1
    Why not establish 1 is the number following zero as your base case? Then, assume that every non-zero natural number up to $n$ has at least one predecessor. Consider $n+1$. You know $n+1$ is preceded by $n$ by the Peano axioms for the natural numbers, hence $n+1$ has at least one predecessor. – SlipEternal Jun 23 '14 at 17:08
  • 1
    @AsafKaragila: unfortunately the fact that all non-zero numbers are successors is not among the axioms I am using, what I have instead is that 0 is a natural number and if b is a natural number than the succesor of b is also a natural number. Is that any help? – Adam Jun 23 '14 at 17:11
  • I will try next time I am posting something. Any idea how to deal with this situation? – Adam Jun 23 '14 at 17:15
  • @Asaf: the axiom you have in mind is not, in fact, one of the usual axioms of Peano arithmetic, nor it is one of the standard second-order Peano axioms. I guess this is because it is a straightforward consequence of induction. – Carl Mummert Jun 23 '14 at 17:19
  • @AsafKaragila: I edited my question. Any idea now? – Adam Jun 23 '14 at 17:22
  • Any transitive set with the successor function being 'send to successor' would satisfy your axioms. I'm assuming you left induction out of the list? –  Jun 23 '14 at 17:28
  • yes, I forgot to include induction – Adam Jun 23 '14 at 17:29
  • Ok, induction is fundamental because otherwise $\omega\cup{\omega}$ would satisfy your axioms where $S(\omega)=\omega$. But $\omega$ has no predecessor. –  Jun 23 '14 at 17:33

3 Answers3

7

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.

Carl Mummert
  • 81,604
  • 1
    A bit technical answer. – leo Jun 23 '14 at 17:29
  • 1
    Note: We also have $$P(x) \equiv x \ne 0 \implies \exists y[S(y)=x].$$ – Dan Christensen Jun 23 '14 at 22:49
  • 1
    @leo: If you're interested in proofs, you should learn a bit of logic. I'm almost a complete novice, but what Carl said is not hard to understand: $\operatorname{P}(x)$ is true iff $x=0$ or there exists some $y$ $(∃y)$ who's successor is $x$ $(x=\operatorname{S}(y))$. It can be restated as Dan said: If $x≠0$, $x$ is the successor of some number $y$ (i.e. $x$ has a predecessor) – Zaz Sep 05 '15 at 17:54
  • To complete the proof, note that since $0$ is not the successor of another natural number, there is no natural number $x$ with the following property:$$ (x = 0)\land (\exists y:x = S(y))$$ This is why $${x\in\mathbb{N}:P(x)}=\mathbb{N}$$ implies that "every number is either $0$ or a successor". – Filippo Oct 09 '21 at 18:05
0

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.

Foster Antony
  • 87
0

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.

martini
  • 84,101