insiemi

Cenni sull'insiemistica
Raffaele Cioffi
Indice
• Concetto di Insieme
• Operazioni con gli Insiemi
• Prodotto Cartesiano
• Relazione Binaria R
Concetto di Insieme
• Esiste un insieme se riusciamo ad identificare un
criterio di comunanza fra gli elementi che lo
compongono: gli oggetti che compongono un
insieme hanno necessariamente un minimo
comune denominatore, una regola, un criterio
appunto che li accomuna fra loro.
• Ad esempio, l'insieme degli scolari del primo anno
di una scuola elementare (1°A), ha come
caratteristica necessaria e sufficiente la comune
appartenenza dei singoli alunni ad una medesima
classe nel medesimo istituto.
• Generalmente gli insiemi sono indicati con le
lettere maiuscole
A, B, C…
• mentre gli elementi che li compongono sono
indicati con le lettere minuscole
a, b, c…
• Per indicare l'appartenenza o meno di un elemento
a ad un insieme A si usano i simboli seguenti:
a A
l ' elemento a appartiene all ' insieme A
a A
l ' elemento a non appartiene all ' insieme A
A  a , b , c , d , e , f ..... definizion e estensiva
A  x / x  regola  definizion e int ensiva
Diagramma di Eulero Wenn
A
a
b
d
f
c
e
Tipi di Insiemi
• Insieme vuoto. Si definisce un insieme vuoto (e si
rappresenta con ) quell'insieme che non contiene
nessun elemento al suo interno.
• Insiemi uguali. Due insiemi si dicono uguali
quando tutti gli elementi facenti parte di uno sono
presenti anche nell'altro e viceversa, tale relazione
è valida se entrambi gli insiemi sono formati
soltanto da elementi comuni:
A = a, b, c, d e B =a, b, c, d  A = B
• Sottoinsiemi. Dato un insieme B ed un insieme A,
si afferma che B è un sottoinsieme di A se ogni
elemento di B appartiene anche ad A ed A ospita
altri elementi che non sono presenti in B.
• B  A (sottoinsieme improprio) esiste almeno un
elemento di B che non appartiene ad A
• B  A (sottoinsieme proprio) non esiste alcun
elemento di B che non appartiene ad A
• L'insieme vuoto è sempre un sottoinsieme di
qualunque altro insieme; ogni insieme dato è
sempre sotto insieme improprio, ma non proprio,
di se stesso ( A  A)
• se A è sottoinsieme improprio di B e B è sotto
insieme di A allora ne consegue che A e B sono
uguali, ossia:
A B e BA A=B
• se A è sottoinsieme improprio di B allora non è
possibile che B sia sottoinsieme proprio di A
A  B  non il contrario.
• Insieme Universo. Si definisce insieme universo
quell'insieme che contiene tutti gli insiemi presi in
considerazione; se prendiamo, per esempio, gli
alunni della città di Firenze, allora l'insieme degli
alunni della 1°A (di una Scuola fiorentina)
appartiene all'insieme universo predeterminato.
• Famiglia di sottoinsiemi. Sia preso in
considerazione un insieme qualsiasi (in questo
caso continueremo a far riferimento all'insieme
degli alunni della 1°A) in esso possono essere
individuati tanti sottoinsiemi: ad esempio l'insieme
dei maschi e quello delle femmine, l'insieme degli
alunni con i capelli castani e quelli con i capelli
biondi…
Operazioni con gli Insiemi
• Unione di Insiemi (U)
• Intersezione fra Insiemi ()
• Partizione di un Insieme
• Differenza fra Insiemi
• Insieme Complemento
Unione di Insiemi (U)
• Siano dati due insiemi A e B, si definisce insieme
unione (o anche insieme somma) quell'insieme
composto da tutti gli elementi appartenenti sia ad
A sia a B, ossia:
siano A  a ,b , c , d  e B  e , f , g , h
 A  B  a ,b , c , d , e , f , g , h
o anche A  B  x / x  A oppure x  B
• Volendo rappresentare graficamente l'operazione
dell'unione avremmo:
U
a, b, c, d
=
e, f, g, h
a, b, c, d
e, f, g, h
• Insieme unito con se stesso. Un insieme unito con
se stesso da come risultato lo stesso insieme, ossia,
AUA=A
• Insieme A unito all'insieme vuoto. Un insieme A
unito all'insieme vuoto da come risultato l'insieme
A:
AU =A
• Proprietà commutativa. L'unione fra l'insieme A e
l'insieme B è uguale all'unione fra l'insieme B e
l'insieme A, ovvero….
AB=BA
• Proprietà associativa. L'unione fra l'insieme A e B
successivamente uniti con l'insieme C, è uguale
all'unione fra l'insieme B con C e successivamente
con l'insieme A, ovvero…
(A  B)  C = A  (B  C)
• Proprietà disgiuntiva. L'unione fra l'insieme A e
l'insieme composto BC è uguale all'intersezione
(concetto che vedremo successivamente) fra
l'unione di A con B e A con C, ovvero…
A  (BC) = (A  B)  (A  C)
Intersezione fra Insiemi ()
• Siano dati due insiemi A e B, si dice intersezione
di A con B quell'insieme che è formato da tutti gli
elementi che appartengono contemporaneamente
sia ad A sia a B, in altre parole:
sia A  a , b , c , d , e , f  sia B  e , f , g , h ,i
 A  B  e , f 
o anche A  B  x / x  A e x  B
• Se l'intersezione fra l'insieme A e l'insieme B
dovesse generare un insieme vuoto, allora si
potrebbe pensare che A e B non hanno elementi in
comune.
• In questo caso si parla anche di insiemi disgiunti.
• Graficamente l'intersezione è così rappresentata:
a, b, c, d, e, f
e, f
e, f, g, h, i

=
• L'intersezione di insiemi disgiunti da come
risultato l'insieme vuoto
• Proprietà commutativa. L'intersezione fra
l'insieme A e l'insieme B è uguale all'intersezione
fra l'insieme B con l'insieme A, ovvero…
AB=BA
• Proprietà associativa. Tutta l'intersezione fra
l'insieme A e l'insieme B intersecata con l'insieme
C è uguale a tutta l'intersezione fra B e C
intersecata ancora con A, ovvero…
(A  B)  C = A  (B  C)
• Proprietà distributiva. L'unione degli insiemi B e
C intersecata con l'insieme A, è uguale all'unione
fra l'intersezione di A con B e di A con C,
ovvero…
A  (B  C) = (A  B)  (A  C)
Partizione di un Insieme
• Sia dato un insieme A, l'operazione di partizione
consente di suddividere tale insieme in tanti sotto
insiemi impropri di A.
• Sia dato quindi un insieme S definito come
l'insieme di studenti di una Scuola Media
Superiore, tramite l'operazione di partizione si
possono individuare altri sottoinsiemi impropri
all'interno di S.
S=x / studenti di Scuola Media Superiore
suddivisi in calssi
• Graficamente, quindi,
rappresenta come:
questa
operazione
si
• La partizione di un insieme deve necessariamente
generare insiemi pieni e non vuoti.
• I sottoinsiemi ricavati devono essere disgiunti.
• L'unione di tutti i sottoinsiemi deve dare l'insieme
generatore.
Differenza fra Insiemi
• Siano dati due insiemi A e B, è detto insieme
differenza fra A e B, quell'insieme composto dagli
elementi di A ma non di B, ossia:
sia A  a , b , c , d , e sia B  d , e , f , g , h  A  B  a , b , c
oppure A  B  x / x  A e x  B
• L'insieme A sottratto per se stesso genera l'insieme
vuoto:
A-A= 
• L'insieme A sottratto dell'insieme B non è uguale
all'insieme B sottratto dell'insieme A. ossia:
A-BB-A
Insieme Complemento
• Sia dato l'insieme B, tale che B deve essere un
sottoinsieme dell'insieme A, si dice insieme
complemento di B in A (e si chiama B')
quell'insieme composto da tutti gli elementi di A
che non compaiono in B, in altre parole:
sia A  a , b , c , d , e , f , g , h sia B  a , b , c , d , e
 B'   f , g , h
oppure B'  x / x  A ed x  B
• Questa operazione quindi è possibile quando B è
un sottoinsieme improprio di A (B  A).
• Volendo rappresentare con dei diagrammi…
B'
a, b, c, d, e, f, g, h
a, b, c, d, e
a, b, c, d
• Unendo l'insieme B con B' si ha l'insieme A:
B U B' = A
• L'intersezione fra l'insieme B e l'insieme
complemento B' genera l'insieme vuoto:
B  B' = 
Prodotto Cartesiano
• Siano dati due insiemi A e B, si definisce insieme
prodotto cartesiano di A e B quell'insieme formato
da tutte le coppie ordinate di elementi, col primo
elemento appartenente all'insieme A ed il secondo
elemento appartenente all'insieme B, ossia:
sia A  a , b e B  c , d   AΧ B  ( a , b ),( a , c ),( b , c ),( b , d )
oppure AΧ B  ( x , y / x  A e y  B
• Si noti che il prodotto cartesiano fra l'insieme A e
l'insieme vuoto da come risultato l'insieme vuoto:
AX =
• Se in oltre l'insieme A è diverso dall'insieme B,
allora ne consegue che il prodotto cartesiano fra A
e B è diverso dal prodotto cartesiano fra B ed A:
AB AX B B XA
Tipi di Prodotto Cartesiano
• Prodotto cartesiano tra due insiemi A X B.
• Contiene tutte le coppie ordinate formate da ogni
elemento di A associato ad ogni elemento di B: sia
dato l'insieme
A=x/4 scolari o anche A=a, b, c, d
• e sia anche dato l'insieme
B=y/3 domande o anche B=e, f, g,
• la relazione che si vuole individuare è che gli
scolari (insieme A, elementi x) debbano rispondere
a delle domande (insieme B, elementi y)
A X B=(a, e),(a, f),(a, g),(b, e),(b, f),(b, g),(c, e),(c,
f),(c, g),(d, e),(d, f),(d, g)
• è formata da coppie ordinate perché
AXBBXA
• quindi anche
(a, e)  (e, a)
• e così rappresentabili:
g
f
e
a
b
c
d
• Prodotto cartesiano tra tre insiemi A X B X C.
• Contiene tutte le n-tuple formate dagli elementi
degli insiemi dati. Sia dato l'insieme
A = x/2 scolari o anche A = a, b,
• sia anche dato l'insieme
B = y/3 materia o anche B=m, p, f
• e sia dato infine l'insieme
C = z/2 modalità d'esame o anche C = s, o,
• potremmo avere due relazioni grafiche:
• Coppie ordinate
S
O
(a,m)
(a,f)
(a,p)
(b,m)
(b,f)
(b,p)
• Triple ordinate
p
f
m
a
b
• Prodotto cartesiano A X A2
• Sia l'insieme
A = a, b, c,
• sia data anche la relazione binaria
AR = ”stessa età”,
• si avrà che:
A2 = (a, a)(a, b)(a, c)… c, c)
• A livello grafico questo tipo di prodotto si
rappresenta nella seguente maniera:
c
b
a
a
b
c
Relazione Binaria R
• E' definita relazione binaria R tra due insiemi A e
B un insieme qualsiasi composto da coppie
ordinate di elementi appartenenti ad entrambi gli
insiemi dati (questo tipo di relazione è un
sottoinsieme del prodotto cartesiano) R  A X B
R  ( x , y ) / x  A y  B
• L'insieme formato da tutte le x costituisce il
dominio D di R, mentre l'insieme formato da tutte
le y costituisce l'insieme codominio C di R; da ciò
se ne inferisce che:
D  A e che C  B.
• Esempio 1
• Sia dato l'insieme A=a, b, c
oppure anche A=x/x sono tre studenti
• Sia dato l'insieme B=e, d
oppure anche B=y/y due esami
• La relazione binaria R è del tipo "x sceglie y" e
potrà essere rappresentata sugli assi cartesiani ...
e
d
a
b
c
• Se noi andassimo a considerare soltanto alcune
coppie del prodotto cartesiano si avrebbe:
R=(a, d)(a,e)(b,d)(c,e)
• Dal momento che sono state individuate
dall'insieme R si può affermare che queste sono le
coppie soddisfano “R”.
• Nel caso invece l'insieme A coincide con l'insieme
B abbiamo una relazione binaria con questa
rappresentazione:
A: R  A2
• Esempio 2
• Sia dato l'insieme:
A = a,b,c,d
• Sia data la relazione binaria
R = ”x creativo come y”,
• allora il grafico cartesiano sarebbe strutturato
come segue:
d
c
b
a
a
b
c
d
• La relazione binaria del grafico è così strutturata:
R = (a,a)(a,b)(b,a)(b,b)(c,c)(d,d)
• Esempio 3
• Sia dato un insieme
A = triangolo, pentagono, quadrato,
• sia dato ancora l'insieme
B = giallo, rosso, verde,
• una relazione binaria possibile potrebbe essere:
R = figure con meno di 5 lati e di colore giallo o
rosso
• ossia:
R = triangolo giallo, triangolo rosso, quadrato
giallo, quadrato rosso
• Questo criterio ci consentirà di discriminare un
Dominio ed un Codominio espressi nella maniera
seguente:
D = triangolo, quadrato
C = giallo, rosso
Proprietà delle Relazioni Binarie
• Proprietà riflessiva. Per ogni elemento x che
appartiene all'insieme A, l'elemento x è in
relazione con se stesso.
x  A ,
xRx
• Proprietà simmetrica. Dati due elementi (x e y)
appartenenti all'insieme A, possiamo sostenere che
l'elemento x ha le stesse caratteristiche
dell'elemento y (x veloce come y).
x , y  A, xRy  yRx
• Proprietà asimmetrica. Dati due elementi (x e y)
appartenenti all'insieme A, può valere la proprietà
dell'asimmetria (x luminoso come y e non il
contrario).
x , y  A, xRy ma non yRx
• Proprietà transitiva. Siano dati tre elementi (x, y, z)
appartenenti all'insieme A, se a è in relazione binaria
con y e y è in relazione binaria con z allora anche x
può essere in relazione binaria con z (se Marco è alto
come Luca e Luca è alto come Franco, allora anche
Franco è alto come Luca).
x , y , z  A, xRy yRz  xRz
• Proprietà della connessione. Siano dati due
elementi (x, y) appartenenti all'insieme A, dove però
sono distinti e diversi, si deve avere una precisa
relazione: o x anticipa y oppure l'inverso, ma non
contemporaneamente (o Marco è più abile di
Valerio oppure il contrario).
x , y  A, vel xRy vel yRx
• Proprietà della connessione forte. Dati due elementi
(x, y) appartenenti all'insieme A, per ogni valore, non
necessariamente distinti e separati, si possono avere
relazioni di parità o disuguaglianza (o Luca è più alto
o della stessa altezza di Andrea oppure il contrario).
x , y  A, aut xRy aut yRx
Tipi di Relazioni Binarie in A
• Le relazioni binarie in A sono caratterizzate da:
Relazioni di equivalenza in A: x ~ y
• Una relazione binaria in un insieme è detta
relazione di equivalenza se gode delle tre proprietà
seguenti:
• Proprietà riflessiva. Se con qualsiasi x preso a
caso ed appartenente a R, si ha anche che la coppia
(x, x) appartiene a R, ossia…
 x  R  (x, x)  R
• Proprietà simmetrica. Se con qualsiasi coppia (x,
y) appartenenti a R, anche la coppia (y, x) dovrà
appartenere a R, ossia…
 (x, y)  R  (y, x)  R
• Proprietà transitiva. Se data la coppia (x, y)
appartenente a R e la coppia (y, z) appartenete a R,
allora anche la coppia (x, z) dovrà appartenere a R.
data (x, y)  R e(y, z)  R  (x, z)  R
Relazioni di ordine stretto totale in A: x < y
(x precede y)
• Si può avere una relazione di ordine stretto totale
in A, dove l'elemento x precede l'elemento y, se
sono garantite le seguenti proprietà:
• Proprietà di connessione. Si ha nel caso in cui x è
diverso da y (con x  y). In questo caso la
relazione è monodirezionale (o x < y oppure y >
x). Ad esempio: Luca è meno attivo di Vincenzo.
• Proprietà asimmetrica. Si ha nel caso di una
diversità di proprietà degli elementi (se x è meno
attivo di y non può essere che y sia meno attiva di
x).
• Proprietà transitiva. Se x è attivo meno di y e y è
attivo meno di z, allora anche x è attivo meno di z.
Sistemi Relazionali
• Sia dato un insieme A e tutte le relazioni R definite
in
esso,
si
chiama
insieme
relazionale
quell'insieme composto da A e dalle relazioni R.. A
tal riguardo si deve precisare che l'insieme
dominio D dell'insieme relazionale è lo stesso
insieme
A,
l'equazione...:
generalmente
si
indica
con
A  A, R1 , R2
A: dominio o sostegno della relazione
R: relazioni definite in A
• Due sistemi relazionali sono simili quando
hanno lo stesso numero di relazioni in comune e
queste relazioni sono dello stesso grado.
• Un sistema relazionale può essere definito:
empirico (se l'insieme A-dominio è composto da
elementi non numerici), numerico (se l'insieme
A è composto da elementi numerici).
• Esempio
• Sia dato l'insieme
A = x/5 persone
A = A, R1, R2
R1 = ”x è più anziano di y”
R2 = ”x coetaneo di y”
• Sia dato ancora l'insieme
N = x / un sottoinsieme dei reali
• quindi è un sistema relazionale numerico
N = N, S1, S2
S1 = “ x > y”
S2 = ”x = y”
• Si può affermare che il sistema relazionale A e n
sono simili perché hanno entrambi due relazioni e
a coppie le relazioni sono dello stesso grado.
• Ad esempio: ”essere più anziano” e “x > y” sono
relazioni lineari con due elementi.