# For what sets $X$ do there exist a pair of functions from $X$ to $X$ with the identity being the only function that commutes with both?

It is not too difficult to show that if $$X$$ is an infinite set, then there exists a two-element subset of the group $$\operatorname{Sym}(X)$$ with trivial centralizer iff $$\lvert X\rvert \leq \lvert\mathbb{R}\rvert$$.

My question is if this is true if we replace $$\operatorname{Sym}(X)$$ with $$\operatorname{End}(X)$$.

I.e., for what infinite sets $$X$$ do there exist functions $$f,g: X \rightarrow X$$, such that if $$h:X \rightarrow X$$ satisfies $$fh = hf$$ and $$gh = hg$$, then $$h = I$$? The same argument from the $$\operatorname{Sym}(X)$$ case shows that it is true when $$|X| \leq \mathbb{R}$$ (and was given as a problem in the 6th Romanian Masters of Mathematics competition). But is it false for $$|X| > |\mathbb{R}|$$?

• I think $h = I$ is too much to ask for in general, as you can always set $g = f^{\circ k}$ for some $k\in\mathbb{N}$. Then by re-associating you have that any $h = f^{\circ n}$ works, but may not be the identity.
– Mark
Apr 20, 2020 at 19:07
• @Mark OP is right that there exists a pair in $\mathrm{Sym}(c)$ whose centralizer is trivial. If the idea you have in mind contradicts this, it means it does not work.
– YCor
Apr 20, 2020 at 19:08
• Don't use Sym$(X)$ Sym$(X)$ for upright text in math mode. $\operatorname{Sym}(X)$ $\operatorname{Sym}(X)$ is best. I have edited accordingly. Apr 20, 2020 at 19:10
• It's very interesting; I'm curious what your motivation is. One is that the sentence, in a group "there exists a pair with trivial centralizer" can be written as a first-order formula, and for the symmetric groups $\mathrm{Sym}(X)$, it indeed characterizes $|X|\le c$ (while for $|X|>c$ every countable subset has centralizer of cardinal $|X|$).
– YCor
Apr 20, 2020 at 19:19

The answer is no: for every set $$X$$ there exists a pair in the monoid $$X^X$$ of self-maps of $$X$$, with centralizer reduced to $$\{\mathrm{id}\}$$.

(I first left my original "groupwise" answer because it's easier and because it has other follow-up questions. It's now deleted and copied as an answer to another question).

For $$X$$ empty take $$(\mathrm{id},\mathrm{id})$$. For $$X$$ finite nonempty, take a constant, and a cycle. So henceforth I assume that $$X$$ is infinite.

(a) First I use Sierpiński-Banach theorem [cf. here and here] that every countable subset (here just finite is fine) of $$X^X$$ is contained in the subsemigroup generated by a 2-element subset. This reduces to proving that there is a finite (actually 6-element) subset $$\Sigma\subset X^X$$ with trivial centralizer.

(b) Next I split $$X$$ as union of two subsets $$Y,Z$$ of the same cardinal. Let $$f,g\in X^X$$ have image equal to $$Y$$ and $$Z$$ respectively. If $$u$$ commutes to $$f$$, then $$u$$ stabilizes $$\mathrm{Im}(Y)$$, and similarly with $$g$$, $$Z$$. I'll therefore assume $$f,g\in\Sigma$$, and hence every $$u$$ in the centralizer of $$\Sigma$$ stabilizes both $$Y$$ and $$Z$$.

(c) It was proved in [VPH] that there exists a "strongly rigid" binary relation on $$Y$$: a subset $$R\subset Y^2$$ (actually, $$R$$ being subset of a well-ordering) such that the only endomorphism $$u$$ of $$(Y,R)$$ is the identity. (Here endomorphism means that $$u\times u:Y^2\to Y^2$$ maps $$R$$ into itself.) Clearly the cardinal of $$R$$ is that of $$|Y|=|X|$$.

Choose a partition $$Z=Z'\sqcup Z''$$ of $$Z$$ in subsets of the same cardinal. Choose a bijection $$i$$ from $$R$$ to $$Z'$$. Define self-maps $$p,q$$ of $$X$$ as follows. On $$Y$$, $$p$$ and $$q$$ are chosen as injective maps into $$Z''$$. Also $$p$$ and $$q$$ are defined on $$Z'$$ by: for $$(y,y')\in Y^2$$ and $$z=i(y,y')$$, $$q(z)=p(y)$$ and $$p(z)=q(y')$$. Finally, extend $$p,q$$ arbitrarily choosing maps $$Z''\to Y$$.

Then, for $$(y,y')\in Y^2$$, we have $$(y,y')\in R$$ if and only if there exists $$z_1,z,z_2\in Z$$ such that $$p(y)=z_1$$, $$q(z)=z_1$$, $$p(z)=z_2$$, $$q(y')=z_2$$. [Intuition: this is a "$$\stackrel{p}\to\stackrel{q}\leftarrow\stackrel{p}\to\stackrel{q}\leftarrow$$ path" from $$y$$ to $$y'$$]

Indeed $$\Rightarrow$$ works by construction with $$z_1=p(y)$$, $$z=i(y,y')$$, $$z_2=q(y')$$. Conversely, suppose that such elements exist; write $$(Y,Y')=i^{-1}(z)$$, so $$(Y,Y')\in R$$. By definition $$p(z)=q(Y')$$ and $$q(z)=p(Y)$$. So $$q(Y')=q(y')$$ and $$p(Y)=p(y)$$. By injectivity of $$p$$ and $$q$$ on $$Y$$, we have $$(y,y')=(Y,Y')\in R$$.

As a consequence, if $$u$$ stabilizes $$Z$$ and $$Y$$ and commutes with $$p$$ and $$q$$, then $$u$$ preserves $$R$$ on $$Y$$.

Next we define similarly $$p',q'$$ from a strongly rigid binary relation on $$Z$$.

Then the above proves that the centralizer of $$\{f,g,p,q,p',q'\}$$ in $$X^X$$ is reduced to $$\{\mathrm{id}\}$$.

[VPH] Vopěnka, P.; Pultr, A.; Hedrlín, Z. A rigid relation exists on any set. Comment. Math. Univ. Carolinae 6 (1965), 149–155.

Informal outline: the hard step is the above reference (existence of a strongly rigid binary relation). Then, the 0th step is Sierpinski-Banach (which is not hard) to pass from 6 to 2. The second is quite trivial: there exists a pair such that centralizing this pair implies preserving each component of a partition into two moieties. The third step is to encode a binary relation into a pair of self-maps using such a $$\stackrel{p}\to\stackrel{q}\leftarrow\stackrel{p}\to\stackrel{q}\leftarrow$$ path and the "coloring" by the 2-component partition.

• One related question I couldn't answer so far is whether there exists $f\in X^X$ whose centralizer is reduced to $\{f^n:n\ge 0\}$. Or if at the opposite, is it true that for $|X|>c$ every $f\in X^X$ has a centralizer cardinal $2^{|X|}$.
– YCor
Apr 28, 2020 at 10:40
• Eventually I made it a separate question: mathoverflow.net/questions/359660
– YCor
May 7, 2020 at 19:09
• I used above the existence of a strongly rigid binary relation on every set (in ZFC). Let me mention that Hamkins–Palumbo proved that it is consistent with ZF that there exists a set with no rigid binary relation, that is, in which every binary relation has a nontrivial automorphism group, see this post.
– YCor
May 8, 2020 at 8:31
• I took the liberty to add references to the result by Sierpiński and Banach (which I did not know). Dec 2, 2021 at 22:52