Ogni set ha una rigida auto-mappa?
La domanda è stata posta su Mathematics Stackexchange ma finora è rimasta senza risposta.
Un'auto-mappa è una mappa $f:X\to X$ da un set $X$a se stesso. C'è una nozione ovvia di morfismo , e quindi di isomorfismo e automorfismo , di auto-mappe. [Un morfismo da$f:X\to X$ per $g:Y\to Y$ è una mappa $\phi:X\to Y$ tale che $g\circ\phi=\phi\circ f$.]
Un'auto-mappa è rigida se non ha automorfismo non banale.
La domanda è nel titolo:
Ogni set ha una rigida auto-mappa?
Chiaramente, l'esistenza di una rigida auto-mappa di un dato insieme $X$ dipende solo dalla cardinalità $|X|$ di $X$.
C'è una nozione ovvia del coprodotto $f:X\to X$ di una famiglia $f_i:X_i\to X_i$di auto-mappe. [Il set$X$ è l'unione disgiunta di $X_i$ e $f$ coincide con $f_i$ sopra $X_i$.] Ogni auto-mappa è il coprodotto delle sue componenti indecomponibili , e un'auto-mappa è rigida se e solo se le sue componenti indecomponibili sono rigide e non isomorfe a coppie. (Nel seguito utilizzo l'espressione "componente" invece di "componente indecomponibile". Inoltre l'identità dell'insieme vuoto non conta come componente.)
Affermiamo:
(1) Se $|X|\le2^{2^{\aleph_0}}$, poi $X$ ha una rigida auto-mappa.
Definire $f:\mathbb N\to\mathbb N$ di $f(i)=\max(i-1,0)$. Poi$f$è rigido. Inoltre, per ciascuno$n\in\mathbb N$ la mappa $f$ induce una rigida auto-mappa dell'insieme $\{0,1,\ldots,n\}$. Ciò dimostra che (1) vale per$|X|\le\aleph_0$.
Resta da dimostrarlo $X$ ha una rigida auto-mappa quando $\aleph_0<|X|\le2^{2^{\aleph_0}}$.
Questo seguirà dai Lemmi 1, 2 e 3 di seguito.
Lemma 1. Let$X$ essere un insieme infinito e $\Sigma$ un insieme di auto-mappe indecomponibili suriettive rigide non isomorfe di $X$. Assumere$|\Sigma|>|X|$. Quindi il coprodotto degli elementi di$\Sigma$ è una rigida auto-mappa suriettiva di un insieme di cardinalità $|\Sigma|$.
Questo è ovvio.
Lemma 2. Let$f$ essere una rigida auto-mappa suriettiva di un insieme infinito $X$, e $Y$ un insieme soddisfacente $|X|\le|Y|\le2^{|X|}$. Poi$Y$ ha una rigida auto-mappa.
Prova. Permettere$X'$ essere un insieme disgiunto da $X$ e $\phi:X'\to X$una biiezione. Per ogni sottoinsieme$S$ di $X'$ mettere $X_S=X\sqcup S$ (unione disgiunta) e definire $f_S:X_S\to X_S$ IMPOSTANDO $f_S(x)=f(x)$ per $x\in X$ e $f_S(s)=\phi(s)$ per $s\in S$.
È sufficiente dimostrare che il coprodotto $g:Y\to Y$ del $f_S:X_S\to X_S$ (dove $S$ corre su tutti i sottoinsiemi di $X'$) è rigido.
Permettere $h:Z\to Z$ essere un componente di $g$. Poi$h$ è un componente di $f_S$ per alcuni $S$. È facile vedere che esiste un componente unico$f_0:X_0\to X_0$ di $f$ tale che, se impostiamo $S_0:=S\cap\phi^{-1}(X_0)$, poi $h$ è uguale a $$ f_{0,S_0}:X_{0,S_0}\to X_{0,S_0}, $$ dove $f_{0,S_0}$ è definito come $f_S$ è stato definito sopra (sostituendo il file bijection $\phi:X'\to X$ con la biiezione $\phi^{-1}(X_0)\to X_0$ indotto da $\phi$).
Permettere $$ f_{1,T_1}:X_{1,T_1}\to X_{1,T_1} $$ essere un altro componente di $g$, corrispondente a un sottoinsieme $T$ di $X'$, e lascia $$ \psi:X_{0,S_0}\to X_{1,T_1} $$ essere un isomorfismo da $f_{0,S_0}$ per $f_{1,T_1}$. Da$X_0$ e $X_1$ sono le rispettive immagini di $f_{0,S_0}$ e $f_{1,T_1}$ per suriettività di $f$, l'isomorfismo $\psi$ mappe $X_0$ su $X_1$ e $S_0$ su $T_1$. Per rigidità di$f$ noi abbiamo $X_0=X_1$ e $\psi(x)=x$ per tutti $x\in X_0$. Permettere$s$ essere dentro $S_0$. Basta mostrare$\psi(s)=s$. Impostato$x=\phi(s)\in X_0$. Poi$\psi$ mappa la fibra di $\phi$ sopra $x$ a se stesso, ma $s$è l'unico punto in questa fibra. Questo completa la dimostrazione del Lemma 2.
Lemma 3. Let$A$ essere l'insieme di tutte le auto-mappe crescenti di $\mathbb N$ tale che $a(0)\ge1$. Poi c'è una famiglia di auto-mappe indecomponibili suriettive rigide non isomorfe a coppie$$ (f_a:X_a\to X_a)_{a\in A}, $$ dove ciascuno $X_a$ è un sottoinsieme infinito di $\mathbb N^2$.
Prova. Definisci il sottoinsieme$X_a$ di $\mathbb N^2$ dalla condizione che $(i,j)\in X_a$ Se $i\in a(\mathbb N)$ o se $j=0$e definire $f_a:X_a\to X_a$ IMPOSTANDO
$\bullet\ f_a(i,j)=(i,j-1)$ Se $j\ge1$,
$\bullet\ f_a(i,0)=(i-1,0)$ Se $i\ge1$,
$\bullet\ f_a(0,0)=(0,0)$.
Cerchiamo di aggiustare $a\in A$ e abbozza la prova che $f_a$ è una rigida auto-mappa di $X_a$.
Il punto $(0,0)$è l'unico punto fermo. I punti della forma$(i,0)$ con $i\ge1$ sono caratterizzati dal fatto che hanno antenati che hanno due genitori, e due distinti di tali punti si trovano a distanze diverse da $(0,0)$. Quindi i punti$(i,0)$ sono fissati da qualsiasi automorfismo di $f_a$. Il punto$(a(n),j)$ con $j\ge1$ non ha antenati con due genitori, il suo primo discendente con due genitori lo è $(a(n),0)$, che è fissato dagli automorfismi di $f_a$, il punto $(a(n),j)$ è a distanza $j$ a partire dal $(a(n),0)$e queste proprietà caratterizzano $(a(n),j)$. Così$(a(n),j)$ è fissato dagli automorfismi di $f_a$.
Questo argomento mostra anche che il $f_a$sono a coppie non isomorfe. Le altre affermazioni sono chiare.
[Se $y=f(x)$ lo diciamo noi $x$è un genitore di$y$. Se$y=f^n(x)$ per $n\in\mathbb N$ lo diciamo noi $x$è un antenato di$y$ e $y$un discendente di$x$.]
insiemistica
Risposte
Sì. In realtà, questa era parte della mia prima risposta a questa domanda , ma questa era una digressione lì (e ho anche postato un'altra risposta alla stessa domanda che l'ha indirizzata ed è stata accettata). Quindi sto copiando questa digressione qui e cancellerò la risposta iniziale a quella domanda per evitare un duplicato.
Fatto. Per ogni set$X$ lì esiste $f\in X^X$ il cui centralizzatore in $\mathrm{Sym}(X)$ è ridotto a $\{\mathrm{id}_X\}$
Si basa sul seguente secondo fatto: esiste (per $X\neq\emptyset$) una struttura ad albero radicata su $X$il cui gruppo di automorfismo è banale. In effetti, concedendo questo e denotando$v_0$ la radice, per un vertice $v$ definire $f(v)$ come $v_0$ Se $v_0=v$e come vertice unico in $[v_0,v]$ a distanza da 1 a $v$altrimenti. Poi$f\in X^X$ e il suo centralizzatore in $\mathrm{Sym}(X)$ è il gruppo di automorfismi dell'albero radicato corrispondente, che è ridotto a $\{\mathrm{id}_X\}$.
Per provare il secondo fatto, se $X$è finito basta prendere un albero lineare radicato in un vertice estremo. Se$X$è infinito, da un argomento elementare ma molto complicato (vedi questa risposta dell'utente "bof"), in realtà esistono per ogni cardinale infinito$\kappa$, $2^{\kappa}$ alberi a coppie non isomorfi del cardinale $\kappa$ciascuno con banale gruppo automorfismo. [È interessante notare che l'induzione richiede davvero di dimostrare che ci sono$>\kappa$ tali alberi, e non solo uno.]