dato un insieme $ X $, $ |X| $ è la sua cardinalità, ed $ S_X $ è l'insieme delle sue permutazioni (bigezioni di $ X $ in sè, come diavolo preferite chiamarle).
siano $ X $ e $ Y $ non sono vuoti. dimostrare che $ |X|=|Y| $ se e solo se $ S_X\simeq S_Y $.
equipotenze vs isomorfismi
C.N.: poiché $ |X| = |Y| $, esiste $ \varphi: X \to Y $ bigettiva. Per ogni $ f \in \mathcal{S}_X $, succede allora che $ \varphi \circ f \circ \varphi^{-1} $ è una permutazione di $ Y $. Banalmente, $ \psi: \mathcal{S}_X \to \mathcal{S}_Y: f \mapsto \varphi \circ f \circ \varphi^{-1} $ è una biezione.
C.S.: poiché $ \mathcal{S}_X \simeq \mathcal{S}_Y $, esiste un isomorfismo $ \psi: \mathcal{S}_X \to \mathcal{S}_Y $ t.c. $ \mbox{id}_Y = \psi(f) $ [era $ \psi \circ f $], per qualche $ f \in \mathcal{S}_X $.
C.S.: poiché $ \mathcal{S}_X \simeq \mathcal{S}_Y $, esiste un isomorfismo $ \psi: \mathcal{S}_X \to \mathcal{S}_Y $ t.c. $ \mbox{id}_Y = \psi(f) $ [era $ \psi \circ f $], per qualche $ f \in \mathcal{S}_X $.
Ultima modifica di HiTLeuLeR il 13 mag 2007, 12:41, modificato 1 volta in totale.
CN va benissimo, era la freccia facile.
CS non va bene: giusto due obiezioni...
a parte che se la tua dimostrazione funzionasse, avresti dimostrato che $ |2^X| = |2^Y| $ implica $ |X|=|Y| $ (cosa che se non mi hanno riferito male non è dimostrabile con solo ZFC).
detto ciò, la tua $ f $ va da $ X $ in sè, e la componi con una $ \psi $ che va da $ S_X $ ad $ S_Y $... qualcosa non torna!
ritenta, hit, sarai più fortunato!
CS non va bene: giusto due obiezioni...
a parte che se la tua dimostrazione funzionasse, avresti dimostrato che $ |2^X| = |2^Y| $ implica $ |X|=|Y| $ (cosa che se non mi hanno riferito male non è dimostrabile con solo ZFC).
detto ciò, la tua $ f $ va da $ X $ in sè, e la componi con una $ \psi $ che va da $ S_X $ ad $ S_Y $... qualcosa non torna!
ritenta, hit, sarai più fortunato!
Boh, io la farei così, che mi pare anche più facile...
X ha "pressappoco" la stessa cardinalità delle trasposizioni che coinvolgono un certo elemento. Le trasposizioni di X e di Y sono le stesse, via iso, ergo...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Hai ragione. Controesempio: un qualunque automorfismo non interno di $ S_6 $.
Il "pressappoco" era perché le trasposizioni sono in corrispondenza biunivoca con X meno l'elemento scelto, che in generale non ha la stessa cardinalità di X.
Il "pressappoco" era perché le trasposizioni sono in corrispondenza biunivoca con X meno l'elemento scelto, che in generale non ha la stessa cardinalità di X.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
In $ ~ S_X $ consideriamo tutte le permutazioni che lasciano fissi tutti gli elementi, tranne un numero finito. Chiamiamo $ ~ F_X $ questo insieme.
- è un sottogruppo. Infatti, prendiamo $ ~ a,b \in F_X $. Se un elemento è mosso da ab, allora è mosso da a o da b, ma l'unione di insiemi finiti è finita. Per trovare l'inverso, e ancora più banale.
- è un sottogruppo normale. Infatti, consideriamo $ ~ xax^{-1} $: se x manda un certo elemento in un punto fisso di a, allora questo elemento diventa chiaramente un punto fisso di $ ~ xax^{-1} $, e gli elementi la cui immagine è un non-punto-fisso di a, sono finiti.
Ora, abbiamo descritto $ ~ F_X $ dicendo "come sono" i suoi elementi. Proviamo a descriverlo dicendo solo "come si comportanto gli altri" i suoi elementi.
Ad esempio: se compongo un elemento $ ~ a \in S_X $ con $ ~f \in F_X $, allora f non darà troppo fastidio ad a, cambia gli spostamenti solo di pochi elementi. Questo si ripercuote sul commutatore: si verifica facilmente che $ ~ afa^{-1}f^{-1} \in F_X $. Inoltre ogni elemento di $ ~ F_X $ ha un ordine finito. Il claim è: $ ~ F_X $ è il più grande sottogruppo con queste proprietà.
Sia S un sottogruppo con queste proprietà. Ogni elemento di S ha un ordine finito, vuol dire che è un prodotto di cicli finiti. (dalla lunghezza sup. limitata, ma poco importa) Supponiamo che ci sia un elemento s di S che non appartenga ad $ ~ F_X $, questo implica che è prodotto di un numero infinito di cicli disgiunti, di lunghezza finita. Prendiamo giusto una quantità numerabile di cicli, in corrispondenza biunivoca con $ ~\mathbb{Z} $
$ ~ s = \ldots (a_{-10,1}\ a_{-10,2}\ a_{-10,k_{-10}})\ldots (a_{1,1}\ a_{1,2}\ \ldots \ a_{1,k_1}) $$ (a_{2,1}\ a_{2,2}\ \ldots \ a_{2,k_2}) \ldots $
Ora costruiamo una permutazione h tale che $ ~ hsh^{-1}s^{-1} $ ha un ciclo infinito. h è quella permutazione che manda $ ~ a_{i,1} $ in $ ~ a_{i+1,1} $, e lascia fissi tutti gli altri elementi. Si vede facilmente che $ ~ hsh^{-1}s^{-1} $ ha un ciclo infinito che scorre per il primo elementi di ciascun ciclo scelto da s.
Quindi, detto $ ~ f:S_X\rightarrow S_Y $ il nostro isomorfismo, porta $ ~ F_X $ in un sottogruppo di $ ~ S_Y $ che avrà ancora ogni elemento di ordine finito, e avrà ancora la proprietà che $ ~ a\in f(F_X), b \in S_Y \Rightarrow aba^{-1}b^{-1} \in f(S_X) $. Per quanto detto prima, $ ~ f(S_X) \subset F_Y $.
Ora non resta che calcolare la cardinalità di $ ~ F_X $.
Per ogni naturale k, quante sono le permutazioni che lasciano fissi tutti tranne k elementi? Sono in corrispondenza biunuvoca con:
{k-sottoinsiemi di X} x {k-permutazioni senza punti fissi}
ora, essendo il primo insieme infinito e il secondo finito, possiamo tranquillamente dire che sono tante quanti i {k-sottoinsiemi di X}, che sono meno di $ ~ |X^k| $, ma questo è noto (anche se ora come ora non saprei dimostrarlo) essere equipotente a $ ~ |X| $.
Quindi in totale, le permutazioni con finiti punti non fissi sono l'unione di un po' di $ ~ X $, diciamo $ ~ \mathbb{N}\times X $, che è sempre equipotente a X, concludiamo che $ ~ |F_X| = |X| $ (sempre suppondendo X infinito).
Quindi, siccome $ ~ f(F_X) \subset F_Y $ otteniamo $ ~ |Y| \ge |X| $ e anche $ ~ |X| \ge |Y| $, quindi alla fine X,Y sono equipotenti.
Bel problema! In fondo il gruppo delle permutazioni è un buon rappresentante della cardinalità di un insieme.
- è un sottogruppo. Infatti, prendiamo $ ~ a,b \in F_X $. Se un elemento è mosso da ab, allora è mosso da a o da b, ma l'unione di insiemi finiti è finita. Per trovare l'inverso, e ancora più banale.
- è un sottogruppo normale. Infatti, consideriamo $ ~ xax^{-1} $: se x manda un certo elemento in un punto fisso di a, allora questo elemento diventa chiaramente un punto fisso di $ ~ xax^{-1} $, e gli elementi la cui immagine è un non-punto-fisso di a, sono finiti.
Ora, abbiamo descritto $ ~ F_X $ dicendo "come sono" i suoi elementi. Proviamo a descriverlo dicendo solo "come si comportanto gli altri" i suoi elementi.
Ad esempio: se compongo un elemento $ ~ a \in S_X $ con $ ~f \in F_X $, allora f non darà troppo fastidio ad a, cambia gli spostamenti solo di pochi elementi. Questo si ripercuote sul commutatore: si verifica facilmente che $ ~ afa^{-1}f^{-1} \in F_X $. Inoltre ogni elemento di $ ~ F_X $ ha un ordine finito. Il claim è: $ ~ F_X $ è il più grande sottogruppo con queste proprietà.
Sia S un sottogruppo con queste proprietà. Ogni elemento di S ha un ordine finito, vuol dire che è un prodotto di cicli finiti. (dalla lunghezza sup. limitata, ma poco importa) Supponiamo che ci sia un elemento s di S che non appartenga ad $ ~ F_X $, questo implica che è prodotto di un numero infinito di cicli disgiunti, di lunghezza finita. Prendiamo giusto una quantità numerabile di cicli, in corrispondenza biunivoca con $ ~\mathbb{Z} $
$ ~ s = \ldots (a_{-10,1}\ a_{-10,2}\ a_{-10,k_{-10}})\ldots (a_{1,1}\ a_{1,2}\ \ldots \ a_{1,k_1}) $$ (a_{2,1}\ a_{2,2}\ \ldots \ a_{2,k_2}) \ldots $
Ora costruiamo una permutazione h tale che $ ~ hsh^{-1}s^{-1} $ ha un ciclo infinito. h è quella permutazione che manda $ ~ a_{i,1} $ in $ ~ a_{i+1,1} $, e lascia fissi tutti gli altri elementi. Si vede facilmente che $ ~ hsh^{-1}s^{-1} $ ha un ciclo infinito che scorre per il primo elementi di ciascun ciclo scelto da s.
Quindi, detto $ ~ f:S_X\rightarrow S_Y $ il nostro isomorfismo, porta $ ~ F_X $ in un sottogruppo di $ ~ S_Y $ che avrà ancora ogni elemento di ordine finito, e avrà ancora la proprietà che $ ~ a\in f(F_X), b \in S_Y \Rightarrow aba^{-1}b^{-1} \in f(S_X) $. Per quanto detto prima, $ ~ f(S_X) \subset F_Y $.
Ora non resta che calcolare la cardinalità di $ ~ F_X $.
Per ogni naturale k, quante sono le permutazioni che lasciano fissi tutti tranne k elementi? Sono in corrispondenza biunuvoca con:
{k-sottoinsiemi di X} x {k-permutazioni senza punti fissi}
ora, essendo il primo insieme infinito e il secondo finito, possiamo tranquillamente dire che sono tante quanti i {k-sottoinsiemi di X}, che sono meno di $ ~ |X^k| $, ma questo è noto (anche se ora come ora non saprei dimostrarlo) essere equipotente a $ ~ |X| $.
Quindi in totale, le permutazioni con finiti punti non fissi sono l'unione di un po' di $ ~ X $, diciamo $ ~ \mathbb{N}\times X $, che è sempre equipotente a X, concludiamo che $ ~ |F_X| = |X| $ (sempre suppondendo X infinito).
Quindi, siccome $ ~ f(F_X) \subset F_Y $ otteniamo $ ~ |Y| \ge |X| $ e anche $ ~ |X| \ge |Y| $, quindi alla fine X,Y sono equipotenti.
Bel problema! In fondo il gruppo delle permutazioni è un buon rappresentante della cardinalità di un insieme.