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
![$ \varnothing $](img18.gif)
l'
insieme vuoto, ovvero l'insieme
caratterizzato dalla proprietà di non avere elementi, in altri
termini l'insieme tale che per ogni
![$ x\not\in\varnothing $](img19.gif)
.
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
![$ P(x)$](img20.gif)
è una qualsiasi proprietà attribuibile a
![$ x$](img11.gif)
, (ad
esempio "
![$ x$](img11.gif)
ha gli occhi azzurri") allora l'asserzione
è vera. Ricordiamo infatti che un'implicazione
![$ Q \Rightarrow P$](img22.gif)
altro
non è che un modo diverso per scrivere
ossia o vale la tesi o non vale l'ipotesi. Quindi se l'ipotesi
![$ Q$](img26.gif)
è 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
![$ X$](img28.gif)
e
![$ Y$](img29.gif)
due insiemi, si dice che
![$ X$](img28.gif)
è
contenuto in
![$ Y$](img29.gif)
(o
anche
![$ X$](img28.gif)
è
sottinsieme di
![$ Y$](img29.gif)
), e si denota con
![$ X \subseteq Y$](img30.gif)
se
ogni elemento di
![$ X$](img28.gif)
è elemento di
![$ Y$](img29.gif)
, in simboli,
![$ \forall x (x\in X
\Rightarrow x\in Y)$](img31.gif)
.
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
![$ X$](img28.gif)
è un insieme e
![$ P$](img34.gif)
è una proprietà esprimibile in termini del
linguaggio della teoria degli insiemi, allora la collezione
![$\displaystyle \{x\mid x\in X$](img37.gif)
e
è un insieme. Si userà spesso anche la notazione
![$ \{x\in X\mid P(x)\}$](img39.gif)
, per
indicare questo insieme.
Definizione 1.7
Se
![$ X$](img28.gif)
e
![$ Y$](img29.gif)
sono insiemi si costruiscono altri insiemi:
Se
![$ I$](img54.gif)
è un insieme e per ogni
![$ i\in I$](img55.gif)
è dato un insieme
![$ X_i$](img56.gif)
, 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
![$ X$](img28.gif)
e
![$ Y$](img29.gif)
insiemi, si provi che
![$ X\subseteq Y \iff X\cap Y = X \iff
X\cup Y = Y$](img66.gif)
.
Soluzione
Esercizio 1.3
Siano
![$ X$](img28.gif)
,
![$ Y$](img29.gif)
,
![$ Z$](img67.gif)
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
![$ X$](img28.gif)
,
![$ Y$](img29.gif)
,
![$ Z$](img67.gif)
insiemi, si provino le seguenti:
-
-
Soluzione
Relazioni, funzioni parziali e funzioni totali
Definizione 1.9
Siano
![$ X$](img28.gif)
e
![$ Y$](img29.gif)
insiemi si dice
relazione tra
![$ X$](img28.gif)
e
![$ Y$](img29.gif)
, un
sottinsieme
![$ {\cal R}\subseteq X\times Y$](img92.gif)
. Se
![$ \cal R$](img93.gif)
è una relazione
si scriverà anche
![$ x{\cal R}y$](img94.gif)
come sinonimo di
![$ (x,y)\in {\cal R}$](img95.gif)
.
Una relazione tra
e se stesso, si dirà anche una
relazione binaria su
.
Definizione 1.10
Una relazione
![$ f\subseteq X\times Y$](img96.gif)
si dice una
funzione
parziale se per ogni
![$ x\in X$](img97.gif)
esiste al più un
![$ y\in Y$](img98.gif)
tale
che
![$ (x,y)\in f$](img99.gif)
. In simboli:
![$\displaystyle \forall x\in X ((x,y)\in f$](img100.gif)
e
Si scriverà
![$ f:X\rightharpoonup Y$](img102.gif)
per dire che
![$ f$](img103.gif)
è una funzione parziale
da
![$ X$](img28.gif)
a
![$ Y$](img29.gif)
e in tal caso si scriverà anche
![$ y=f(x)$](img104.gif)
come
sinonimo di
![$ (x,y)\in f$](img99.gif)
.
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
![$ x\in\mathop{\rm dom}\nolimits (f)$](img113.gif)
associa l'unico
elemento
![$ y\in Y$](img98.gif)
tale che
![$ (x,y)\in f$](img99.gif)
, questo elemento si denota
con
![$ f(x)$](img114.gif)
. Con questa interpretazione, si dà senso proprio
all'uguale contenuto nella scrittura
![$ y=f(x)$](img104.gif)
, scrittura che quindi
è equivalente a
![$ (x,y)\in f$](img99.gif)
. In questa accezione (legge che
associa ad un elemento un altro elemento) verranno generalmente
usate le funzioni.
Esercizio 1.5
Siano
![$ f,g \in Y^X$](img115.gif)
due funzioni da
![$ X$](img28.gif)
in
![$ Y$](img29.gif)
. Si provi che
![$ f=g$](img116.gif)
se
e solo se
![$ f(x)=g(x)$](img117.gif)
per ogni
![$ x\in X$](img97.gif)
.
Soluzione
Esempio 1.12
Se
![$ X$](img28.gif)
è un insieme
![$ {\rm id}_X=\{(x_1,x_2)\in X\times X\mid x_1=x_2\}$](img118.gif)
è una funzione, che viene chiamata l'
identità di
![$ X$](img28.gif)
. In
altri termini
![$ {\rm id}_X(x)=x$](img119.gif)
per ogni
![$ x\in X$](img97.gif)
.
Esempio 1.13
Se
![$ f:X\to
Y$](img110.gif)
è una funzione e
![$ A\subseteq X$](img120.gif)
, allora
![$ f\cap (A
\times Y)$](img121.gif)
è anch'essa una funzione, che si denota con
![$ \setbox\restrictbox=\hbox{$\hbox{$f$}_{A}$}\setbox0\hbox{$f$} {{f} \vrule wid...
...ictbox
depth\dp\restrictbox \hbox{\vrule depth\dp0 height \ht0 width0pt}_{A}}$](img122.gif)
e viene chiamata
restrizione di
![$ f$](img103.gif)
ad
![$ A$](img10.gif)
.
Esempio 1.14
Se
![$ f:A \to Y$](img123.gif)
e
![$ g:B\to Y$](img124.gif)
sono funzioni, non è detto che
l'unione
![$ f \cup g \subseteq (A\cup B) \times Y$](img125.gif)
, sia ancora una
funzione. In effetti, dato che
![$ ((A\setminus B) \times Y) \cap g
=\varnothing $](img126.gif)
, se
![$ x\in A\setminus B$](img127.gif)
allora esiste un unico
![$ y\in Y$](img98.gif)
tale
![$ (x,y)\in f\cup g$](img128.gif)
e precisamente quello tale che
![$ (x,y)\in f$](img99.gif)
. Analogamente se
![$ x\in B\setminus A$](img129.gif)
. Se invece
![$ x\in A\cap B$](img130.gif)
potrebbero esisterne un unico
![$ y_1$](img131.gif)
tale che
![$ (x,y_1(\in f$](img132.gif)
ed
esiste un unico
![$ y_2$](img133.gif)
tale che
![$ (x,y_2)\in g$](img134.gif)
, quindi affinché
![$ f\cup g$](img135.gif)
sia una funzione è necessario che per ogni
![$ x\in A\cap B$](img130.gif)
questi due elementi coincidano, in altre parole è necessario
che
![$ \restriction{f}{a\cap B}=\restriction{g}{a\cap B}$](img136.gif)
.
Esercizio 1.6
Se
![$ X$](img28.gif)
è un insieme, come sono fatti
![$ X^\varnothing $](img137.gif)
e
![$ \varnothing ^X$](img138.gif)
?
Soluzione
Definizione 1.15
Siano
![$ f:X\rightharpoonup Y$](img102.gif)
e
![$ g:Y\rightharpoonup Z$](img139.gif)
si chiama
composizione di
![$ f$](img103.gif)
e
![$ g$](img140.gif)
la relazione tra
![$ X$](img28.gif)
e
![$ Z$](img67.gif)
definita da
![$\displaystyle g\circ f = \{(x,z)\mid \exists y\in Y : y=f(x)$](img141.gif)
e
Proposizione 1.16
Se
![$ f:X\rightharpoonup Y$](img102.gif)
e
![$ g:Y\rightharpoonup Z$](img139.gif)
allora
![$ g\circ f:X\rightharpoonup Z$](img143.gif)
. Se
![$ f:X\to
Y$](img110.gif)
e
![$ g:Y\to Z$](img144.gif)
allora
![$ g\circ f:X\to Z$](img145.gif)
.
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
![$ g\circ f(x)=g(f(x))$](img159.gif)
.
Definizione 1.18
Sia
![$ f:X\to
Y$](img110.gif)
ed
![$ A\subseteq X$](img120.gif)
, si chiamo
immagine
di
![$ A$](img10.gif)
tramite
![$ f$](img103.gif)
l'insieme:
Definizione 1.19
Sia
![$ f:X\to
Y$](img110.gif)
ed
![$ A\subseteq Y$](img161.gif)
, si chiamo
immagine inversa
di
![$ A$](img10.gif)
tramite
![$ f$](img103.gif)
l'insieme:
Proposizione 1.21
Sia
![$ f:X\to
Y$](img110.gif)
una bigezione, allora esiste un'unica funzione
![$ g:Y\to X$](img166.gif)
tale che
![$ f\circ g= {\rm id}_Y$](img167.gif)
e
![$ g\circ f= {\rm id}_X$](img168.gif)
. Tale
funzione si chiama
inversa di
![$ f$](img103.gif)
e si denota con
![$ f^{-1}$](img169.gif)
.
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
![$ f:X\to
Y$](img110.gif)
e si supponga che esista una funzione
![$ g:Y\to X$](img166.gif)
tale
che
![$ g\circ f= {\rm id}_X$](img168.gif)
e
![$ f\circ g= {\rm id}_Y$](img167.gif)
. Si provi che allora
![$ f$](img103.gif)
è
bigettiva.
Soluzione
Esercizio 1.8
Perché se
![$ X$](img28.gif)
e
![$ Y$](img29.gif)
sono insiemi allora anche
![$ Y^X$](img111.gif)
è un
insieme?
Soluzione
Esercizio 1.9
Siano
![$ f:X\rightharpoonup Y$](img102.gif)
e
![$ g:Y\rightharpoonup Z$](img139.gif)
, si determini
![$ \mathop{\rm dom}\nolimits (g\circ f)$](img176.gif)
.
Soluzione
Esercizio 1.11
Siano
![$ X,Y,I$](img177.gif)
insiemi,
![$ f:X\to
Y$](img110.gif)
e
![$ A_i\subseteq Y$](img178.gif)
per ogni
![$ i\in I$](img55.gif)
. Si provi che
Soluzione
Esercizio 1.12
Siano
![$ X,Y,I$](img177.gif)
insiemi,
![$ f:X\to
Y$](img110.gif)
e
![$ A_i\subseteq X$](img180.gif)
per ogni
![$ i\in I$](img55.gif)
. 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