No Natural Number between Number and Successor

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\N$ be the natural numbers.

Let $n \in \N$.

Then no natural number $m$ exists strictly between $n$ and its successor:

$\neg \exists m \in \N: \paren {n < m < n^+}$


That is:

If $m \le n \le m^+$, then $m = n$ or $m = n^+$.


Proof using Minimal Infinite Successor Set

Aiming for a contradiction, suppose such an ordinal $y$ exists.


Then, by Ordering on Ordinal is Subset Relation:

$x \in y$

and from Transitive Set is Proper Subset of Ordinal iff Element of Ordinal:

$y \in x^+$


Applying the definition of a successor set, we have:

$y \in x \lor y = x$

But this creates a membership loop, in that:

$x \in y \in x \lor x \in x$


By No Membership Loops, we have created a contradiction.

The result follows from Proof by Contradiction.

$\blacksquare$


Proof using Von Neumann Construction

Let $\N$ be defined as the von Neumann construction $\omega$.

By definition of the ordering on von Neumann construction:

$m \le n \iff m \subseteq n$

From Von Neumann Construction of Natural Numbers is Minimally Inductive, $\omega$ is minimally inductive class under the successor mapping.


The result follows from the Sandwich Principle:

$\forall m, n \in \omega: m \subseteq n \lor n \subseteq m$

$\blacksquare$