2
$\begingroup$

Let $X$ be an infinite set and let $\text{End}(X)$ be the set of all functions $f:X\to X$. For $f\in\text{End}(X)$ let $$\text{Com}(f) = \{g\in\text{End}(X): g\circ f = f \circ g\}.$$ Is there $f\in \text{End}(X)$ such that $\text{Com}(f) = \{\text{id}_X, f\}$?

If not, what is $\min\{|\text{Com}(f)|:f\in\text{End}(X)\}$, in terms of $|X|$?

$\endgroup$
2
  • 2
    $\begingroup$ The powers of f commute with f. $\endgroup$ Dec 28, 2016 at 14:28
  • $\begingroup$ This paper by Bonatti, Crovisier, and Wilkinson doi.org/10.1007/s10240-009-0021-z shows that for (Baire-)generic C^1 diffeomorphisms of a compact manifold, the centralizer of f contains only the powers of f. See the paper's introduction for related results. $\endgroup$ Dec 28, 2016 at 14:36

2 Answers 2

5
$\begingroup$

Nope: since $f^2$ commutes with $f$, we should have either $f^2=\mathrm{id}_X$ or $f^2=f$, that is $f$ is either idempotent or involutive. But on an infinite set it is easy to see these always have infinite commutators.

$\endgroup$
9
  • 1
    $\begingroup$ Thanks for this argument! It shows that $|\text{Com}(f)| \geq \aleph_0$ for all $f\in\text{End}(X)$. But it could still be that there is an uncountable set $X$ and $f:X\to X$ such that $|\text{Com}(f)| < |X|$, or does your argument exclude that? $\endgroup$ Dec 28, 2016 at 15:16
  • 2
    $\begingroup$ Consider $X:=\omega_1$, the first uncountable ordinal, and define $f(\alpha)=\alpha+1$. Then as for $X=\mathbf{N}$ an element $g$ of $\text{End}(X)$ must be a $f^\alpha$, $\alpha\in\omega_1$. Because the addition of ordinals is not commutative we have $\alpha<\omega$. We obtain $|\text{Com{f}}|=|\omega|<|X|$. $\endgroup$
    – Joel Adler
    Dec 28, 2016 at 15:41
  • $\begingroup$ @JoelAdler But why $g(n)=s+n$ does not commute with $f$ for any $a\in\omega_1$? We have $g(f(n))=g(n+1)=a+n+1=(a+n)+1=f(g(n)$... $\endgroup$ Dec 28, 2016 at 16:06
  • 1
    $\begingroup$ In fact it seems to me that even for $X=\omega^2$ there are continuum many maps commutating with $x\mapsto x+1$. Indeed, $f:\omega^2\to \omega^2$ decomposes into countably many invariant sets, i.e. the intervals $\{\omega\cdot k\le x< \omega\cdot (k+1)\} $, in each of them being isomorphic to $ f:\omega \to \omega $. Choosing $g$ to be either $f$ or $id$ on each of these intervals, one finds continuum many $g$ commutating with $f$. $\endgroup$ Dec 28, 2016 at 16:33
  • $\begingroup$ Sorry, my argument is wrong. $\endgroup$
    – Joel Adler
    Dec 28, 2016 at 16:47
4
$\begingroup$

Let $X:=\mathbf{N}$ and $f:X\rightarrow X$ be defined by $f(n)=n+1$, and let $g:X\rightarrow X$ commute with $f$.

We have $g(n+1)=g(f(n))=f(g(n))=g(n)+1$ for all $n\in X$. Thus, with $g(0)=a$ we obtain $g(n)=a+n=f^a(n)$, which means that the powers of $f$ are the only elements of $\text{End}(X)$ commuting with $f$.

Thus $|\text{Com(f)}|=|\mathbf{N}|=|X|$.

$\endgroup$
2
  • $\begingroup$ This is nice, and this is maybe the minimum cardinality, isn't it? $\endgroup$ Dec 28, 2016 at 14:56
  • $\begingroup$ Thanks! So for this particular $f:\mathbb{N}\to\mathbb{N}$ you prove that $\text{Com}(f)$ is infinite - but is there maybe another $f_0:\mathbb{N}\to\mathbb{N}$ such that $\text{Com}(f_0)$ is finite? -- Oh ok - I just saw Pietro Majer's input on this! $\endgroup$ Dec 28, 2016 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.