Insiemi

Formulario di matematica

G. Sammito, A. Bernardo, Insiemi

F. Cimolin, L. Barletta, L. Lussardi

…………………………………………………………………………………………………………………………………………………………………………………

A ∪

A B

B

Figura 2.2. In grigio A unito B

A B

intersezione

L' tra insiemi è un operatore fra due insiemi, e , che restituisce l'insieme degli

A B

che a . L'operatore intersezione viene definito

elementi appartenenti contemporaneamente sia ad ∧ :

formalmente facendo uso dell'operatore logico AND, il cui simbolo è

∩ ∈ ∧ ∈

A B = {

a : a A a B

}

A B ∩

A B

Figura 2.3. In grigio A intersezione B

differenza fra due insiemi A e B, restituisce l'insieme contenente gli elementi che appartengono ad

La

A e che contemporaneamente non appartengono a B.

∈ ∧ ∉

A \ B = {

a : a A a B

}

A A \ B

B

Figura 2.4. In grigio l’insieme differenza tra A e B

differenza simmetrica fra due insiemi coincide con l'insieme degli elementi appartenenti ad uno

La

dei due insiemi di partenza ma non ad entrambi contemporaneamente. Pertanto la differenza

simmetrica è, per certi versi, analoga all'operatore OR esclusivo.

Δ ∪ ∩

A B = ( A B ) \ ( A B ) 2

………………………………… …………………………………

www.matematicamente.it

Formulario di matematica

G. Sammito, A. Bernardo, Insiemi

F. Cimolin, L. Barletta, L. Lussardi

…………………………………………………………………………………………………………………………………………………………………………………

A Δ

A B

B

Figura 2.5. In grigio la differenza simmetrica tra A e B

complementare richiede uno spazio ambiente, ovvero l'insieme a cui appartengono

L'operazione di ⊆

tutti gli elementi esistenti. Se X è lo spazio ambiente e A è un suo sottoinsieme ( A X ) allora il

A X X A

, rispetto a , è l'insieme di tutti gli elementi (di ) che non appartengono ad :

complementare di ∈ ∧ ∉

c

A = C = A = X \ A = { x : x X x A

}

A X

A

‰

A

In grigio il complementare di A rispetto all’insieme ambiente X

Figura 2.6.

L' , o , di un insieme A è l'insieme che ha per elementi tutti i

insieme potenza insieme delle parti

.

sottoinsiemi di A ℘ ⊆

( ) = { : }

A X X A

∅ ∈℘ ∈℘

( A

) A ( A

)

Nota che e . ( )

℘ n

Se l’insieme A è formato da n elementi, l’insime delle parti è formato da elementi.

2

A

A B

fra due insiemi, e , restituisce l'insieme di tutte le coppie ordinate, tali per

Il prodotto cartesiano ed il secondo a .

cui il primo elemento della coppia appartiene ad A B

× ∈ ∧ ∈

A B = {( a , b ) : a A b B

}

≠ × ≠ ×

Nota che se allora .

A B A B B A

× = 2

A A A .

Si usa anche la notazione

Proprietà degli operatori insiemistici

∩ ∅ ∅ ∅ è l'elemento assorbente dell'intersezione

A =

∪ ∅ ∅ è l'elemento neutro rispetto all'unione

A = A

∅ ∅ è l'elemento neutro (a destra) rispetto alla differenza insiemistica

A A

\ =

⊆ proprietà riflessiva dell’inclusione

A A

⊆ ∧ ⊆ ⇒ ⊆ proprietà transitiva dell’inclusione

A B B C A C 3

………………………………… …………………………………

www.matematicamente.it

Formulario di matematica

G. Sammito, A. Bernardo, Insiemi

F. Cimolin, L. Barletta, L. Lussardi

…………………………………………………………………………………………………………………………………………………………………………………

∩ ∩ proprietà commutativa dell'intersezione

A B B A

=

∪ ∪ proprietà commutativa dell'unione

A B B A

=

∩ ∩ ∩ ∩

A B C A B C

( ) = ( ) proprietà associativa dell'intersezione

∪ ∪ ∪ ∪ proprietà associativa dell'unione

A B C A B C

( ) = ( )

∩ ∪ ∩ ∪ ∩

A B C A B B C

( ) = ( ) ( ) proprietà distributiva dell'intersezione rispetto all'unione

∪ ∩ ∪ ∩ ∪ proprietà distributiva dell'unione rispetto all'intersezione

A B C A B A C

( ) = ( ) ( ) ∅ ∅ ∩ ∅ ∪

c c c c

Se è l'insieme universo, allora , , , (leggi di

X X A A

= = =

X A A X

=

complementazione).

∩ c

A B A B

= \ proprietà del complementare rispetto all'intersezione

∩ c

A B A B

\ = proprietà del complementare rispetto alla differenza

× ∪ × ∪ ×

A B C A B A C

( ) = ( ) ( ) proprietà distributiva del prodotto cartesiano rispetto all'unione

× ∩ × ∩ × proprietà distributiva del prodotto cartesiano rispetto all'intersezione

A B C A B A C

( ) = ( ) ( )

× × ×

A B C A C B C proprietà distributività del prodotto cartesiano rispetto alla differenza

( \ ) = ( ) \ ( )

insiemistica

∩ ∪ ∪ ∩

c c c c c c

, leggi di De Morgan

A B A B A B A B

( ) = ( ) = …

fra insiemi, è un sottoinsieme del prodotto cartesiano

Una relazione X X X

, , ,

n 1 2 n

× × ×

… . Una relazione di questo genere è detta anche -aria.

X X X n

1 2 n ×

Una fra due insiemi e è un sottoinsieme del prodotto cartesiano . Se

relazione binaria A B A B

, si dice che una relazione binaria su è un sottoinsieme del prodotto cartesiano

accade che A B A

=

× .

A A ℜ ⊆ × ℜ

Sia una relazione binaria fra due insiemi. Si dice che è iniettiva se e

Relazione iniettiva. A B ℜ

soltanto se elementi distinti di corrispondono a elementi distinti di secondo la relazione , cioè

A B

∈ ℜ ∈ℜ

se e soltanto se dati e risulta

a b a b

( , ) ( , )

1 1 2 2

∀ ∈ ⇒

a , a A

, b = b a = a .

1 2 1 2 1 2

ℜ ⊆ × ℜ

Relazione suriettiva. Sia A B una relazione binaria fra due insiemi. Si dice che è suriettiva

( )

∀ ∈ ∃ ∈ ∈ ℜ

se e soltanto se .

b B a A : a , b

ℜ ⊆ × ℜ

Relazione biunivoca. una relazione binaria fra due insiemi. Si dice che

Sia è una

A B

relazione biunivoca se e soltanto se è contestualmente iniettiva e suriettiva.

Proprietà delle relazioni

ℜ ⊆ × A

Sia A A una relazione binaria su . ∈ℜ ∀ ∈

ℜ a a a A

( , )

Proprietà riflessiva. La relazione si dice riflessiva se e soltanto se . ∈

ℜ

Proprietà transitiva. a b c A

, ,

La relazione si dice transitiva se e soltanto se per ogni terna vale

∈ℜ ∧ ∈ℜ ⇒ ∈ℜ

a b b c a c

( , ) ( , ) ( , ) . ∈

Proprietà simmetrica. R a b A

,

La relazione si dice simmetrica se e soltanto se per ogni coppia

∈ℜ ⇒ ∈ℜ

a b b a

( , ) ( , ) .

vale ℜ

Proprietà antisimmetrica. La relazione si dice antisimmetrica se e soltanto se per ogni coppia

∈ ∈ ∧ ∈ ⇒

a , b A vale ( a , b ) R (

b

, a ) R a = b . ℜ A

relazione di equivalenza è una relazione binaria su un insieme che rispetta le proprietà

Una

riflessiva, simmetrica e transitiva. R

Esempio: la relazione di uguaglianza su (insieme dei numeri reali) è una relazione di equivalenza.

= 4

………………………………… …………………………………

www.matematicamente.it

Formulario di matematica

G. Sammito, A. Bernardo, Insiemi

F. Cimolin, L. Barletta, L. Lussardi

…………………………………………………………………………………………………………………………………………………………………………………

ℜ

relazione d’ordine è una relazione binaria su un insieme se e soltanto se rispetta le

Una A

proprietà riflessiva, antisimmetrica e transitiva.

R

≤

:

Esempio la relazione su (Insieme dei numeri reali) è una relazione d'ordine.

partizione

Una di un insieme X è una suddivisione di X in sottoinsiemi X , X ,... X tali che:

n

1 2

∪ ∪ ∪ = ;

- l'unione di tutti i sottoinsiemi è l'insieme X stesso, cioè X X ... X X

n

1 2

- due qualsiasi sottoinsiemi della partizione sono disgiunti, cioè

{ }

∩ = ∅ ∀ ∈ ≠ ;

X X i , j 1, 2,...

n , con i j

i j { }

≠ ∅ ∀ ∈ .

- nessun sottoinsime è vuoto, cioè X i n

1, 2,...,

i

ℜ A

Ogni relazione di equivalenza su un insieme determina una partizione di A, costituita da

ℜ . Ognuno di questi

sottoinsiemi formati da elementi equivalenti fra di loro secondo la relazione

classe di equivalenza

sottoinsiemi prende il nome di ; l’insieme delle classi di equivalenza forma

ℜ

insieme quoziente

, che si indica con il rimbolo .

l’ A /

2.3 Funzione

Funzione f A B

. Una corrispondenza univoca, o applicazione, o anche funzione, da in , associa a

∈ ∈

ogni elemento a A uno, e uno solo, elemento b B . Per indicare una funzione si usa il simbolo

→

f A B

: . f

A B

Figura 2.7. Rapresentazione di una funzione o corrispondenza univoca; a ogni elemento di A è

associato un solo elemento di B. ( )

=

dominio codominio

Il della funzione f è l’insieme ; il è l’insieme B. L’elemento si dice

A b f a

immagine controimmagine insieme immagine f

di a, mentre si dice di . L’ di è l’insieme

a b

{ }

( ) ( )

= ∈ ∃ ∈ =

f A b B : a A / f a b . ( ) =

. Una funzione si dice suriettiva quando .

Funzione suriettiva f A B

Una funzione si dice iniettiva se ad elementi distinti di A associa elementi distinti

Funzione iniettiva. ( ) ( )

≠ ⇒ ≠

di B, in simboli .

x x f x f x

1 2 1 2

{ } { } →

= =

, , associa a un elemento di il suo

Esempio 1: f A B A

:

A B

1, 2,3 1, 2,3, 4,5, 6, 7,8,9 ( ) { }

= ⊂ . La funzione è iniettiva

quadrato. Questa funzione non è sureittiva poiché f

f A 1, 4,9 B

perché ad elementi distinti di associa elementi distinti in .

A B

{ } { } →

= − + + = g C D

:

, , associa a un elemento di il suo

Esempio 2: C D

1, 0, 1, 2 0,1, 2,3, 4 C 5

………………………………… …………………………………

www.matematicamente.it

Formulario di matematica

G. Sammito, A. Bernardo, Insiemi

F. Cimolin, L. Barletta, L. Lussardi

…………………………………………………………………………………………………………………………………………………………………………………

( ) ( )

− = + = .

quadrato. Questa funzione non è iniettiva poiché f 1 f 1 1

A C

B D

1

f g

-1 0

8

1 2 0

3 9 7 1 4

2 +1

4 6 2

3 5 +2

→ →

Figura 2.8. La funzione è iniettiva; la funzione non è iniettiva.

f A B g C D

: :

Una funzione si dice biettiva se è iniettiva e suriettiva.

Funzione biettiva. →

Si dice funzione inversa di una funzione biettiva la funzione, indicata

Funzione inversa. f A B

: ( )

− ∈ ∈ =

1

con f che associa a ogni elemento l’unica controimmagine tale che .

b B a A f a b

→ →

f A B g B C

: :

Date due funzioni e risulta definita una terza funzione

Funzione composta.

→ f

che ad un elemento di A associa un elemento di C ottenuto applicando ad e poi

a

h : A C ( )

g g

applicando ad . Questa funzione si dice funzione composta di e e si indica con

f

f a ( )

( )

= =

h g f h g f x

, oppure . f B

A C

g

a b c

h

Figura 2.9. La funzione composta

→

La o è l’applicazione che lascia inalterati gli elementi di A e

funzione identica identità :

f A A

( ) ( ) ( )

= ∀ ∈ , solitamente indicata con oppure .

cioè tale che f a a a A I A id A

2.4 Strutture algebriche

Una è un’applicazione che associa ad ogni coppia ordinata di

legge di composizione interna binaria

elementi di uno e un solo elemento c di . In simboli

,

a b A A

× →

f : A A A ⊗ =

oppure a b c

( )

a , b c

Una è un insieme sul quale è definito una legge di composizione interna. Una

struttura algebrica ( ) ⊗

⊗ A

struttura algebrica si indica come una coppia , dove è l’insieme, l’operazione interna.

,

A

( ) ⊗

⊗

Un è una struttura algebrica in cui l’operazione è associativa, cioè

semigruppo A

, 6

………………………………… …………………………………

www.matematicamente.it