# Does every set have a rigid self-map?

The question was asked on Mathematics Stackexchange but has remained unanswered so far.

A self-map is a map $$f:X\to X$$ from a set $$X$$ to itself. There is an obvious notion of morphism, and thus of isomorphism and automorphism, of self-maps. [A morphism from $$f:X\to X$$ to $$g:Y\to Y$$ is a map $$\phi:X\to Y$$ such that $$g\circ\phi=\phi\circ f$$.]

A self-map is rigid if it has no non-trivial automorphism.

The question is in the title:

Does every set have a rigid self-map?

Clearly, the existence of a rigid self-map of a given set $$X$$ depends only on the cardinality $$|X|$$ of $$X$$.

There is an obvious notion of the coproduct $$f:X\to X$$ of a family $$f_i:X_i\to X_i$$ of self-maps. [The set $$X$$ is the disjoint union of the $$X_i$$ and $$f$$ coincides with $$f_i$$ on $$X_i$$.] Any self-map is the coproduct of its indecomposable components, and a self-map is rigid if and only if its indecomposable components are rigid and pairwise non-isomorphic. (In the sequel I use the expression "component" instead of "indecomposable component". Moreover the identity of the empty set does not count as a component.)

We claim:

(1) If $$|X|\le2^{2^{\aleph_0}}$$, then $$X$$ has a rigid self-map.

Define $$f:\mathbb N\to\mathbb N$$ by $$f(i)=\max(i-1,0)$$. Then $$f$$ is rigid. Moreover, for each $$n\in\mathbb N$$ the map $$f$$ induces a rigid self-map of the set $$\{0,1,\ldots,n\}$$. This proves that (1) holds for $$|X|\le\aleph_0$$.

It remains to prove that $$X$$ has a rigid self-map when $$\aleph_0<|X|\le2^{2^{\aleph_0}}$$.

This will follow from Lemmas 1, 2 and 3 below.

Lemma 1. Let $$X$$ be an infinite set and $$\Sigma$$ a set of non-isomorphic rigid surjective indecomposable self-maps of $$X$$. Assume $$|\Sigma|>|X|$$. Then the coproduct of the elements of $$\Sigma$$ is a rigid surjective self-map of a set of cardinality $$|\Sigma|$$.

This is obvious.

Lemma 2. Let $$f$$ be a rigid surjective self-map of an infinite set $$X$$, and $$Y$$ a set satisfying $$|X|\le|Y|\le2^{|X|}$$. Then $$Y$$ has a rigid self-map.

Proof. Let $$X'$$ be a set disjoint from $$X$$ and $$\phi:X'\to X$$ a bijection. For each subset $$S$$ of $$X'$$ put $$X_S=X\sqcup S$$ (disjoint union) and define $$f_S:X_S\to X_S$$ by setting $$f_S(x)=f(x)$$ for $$x\in X$$ and $$f_S(s)=\phi(s)$$ for $$s\in S$$.

It suffices to show that the coproduct $$g:Y\to Y$$ of the $$f_S:X_S\to X_S$$ (where $$S$$ runs over all the subsets of $$X'$$) is rigid.

Let $$h:Z\to Z$$ be a component of $$g$$. Then $$h$$ is a component of $$f_S$$ for some $$S$$. It is easy to see that there is a unique component $$f_0:X_0\to X_0$$ of $$f$$ such that, if we set $$S_0:=S\cap\phi^{-1}(X_0)$$, then $$h$$ is equal to $$f_{0,S_0}:X_{0,S_0}\to X_{0,S_0},$$ where $$f_{0,S_0}$$ is defined as $$f_S$$ was defined above (replacing the bijection $$\phi:X'\to X$$ with the bijection $$\phi^{-1}(X_0)\to X_0$$ induced by $$\phi$$).

Let $$f_{1,T_1}:X_{1,T_1}\to X_{1,T_1}$$ be another component of $$g$$, corresponding to a subset $$T$$ of $$X'$$, and let $$\psi:X_{0,S_0}\to X_{1,T_1}$$ be an isomorphism from $$f_{0,S_0}$$ to $$f_{1,T_1}$$. Since $$X_0$$ and $$X_1$$ are the respective images of $$f_{0,S_0}$$ and $$f_{1,T_1}$$ by surjectivity of $$f$$, the isomorphism $$\psi$$ maps $$X_0$$ onto $$X_1$$ and $$S_0$$ onto $$T_1$$. By rigidity of $$f$$ we have $$X_0=X_1$$ and $$\psi(x)=x$$ for all $$x\in X_0$$. Let $$s$$ be in $$S_0$$. It suffices to show $$\psi(s)=s$$. Set $$x=\phi(s)\in X_0$$. Then $$\psi$$ maps the fiber of $$\phi$$ above $$x$$ to itself, but $$s$$ is the only point in this fiber. This completes the proof of Lemma 2.

Lemma 3. Let $$A$$ be the set of all increasing self-maps of $$\mathbb N$$ such that $$a(0)\ge1$$. Then there is a family of pairwise non-isomorphic rigid surjective indecomposable self-maps $$(f_a:X_a\to X_a)_{a\in A},$$ where each $$X_a$$ is an infinite subset of $$\mathbb N^2$$.

Proof. Define the subset $$X_a$$ of $$\mathbb N^2$$ by the condition that $$(i,j)\in X_a$$ if $$i\in a(\mathbb N)$$ or if $$j=0$$, and define $$f_a:X_a\to X_a$$ by setting

$$\bullet\ f_a(i,j)=(i,j-1)$$ if $$j\ge1$$,

$$\bullet\ f_a(i,0)=(i-1,0)$$ if $$i\ge1$$,

$$\bullet\ f_a(0,0)=(0,0)$$.

Let us fix $$a\in A$$ and sketch the proof that $$f_a$$ is a rigid self-map of $$X_a$$.

The point $$(0,0)$$ is the only fixed point. The points of the form $$(i,0)$$ with $$i\ge1$$ are characterized by the fact that they have ancestors which have two parents, and any two distinct such points are at different distances to $$(0,0)$$. Therefore the points $$(i,0)$$ are fixed by any automorphism of $$f_a$$. The point $$(a(n),j)$$ with $$j\ge1$$ has no ancestor with two parents, its first descendent with two parents is $$(a(n),0)$$, which is fixed by the automorphisms of $$f_a$$, the point $$(a(n),j)$$ is at distance $$j$$ from $$(a(n),0)$$, and these properties characterize $$(a(n),j)$$. Thus $$(a(n),j)$$ is fixed by the automorphisms of $$f_a$$.

This argument shows also that the $$f_a$$ are pairwise non-isomorphic. The other statements are clear.

[If $$y=f(x)$$ we say that $$x$$ is a parent of $$y$$. If $$y=f^n(x)$$ for $$n\in\mathbb N$$ we say that $$x$$ is an ancestor of $$y$$ and $$y$$ a descendent of $$x$$.]

set-theory

• "selfmap/self-map" seems more usual. Actually set + self-map is the same as a $G$-set, for $G$ the 1-generated free monoid (or 1-generated free semigroup). – YCor Aug 23 '20 at 16:14
• I sometimes find myself saying "endofunction", but I'm not sure whether that's more or less standard than "self-map". – Tim Campion Aug 23 '20 at 17:15
• @TimCampion - Not sure what it really means, but I did this Ngram search books.google.com/ngrams/… – Pierre-Yves Gaillard Aug 23 '20 at 17:24

Fact. For every set $$X$$ there exists $$f\in X^X$$ whose centralizer in $$\mathrm{Sym}(X)$$ is reduced to $$\{\mathrm{id}_X\}$$
It relies on the following second fact: there exists (for $$X\neq\emptyset$$) a rooted tree structure on $$X$$ whose automorphism group is trivial. Indeed, granting this, and denoting $$v_0$$ the root, for a vertex $$v$$ define $$f(v)$$ as $$v_0$$ if $$v_0=v$$, and as the unique vertex in $$[v_0,v]$$ at distance 1 to $$v$$ otherwise. Then $$f\in X^X$$ and its centralizer in $$\mathrm{Sym}(X)$$ is the automorphism group of the corresponding rooted tree, which is reduced to $$\{\mathrm{id}_X\}$$.
To prove the second fact, if $$X$$ is finite just take a linear tree rooted at an extremal vertex. If $$X$$ is infinite, by an elementary but very tricky argument (see this answer by user "bof"), there actually exist for every infinite cardinal $$\kappa$$, $$2^{\kappa}$$ pairwise non-isomorphic trees of cardinal $$\kappa$$ each with trivial automorphism group. [Interestingly the induction really requires proving that there are $$>\kappa$$ such trees, and not only a single one.]