Next: Lezione 2
Up: Matematica Discreta (II modulo)
Previous: Matematica Discreta (II modulo)
Subsections
Insiemi e operazioni tra insiemi
Non intendiamo qui dare un'assiomatica della teoria degli insiemi (cosa che
esula dalle finalità di questo corso e demandata ad altri eventuali corsi
successivi), ma soltanto elencare alcune delle proprietà e delle costruzioni
che permettono di confrontare insiemi e costruire nuovi insiemi a partire da
altri, facendo eventualmente notare la necessità di assiomatizzare tali
cosatruzioni.
Per noi un insieme sarà soltanto una collezione di oggetti detti i suoi elementi. La proprietà fondamentale che si richiede affinché un oggetto
sia un insieme è che si possa sempre stabilire senza ambiguità se qualche
cosa è un suo elemento oppure no. In simboli, se
è un insieme allora per
ogni
si ha che
(
appartiene ad
) oppure
(
non appartiene ad
). Questa che può sembrare una richiesta ovvia
in realtà non lo è. Si consideri l'oggetto definito da:
e si provi a stabilire se
oppure no.
- Se
, allora, dalla definizione di
segue che
- Se
allora, per definizione di
,
Quindi
non può essere un insieme, in quanto non possiamo decidere se
oppure no. Questo esempio è noto come il paradosso di Russel.
Il criterio per stabilire quando due insiemi sono uguali, è fornito dal
seguente
Assioma 1.1 (estensionalità)
Due insiemi sono uguali se e solo se hanno gli stessi elementi. In simboli
Definizione 1.2 (vuoto)
Si denota con

l'
insieme vuoto, ovvero l'insieme
caratterizzato dalla proprietà di non avere elementi, in altri
termini l'insieme tale che per ogni

.
Osservazione 1.3
L'assioma di estensionalità garantisce evidentemente che se
l'insieme vuoto esiste esso è anche unico. In effetti la sua
esistenza va presa come assioma.
Osservazione 1.4
Se

è una qualsiasi proprietà attribuibile a

, (ad
esempio "

ha gli occhi azzurri") allora l'asserzione
è vera. Ricordiamo infatti che un'implicazione

altro
non è che un modo diverso per scrivere
ossia o vale la tesi o non vale l'ipotesi. Quindi se l'ipotesi

è sempre
falsa, l'implicazione risulta vero (gli antichi dicevano
ex
falso quodlibet, dal falso segue qualsiasi cosa).
Nel nostro caso, per definizione di vuoto, la premessa
è sempre falsa, per qualsiasi
, quindi l'implicazione è
vera. Possiamo pertanto asserire che gli elementi dell'insieme vuoto
hanno gli occhi azzurri.
Definizione 1.5
Siano

e

due insiemi, si dice che

è
contenuto in

(o
anche

è
sottinsieme di

), e si denota con

se
ogni elemento di

è elemento di

, in simboli,

.
Si dice che
è contenuto strettamente in
(o anche che è un
sottinsieme proprio di
) e si denota con
, se
e
.
Un modo di definire degli insiemi è quello di usare una ``proprietà'' che ne
caratterizzi gli elementi. Ossia se
è una, formula della teoria
degli insiemi, per intenderci una proprietà esprimibile in
termini del simbolo di appartenenza e di uguaglianza, dei quantificatori e dei
connettivi logici, (e, o,
, non) allora con
, si
intende la collezzione di tutti gli
che soddisfano la proprietà
. Il
paradosso di Russel mostra che in generale un tale oggetto può non essere un
insieme. Si dà però il seguente
Assioma 1.6 (separazione)
Se

è un insieme e

è una proprietà esprimibile in termini del
linguaggio della teoria degli insiemi, allora la collezione

e
è un insieme. Si userà spesso anche la notazione

, per
indicare questo insieme.
Definizione 1.7
Se

e

sono insiemi si costruiscono altri insiemi:
Se

è un insieme e per ogni

è dato un insieme

, si
definiscono
- intersezione
- unione
Osservazione 1.8
Quelle che abbiamo appena dato come definizioni, sono solo in parte
tali. Se infatti gli insiemi intersezione, differenza e complemento
sono effettivamente definibili a usando l'
assioma di
separazione, per gli
altri tale assioma non è più sufficiente (non si separano degli
elementi da un insieme, ma si costruiscono, insiemi ``più
grandi'') e quindi tali costruzioni devono essere opportunamente
assiomatizzate, cosa che però noi non facciamo.
Esercizio 1.2
Siano

e

insiemi, si provi che

.
Soluzione
Esercizio 1.3
Siano

,

,

insiemi, si provino le seguenti:
- proprietà associativa dell'intersezione e dell'unione
- proprietà commutativa
- proprietà di assorbimento
- proprietà distributiva dell'intersezione rispetto all'unione e
dell'unione rispetto all'intersezione
- leggi di de Morgan
-
- se
allora
.
Soluzione
Esercizio 1.4
Siano

,

,

insiemi, si provino le seguenti:
-
-
Soluzione
Relazioni, funzioni parziali e funzioni totali
Definizione 1.9
Siano

e

insiemi si dice
relazione tra

e

, un
sottinsieme

. Se

è una relazione
si scriverà anche

come sinonimo di

.
Una relazione tra
e se stesso, si dirà anche una
relazione binaria su
.
Definizione 1.10
Una relazione

si dice una
funzione
parziale se per ogni

esiste al più un

tale
che

. In simboli:

e
Si scriverà

per dire che

è una funzione parziale
da

a

e in tal caso si scriverà anche

come
sinonimo di

.
L'insieme
è detto il
dominio di
e si denota con
.
L'insieme
è detto
l'immagine di
e si denota con
.
Una funzione parziale
si dice funzione totale o
semplicemente funzione se
, in tal caso si scrive
.
Si denota
l'insieme di tutte le funzioni (totali) da
a
, ossia
.
Osservazione 1.11
Una funzione parziale può essere pensata come ``una legge ben
definita'' che ad ogni elemento

associa l'unico
elemento

tale che

, questo elemento si denota
con

. Con questa interpretazione, si dà senso proprio
all'uguale contenuto nella scrittura

, scrittura che quindi
è equivalente a

. In questa accezione (legge che
associa ad un elemento un altro elemento) verranno generalmente
usate le funzioni.
Esercizio 1.5
Siano

due funzioni da

in

. Si provi che

se
e solo se

per ogni

.
Soluzione
Esempio 1.12
Se

è un insieme

è una funzione, che viene chiamata l'
identità di

. In
altri termini

per ogni

.
Esempio 1.13
Se

è una funzione e

, allora

è anch'essa una funzione, che si denota con

e viene chiamata
restrizione di

ad

.
Esempio 1.14
Se

e

sono funzioni, non è detto che
l'unione

, sia ancora una
funzione. In effetti, dato che

, se

allora esiste un unico

tale

e precisamente quello tale che

. Analogamente se

. Se invece

potrebbero esisterne un unico

tale che

ed
esiste un unico

tale che

, quindi affinché

sia una funzione è necessario che per ogni

questi due elementi coincidano, in altre parole è necessario
che

.
Esercizio 1.6
Se

è un insieme, come sono fatti

e

?
Soluzione
Definizione 1.15
Siano

e

si chiama
composizione di

e

la relazione tra

e

definita da

e
Proposizione 1.16
Se

e

allora

. Se

e

allora

.
Dimostrazione. Per provare il primo punto, dobbiamo mostrare che se
allora
. Per definizione di
esiste
tale che
e
ed esiste un
tale che
e
. Ma allora, dato che
è una
funzione parziali,
, e quindi, dato che anche
è una
funzione parziale
.
Se
e
sono funzioni totali, sono in particolare delle funzioni
parziali e quindi, per quanto appena mostrato,
è una
funzione parziale. Dobbiamo provare che per ogni
esiste uno
tale che
. Sia
, dato che
`e una
funzione totale, esiste
tale che
, dato che anche
è totale esiste allora
tale che
, ma questo
significa che
, ovvero
.
Osservazione 1.17
Con l'interpretazione data nell'osservazione
1.11 si ha
allora che

.
Definizione 1.18
Sia

ed

, si chiamo
immagine
di

tramite

l'insieme:
Definizione 1.19
Sia

ed

, si chiamo
immagine inversa
di

tramite

l'insieme:
Proposizione 1.21
Sia

una bigezione, allora esiste un'unica funzione

tale che

e

. Tale
funzione si chiama
inversa di

e si denota con

.
Dimostrazione. Dato
esiste un unico
tale che
(esiste perché
è surgettiva, è unico perché è
iniettiva); chiamiamo
tale elemento. È allora evidente che
per ogni
. D'altra parte
per
ogni
(applico la relazione precedente con
), e quindi
per l'iniettività di
si ha che
. È chiaro che tale
funzione è l'unica possibile con le proprietà richieste.
Il seguente esercizio inverte il risultato della proposizione precedente.
Esercizio 1.7
Sia

e si supponga che esista una funzione

tale
che

e

. Si provi che allora

è
bigettiva.
Soluzione
Esercizio 1.8
Perché se

e

sono insiemi allora anche

è un
insieme?
Soluzione
Esercizio 1.9
Siano

e

, si determini

.
Soluzione
Esercizio 1.11
Siano

insiemi,

e

per ogni

. Si provi che
Soluzione
Esercizio 1.12
Siano

insiemi,

e

per ogni

. Si provi che
Si provi che in generale nella seconda delle due non può valere l'uguaglianza.
Soluzione
Next: Lezione 2
Up: Matematica Discreta (II modulo)
Previous: Matematica Discreta (II modulo)
Domenico Luminati
2004-03-18