Skip to main content
2 of 3
f(x), not f()
Goldstern
  • 14k
  • 1
  • 47
  • 71

Here are some useful reductions, including a resolution of the case when two distinct powers of $f$ are equal.

We freely use the axiom of choice for many useful facts about infinite cardinals. In particular, if $|A| + |B| \geq |X|$ then $|A| \geq X$ or $|B| \geq X$.

Consider the directed graph associated to $f$, with one vertex for each $x\in X$, with an edge connecting $x \to f(x)$.

If the graph of $f$ has at least $|X|$ many connected components, 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.

So we may reduce to the case when the graph of $f$ has fewer than $|X|$ finite components, hence at least $|X|$ elements in infinite components. From here we may reduce to the case when the graph is connected, because if for each infinite component there are at least as many endomorphisms as elements, by multiplying them we get at least as many endomorphisms as elements in all the infinite components combined.

After this reduction, the graph either ends in a $k$-cycle or is an infinite tree.

Using this, let's handle Stefan's Q1.

If $f^n = f^m$ for some $n,m$ with $n<m$, then the graph certainly ends in a $k$-cycle for $k| m-n$, and has depth $\leq n$ below that $k$-cycle. So all elements are $n$-fold predecessors of elements in the $k$-cycle. Because finite powers of an infinite cardinal recover that cardinal, some element has at least $|X|$ direct predecessors. So for some $r \leq n$ it has at least $|X|$ predecessors which are in the image of $f^r$ but not $f^{r+1}$. We can permute these freely, as in Goldstern's answer, so there are at least $|X|$ possible commuting maps.

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563