Boolean endomorphisms vs endofunctions on finite sets

Question

I stumbled upon a funny fact:

Let $\mathbf{Bool} = \{0, 1 \}$. For all functions $f: \mathbf{Bool} \to \mathbf{Bool}$ it is the case that $f^3 = f$.

This got me excited and I was wondering whether there's anything similar for endofunctions on finite sets, but I quickly realised it does not generalise (at least in the straightforward way) to any larger cases.

So, I have two questions:

1. Does this generalise in some way to endomorphisms on larger finite sets?
2. Is there any "deeper" reason why the fact holds for boolean endomorphisms?

Thanks!

Answer 1

If we restrict our attention to bijections $f: S\rightarrow S$ of a set $S$ of size $n$, then elementary group theory tells us that $f^{n!+1} = f$.

While it is not true that for every function $f:S\rightarrow S$ there is some $m$ such that $f^m = f$, it is true that for every such function there are some $m \neq k$ and $k < n$ so that $f^m = f^k$. The reason for this is that $f^k$ must be a bijection on $f^k(S)$ for some $k < n$ (because $f^{p+1}(S) \subseteq f^p(S)$, and this can only be decreasing for so long before it is constant). Then apply the above observation to $f^k$.

Answer 2

For this answer, let $X$ be a set with $n$ elements. A little bit of group theory shows us that, for any bijection $f: X\mapsto X$, $f^{n!+1} = f$ (because $f^{n!} = \operatorname{id}_X$). However, for $n>2$, this does not hold for arbitrary functions. We can see why by considering the restriction of $f$ onto its image.

If the restriction $f|_{\operatorname{im}f}$ is bijective, then we have that, if $m=|\operatorname{im}f|$, $(f|_{\operatorname{im}f})^{m!} = \operatorname{id}_{\operatorname{im} f}$. Since $m!|n!$, and, for any $a$, $f(a) \in \operatorname{im} f$, we then have that $f^{n!+1} = f$.

The reason that this holds for any $f: \mathbf{Bool} \mapsto \mathbf{Bool}$, then, is that $\mathbf{Bool}$ has only two elements, and so any such $f$ is either a bijection, or has an image of size one, and so the restriction onto the image must be a bijection.

Interestingly, for any $f$ that is not bijective on its image, there can be no $k$ such that $f^{k} = f$. This is because, if $f|_{\operatorname{im}f}$ is not bijective, then $\operatorname{im}f^k \subset \operatorname{im}f$ for all $k$, so those functions cannot be equal. Therefore, we have the following result:

If, for a given $f: X\mapsto X$, there exists a $k$ such that $f^k = f$, then $f^{|X|!+1}=f$.

Answer 3

Actually, a slightly more precise result holds: every function $f$ from $\{0,1\}$ into itself satisfies either $f^2 = Id$ or $f^2 = f$. This property is actually a combination of two properties of functions from $\{0, ..., n-1\}$ into itself:

1. If $f$ is a bijection, then $f^{n!} = Id$ and hence $f^{n! + 1} = f$.
2. If $f$ is a constant map, then $f^2 = f$.

Related result: given a finite semigroup $S$, there exists an integer $n$ such that for all $x \in S$, $(x^n)^2 = x^n$.