Calcolo combinatorio

Page 1

Definizione 1. Si dice che due insiemiX eY sono equipotentiY se esiste una bigezione tra X e Y . Definizione 2. 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 in quanto (per esempio) l’applicazione f : N→ N tale che per ogni n∈ N, f(n) = 2 n, ` e ingettiva ma non surgettiva. Osservazione 1. SeX ` e un insieme infinito ed ` e contenuto in un insiemeY , allora anche Y ` e infinito. Quindi gli insiemi numerici Z, Q, R sono infiniti in quanto contengono N. Definizione 3. 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 n ∈ N ed ed esiste un’applicazione bigettivaγ :Jn→X, dove Jn ={1, 2,...,n }. Osservazione 2. Nelle stesse condizioni del Teorema 1, si pu` o scrivere X ={γ(1),γ (2),...,γ (n)}. Inoltre si dice che X ha cardinalit` an e si scrive: |X| =n. Proposizione 1. Due insiemi finiti X eY sono equipotenti se e solo se hanno la stessa cardinalit` a. Dimostrazione. Si supponga cheX eY siano equipotenti: allora esiste un’applicazione bigettivaϕ :X→Y ; inoltre esiste n∈ N ed esiste un’applicaione bigettiva γ :Jn→X, per cui |X| = n. Allora l’applicazione ϕ◦γ : Jn→ Y ` e bigettiva, come applicazione composta di due applicazioni bigettive e quindi |Y| =n =|X|. Viceversa, si supponga che |Y| =|X| = n. Allora esistono due applicazioni bigettive γ : Jn → X, ρ : Jn → Y . Poich` e γ ` e bigettiva, si pu` o considerare l’applicazione inversa γ−1 : X→ Jn, anch’essa bigettiva. Quindi l’applicazione ρ◦γ−1 : X→ Y ` e un’applicazione bigettiva di X in Y : questo prova che X e Y sono equipotenti. Definizione 4. Un’applicazione bigettiva di un insieme finito in s´ e si dicepermutazione Osservazione 3.…