# Existence of One-Sided Inverses on Natural Numbers whose Composition is Identity Mapping

Jump to navigation
Jump to search

## Theorem

Consider the set of natural numbers $\N$.

There exist mappings $f: \N \to \N$ and $g: \N \to \N$ such that:

- $g \circ f = I_\N$

where:

- $\circ$ denotes composition of mappings
- $I_\N$ denotes the identity mapping on $\N$

such that neither $f$ nor $g$ are permutations on $\N$.

## Proof

Let $f: \N \to \N$ be the mapping defined as:

- $\forall x \in \N: \map f x = x + 1$

Let $g: \N \to \N$ be the mapping defined as:

- $\forall x \in \N: \map g x = \begin {cases} x - 1 & : x > 0 \\ 0 & : x = 0 \end {cases}$

It is apparent by inspection that:

- $f$ is injective

but

- $f$ is not surjective, as there exists no $x \in \N$ such that $x + 1 = 0$

It is also apparent by inspection that:

- $g$ is surjective

but

- $g$ is not injective, as $\map g 0 = \map g 1 = 0$

Thus neither $f$ nor $g$ are bijective, and hence not permutations on $\N$.

However, it is also apparent by inspection that:

- $g \circ f = I_\N$

$\blacksquare$

## Sources

- 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.17 \ \text {(b)}$