Permutazioni

Page 1

Insiemi infiniti - insiemi finiti - applicazioni tra insiemi finiti Definizione 1. Si dice che un insieme X ` einfinito se esiste un’applicazione ingettiva ma non surgettiva di X in X. Esempio 1. Sicuramente l’insieme N dei numeri naturali ` e infinito: infattti si pu` o considerare, per esempio, l’applicazione f : N→ N tale che per ogni n∈ N, f(n) = 2n. Si vede facilmente che f ` e ingettiva ma non surgettiva. Osservazione 1. Se un insieme infinito X ` e contenuto in un insiemeY , allora anche Y ` e infinito. Definizione 2. Si dice che un insieme X ` efinito se ` e vuoto o se non ` e infinito. Teorema 1. Sia X un insieme finito non vuoto. Allora esiste un sottoinsieme Jn = {1, 2,...,n } di N ed esiste un’applicazione bigettiva γ :Jn→X. Osservazione 2. Nelle condizioni del Teorema 4, si pu` o scrivere X ={γ(1),γ (2),...,γ (n)}. Inoltre si dice che X ` eequipotente a Jn e che ha cardinalit` an e si scrive: |X| =n. In parole povere la cardinalit` a di X ` e il numero degli elementi di X. Inoltre, se Y ` e un altro insieme bigettivo a Jn, si dice anche che X e Y sono equipotenti. Si osservi infine che per dimostrare che due insiemi finiti X eY hanno la stessa cardinalit` a, basta provare che esiste un’applicazione bigettiva tra X e Y . Osservazione 3. Siano X, Y due insiemi finiti. Allora pu` o esistere un’applicazione ingettiva aventeX come insieme di partenza eY come insieme di arrivo solo se|X|≤| Y|; invece pu` o esistere un’applicazione surgettiva solo se |X|≥| Y|. Infine, se |X| =|Y| allora un’applicazione f :X→Y ` e ingettiva se e soltanto se ` e surgettiva e quindi se e soltanto se ` e bigettiva. Definizione 3. Un’applicazione bigettiva di un insieme finito in se si dice permu- tazione. Posto A ={a1,...,a n}, una permutazionef diA si pu` o rappresentare tramite una matrice di tipo…