Insiemi: proprietà, definizioni ed esempi

DEFINIZIONE

Un insieme con 0 elementi è denotato con {} oppure con 0 ed è detto insieme vuoto.

insieme non finiti, con un numero di elementi infinito (ad esempio l’insieme dei

Insiemi infiniti:

numeri naturali)

Un insieme può essere indicato, con l’utilizzo delle notazioni, in due modi:

 Notazione estensionale: elenco tutti gli elementi presenti nell’insieme

 ∀ ∈

Notazione intenzionale: descrivo una proprietà che caratteriza gli elementi. Esempio: { n N | n è

∀ ∈

pari e 1 < n < 7} (si legge: per ogni ( ) elemento n appartenente ( ) all’insieme N tale che (|) n è

pari ed è compreso tra 2 e 5) -> N = {2, 4, 6}

ESEMPI

A = {studenti s in questa aula | s è simpatica} -> {x, y, k}

∈

B = {n N | n è dispari e n è multiplo di 4} -> {}

DEFINIZIONE: Intersezione

L’intersezione di due insiemi A e B è un insieme che contiene gli elementi comuni ad A e B e si

indica con il segno ∩. A ∩ B = {x | x ∈ ∈

A e x B}

DEFINIZIONE: Unione

L’unione di due insiemi A e B è l’insieme formato da tutti gli elementi di A e tutti gli elementi di B

∪.

e si indica con il segno ∈ ∈

∪

A B = {x | x A oppure x B}

ESEMPIO A = {1, 2, 3, a, b}; B = {1, 3, 5, b, c, d}

A ∩ B = {1, 3, b}

∪

A B = {1, 2, 3, 5, a, b, c, d}

Quando A ∩ B = {} si dice che A e B sono DISGIUNTI ⊆

Se A = {1, 2, 3} e B = {1, 2, 3, 4, 5, 6}, si dice che A è INCLUSO in B -> A B (B è un

∩ ∪

sottoinsieme di A). In questo caso, A B = B e A B = A.

DEFINIZIONE

Si dice che B è INCLUSO in A se ogni elemento di B appartiene ad A

<!> IMPORTANTE <!>

 ⊆

Ogni insieme è un sottoinsieme di se stesso: A A

 ⊆

L’insieme vuoto è incluso in qualsiasi insieme: {} A

PARTE 2 ∈

{ x N | x è pari }

N = insieme dei numeri naturali

PROPRIETA’: se x è pari

In genere si scrive { x | P(x) } : insieme degli elementi x che soddisfano la proprietà P

Esempio

Sia P(x) la proprietà “x è nato nel 1996” e Q(x) “x è nato a Varese”

A = { x | P(x) } = { x | x è nato nel 1996 } e B = { x | Q(x) } = { x | x è nato a Varese }

A ∩ B = { x | x è nato a Varese nel 1996 }

∪

B A = { x | x è nato nel 1996 oppure è nato a Varese }

⊆

1. A B = E’ vero che tutti i nati nel 1996 sono nati a Varese?

⊆

2. A B = E’ vero che tutti i nati a Varese sono nati nel 1996?

Per rispondere alle domande 1 e 2 dobbiamo trovare un contro-esempio ovvero un elemento che

non soddisfa una delle due richieste (ad esempio una persona nata a Varese ma non nel 1996 oppure

nata nel 1996 ma non a Varese).

ESERCIZIO

∈

P = {n N | x è pari }

∈

D = {n N | x è dispari }

l’ultima cifra di x è 3 }

∈

T = {n N |

∈

Q = {n N | x è multiplo di 4 }

P ∩ D = {}

∪

P D = N

T ∩ Q = {}

T ∩ Q = T

Q ∩ P = Q

⊆

Q T = NO (non ci sono multipli di 4 che finiscono con il numero 3)

⊆

Q P = SI (tutti i multipli di 4 sono numeri pari)

⊆

Q D = NO (non ci sono multipli di 4 che sono dispari)

⊆

T D = SI (tutti i numeri che finiscono per 3 sono dispari)

DEFINIZIONE

– ∈ ∈

a \ B (= A B) = { x A e x B }

N \ D = P, N \ P = D

DEFINIZIONE

Se x è un insieme finito si indica |x| la cardinalità di x cioè il numero di elementi di x (è anche

chiamata ordine di x)

ESEMPIO

Se x = {a, b, c} allora |x| = 3

∪ ∪

Cosa possiamo dire di |A B|? Se |A| = 3 e |B| = 4 ( A = {a, b, c} e B = {b, c, d, e}) allora |A

B|=5 ≤

∪

max(A oppure B) |A B| |A| + |B|

| {} | = 0

E’ vero che tutti gli studenti di questa aula sono laureati in informatica sono seduti al centro? (in

pratica non ci sono studenti laureati) la risposta è SI, vediamo perchè:

L = { x | x è laureato in informatica }

C = { x | x è seduto al centro }

⊆ ⊆

L C ? -> L = {} -> {} C -> SI

DEFINIZIONE

L’insieme delle parti di un insieme A è l’insieme formato da tutti i sottoinsiemi di a. Si indica con

P(A) (p=pARTI)

A = {a, b, c}

P(A) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A }

B = {a, b}

P(B) = { {}, {a}, {b}, {a,b} OPPURE B }

C = {a}

P(C) = { {}, {a} }

PROPRIETA’

Se l’insieme A ha N elementi allora | P(A) | = N

2

DEFINIZIONE

Una coppia di elementi è formata da 2 elementi tra i quali si distingue un primo e un secondo. Si

usa la notazione (a, b) (a, b) ≠ (b, a) e (a, b) ≠ {a, b}

DEFINIZIONE ∈ ∈

Dati 2 insiemi A e B, si chiama il prodotto cartesiano di A per B (A x B) = { (a, b) | a A, b B }

ESEMPIO

A = { nomi degli studenti } e B = { numero di telefono }

A x B = { (a, b) | a è un nome e b è un numero di telefono }

A x B = { (“Antonio”, 12345), (“Antonio”, 89044), (“Vittorio”, 12345) …. }

A x B ≠ B x A : NON COMMUTATIVA

|A x B| = |A| x |B|

(se |A| = m e |B| = n allora |A x B| = n x m)

ESERCIZIO 1

A = {a, b, c, d, 1, 2, 3} e B = {1, a, 2, b, 6, 7}

A ∩ B = {a, b, 1, 2}

∪

A B = {a, b, c, d, 1, 2, 3, 6, 7}

| A x B | = 42

7

| P(A) | = 2 7 x 2^6

| P(A x P(B)) | = 2

ESERCIZIO 2

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

|A| = 4

P(A) = ? -> |P(A)| = 16 -> { {}, {1}, {2}, {{a}}, {3}, {1, 2}, {1, {a}}, {1, 3}, {2, {a}}, {2, 3},

{{a}, 3}, {2, {a}, 3}, {1, {a}, 3}, {1,2,3}, {1,2,{a}}, A }

∈

{a} {a} ? NO

∈

a {a} ? SI

DEFINIZIONE

Una relazione tra A e B è un sottoinsieme di AxB

Esempio

A = {a, b} e B = {1, 2} ⊆

Relazione R = { (a,1), (a,2), (b,1) } A x B

DEFINIZIONE

Un sottoinsieme di AxA si chiama RELAZIONE BINARIA su A

Esempio

A = {1, 2, 3}

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

2

A x A = A N^2

Quanti sottoinsiemi ha A x A ? Cioè | P(AxA) | ? 2

DEFINIZIONE ∈

Le relazioni tra a e b R si scrivono aRb

Esempio

A = {1, 2, 3, 4}

R = { (1,2), (2,4) } -> 1R2 e 2R4

PROPRIETA’

 ∀ ∈ ∈

Riflessiva: x A, xRx (x,x) R

 ∀ ∈

Simmetrica: x, y A se xRy allora yRx

 ∀

Transitiva: x, y, z se xRy e yRz allora xRz

Esempio

R = { (a,b) | a è amico di b }

Riflessiva? SI

Simmetrica? Dipende :P, scherzi a parte, la risposta è SI. Se a è amico di b allora ancora b è amico

di a. c’è un terzo elemento.

Transitiva? No, non

Un altro esempio…

A = {1, 2, 3, 4} ⊆

R = { (1,1), (2,2), (3,3), (1,3), (3,1) } AxA

∉

Riflessiva? No perchè (4,4) R

Simmetrica? Si [ (1,3) e (3,1) ]

Transitiva? No

ESERCIZIO

∈

A = { n N | n è pari }

B = { 1, 2, 3, 4, 5, 6, 7, 8 }

C = {3, 5, 7, 11, 41 }

∈

D = { n N | n è dispari }

—

| P(A∩B) | = 4

2

( A ∩ B ) x ( C ∩ D ) = 20 elementi in totale…. (troppo lunghi da scrivere :P)

⊆

C D ? SI

A ∩ C ⊆ B ? SI (insieme vuoto)

( ( A ∩ B ) ∩ C ) ∩ D = {}

PARTE 3

PRODOTTO CARTESIANO –

∈ ∈

A x B = { (a, b) | a A, b B } (a, b) è una coppia

⊆

R A x B -> R si chiama relazione tra A e B

⊆

R A x A -> Relazione BINARIA su A

NOTAZIONE ∈

Invece di scrivere (a, b) R, scriviamo aRb

DEFINIZIONE ∈

∀

1. RIFLESSIVA: una relazione binaria su A è riflessiva se a A si ha aRa (relazione con se

∈

stesso). R non è filessiva se esiste un elemento A tale che aRb

∈

2. SIMMETRICA: se pe ogni a, b A, vale che aRb e bRa. R non è simmetrica se esistono a,

∈

b A tali che aRb però bRa ∈

3. TRANSITIVA: per ogni a, b, c A, se vale che aRb e bRc allora deve essere aRc. R non è

∈

transitiva se esistono a, b, c A tali che vale aRb e bRa ma aRc

Esempio

A = {a, b, c} |A| = 3 |P(A)| = 2^3 = 8

|AxA| = 3*3 = 9 AxA = { (a, a), (a, b), (a, c), (b, a), (b, b), (c, b), (c, a), (c, b), (c, c) }