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| ?$$



Cardinality of the set of functions commuting with $f:X\to X$
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.


