md
Un insieme è finito di cardinalità quando esiste una funzione bigettiva , e si scrive
L'insieme vuoto è un insieme finito la cui cardinalità si pone uguale a 0, e si scrive
Se un insieme non vuoto Y è tale che per nessun esiste una funzione bigettiva da a allora si dice che è infinito.
Supponiamo di avere una funzione con . Allora non è iniettiva.
Enunciato generale
Supponiamo di avere una funzione , dove è un insieme di cardinalità e è un insieme di cardinalità , con . Allora f non è iniettiva.
Se oggetti sono sistemati in K scatole, allora c'è (almeno) una scatola che contiene almeno oggetti (qui è la ”parte intera superiore” di , ossia il più piccolo numero intero ).
Supponiamo che e siano insiemi tali che e sia finito. Allora anche è finito e
Supponiamo che sia una funzione fra insiemi finiti e non vuoti tali che . Allora non è surgettiva.
Supponiamo che e siano insiemi finiti non vuoti della stessa cardinalità. Allora una funzione è iniettiva se e solo se è surgettiva.
Dunque, in questo caso dove , per provare che una certa funzione è bigettiva basta provare una sola fra queste due proprietà: è iniettiva o è surgettiva.
Siano e due insiemi. Chiamiamo$ F(X \to Y )$ l'insieme di tutte le funzioni che hanno come dominio e come codominio:
Siano e finiti non vuoti con e . Allora
Sia e .
Proviamo a costruire una funzione da a .
Dove mandiamo ? Abbiamo scelte: .
Dove mandiamo ? Abbiamo sempre scelte: , perché non abbiamo fatto nessuna richiesta sulla funzione (tipo "che sia iniettiva" o "surgettiva" etc…). In generale, dove mandiamo con ? Abbiamo sempre scelte. Dunque alla fine possiamo costruire la nostra funzione in modi diversi.
Siccome ci capiterà di ripetere spesso ragionamenti simili a questo, vale la pena soffermarsi e riscrivere la dimostrazione da un altro punto di vista.
In realtà individuare una funzione equivale ad individuare un elemento del prodotto cartesiano . Infatti un elemento di è una lista di elementi di e per ogni tale lista noi possiamo porre . Viceversa, data una funzione possiamo costruire l'elemento . Dunque vale e noi abbiamo già osservato che .
Chiamiamo l'insieme di tutte le funzioni iniettive che hanno come dominio e come codominio:$ Inj (X \to Y) = {f | f : X \to Y \text{è una funzione iniettiva}}$
Siano e finiti non vuoti con e . Allora
Sia e . Se il lemma dei Cassetti ci dice che. Supponiamo allora e proviamo a costruire una funzione iniettiva da a .
Dove mandiamo ? Abbiamo scelte: .
Dove mandiamox2? Abbiamo scelte, ossia gli elementi di , visto chela funzione deve essere iniettiva.
In generale, dove mandiamo con ? Abbiamo scelte, cioè gli elementi di . In particolare per l'ultimo elemento avremo scelte. Dunque alla fine possiamo costruire la nostra funzione in modi diversi. Come ultima osservazione notiamo che la formula ottenuta vale per ogni e ogni interi positivi, ossia si adatta bene anche al caso in cui : in tal caso infatti la nostra formula è un prodotto di fattori fra i quali è presente anche e dunque ha come risultato che,come abbiamo osservato all'inizio, è proprio il numero di funzioni iniettive da a .
Se allora l'insieme delle funzioni bigettive che hanno come dominio e come codominio è non vuoto:
Siano e finiti non vuoti con . Allora
Visto che allora e dunque si tratta solo di porre nell'enunciato del teorema precedente.
L'insieme delle parti di è l'insieme i cui elementi sono tutti i sottoinsiemi di A:
Osserviamo in particolare che e . In questo paragrafo vogliamo contare quanti elementi ha nel caso in cui sia un insieme finito.
Se allora
Se allora ho solo un sottoinsieme, e la formula torna. Se , per contare quanti sono i sottoinsiemi di immaginiamo di doverne costruire uno. Osserviamo che per individuare un sottoinsieme basta sapere, per ognuno degli elementi di , se tale elemento appartiene o no al sottoinsieme. Possiamo dunque passare in rassegna gli elementi di e per ognuno di loro abbiamo due scelte: SI (sta nel sottoinsieme) oppure NO.
Dunque ci sono distinti sottoinsiemi di . Osserviamo che l'insieme vuoto corrisponde al caso in cui abbiamo ricevuto sempre la risposta NO e l'insieme al caso in cui abbiamo ricevuto sempre la risposta SI.
nelle dispense c'è anche una dimostrazione a pagina 69 molto lunga basata sul'induzione
Dato un insieme finito o infinito, costruiamo dei particolari sottoinsiemi del suo insieme delle parti
Dato , chiamiamo l’insieme i cui elementi sono tutti i sottoinsiemi di che hanno cardinalità :
Indicheremo con il simbolo (si legge: "coefficiente binomiale su ").
Dati , con , vale che
Come prima, fissato un insieme con elementi, cerchiamo di contare la cardinalità di .
Consideriamo e una funzione iniettiva
Chi è ? È un sottoinsieme di di cardinalità , dunque è un elemento di , proprio uno di quelli che dobbiamo "contare". Sarà vero che ogni elemento di lo posso esprimere come immagine di una funzione iniettiva da a ? Sì, preso infatti un elemento di , cioè un sottoinsieme , posso facilmente indicare una funzione iniettiva da a la cui immagine sia proprio : per esempio posso prendere la definita da . Insomma, con le funzioni iniettive da a "raggiungiamo" tutti gli elementi di . Per trovare potremmo allora cominciare a contare , ossia quante sono le funzioni iniettive da a . Ma questo numero lo abbiamo già calcolato: è . È vero allora che ? NO, perché se scriviamo così commettiamo l'errore di contare ogni elemento di più volte. Precisamente, dato un sottoinsieme lo stiamo contando volte, cioè tante volte quante sono le diverse funzioni iniettive possibili da a . Ma sappiamo quanto vale: applicando la formula per il conto delle funzioni iniettive a questo caso particolare in cui dominio e codominio hanno la stessa cardinalità (dunque stiamo in realtà considerando le funzioni bigettive), troviamo che
Allora, visto che col numero abbiamo contato volte ogni elemento di , per avere basterà dividerlo per :
Dati con$ 1 ≤ r < n$, vale
Sia un insieme con elementi. Visto che , possiamo scegliere un elemento . Per calcolare dobbiamo calcolare la cardinalità di . Possiamo adesso dividere in due parti, raggruppando in un sottoinsieme (che chiameremo ) tutti i sottoinsiemi di di cardinalità che contengono , e in un altro (che chiameremo ) tutti i sottoinsiemi di di cardinalità che NON contengono :
Trattandosi di una unione di due insiemi disgiunti, vale che
Ora, un sottoinsieme di cardinalità che contiene è univocamente determinato se si dice quali sono gli altri elementi (quelli diversi da ) che contiene; tali elementi costituiscono un sottoinsieme di cardinalità di . Dunque
Analogamente si osserva che scegliere un sottoinsieme di di cardinalità che non contiene equivale a scegliere un sottoinsieme di di cardinalità , dunque
Allora possiamo concludere che
Il teorema che abbiamo appena dimostrato è il motivo per cui possiamo disporre i coefficienti binomiali in modo da formare il cosiddetto "Triangolo di Pascal-Tartaglia"
Date due variabili e , per ogni vale:
cioè
Cominciamo da un esempio, per avere un'idea di cosa succede. Calcoliamo lo sviluppo di . Se non raggruppiamo i termini troviamo:
Abbiamo espresso come somma di monomi, ognuno dei quali è stato ottenuto, tramite le proprietà distributiva e associativa, scegliendo o o da ogni parentesi che compare in . Quindi, raggruppando adesso i termini tramite la proprietà commutativa, quale sarà il coefficiente di ? Sarà uguale al numero dei monomi in cui troviamo due e una . E questi quanti sono? Sono , ossia sono tanti quanti sono i modi di scegliere due parentesi fra le tre del prodotto (queste saranno le parentesi da cui prendo la ): la prima e la seconda, la prima e la terza, la seconda e la terza. Dunque nello sviluppo avremo . Ovviamente, saremmo arrivati allo stesso risultato contando i modi di scegliere una parentesi fra le tre del prodotto (quella da cui prendo la ), perché . Passiamo al caso generale. Nello sviluppo di troveremo monomi, ciascuno ottenuto scegliendo o o da ognuna delle parentesi del prodotto
Raggruppando i termini, preso un indice con , quale sarà allora il coefficiente di ? Sarà uguale al numero di modi con cui si possono scegliere parentesi fra le del prodotto (quelle da cui prendiamo la ); dunque sarà uguale a . Oppure sarà uguale al numero di modi con cui si possono scegliere parentesi fra le del prodotto (quelle da cui prendiamo la ): infatti come sappiamo . In conclusione, nello sviluppo di troveremo il termine . Siccome questo è vero per ogni , con , abbiamo dimostrato il teorema.