Successor Mapping of Peano Structure has no Fixed Point

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\PP = \struct {P, s, 0}$ be a Peano structure.


Then:

$\forall n \in P: \map s n \ne n$

That is, the successor mapping has no fixed points.


Proof

Let $T$ be the set:

$T = \set {n \in P: \map s n \ne n}$

We will use Peano's Axiom $\text P 5$: Principle of Mathematical Induction to prove that $T = P$.


Part $1$: $0 \in T$

From Peano's Axiom $\text P 4$: $0 \notin \Img s$, a fortiori:

$\map s 0 \ne 0$

Hence $0 \in T$.

$\Box$


Part $2$: $n \in T \implies \map s n \in T$

Let $n \in T$.

Let $m = \map s n$.

Then $n \ne m$, as $\map s n \ne n$.


Aiming for a contradiction, suppose $m \notin T$.

That is:

$\map s m = m$

Then that would mean:

$\map s n = \map s m = m$

But from Peano's Axiom $\text P 3$: $s$ is injective, $s$ is injective.

From this contradiction, it follows that $m \in T$.


Hence we have that:

$n \in T \implies \map s n \in T$

$\Box$


Conclusion

By Peano's Axiom $\text P 5$: Principle of Mathematical Induction, we conclude that $T = P$.

From the definition of $T$, the result follows.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Successor_Mapping_of_Peano_Structure_has_no_Fixed_Point&oldid=570184"