Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algebra > TEORIA DEGLI INSIEMI > Flashcards

TEORIA DEGLI INSIEMI Flashcards

1
Q

INSIEME (definizione e notazione)

A

insieme è una qualunque collezione di oggetti. Le lettere maiuscole denotano l’insieme e quelle minuscole gli elementi

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

RAPPRESENTAZIONE DEGLI INSIEMI

A

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}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

SOTTOINSIEMI

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

OPERAZIONI TRA SISTEMI

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

PROPRIETÀ DEGLI INSIEMI

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

INSIEMI DISGIUNTI

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

INSIEME DELLE PARTI

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

CARDINALITA’

A

si dice cardinalità di un insieme A, e si indica con |A|, il numero di elementi dell’insieme.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

TEOREMA [cardinalità di ℘(A)]

A

Se A è un insieme finito e |A| = n, allora |℘(A)| = 2^n

si dimostra per induzione.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

PRODOTTO CARTESIANO

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

TEOREMA (cardinalità di A x B)

A

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à.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

RELAZIONI

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

FUNZIONE

A

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 ƒ.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

ADDIZIONE E MOLTIPLICAZIONE

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

FUNZIONE CARATTERISTICA E FUNZIONE COSTANTE

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

FUNZIONE IDENTITÀ E IMMERSIONE

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

FUNZIONE INIETTIVA (i-i)

A

Una funzione ƒ: A➝B si dice iniettiva (i-i) sse
1. ∀ x₁, x₂ ∈ A, se x₁ ≠ x₂ ⟹ ƒ(x₁) ≠ ƒ(x₂)

  1. ∀ ƒ(x₁), ƒ(x₂) ∈ B, se ƒ(x₁) = ƒ(x₂) ⟹ x₁ = x₂
    utilizzando la legge contronominale
  2. ∀b∈B ∃ al massimo a∈A : b=ƒ(a)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

FUNZIONE SURIETTIVA (su)

A

Siano A e B due insiemi, ƒ: A➝B
∀b∈B ∃ a∈A : ƒ(a) = b
⟹ Imƒ = B

ƒ non è suriettiva se Imƒ ≠ B

19
Q

FUNZIONE BIETTIVA

A

Una funzione ƒ: A➝B si dice obiettiva (o biezione) sse ƒ è iniettiva e suriettiva.

ƒ è i-i e su sse ∀b∈B ∃! a∈A : ƒ(a) = b

20
Q

COMPOSIZIONE DI FUNZIONI

A

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))

21
Q

RELAZIONE INVERSA

A

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.

22
Q

TEOREMA (sulle funzioni inverse)

A

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.

23
Q

RELAZIONI DI EQUIVALENZA

A

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à:

  1. Riflessiva: ∀a∈A aRa
  2. Simmetrica: ∀a,b∈A se aRb ⇒ bRa
  3. Transitiva: ∀a,b,c∈A se aRb e bRc ⇒ aRc
24
Q

CLASSE DI EQUIVALENZA

A

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 }

25
Q

RELAZIONE DI UGUAGLIANZA

A

si definisce relazione di uguaglianza l’insieme di tutte le coppie (a,b) ∈ A² : a=b.

Osservazione: è una relazione di equivalenza.

26
Q

INSIEME QUOZIENTE

A

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.

27
Q

PROPOSIZIONE (sulle classi di equivalenza)

A

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.

28
Q

PARTIZIONE DI UN INSIEME

A

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]ʀ ]

29
Q

PROPRIETÀ RIFLESSIVA, ANTIRIFLESSIVA, NON RIFLESSIVA.

A

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
30
Q

GRAFI

A

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.

31
Q

PROPRIETÀ SIMMETRICA, ANTISIMMETRICA, NON SIMMETRICA.

A

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
32
Q

RELAZIONE D’ORDINE

A

Sia A un insieme, R una relazione binaria su A. R si dice relazione di ordine parziale se soddisfa le seguenti proprietà:

  1. Riflessiva: ∀a∈A aRa
  2. Antisimmetrica: ∀a,b∈A se aRb e bRa ⇒ a = b
  3. 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.
33
Q

RELAZIONE DI ORDINE TOTALE

A

Una relazione R di ordine parziale su A insieme si dice anche totale se vale la seguente proprietà:

  1. 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.

34
Q

MASSIMO E MINIMO

A

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)

35
Q

MASSIMALE E MINIMALE

A

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)
36
Q

MAGGIORANTE E MINORANTE

A

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
37
Q

ESTREMO SUPERIORE E INFERIORE

A
  • 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.
38
Q

RELAZIONE DI BUON ORDINE

A

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.

39
Q

PROPRIETÀ DELLA CARDINALITÀ

A

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|
40
Q

PRINCIPIO DELLA PICCIONAIA

A

Consideriamo n piccioni e m gabbie.

Supponiamo n > m ⟹ ci sarà necessariamente una gabbia con più piccioni

41
Q

TEOREMA (derivato dal principio della piccionaia)

A

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.
42
Q

TEROEMA (numero dei sottoinsiemi di A)

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)!

43
Q

COEFFICIENTE BINOMIALE

A

Si definisce coefficiente binomiale (n su K):

      n                     n!
   (       )  =      -----------------
      K               K! • (n-K)!
44
Q

TEOREMA BINOMIALE DI NEWTON

A

Siano a,b∈ℕ, n∈ℕ.
n n
(a + b) ⁿ = ∑ ( ) aᴷ bᴷ ⁻¹
K=0 K

si dimostra per induzione su n

Algebra (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions