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 }
