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

Question

If $X$ is an infinite set and $f:X\to X$, do we have $$\big|\{g:X\to X: g\circ f =f \circ g\}\big|\geq |X| ?$$

Answer 1

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.

Answer 2

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.

Answer 3

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)})$.

Answer 4

This isn't a proof for the question itself, but a demonstration that you don't need to assume $X$ infinite. From now on, assume $X$ finite.

Assume $X$ connected, that is, $\forall x, y \exists m, n f^m(x) = f^n(y)$. By the pigeonhole principle, we have some $j \neq k$ with $f^j = f^k$, so eventually $\text{Im} f^i$ is constant. Let $X_0$ be that image.

Claim 1: $X_0$ is a loop. In other words, $\forall x, x' \in X_0 \exists n f^n(x) = x'$

Proof: As $X_0$ is the eventually constant image, we have that $f(X_0) = X_0$, so $f|_{X_0}$ is a bijection. Therefore, there is some $N$ with $f^N|_{X_0} = \text{Id}|_{X_0}$. Combining this with connectedness gives the claim.

Inductively let $X_i = f^{-1}(X_{i - 1})$. By the definition of $X_0$, we have that $X = \cup X_i$. Then there is a smallest $i_0$ with $X_{i_0} = X$. Choose $x_i \in X\backslash X_{i_0 - 1}$.

Claim 2: For any $y \in X$, let $m_y$ be the smallest integer such that there is some $n$ with $f^{m_y}(y) = f^n(x_0)$. Then $n \geq m_y$ for all such $n$.

Proof: Assume $m_y > n$. For some smallest $j$, we have $f^n(x) \in X_j$. Then $x_0 \in X_{j + n}$. By the definition of $x_0$, we must also have that $y \in X_{j + n}$, so $f^n(y) \in X_j$. But as $m_y > n$, we must have that $f^{m_y}(y) \in X_{j - 1}$ or that $j = 0$. By the assumption that $j$ is the smallest, we must have that $j = 0$, so $f^n(y) \in X_0$. But then there is some $n'$ such that $f^{n'}(x) = f^n(y)$, by claim 1, which contradicts the assumption. Therefore, the current claim is proved.

Claim 3: For any $z \in X$, there is a map $g: X \rightarrow X$ such that $g_z \circ f = f \circ g_z, g_z(x_0) = z$.

Proof: For $y \in X$, define $n_y$ as the smallest integer such that $f^{m_y}(y) = f^{n_y}(x_0)$, and define $\iota_{x_0}(y) = n_y - m_y$. By claim 2, $\iota_{x_0}(y) \geq 0$. Then for $z \in X$, define $g_z(y) = f^{\iota_{x_0}}(z)(x_0)$. For $y = x_0$, we have $m_y = n_y = 0$, so $g_z(x_0) = z$.

I claim that $g_z \circ f = f \circ g_z$.

If $m_y \neq 0$, then $m_{f(y)} = m_y - 1, n_{f(y)} = n_y$. We therefore only need to check the case where $m_y = 0$.

If $m_y = 0$, then $y = f^{n_y}(x_0)$, so $f(y) = f^{n_y + 1}(x_0)$. If $n_{f(y)} = n_y + 1$, this is clear: $g_z(f(y)) = f^{n_y + 1}(z) = f(f^{n_y}(z)) = f(g_z(y))$, so we only need to check for $y$ such that $n_{f(y)} \neq n_y + 1$.

It's clear that this can only happen if $f(y) = f^i(x_0)$, recalling that $i$ is the smallest number such that $X_i = X$, and if $y \in X_0$ is the element that precedes it in the "loop". Then $y = f^{p - 1}(f(y))$, where $p$ is the length of the loop. But then $g(y) = f^{i + p - 1}(z)$, so $f(g(y)) = f^p(f^i(z)) = f^i(z) = g(f(y))$ by the definition of $i$ and the loop. So we are done.

Now consider $X$ not connected. We proceed by induction. Let $Y$ be a component of $X$, and $X'$ the rest of $X$. Assume $Y$ consists of a single element $\{y\}, f(y) = y$. Then we know that $|\{g: X' \rightarrow X'|g \circ f = f \circ g\} \geq |X'|$. For each such $g$, we can construct $g': X \rightarrow X$ such that $g'|_{X'} = g, g'(y) = y$; by inspection, this commutes with $y$. We also have the constant map $g_0: g_0(x) = y$. This gives us enough distinct maps that commute with $f$.

Assume neither $Y$ nor $X'$ consists of a single element. Then $\{g: X \rightarrow X|g \circ f = f \circ g\} \supset \{g_1: X' \rightarrow X', g_2: Y \rightarrow Y| g_1 \circ f = f \circ g_1, g_2 \circ f = f \circ g_2\}$, so by induction, $|\{g: X \rightarrow X|g \circ f = f \circ g\}| \geq |\{g: X' \rightarrow X'|g \circ f = f \circ g\}| |\{g: Y \rightarrow Y|g \circ f = f \circ g\}| \geq |X'||Y| \geq |X'| + |Y| = |X|$.

Edit: To picture this, define by a "lasso" a finite set $L = \{f^n(x)\}$. Lassos are characterized by two numbers: the length of the loop, and the length of the "rope" before the loop. Effectively, this proof "collapses" $X$ to the lasso with the longest rope, then shows that for any $i, i', j, j'$ such that $j'|j, i' \leq i$ there is a "lasso map" $L_{ij} \rightarrow L_{i'j'}$.