TEORIA DEGLI INSIEMI Flashcards
INSIEME (definizione e notazione)
insieme è una qualunque collezione di oggetti. Le lettere maiuscole denotano l’insieme e quelle minuscole gli elementi
RAPPRESENTAZIONE DEGLI INSIEMI
Gli insiemi si possono rappresentare per elencazione, ad esempio N: {0,1,2,..}.
Oppure per rappresentazione caratteristica mediante una proprietà,
A: {x: x soddisfa una proprietà P}
esempio: A= {x∈N : 2|x}
SOTTOINSIEMI
siano A e B sue insiemi;
- A si dice sottoinsieme di B se ogni elemento di A è anche in B (A ⊆ B)
- A si dice sottoinsieme proprio di B se è sottoinsieme ma esiste almeno un elemento di B che non è in A (A ⊊ B)
osservazione: siano A e B insiemi, A ⊆ A sempre e
A=B sse A ⊆ B e B ⊆ A.
OPERAZIONI TRA SISTEMI
INTERSEZIONE: A ∩ B = { x∈S: x∈A ⋀ x∈B}
UNIONE: A ∪ B = { x∈S: x∈A ∨ x∈B}
DIFFERENZA: A - B = { x∈S : x∈A ⋀ x∉B}
COMPLEMENTO: A’ = { x∈S : x∉A} = S - A
PROPRIETÀ DEGLI INSIEMI
1) A ∩ B = B ∩ A
2) A ∩ A = A
3) A ∩ ø = ø
4) A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∪ (B ∪ C) = (A ∪ B) ∪ C
5) A ∩ ( B ∪ C) = (A ∩ B) ∪ (A ∩ C)
INSIEMI DISGIUNTI
due insiemi A e B si dicono disgiunti se la loro intersezione è l’insieme vuoto. (A ∩ B = ∅)
ATTENZIONE
disgiunti non implica diversi
diversi non implica disgiunti
INSIEME DELLE PARTI
sia A un insieme. si dice insieme delle parti di A l’insieme dei sottoinsiemi di A, si denota con ℘(A).
Gli elementi di℘(A) sono i sottoinsiemi di A. In particolare ∅ ∈ ℘(A) e A ∈ ℘(A).
CARDINALITA’
si dice cardinalità di un insieme A, e si indica con |A|, il numero di elementi dell’insieme.
TEOREMA [cardinalità di ℘(A)]
Se A è un insieme finito e |A| = n, allora |℘(A)| = 2^n
si dimostra per induzione.
PRODOTTO CARTESIANO
siano A e B insiemi, si dice prodotto cartesiano di A e B, e si denota con AxB l’insieme {(a,b) : a∈A ⋀ b∈B}
A^2 abbrevia A x A
A x B ≠ B x A
TEOREMA (cardinalità di A x B)
siano A,B insiemi finiti. Allora |A x B| = |A| • |B|.
Dim. Vi sono |A| possibilità di scegliere un elemento di A come prima componente di una coppia ordinata in A x B, e, per ognuna di queste possibilità, |B| opportunità di scegliere un elemento di B come seconda componente della coppia. Complessivamente si ottengono |A| • |B| possibilità.
RELAZIONI
siano A,B insiemi. Si chiama relazione di A e B un sottoinsieme R di A X B.
Per A=B si parla di relazione binaria su A
è preferibile scrive aRb invece di (a,b) ∈ R.
OSSERVAZIONE: R ⊆ ∏Ai
(con ∏ produttoria che va da i=1 ad n di A con i).
FUNZIONE
si dice funzione o applicazione di A in B una relazione ƒ tale che,
∀a∈A, esiste uno e un solo b∈B per cui aƒb
- per a∈A, b∈B, aƒb, si scrive b=ƒ(a)
- b si dice elemento immagine di a
- a si dice elemento retro immagine di b
- per ogni X⊆A ƒ(X)= { ƒ(a)∈B : a∈X} ⊆B
- per ogni Y⊆B ƒ^-1(Y)= { a∈A : ƒ(a)∈Y} ⊆A
- A si dice Dominio della funzione
- B si dice Condominio della funzione
- ƒ(A) = {ƒ(a)∈B : a∈A} (ƒ(A) si dice immagine di A tramite ƒ.
ADDIZIONE E MOLTIPLICAZIONE
- Si definisce l’operazione addizione “+” con una funzione da N in N definita nel modo seguente:
+: N x N ➝ N ∀(a,b) ∈ N^2 , (a,b)⟼ a+b - Si definisce l’operazione moltiplicazione “•” con una funzione da N in N definita come segue:
• : N x N ➝ N. ∀(a,b) ∈ N^2 , (a,b)⟼ a•b
FUNZIONE CARATTERISTICA E FUNZIONE COSTANTE
- Sia S un insieme. un sottoinsieme A ⊆ S
1 x∈ A
ƒA: S ➝ {0, 1} ƒ(x) = { ∀x∈S
0 x∉ A
funzione caratteristica (ƒ test) - Siano A, B insiemi, c∈B fissato. Si dice funzione costante la funzione ƒ definita come segue:
ƒ: A➝B ∀a∈A ƒ(a) = c
FUNZIONE IDENTITÀ E IMMERSIONE
- Sia A un insieme, si dice funzione identità di A, idA, la funzione definita come segue:
idA: A➝A ∀a∈A idA(a) = a - Sia B un insieme e A⊆B, si dice immersione di A in B la funzione definita come segue:
i: A➝B ∀a∈A i(a) = a
FUNZIONE INIETTIVA (i-i)
Una funzione ƒ: A➝B si dice iniettiva (i-i) sse
1. ∀ x₁, x₂ ∈ A, se x₁ ≠ x₂ ⟹ ƒ(x₁) ≠ ƒ(x₂)
- ∀ ƒ(x₁), ƒ(x₂) ∈ B, se ƒ(x₁) = ƒ(x₂) ⟹ x₁ = x₂
utilizzando la legge contronominale - ∀b∈B ∃ al massimo a∈A : b=ƒ(a)
FUNZIONE SURIETTIVA (su)
Siano A e B due insiemi, ƒ: A➝B
∀b∈B ∃ a∈A : ƒ(a) = b
⟹ Imƒ = B
ƒ non è suriettiva se Imƒ ≠ B
FUNZIONE BIETTIVA
Una funzione ƒ: A➝B si dice obiettiva (o biezione) sse ƒ è iniettiva e suriettiva.
ƒ è i-i e su sse ∀b∈B ∃! a∈A : ƒ(a) = b
COMPOSIZIONE DI FUNZIONI
Siano A, B e C insiemi, ƒ: A➝B e g: B➝C
Si definisce composizione di ƒ con g, “g∘ƒ”,
la funzione definita come segue:
g∘ƒ: A➝C g∘ƒ(a) = g(ƒ(a))
RELAZIONE INVERSA
Siano A, B insiemi. Sia R una relazione di A e B.
Si definisce relazione inversa di R la relazione R⁻¹ di A e B definita nel modo seguente:
(b,a) ∈ R⁻¹ (⊆ B x A) sse (a,b) ∈ R
bR⁻¹a sse aRb
sia ƒ: A➝B, posso definire la funzione inversa
ƒ ⁻¹ sse ƒ è biettiva.
TEOREMA (sulle funzioni inverse)
Sia ƒ: A➝B, allora ƒ ⁻¹ : B➝A è una funzione di B in A sse f è biettiva, in particolare ƒ ⁻¹ è biettiva.
Dim: ƒ ⁻¹ : B➝A è una funzione di B in A ⟺
∀b∈B ∃! a∈A : ƒ ⁻¹(a) = b ⟹ (b,a) ∈ ƒ ⁻¹ ⟺ (a,b)∈ƒ
⟹ ƒ(a) = b ⟹ ƒ è biettiva.
ƒ : A➝B è una funzione ⟹ ∀a∈A ∃! b∈B : b=ƒ(a)
aƒb ⇒ (a,b)∈ƒ ⇒ (b,a) ∈ ƒ ⁻¹ ⇒ ƒ ⁻¹(b) = a ⇒ ƒ ⁻¹ biettiva.
RELAZIONI DI EQUIVALENZA
Sia A un insieme e R una relazione binaria su A.
Si dice che R è una relazione di equivalenza sse (con R definita ∀a,b ∈ R, aRb) valgono le seguenti tre proprietà:
- Riflessiva: ∀a∈A aRa
- Simmetrica: ∀a,b∈A se aRb ⇒ bRa
- Transitiva: ∀a,b,c∈A se aRb e bRc ⇒ aRc
CLASSE DI EQUIVALENZA
Sia A un insieme, R una relazione di equivalenza su A. Fisso a∈A.
Si definisce classe di equivalenza dell’elemento a rispetto alla relazione R, si indica con [a]ʀ, l’insieme definito
[a]ʀ = { b∈A : aRb }
RELAZIONE DI UGUAGLIANZA
si definisce relazione di uguaglianza l’insieme di tutte le coppie (a,b) ∈ A² : a=b.
Osservazione: è una relazione di equivalenza.
INSIEME QUOZIENTE
Si definisce insieme quoziente di A rispetto alla relazione R, l’insieme definito nel modo seguente:
A/R = { [a]ʀ : a∈A }
cioè tutte le classi di equivalenza di A rispetto alla relazione di equivalenza r.
PROPOSIZIONE (sulle classi di equivalenza)
Siano A un insieme e R relazione di equivalenza.
a,b∈A : aRb ⇒ [a]ʀ = [b]ʀ
se (a,b)∉R ⇒ [a]ʀ ∩ [b]ʀ = ø
Dim. - (⊆) ⇾ { [a]ʀ ⊆ [b]ʀ } ∀c∈[a]ʀ devo dimostrare che c∈[b]ʀ.
c∈[a]ʀ ➝ cRa (per definizione di classe di eq.) ➝ cRb (siccome R è transitiva e per hp aRb) ➝ c∈[b]ʀ.
- (⊇) ⇾ { [a]ʀ ⊇ [b]ʀ } ∀c∈[b]ʀ devo dimostrare che c∈[a]ʀ.
c∈[b]ʀ ➝ cRb (per definizione di classe di eq.) ➝ cRb (siccome R è transitiva e per hp bRa poiché R riflessiva) ➝ c∈[a]ʀ.
- Supponiamo che [a]ʀ ∩ [b]ʀ ≠ ø. Assumiamo cioè che ∃c∈A : c∈[a]ʀ ∩ [b]ʀ ➝ c∈[a]ʀ e c∈[b]ʀ (per def. di ∩) ➝ aRc e cRb ➝ aRb.
Assurdo perché per ipotesi (a,b)∉R.
PARTIZIONE DI UN INSIEME
Sia A un insieme, si dice Partizione dell’insieme A una famiglia di sottoinsiemi di A che sono:
- non vuoti➝ [ [a]ʀ ≠ ø ∀a∈A perché a∈[a]ʀ (aRa) ]
- a due a due disgiunti➝ [ se a≠b, [a]ʀ ∩ [b]ʀ = ø ]
- ⋃ sottoinsiemi coincide con A➝ [ ∀a∈A, a∈[a]ʀ
A=⋃[a]ʀ ]
PROPRIETÀ RIFLESSIVA, ANTIRIFLESSIVA, NON RIFLESSIVA.
Sia A un insieme e R relazione binaria su A
- Riflessiva: ∀a∈A aRa
- Non riflessiva: ¬(∀a∈A aRa) ➝ ∃a∈A : a non è in relazione con a
- Antiriflessiva: ∀a∈A, a non è in relazione con a
GRAFI
Si definisce grafo non orientato o semplicemente grafo, la coppia (V,R) dove V è un insieme no vuoto e R è una relazione antiriflessiva e simmetrica.
Gli elementi di V si dicono vertici o nodi.
le coppie della relazione R si dicono archi o lati.
PROPRIETÀ SIMMETRICA, ANTISIMMETRICA, NON SIMMETRICA.
Sia A un insieme e R una relazione binaria su A
- Simmetrica: ∀a,b∈A aRb ➝ bRa
- Non simmetrica: ∃a,b∈A: aRb ⇏ bRa
- Antisimmetrica: ∀a,b∈A se aRb e bRa ⇒ a=b
RELAZIONE D’ORDINE
Sia A un insieme, R una relazione binaria su A. R si dice relazione di ordine parziale se soddisfa le seguenti proprietà:
- Riflessiva: ∀a∈A aRa
- Antisimmetrica: ∀a,b∈A se aRb e bRa ⇒ a = b
- Transitiva: ∀a,b,c∈A se aRb e bRc ⇒ aRc
Un insieme A con una relazione R di ordine parziale si dice parzialmente ordinato. Una coppia (A,R) si dice parzialmente ordinata se R relazione di ordine parziale sull'insieme A.
RELAZIONE DI ORDINE TOTALE
Una relazione R di ordine parziale su A insieme si dice anche totale se vale la seguente proprietà:
- Dicotomia: ∀a,b∈A aRb oppure bRa
cioè a e b sono sempre confrontabili rispetto alla relazione R.
Se R è relazione di ordine totale si dirà che l’insieme (A,R) è totalmente ordinato.
MASSIMO E MINIMO
Sia A un insieme e R una relazione di ordine parziale e a∈A.
- a si dice ELEMENTO DI MINIMO in A rispetto alla relazione R sse
aRb ∀b∈A (a = minᵣ A) - a si dice ELEMANTO DI MASSIMO in rispetto alla relazione R sse
bRa ∀b∈A (a = maxᵣ A)
OSSERVAZIONE: se ∃ a = minᵣ A o a = maxᵣ A essi sono unici
(si dimostra per assurdo)
MASSIMALE E MINIMALE
Sia A un insieme, R relazione di ordine parziale e a∈A
- Si dice che a∈A è MINIMALE sse
∀b∈A se bRa ⇒ b = a
(∀b∈A, b ≠ a, allora b NON è in relazione R con a, cioè a è minimale se nessun altro elemento distinto e in relazione con lui) - Si dice che a∈A è MASSIMALE sse
∀b∈A se aRb ⇒ a = b
(∀b∈A, b ≠ a, allora a NON è in relazione R con b)
MAGGIORANTE E MINORANTE
Sia (A,R) un insieme parzialmente ordinato, X⊆A, X ≠ Ø.
- Sia x∈A, x si dice MINORANTE di X rispetto alla relazione R sse
xRb ∀b∈X si denota con MINORʀ(X) l’insieme dei minoranti
di X rispetto ad R - Sia x∈A, x si dice MAGGIORANTE di X rispetto alla relazione R sse
bRx ∀b∈X si denota con MAGGIORʀ(X) l’insieme dei
maggioranti di X rispetto ad R
ESTREMO SUPERIORE E INFERIORE
- Si definisce estremo superiore di X, si denota con supᵣ X, il minimo dei maggioranti.
- Si definisce estremo inferiore di X, si denota con infᵣ X, il massimo dei minoranti.
RELAZIONE DI BUON ORDINE
Una relazione di ordine parziale su un insieme A si dice di BUONORDINE se
∀X⊆A, X ≠ Ø, X ammette un elemento di minino rispetto alla relazione R.
Si dice che (A, R) è un insieme BENORDINATO se R è una relazione di buonordine.
OSSERVAZIONE: dati a,b∈A, (A, R) insieme benordinato, il sottoinsieme {a,b} ammette minimo ➝ aRb oppure bRa ⇒ R relazione di ordine totale.
PROPRIETÀ DELLA CARDINALITÀ
Siano A,B,C insiemi finiti.
- |℘(A)| = 2^n
- | A x B | = |A| x |B|
- | A ⋃ B | = |A| + |B| - |A ⋂ B|
- | A ⋃ B ⋃ C | = |A| + |B| + |C| - |A ⋂ B| - |B ⋂ C| - |A ⋂ C| + |A ⋂ B ⋂ C|
- | A - B | = |A| - |A ⋂ B|
- se B⊆A | A - B | = |A| - |B|
PRINCIPIO DELLA PICCIONAIA
Consideriamo n piccioni e m gabbie.
Supponiamo n > m ⟹ ci sarà necessariamente una gabbia con più piccioni
TEOREMA (derivato dal principio della piccionaia)
Dati A e B insiemi finiti, A = {a₁, …., an} e B = {b₁, …., bn}, |A| = n e |B| = m, allora:
- ∃ una funzione iniettiva da A in B sse n ≤ m
- ∃ una funzione suriettiva da A in B sse n ≥ m
- ∃ una funzione biettiva da A in B sse n = m
DIMOSTRAZIONE: per costruzione di funzioni.
COROLLARIO: A, B insiemi finiti, |A| = N e |B| = m, e n ≤ m allora:
- esistono m•(m-1)• ….. •(m-n+1) funzioni iniettive da A in B.
- esistono mⁿ possibili funzioni di A in B.
- ƒ: A➝A ƒ i-i sse su sse biettiva. Esistono n! funzioni biettive da A in B.
TEROEMA (numero dei sottoinsiemi di A)
Sia A un insieme di n elementi (n∈ℕ) e sia K ≤ n. Allorail numero dei sottoinsiemi di A di K elementi e uguale a:
n! ∕ K! • (n-K)!
COEFFICIENTE BINOMIALE
Si definisce coefficiente binomiale (n su K):
n n!
( ) = -----------------
K K! • (n-K)!
TEOREMA BINOMIALE DI NEWTON
Siano a,b∈ℕ, n∈ℕ.
n n
(a + b) ⁿ = ∑ ( ) aᴷ bᴷ ⁻¹
K=0 K
si dimostra per induzione su n
