Fixed Point of Idempotent Mapping

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $f: S \to S$ be an idempotent mapping.

Let $f \left[{S}\right]$ be the image of $S$ under $f$.

Let $x \in S$.


Then $x$ is a fixed point of $f$ if and only if $x \in f \left[{S}\right]$.


Proof

Necessary Condition

Let $x$ be a fixed point of $f$.

Then:

$f \left({x}\right) = x$

and so by the definition of image of mapping:

$x \in f \left[{S}\right]$

$\Box$


Sufficient Condition

Let $x \in f \left[{S}\right]$.

Then by the definition of image:

$\exists y \in S: f \left({y}\right) = x$

Then:

\(\displaystyle x\) \(=\) \(\displaystyle f \left({y}\right)\)
\(\displaystyle \implies \ \ \) \(\displaystyle f \left({x}\right)\) \(=\) \(\displaystyle f \left({f \left({y}\right)}\right)\) Definition of Mapping
\(\displaystyle \) \(=\) \(\displaystyle f \left({y}\right)\) Definition of Idempotent Mapping
\(\displaystyle \) \(=\) \(\displaystyle x\)


Thus by definition $x$ is a fixed point of $f$.

$\blacksquare$