Prove if $x \neq 1$ then there exists exactly one $u$ such that $x=u'$

Question

While I'm reading E. Landau's Grundlagen der Analysis (tr. Foundations of Analysis, 1966), I couldn't understand the proof of Theorem 3 at the segment of Natural Numbers which I've quoted below.

Theorem 3: If
$$x \neq 1$$ then there exists one (hence, by Axiom 4, exactly one) $u$ such that
$$x = u'$$ Proof: Let $\mathbb{S}$ be the set consisting of the number $1$ and of all those $x$ for which there exists such a $u$. (For any such $x$, we have of necessity that
$$x \neq 1$$ by Axiom 3.)
I) $1$ belongs to $\mathbb{S}$.
II) If $x$ belongs to $\mathbb{S}$, then, with $u$ denoting the number $x$, we have
$$x'=u'$$
so that $x'$ belongs to $\mathbb{S}$.
By Axiom 5, $\mathbb{S}$ therefore contains all the natural numbers. $\square$

Sir Landau refers to the Axioms of Peano on proof text. Can someone explain what's going on?

Answer 1

Here the axioms for $\mathbb N$ as of set natural numbers probably take the shape:

• $1\in\mathbb N$
• there is an injective function $\mathbb N\to\mathbb N$ denoted by $x\mapsto x'$
• no $x\in\mathbb N$ exists with $1=x'$
• If $S\subseteq\mathbb N$ satisfies the conditions $1\in S$ and $x\in S\implies x'\in S$ for every $x\in S$ then $S=\mathbb N$.

In the proof that you quote it is proved that the set $\mathbb S$ (as defined in your question) satisfies these conditions, justifying the conclusion that $\mathbb S=\mathbb N$.

So if $x\in\mathbb N$ and $x\neq1$ then $x\in\mathbb S$ and $x\neq 1$, which means exactly that $x=u'$ for some $u\in\mathbb N$.

---

edit:

Let $\mathbb S\subseteq\mathbb N$ with: $$\mathbb S=\{1\}\cup\{x\in\mathbb N\mid x=u'\text{ for some }u\in\mathbb N\}$$

Then $1\in\mathbb S$ so in order to prove that $\mathbb S=\mathbb N$ it is enough to prove that $x'\in\mathbb S$ for every $x\in\mathbb S$.

Note now that it is immediate that we have $x'=u'$ for some $u\in\mathbb N$.

For which $u\in\mathbb N$ then?... Well, for $u:=x$.

Answer 2

Everybody describes the Peano axioms in slightly different ways, so you should probably check earlier in the text to see exactly how Landau is numbering them.

But the basic notion is that a set $N$ endowed by a "successor" mapping $S:N\to N$ (which Landau is calling $n\mapsto n'$) is a natural number system if it obeys the following axioms:

• There is an element $0\in N$ such that $0\notin \mathrm{Rng}\, S$
• $S$ is injective
• If $A$ is a set such that $0\in A$ and $S(A)\subset A$, then $A=N$.

Answer 3

The author wants to prove that the set $\text {Suc}$ of numbers that are successors of some number [this means to say that $x=u'$, for some $u$] contains all numbers except $1$ (by Axiom 3 [page 2], $1$ is not a successor)..

In order to do this, he consider [page 3] the set $\mathfrak S = \text {Suc} \cup \{ 1 \}$, i.e. the set of all numbers that are successors plus the number $1$.

Then he use the Induction axiom to prove that $\mathfrak S$ is equal to $\mathbb N$.

Conclusion : $\text {Suc} = \mathbb N \setminus \{ 1 \}$.

The Induction axioms says :

"Let there be given a set $\mathfrak M$ of natural numbers, with the following properties:

I) $1$ belongs to $\mathfrak M$.

II) if $x$ belongs to $\mathfrak M$ then so does $x'$.

Then $\mathfrak M$ contains all the natural numbers."

The proof runs as follows :

I) $1 ∈ \mathfrak S = \text {Suc} \cup \{ 1 \}$ by construction.

II) if $x ∈ \mathfrak S$, then (irrespective of the fact that $x=1$ or $x$ is a successor) we have that $x′$ is a successor : obviously, it is the successor of $x$.

This means that $x′ ∈ \text {Suc}$ and thus $x′ ∈ \mathfrak S$.

Then, by Induction axiom, the set $\mathfrak S$ contains all the natural numbers.