10
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ "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). $\endgroup$
    – YCor
    Aug 23, 2020 at 16:14
  • $\begingroup$ I sometimes find myself saying "endofunction", but I'm not sure whether that's more or less standard than "self-map". $\endgroup$
    – Tim Campion
    Aug 23, 2020 at 17:15
  • $\begingroup$ @TimCampion - Not sure what it really means, but I did this Ngram search books.google.com/ngrams/… $\endgroup$ Aug 23, 2020 at 17:24

1 Answer 1

11
$\begingroup$

Yes. Actually, this was part of my first answer to this question, but this was a digression there (and I also posted there another answer to the same question which addressed it and was accepted). So I'm copying this digression here and will delete the initial answer to that question to avoid a duplicate.

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.]

$\endgroup$
1
  • 3
    $\begingroup$ I think it's important to note that the term "tree" means something different in set theory from what it means in graph theory (although the two definitions are equivalent when the tree is finite -- I'm not clear on the relationship in the infinite case). It's graph-theoretic trees which are related to endofunctions. And indeed, the linked construction builds graph-theoretic trees rather than set-theoretic ones. $\endgroup$
    – Tim Campion
    Aug 23, 2020 at 17:13

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.