Insiemi e varie operazioni

Insiemi

Def.: Collezione di oggetti (A: X)

Elemento

Note

Appartiene ∈, non appartiene ∉

a ∈ A A = {1, 2} 3 ∉ A

Non conta l'ordine

Non conteremo i doppi

Inclusione

A ⊂ B se per ogni a ∈ A si ha che A è sottoinsieme di B

Attenzione!!!

a ∈ A a ⊆ A

A ⊆ A

{a} ⊆ A ⊆ A ∪ B

A = B se A ⊂ B ∧ B ⊂ A

Inclusione stretta ⊂

Incluso ⊆ oppure ⊆

Insieme vuoto ø

{ }

ø = contenuto in qualsiasi insieme

Insieme delle parti

P(A) = l'insieme di tutti i sottoinsiemi di A

A = {1, 2}

P(A) = {ø, {1}, {2}, {1, 2}}

Oss: se n = n elementi, P(n) = 2ⁿ elementi

Insiemi infiniti

• N: Naturali
• Q: Razionali
• C: Complessi
• Z: Interi
• R: Reali

Operazioni tra insiemi

Unione ∪

A ∪ B = {x ∈ X ∣ x∈ A ∨ x ∈ B}

Intersezione ∩

A ∩ B = {x ∈ X ∣ x ∈ A ∧ x ∈ B}

Differenza

A\B = {x ∈ X ∣ x ∈ A ∧ x ∉ B}

Complementare rispetto a A

Connotato come Δ

Complementare

A ∪ A^c = X

Prodotto cartesiano

A × B = {(a, b) ∈ X × X ∣ a ∈ A, b ∈ B}

Oss

A × B ≠ B × A

Insiemi

Def: "Collezione di oggetti".

Elemento

Note:

Appartiene ∈ → non appartiene ∉

a ∈ A, A = {1, 2, 3} → se

Non conta l'ordine

Non contare i doppi elementi

Inclusione

A ⊆ B se per ogni a ∈ A si ha che a ∈ B allora A è sottoinsieme di B.

Attenzione!!!

a ∉ A ⇒ A ≠ a

∀A A ⊆ A

∀A ∅ ⊆ A

B = B e A ⊂ B e B ⊄ A

Inclusione stretta A ⊂ B

Incluso in doppio

Insieme vuoto ∅

{ ∅ }

A ⊆ P(A) = contenuto in qualsiasi insieme

Insieme delle parti

Insieme delle parti = insieme di tutti i sottoinsiemi di A

A = {1, 2} P(A) = { {1}, {2}, {1, 2}, {3}, {} }

Oss se n = n elementi, P(A) n 2n elementi

Insiemi infiniti

N = naturali Q = razionali C = complessi

Z = interi R = reali

Operazioni tra insiemi

Unione ⋃

A ⋃ B = { x ∈ A ∨ x ∈ B }

Intersezione ⋂

A ⋂ B = { x : x ∈ A ∧ x ∈ B }

Complemento

A \ B = { x ∈ A ∧ x ∉ B }

Complemento rispetto A

Complementare rispetto A

Complemento

A \ B

Complemento

A - B

Insieme differenza A

Prodotto cartesiano

A × B = { (a, b) ∈ X x B | a ∈ A, b ∈ B }

Oss A × B ≠ B × C X × X

Proprietà

Fondamentali leggi de Morgan/de Monne

• 1. (A∪B)^c = A^c∩B^c
• 2. (A∩B)^c = A^c∪B^c

Elementari

• A∪∅ = A
• X∩X = X
• A∩∅ = ∅
• A∪A = A
• A∩X = A∪X = X

Nota: quantificatori

• ∀ per ogni
• ∃ esiste
• ! esiste ed è unico
• ∃: t.c
• ∀x∈A, ∃B
• ∀x∈A, ∃B
• ∀A, B∈B

Proposizione

Si può dire univocamente se è vera o falsa

• A, M∈N ∧ M/N ∧ M/NM è una proposizione.

X ∈N per Paolo oggi non è una proposizione.

Negazione di una proposizione

Q ¬nonP

¬Q nonP

¬F V

Connettivo logico

“e”, “o” se almeno uno

∧ ∨

∧ ∧

¬ entrambi

∧ ∧ almeno uno

Q(n): n è pari

O(n): n è multiplo di 5

(P⊕Q)(n) = O(n) per n multiplo di 3

(P⊕Q)(10) ⇒ V

(P⊕Q)(18) ⇒ F

(P⊕Q)(20)=¬(n è il primo multiplo di 5)

P(e), Q(n) :

P: n ∈ Pn; ∀α > n : (α ∈ n) vera;

Q(α): Q(n) : n ∈ Qn; ∀(n ∈ α) n è vera.

Implicazione

Q → P = (¬Q) ∨ Q P imp⇒ Q

P è condizione sufficiente per Q

Q è condizione necessaria per P

Quindi l'operazione logica implicazione è simmetrica

Se "Se Studi, passerai l'esame";

¬ Studiare → ¬ passare l'esame

Teorema

Dimo: dimostrare che è vero un'implicazione del tipo: ∀x∈X (P(x) ⇒ Q(x))

∀n∈N: {n è pari} Q(n): n è pari; P(n): n = k 4; k ∀n∈N {P(n) ⇒ Q(n)}

Dim

Fisso m ∈ N dobbiamo vedere che P(n) ⇒ Q(n)

Se ¬Q(n) ( supp) → Q(n+1) Q(m) vera;

P è pari,

Q(m) vera v è pari n ≡ k = 2k + 1, n² = 2n¹ = 4 x (n)² + 1

∀n∈N {Q(n ) ⇒ P(n)} No!

P(n)⇒(n dispari) quindi → fermo dispari.

P è abbassamento; ¬ non(∀n ∈ N) ⇒ Q(n) ∃N∈N tc. non(Q(n)) = Q(m) Q(n) e non(Q(m))

Negazione di una proposizione

Non (p ∨ q) = (non p) ∧ (non q)

Non (p ∧ q) = (non p) ∨ (non q)

Regola generale: per negare una proposizione con ∀, ∃

Cambiano si scambiano ∀ e ∃

Es. non (∀x, β(x)) = ∃x, non β(x)

Non (∃x, β(x)) = ∀x, non β(x)

Non (∃x ∈ R)(x² ≤ 0)

∀x ∈ R, non (x² ≤ 0)

Dimostrazione per contronominale

Dim. per contronominale

∀x, β(x) ⇔ ∃x0 s.t. non β(x)

Equivalente ∀x, non β(x) ⇒ non β(x)

Es. n ∈ N = n pari ⇒ n è pari

Dimostrazione per assurdo

Dim. per assurdo

Non esiste un numero razionale il cui quadrato è 2

∃a: q² = 2

a = m/n ∈ Q con m, n primi tra loro, n ≠ 0

q² = m²/n² ⇔ 2 = m²/n² ⇔ m² = 2n²

Quindi m ∈ Dispari ⇒ m² è pari

Proprietà assiomi

Assioma 1:2 definita in R, θ (0) un'operazione...

Assioma 2:2 con cui R, θ (0) un'operazione...

Assioma 3:3 definiti in un insieme.

Assioma 4:4 secondo pari...

R, Q sono altri gruppi abeliani

Nota x ∈ A quando x ∉ A, x ∉ _Q(i dati di descrivere le lunghezze)

Assioma di completude

(dell'elemento separatore)

∀a,b,c ∈ R non vuoti ∃c ∈ R w(c)(a non ∃ SER elemento separatore ∃ ∃(c*b))

Oss. assioma al completezza non vale in Q

A = {11/2