Cada conjunto tem um auto-mapa rígido?
A pergunta foi feita no Mathematics Stackexchange, mas permaneceu sem resposta até agora.
Um mapa próprio é um mapa $f:X\to X$ de um conjunto $X$para si mesmo. Há uma noção óbvia de morfismo e, portanto, de isomorfismo e automorfismo , de mapas próprios. [Um morfismo de$f:X\to X$ para $g:Y\to Y$ é um mapa $\phi:X\to Y$ de tal modo que $g\circ\phi=\phi\circ f$.]
Um mapa próprio é rígido se não tiver um automorfismo não trivial.
A pergunta está no título:
Cada conjunto tem um auto-mapa rígido?
Claramente, a existência de um auto-mapa rígido de um determinado conjunto $X$ depende apenas da cardinalidade $|X|$ do $X$.
Existe uma noção óbvia do coproduto $f:X\to X$ de uma família $f_i:X_i\to X_i$de auto-mapas. [O conjunto$X$ é a união disjunta do $X_i$ e $f$ coincide com $f_i$ em $X_i$.] Qualquer auto-mapa é o coproduto de seus componentes indecomponíveis , e um auto-mapa é rígido se e somente se seus componentes indecomponíveis forem rígidos e não isomórficos em pares. (Na sequência, uso a expressão "componente" em vez de "componente indecomponível". Além disso, a identidade do conjunto vazio não conta como um componente.)
Nós reivindicamos:
(1) Se $|X|\le2^{2^{\aleph_0}}$, então $X$ tem um auto-mapa rígido.
Definir $f:\mathbb N\to\mathbb N$ de $f(i)=\max(i-1,0)$. Então$f$é rígido. Além disso, para cada$n\in\mathbb N$ o mapa $f$ induz um auto-mapa rígido do conjunto $\{0,1,\ldots,n\}$. Isso prova que (1) vale para$|X|\le\aleph_0$.
Resta provar que $X$ tem um auto-mapa rígido quando $\aleph_0<|X|\le2^{2^{\aleph_0}}$.
Isso virá dos Lemas 1, 2 e 3 abaixo.
Lema 1. Vamos$X$ ser um conjunto infinito e $\Sigma$ um conjunto de auto-mapas não-isomórficos rígidos sobrejetivos indecomponíveis de $X$. Presumir$|\Sigma|>|X|$. Então o coproduto dos elementos de$\Sigma$ é um auto-mapa sobrejetivo rígido de um conjunto de cardinalidade $|\Sigma|$.
Isso é óbvio.
Lema 2. Vamos$f$ ser um auto-mapa sobrejetivo rígido de um conjunto infinito $X$e $Y$ um conjunto satisfatório $|X|\le|Y|\le2^{|X|}$. Então$Y$ tem um auto-mapa rígido.
Prova. Deixei$X'$ ser um conjunto separado de $X$ e $\phi:X'\to X$uma bijeção. Para cada subconjunto$S$ do $X'$ colocar $X_S=X\sqcup S$ (união disjunta) e definir $f_S:X_S\to X_S$ definindo $f_S(x)=f(x)$ para $x\in X$ e $f_S(s)=\phi(s)$ para $s\in S$.
Basta mostrar que o coproduto $g:Y\to Y$ do $f_S:X_S\to X_S$ (Onde $S$ percorre todos os subconjuntos de $X'$) é rígido.
Deixei $h:Z\to Z$ ser um componente de $g$. Então$h$ é um componente de $f_S$ para alguns $S$. É fácil ver que existe um componente único$f_0:X_0\to X_0$ do $f$ de modo que, se definirmos $S_0:=S\cap\phi^{-1}(X_0)$, então $h$ é igual a $$ f_{0,S_0}:X_{0,S_0}\to X_{0,S_0}, $$ Onde $f_{0,S_0}$ é definido como $f_S$ foi definido acima (substituindo a bijeção $\phi:X'\to X$ com a bijeção $\phi^{-1}(X_0)\to X_0$ induzido por $\phi$)
Deixei $$ f_{1,T_1}:X_{1,T_1}\to X_{1,T_1} $$ ser outro componente de $g$, correspondendo a um subconjunto $T$ do $X'$, e deixar $$ \psi:X_{0,S_0}\to X_{1,T_1} $$ ser um isomorfismo de $f_{0,S_0}$ para $f_{1,T_1}$. Desde a$X_0$ e $X_1$ são as respectivas imagens de $f_{0,S_0}$ e $f_{1,T_1}$ por sobrejetividade de $f$, o isomorfismo $\psi$ mapas $X_0$ para $X_1$ e $S_0$ para $T_1$. Por rigidez de$f$ temos $X_0=X_1$ e $\psi(x)=x$ para todos $x\in X_0$. Deixei$s$ estar em $S_0$. Basta mostrar$\psi(s)=s$. Conjunto$x=\phi(s)\in X_0$. Então$\psi$ mapeia a fibra de $\phi$ acima $x$ para si mesmo, mas $s$é o único ponto nesta fibra. Isso completa a prova do Lema 2.
Lema 3. Vamos$A$ ser o conjunto de todos os auto-mapas crescentes de $\mathbb N$ de tal modo que $a(0)\ge1$. Então, há uma família de auto-mapas não-isomórficos rígidos sobrejetivos indecomponíveis em pares$$ (f_a:X_a\to X_a)_{a\in A}, $$ onde cada $X_a$ é um subconjunto infinito de $\mathbb N^2$.
Prova. Defina o subconjunto$X_a$ do $\mathbb N^2$ pela condição que $(i,j)\in X_a$ E se $i\in a(\mathbb N)$ ou se $j=0$, e definir $f_a:X_a\to X_a$ definindo
$\bullet\ f_a(i,j)=(i,j-1)$ E se $j\ge1$,
$\bullet\ f_a(i,0)=(i-1,0)$ E se $i\ge1$,
$\bullet\ f_a(0,0)=(0,0)$.
Vamos consertar $a\in A$ e esboçar a prova de que $f_a$ é um auto-mapa rígido de $X_a$.
O ponto $(0,0)$é o único ponto fixo. Os pontos do formulário$(i,0)$ com $i\ge1$ são caracterizados pelo fato de que eles têm ancestrais que têm dois pais, e quaisquer dois pontos distintos estão em distâncias diferentes para $(0,0)$. Portanto, os pontos$(i,0)$ são fixados por qualquer automorfismo de $f_a$. O ponto$(a(n),j)$ com $j\ge1$ não tem ancestral com dois pais, seu primeiro descendente com dois pais é $(a(n),0)$, que é fixado pelos automorfismos de $f_a$, o ponto $(a(n),j)$ está à distância $j$ de $(a(n),0)$, e essas propriedades caracterizam $(a(n),j)$. portanto$(a(n),j)$ é fixado pelos automorfismos de $f_a$.
Este argumento mostra também que o $f_a$são pares não isomórficos. As outras declarações são claras.
[E se $y=f(x)$ nós dizemos isso $x$é um pai de$y$. E se$y=f^n(x)$ para $n\in\mathbb N$ nós dizemos isso $x$é um ancestral de$y$ e $y$um descendente de$x$.]
teoria de conjuntos
Respostas
Sim. Na verdade, essa foi parte da minha primeira resposta a essa pergunta , mas isso foi uma digressão aí (e eu também postei ali outra resposta à mesma pergunta que a abordava e foi aceita). Então, estou copiando esta digressão aqui e irei deletar a resposta inicial a essa pergunta para evitar uma duplicata.
Facto. Para cada conjunto$X$ existe $f\in X^X$ cujo centralizador em $\mathrm{Sym}(X)$ é reduzido a $\{\mathrm{id}_X\}$
Baseia-se no seguinte segundo fato: existe (para $X\neq\emptyset$) uma estrutura de árvore enraizada em $X$cujo grupo de automorfismo é trivial. Na verdade, concedendo isso, e denotando$v_0$ a raiz, para um vértice $v$ definir $f(v)$ Como $v_0$ E se $v_0=v$, e como o único vértice em $[v_0,v]$ na distância 1 para $v$de outra forma. Então$f\in X^X$ e seu centralizador em $\mathrm{Sym}(X)$ é o grupo de automorfismo da árvore com raiz correspondente, que é reduzido a $\{\mathrm{id}_X\}$.
Para provar o segundo fato, se $X$é finito, basta pegar uma árvore linear enraizada em um vértice extremo. E se$X$é infinito, por um argumento elementar, mas muito complicado (veja esta resposta do usuário "bof"), existe realmente para cada cardinal infinito$\kappa$, $2^{\kappa}$ árvores não isomórficas pareadas de cardeais $\kappa$cada um com grupo de automorfismo trivial. [Curiosamente, a indução realmente requer a prova de que existem$>\kappa$ tais árvores, e não apenas uma.]