Insieme delle corrispondenze biunivoche

[milos144]

Se $S={ x_1,x_2,x_3}$ un insieme di tre elementi, $A(S)$ è l'insieme delle corrispondenze biunivoche di $S$ su se stesso.

Come si fa a trovare la cardinalità di $A(S)$?

Esiste poi un elemento $t$ (applicazione identica) in $A$ a^-1 in A(A) $(S)$ tale che $a@t=t@a=a$

Esiste un elemento $a^-1 in A(S)$ tale che $a@a^-1=a^-1@a=t$

Mi servirebbe un esempio per capire.

[Kashaman]

Per il primo punto, cerca di capire quante possibile mappe bigettive del tipo $S -> S$ puoi costruire. È tutta una questione di combinatoria. Prima di vedere lo spoiler provaci.

Una generica mappa $\phi : S -> S$ è fatta in questa maniera
$x_1 -> a$
$x_2 -> b$
$x_3 -> c$ dove $a,b,c \in S$.
Cerchiamone quelle bijettive. Poiché $S$ è finito basterà cercare quelle ingettive.
Quindi,
$a \in S$ ,
$b \in S\\{a}$
$c \in S\\{a,b}$
Cioè per $a$ ho tre scelte, per $b$ ne ho due e per $c$ ne ho una.
In totale ho $3*2*1$ funzioni di questo tipo. Cioé $|A(S)|=3$.

Ora prova ad estendere questo che hai visto nel caso particolare..
Se $|S|=n>=1$ , $|A(S)|=?$

Si discosta un po' dall'esercizio, però voglio proporti questo risultato che può essere provato in maniera abbastanza elementare utilizzando la teoria vista qui :
Dimostra che $\forall n \in NN : n!<=n^n$

Per il secondo punto, per applicazione identica si intende una mappa che lascia "fissi" gli elementi, e precisamente, nel nostro caso è questa :
$i :S -> S , \forall j = {1,2,3} : i(x_j)=x_j$.
Verifica tu stesso che per ogni altra mappa $a \in A(S) : a@i=i@a=a$


Per l'ultimo punto, beh, ti garantisce l'esistenza per ogni $a \in A(S)$ di una applicazione inversa. Riusciresti a costruirla?

Una generica mappa puoi pensarla così $a(x_1)= \alpha_1 , a(x_2)=\alpha_2 , a(x_3)=\alpha_3$
Se $g$ è l'inversa di $a$ deve verificarsi che $g@a(x_j)=x_j=a@g(x_j)$.
Ti rendi conto facilmente che basta prendere $g(alpha_j)=x_j$

[milos144]

Intanto grazie per l'aiuto.

Provo a riassumere:

la cardinalità di $A(S)$ ,intesa come numero di funzioni da $A->A$, se $S$ ha $3$ elementi è data da $n^n$, quindi $3^3=27$

Il numero delle funzioni iniettive da $A->A$ è dato invece da $n!$, quindi $3!$ $=6$

In questo caso anche il numero delle funzioni biunivoche è $6$

Non capisco perché tu dicevi che erano $3$

Infine... CI PROVO!...

$n! ≤ n^n $

Per $n = 1$ è banalmente vera.

$P(n) -> P(n+1)$, infatti


$(n + 1)! <= (n + 1)n! <= (n + 1)n^n <= (n + 1)^(n+1) $

[Kashaman]

"milos144":Intanto grazie per l'aiuto.


Non capisco perché tu dicevi che erano $3$

Perché $A(S)$ è l'insieme delle applicazioni biunivoche. L'insieme di tutte le applicazioni però hai ragione.. nel tuo caso ne ha $3^3$, quindi in generale $n^n$

Infine... CI PROVO!...

$n! ≤ n^n $

Per $n = 1$ è banalmente vera.

$P(n) -> P(n+1)$, infatti


$(n + 1)! <= (n + 1)n! <= (n + 1)n^n <= (n + 1)^(n+1) $

Se $T(A)$ è l'insieme di tutte le applicazioni da $A$ in $A$, converrai con me che $A(S)sube T(A)$.
Quindi.. $|A(S)| <= |T(A)|$

[milos144]

Scusami, ma concordi che l'insieme delle funzioni biunivoche nel nostro caso è $6$? Io ho usato la formula $n!$