Cardinality of the set of functions commuting with $f:X\to X$

If $\operatorname{card}(X) > \omega$ is regular, the answer is yes:

Lemma 1. Let $\kappa$ be a regular, uncountable cardinal and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \kappa. $$

Proof. For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

It now suffices to show that $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Let $\alpha < \kappa$. By our assumption there is some $\xi < \kappa$ such that $\sup \bigcup_{\beta \le \alpha} C_\beta < \xi$ and $f(\xi) \neq \xi$. Thus, for all $\beta \le \alpha$, $g_{\beta}(\xi) = \xi \neq f(\xi) = g_{\xi}(\xi)$. The regularity of $\kappa$ now implies $\operatorname{card}(\{ g_{\alpha} \mid \alpha < \kappa \}) = \kappa$. Q.E.D.

Lemma 2. Let $\kappa$ be a (possibly singular) cardinal and let $f \colon \kappa \to \kappa$ be such that $\{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is bounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) = 2^\kappa > \kappa. $$

Proof. Fix $\alpha < \kappa$ such that $f(\xi) = \xi$ for all $\xi \ge \alpha$. Then for each $g \colon \kappa \to \kappa$ with $g \restriction \alpha = \operatorname{id}$ we have $f \circ g = g \circ f$ and there are $2^\kappa > \kappa$ many such functions $g$. Q.E.D.

So the remaining cases are

Q 1. Let $f \colon \omega \to \omega$ be such that $\{f^n \mid n < \omega\}$ is finite. Are there infinitely many $g \colon \omega \to \omega$ such that $f \circ g = g \circ f$?

This case has now been handled by Martin Goldstern and Will Sawin in separate answers. So the only remaining question is:

Q 2. Let $\kappa$ be a singular cardinal. Is there some function $f \colon \kappa \to \kappa$ such that $$ \operatorname{card} (\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) < \kappa? $$

---

Let me provide, as a first approach to Q 2., the details of my previous claim in the comment section:

Lemma 3. Let $\kappa$ be a cardinal such that $\operatorname{cf}(\kappa) > \omega$ and let $f \colon \kappa \to \kappa$ be such that $S := \{ \xi < \kappa \mid f(\xi) \neq \xi \}$ is unbounded. Then $$ \operatorname{card}(\{ g \colon \kappa \to \kappa \mid f \circ g = g \circ f \}) \ge \operatorname{cf}(\kappa). $$

Proof. The argument is a slight refinement of the previous proof of Lemma 1:

For each $\alpha \in \kappa$ let $C_{\alpha} := \{ f^{n}(\alpha) \mid n < \omega \}$ and $$ g_{\alpha} \colon \kappa \to \kappa, \xi \mapsto \begin{cases} f(\xi) & \text{, if } \xi \in C_{\alpha} \\ \xi & \text{, otherwise}. \end{cases} $$

Then $$\begin{align*} f \circ g_{\alpha} &= f^2 \restriction C_{\alpha} \cup f \restriction (\kappa \setminus C_{\alpha}) \\ &= g_{\alpha} \circ f. \end{align*}$$

We now recursively construct a strictly increasing sequence $(\alpha_\beta \mid \beta < \operatorname{cf}(\kappa))$ such that, for all $\beta < \operatorname{cf}(\kappa)$, $f \circ g_{\alpha_\beta} = g_{\alpha_\beta} \circ f$:

Given $(\alpha_\beta \mid \beta < \gamma)$ for some $\gamma < \operatorname{cf}(\kappa)$ note that $\bigcup_{\beta < \gamma} C_{\alpha_\beta}$ is not cofinal in $\kappa$. Hence there is some $\xi > \sup \bigcup_{\beta < \gamma} C_{\alpha_\beta}$ such that $f(\xi) \neq \xi$. Let $\xi$ be minimal with this property and let $\alpha_\gamma := \xi$. As before we see that $f \circ g_{\alpha_\gamma} = g_{\alpha_\gamma} \circ f$ and $g_{\alpha_\gamma} \not \in \{ g_{\alpha_\beta} \mid \beta < \gamma \}$. Hence the resulting sequence $(g_{\alpha_\beta} \mid \beta < \operatorname{cf}(\kappa))$ is as desired. Q.E.D.

I think I can show this in general $X$, heavily borrowing from Goldstern's constructions.

Lemma 1: Let $\alpha$ be the supremum of numbers of parents of elements of $X$. If, for each $x_1,x_2 \in X$, there is some $n_1,n_2$ with $f^{n_1}(x_1) = f^{n_2}(x_2)$, and $X$ is uncountably infinite, then $\alpha = |X|$.

Proof: Fix an $x_0$, and for each $n$ let $Y_n$ be the set of $x$ where there exists an $m$ such that $f^n(x) = f^m(x_0)$. Then $Y_0$ is countable and $|Y_{n+1}| \leq \alpha |Y_n|= \sup(\alpha,|Y_n|)$ by the axiom of choice, so inductively $|Y_n| = \sup ( \aleph_0, \alpha)$. But since the union of the $Y_n$ is $X$, the supremum of the $|Y_n|$ must be the cardinality of $X$, so since $|X|> \aleph_0$, $|X|=\alpha$. QED

Lemma 2: Let $x$ be an element of $X$, and let $\alpha$ be the number of parents of $x$. Then there are at least $\alpha$ commuting maps $g$.

Proof: The proof is a generalization of Goldstern’s argument. To an ancestor $y$ of $x$ that does not have an infinite chain of ancestors, assign an ordinal $\omega_y$ by the inductive rule that $\omega_y$ is the least ordinal greater than $\omega_z$ for all $z$ with $f(z)=y$. Let $\omega_{y}$ for $y$ an ancestor of $x$ that does have an infinite chain of ancestors be some fixed ordinal with cardinality greater than $|X|$ - in particular, greater than all other ordinals appearing.

Then any map $g$ from the set of parents of $x$ to itself such that $\omega_{g(z)}\geq \omega_z$ for all $z$ can be extended to a commuting map $g$, by 1 setting $g(z)=z$ if $g$ is not an ancestor of $x$, or is a descendent of x

2 Inductively choose, for each $z’$ an ancestor of $x$ but not a descendent of $x$, a $g(z’)$ satisfying $\omega_{g(z’)} \geq \omega_{z' }$,

This is possible since, if $f(z')$ does not admit an infinite chain of ancestors, $\omega_{g(f(z’)} \geq \omega_{f(z’)} > \omega_{z’}$, so by definition of $\omega_{g(f(z'))}$ there exists $w’$ with $\omega_w \geq \omega_{z’}$ and $f(w)=g(f(z’)$ and we set $g(z')=w'$, while if $f(z')$ does admit an infinite chain of ancestors then $g(f(z'))$ does as well and we may choose $g(z')$ to be the parent in this chain.

There are always at least $\alpha$ such maps, because there is some parent with a minimal ordinal, and we can send it to any other parent. QED

Lemma 3 If $X$ is infinite, and for each $x_1,x_2 \in X$, there is some $n_1,n_2$ with $f^{n_1}(x_1)=f^{n_2}(x_2)$, then there are at least $|X|$ commuting endomorphisms.

Proof: In view of Lemma 2 we may assume that the supremum of the number of ancestors of $|X|$ is less than $|X|$. In view of Lemma 1 we may assume that $X$ is countable. So in fact each element has a finite number of parents. If the set of maps $\{f^k | k \in \mathbb N\}$ has infinitely many distinct elements, we are done. Otherwise, $X$ is finite, because for a fixed $x_0 \in X$, each element of $X$ satisfies one of finitely many equations $f^n (x) = f^m(x_0)$, each of which has only finitely many solutions. QED

Now consider the directed graph associated to $f$, with one vertex for each $x\in X$, with an edge connecting $x \to f(x)$. The condition of Lemma 3 is equivalent to saying that this graph is connected. We are certainly done if the total number of elements in infinite components is $|X|$, because for each infinite component there are at least as many endomorphisms as elements, so by multiplying them we get at least as many endomorphisms as elements in all the infinite components combined.

So we may assume the total number of elements in finite components is $|X|$. So the total number of finite components is at least $|X|$. Then there are at least $2^{|X|}$ examples by Goldstern's argument, choosing either a permutation of the singleton components or a choice of identity versus $f$ on each component.

I think in fact one can get a lower bound of $2^{|X|}$ whenever $X$ is countable but I didn't check all the steps.

Let $X$ be countable:

We partition $X$ by the relation $x\sim y$ iff there are $n,k$ with $f^n(x)=f^k(y)$. If $X$ is countable and has infinitely many singleton components, $g$ can be chosen to permute them arbitrarily (and identity otherwise). This gives uncountably many possibilities for $g$.

If $X$ is countable and has infinitely many non-singleton components, then $g$ can be chosen as $f$ on some components, and as $f^2$ on others, which again gives you uncountably many possibilities.

From now on assume that the set of all powers of $f$ is finite. Then there is some $n$ and $k>0$ with $f^{n+k}=f^n$.

If $X$ has only finitely many components, then there must be some $y$ with infinitely many predecessors. We can define infinitely many $g$ as follows:

• $g(y)=y$, and $g(z)=z$ whenever there is no $j>0$ with $f^j(z)=y$. Also $g(f^r(y))=f^r(y)$.
• Otherwise: for each $x$ with $f(x)=y$ (except possibly the one which is an iterated image of $y$) let $n_x$ be maximal such that there is $\bar x$ with $f^{n_x} (\bar x)=x$.
• Now let $g$ map any such $x$ to some $x'$ with $n_{x'}\ge n_x$. This defines $g$ on $f^{-1}(y)$. There are infinitely many possibilities for $g$.
• Now let $f^j(z)=y$, $j>1$. So $j\le n_z$. Consider $x:={f^{j-1}(z)}$. Let $g(z):= f^{n_{ g( x)}-j}(\overline{g(x)})$.