Appunti di Matematica discreta

NUMERI

N N→ ̸ ̸= =⇒ =: è una funzione iniettiva cioè se n mσ σ σN N n m∈/ (N)(σ0 non è suriettiva)⊆ ∈ ⊆W (S) =se tale che 0 alloraS S S SσN NOsservazioni:1. si “postula” l’esistenza di (N, 0, )σ(n) = +2. se scelgo N = 0,1,2, . . . , 1 è iniettivanσ3. corrisponde al principio di induzione4. dai soli assiomi (in maniera ricorsiva) si può costruire la struttura di somma, prodotto con≤ ⇐⇒ ∃k ∈ + =proprietà e introduce la relazione n m n k mN,5. Peano mostra che gli assiomi caratterizzano la terna (N, 0, ) in modo unico a meno di isomorfiσ′ ′′ ′ ∃!ϕ ⇒, , =⇒TEOREMA Se (N, 0, ) e (N 0 ) soddisfano tutti gli assiomi di Peano :σ σ N N′=biunivoca 0ϕ 0 ∀n ∈= cioè mette in corrispondenza 0 e , ed il successivo di n con il successivonϕσ σ ϕn ϕ σNdi ϕ(n). 910 CHAPTER 3. NUMERINATURALI Chapter 4 CARDINALITÀ L'equipotenza è una relazione di equivalenza, cioè ha la proprietà riflessiva, simmetrica e transitiva. Definizione: una funzione f: A -> B è BIUNIVOCA se è iniettiva e suriettiva. f^(-1) indica la funzione inversa di f. Definizione: due insiemi A e B si dicono EQUIPOTENTI se esiste una funzione biunivoca (A B). Esiste un numero naturale n tale che |A| = |B| = n. Definizione: se A e B sono equipotenti, allora si dice che la CARDINALITÀ di A è uguale alla cardinalità di B. La definizione si estende all'insieme vuoto, ponendo |∅| = 0. Definizione: un insieme A si dice FINITO se esiste un numero naturale n tale che |A| = n. Se A è un insieme finito, la cardinalità indica il numero di elementi di A. Osservazione: se f: A -> {1, . . . , n} è biunivoca, f opera in questo modo: f(a_1) = 1, f(a_2) = 2, ..., f(a_n) = n, dove a_1, a_2, ..., a_n sono gli elementi di A. Quindi f definisce un modo per enumerare gli elementi di A.

Contare gli elementi di un dato insieme X: |X|

Una relazione R è un sottoinsieme del prodotto cartesiano X x X: R ⊆ X x X

Relazioni di equivalenza in un insieme X:

• Definizione: Se R è una relazione di equivalenza, allora si chiamano classi di equivalenza di X[a] l'insieme formato da tutti gli elementi che sono equivalenti ad a: X[a]
• Proprietà: La relazione "A sono equipollenti" è una relazione di equivalenza.
1. Riflessività: A è equivalente ad A per ogni A ∈ X: A ~ A
2. Simmetria: Se A è equivalente a B, allora B è equivalente ad A: A ~ B ⇔ B ~ A
3. Transitività: Se A è equivalente a B e B è equivalente a C, allora A è equivalente a C: A ~ B ∧ B ~ C ⇒ A ~ C

La funzione identità in un insieme A è una funzione biunivoca: f: A → A

La funzione inversa è biunivoca: f^-1: A → A

^∃ ⇒ ◦=⇒3.2. se : biunivoca e : biunivoca : prendo : : è ancoraf A B g B C h A C h g fbiunivoca 1112 CHAPTER 4. CARDINALITÀtutti gli insiemi equipollenti con uno stesso insieme finito hanno la stessa cardinalitàCorollario:Osservazione: la relazione di equipollenza vale anche tra insiemi non finitiDefinizione: ⇐⇒ ∼• A si dice NUMERABILE A B⇐⇒• A si dice NON NUMERABILE A né finito né numerabile⇐⇒• A si dice “AL PIÙ” NUMERABILE A è finito o numerabile⇐⇒• A si dice “AL PIÙ” NUMERABILE A è finito o numerabileLo studio del “contare” con insiemi non finiti è stato effettuato da Georg Cantor.4.1 Equivalenza al concetto di insieme finitoTEOREMA Le seguenti condizioni sono equivalenti1. A è infinito2. A contiene un sottoinsieme numerabile3. A è equipotente ad un sottoinsieme improprio=⇒ =⇒ =⇒Dimostrazione: si può dimostrare che 1) 2) 3)1) Definizione di CONFRONTO TRA CARDINALITÀ DI INSIEMI INFINITI:

|A| ≤ |B| ⟺ ∃: iniettiva f: A → B ⟹ A ⊆ B, ⟹ |A| ⊆ |B|, ⟹ = Se vero perché posso scegliere

Osservazione 1: A ⊆ B ⟹ ∃: iniettiva f: A → B ⟹ |A| ≤ |B|

Osservazione 2: La relazione è trasitiva? |A| ≤ |B| e |B| ≤ |C| ⟹ |A| ≤ |C| ⟹ Cioè se ∃ ⟹ ∃ ⟹: se scelgo è ancora iniettiva h: A → C h = g ∘ f ⟹ |A| ≤ |C| ⟹ = ⟹: se scelgo è ancora iniettiva

Osservazione 3: Se (cioè sono equipotenti) A ≈ B ⟹ ∃ ϕ ⟹ |A| ≤ |B| ⟹ = ⟹ Se vuol dire che è biunivoca anche iniettiva ok

A ⊆ B A ≈ B ϕ⁻¹ ∃ ⟹ |B| ≤ |A| ⟹ = ⟹ Inoltre, è biunivoca iniettiva f: B → A ⟹ |A| ≤ |B| |B| ≤ |A| ≈ ∃ ⟹ ∃ ⟹ =

Vale il viceversa? Quindi se Se è iniettiva, è A ⊆ B? f: A → B g: B → A ∃ ⟹ = ⟹ iniettiva ⟹ biiettiva?

h: A → B

La risposta è

sı̀ ed è il contenuto del teorema di Cantor-Bernstein|A| ≤ |B|Osservazione 4: Se vale il teorema vale allora la relazione di confronto tra cardinalitàavrebbe tre proprietà:|A| ≤ |A|1. riflessiva |A| ≤ |B| |B| ≤ |C| |A| ≤ |C|=⇒2. transitiva se e|A| ≤ |B| |B| ≤ |A| ⇐⇒ |A| = |B|=3. antisimmetrica se eUna relazione con le proprietà 1, 2, 3 si dice che è una relazione d’ordine.4.2. CLASSE DELL’INSIEME 134.2 Classe dell’insiemeTEOREMA Se in X c’è una relazione di equivalenza allora le classi di equivalenza formano unaclasse dell’insieme∀a ∈ ̸ =i. 0/ (proprietà riflessiva)X[a]N∀a, ∈ T=⇒ [a] = [b] [a] [b] =ii. oppure 0/ (usando proprietà transitiva e simmetrica)b Xiii. [ [a] = Xa∈XDefinizione: Si chiama QUIZIENTE e si indica con l’insieme di tutte le classi di equivalenzaX(cioè la partizione)La cardinalità di un insieme A, in modo informale, è come

un’etichetta che carat-Osservazione:terizza la classe di equivalenza a cui A appartiene, cioè è le caratteristiche che accomunano gliinsiemi equipotenti ad A

Definizione CONFRONTO TRA CARDINALITÀ EVENTUALMENTE DIVERSE:

|A| ≤ |B|∀A1. (proprietà riflessiva)

|A| ≤ |B| |B| ≤ |C| |A| ≤ |C|=⇒2. e (proprietà transitiva)

|A| ≤ |B| |B| ≤ |A| ⇐⇒ |A| |B|=TEOREMA DI CANTOR-BERNSTEIN Se e cioè A e B sonoequipotenti =⇒Il teorema di Cantor-Bernstein afferma che vale la proprietà antisimmetrica siOsservazione:può concludere che il minore-uguale (≤) è una relazione d’ordine→ |P| |N|=Esempio: : è iniettiva maf P N7−→ |P| ≤ |N|=⇒non suriettivan n ̸ ∃ → ⇐⇒ ∃=Proprietà: Se 0,/ : iniettiva : suriettivaA, B f A B g BarrowA|N| |R|<Esempio:1) ci sono cardinalità intermedie?Non possiamo rispondere, se assumiamo che non ce ne siano stiamo assumendo “l’ipotesi del

con-tinuo”2) ci sono cardinalità più grandi?

Definizione: Dato A un insieme qualsiasi, si chiama insieme delle parti di A, individuato con P(A), la famiglia di tutti i sottoinsiemi di A. |A| = |P(A)|.

Esempio: Se A = {a, b, c}, allora P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. |P(A)| = 8.

Proprietà: Se 2^n = |A|, allora |A| < |P(A)|.

TEOREMA DI CANTOR: |A| ≤ |P(A)|, ma |A| ≠ |P(A)|.

Dimostrazione:

basta trovare una funzione iniettiva f: A → P(A) tale che |A| ≥ |P(A)|.

Voglio dire che esiste una funzione iniettiva f: P(A) → A oppure non esiste una funzione suriettiva g: A → P(A).

Sia f una funzione arbitraria, faccio vedere che non è suriettiva, cioè esiste un B ∈ P(A) che non è nell'immagine di g.

Mostriamo che per ogni B ∈ P(A), esiste un elemento a ∈ A tale che g(a) ≠ B.

Se per def. di B, g(a) = B, allora g(a) ∈ B, ma per def. di B, g(a) ∉ B. ASSURDO.

B (a) a (a) ∈ ∈/ = ⇒ =Se ASSURDOa B (a) a (a) B=⇒ g non può essere suriettiva|A| ≥ |P(A)|=⇒ non vale|A| |P(A)|=⇒ <Chapter 5CONTARE CON INSIEMI FINITI EINFINITI5.1 Contare con insiemi finiti S=TEOREMA (regola della somma) sia una partizione finitaSia A un insieme finito e AA jj∈I|A| ∈ |=⇒ = I|A∑ jjS=N.B.! è una famigliaA A jj∈I∩ ̸= =N.B.! 0/ se (sono a due a due disgiunte)A A i jj iApplicazione: certe volte è utile ”scomporre un insieme” e contare le cardinalità dei sottoinsiemiS={parole da 10 caratteri: si usano solo le lettere a, b e a oppure b compare esattamente una volta}”parola”=”stringa”= sequenza ordinata di simbolilunghezza= numero di elementi della parola o stringa...a a a a a a b...b a a a a a aS= ...a b a a a a a|S|=?={parole con una sola a}Sa ={parole con una sola b}Sb|S | |= =10 ,|S 10a b |S| |S | |S |= + =⇒ = + = + =10 10 20S S Sa ab bDefinizione (ilprodotto cartesiano):Dati A e B se: × ∈ ∈=⇒ = (a,• non sono vuoti :A B b) a A, b B×=⇒ =• A o B oppure entrambi sono 0/ 0/A B n× ̸ × → × × × ×= ... =Osservazione: conta l’ordineA B B A A A A A A|A × |A| · |B|=⇒ =TEOREMA Se A, B sono fin