Matematica Discreta Lezione del giorno 6 ottobre 2008 Eguaglianza fra insiemi

Matematica Discreta

Lezione del giorno 6 ottobre 2008 Eguaglianza fra insiemi

Due insiemi A, B sono uguali se contengono gli stessi elementi: questo equivale ad affermare che ogni elemento di A è anche elemento di B e che viceversa ogni elemento di B è anche elemento di A. Quindi l’eguaglianza di insiemi A=B equivale alla “doppia inclusione” AB e BA .

Se gli insiemi sono descritti in modo implicito, mediante predicati:

A = { x / P(x) } B = { x / Q(x) }

allora verificare che A=B equivale a dimostrare vera sia l’implicazione Q  P che l’implicazione inversa P  Q, quindi in questo caso l’eguaglianza di insiemi A=B corrisponde all’equivalenza dei predicati: P  Q .

Per ogni insieme A, è ovvio che A è sottoinsieme di sé stesso:

AA

Per convenzione l’insieme vuoto  si considera sottoinsieme di qualunque insieme A.

Poiché, dato un insieme A qualunque, si ha sempre A e AA, i due sottoinsiemi , A sono detti sottoinsiemi banali o impropri dell’insieme A. Per indicare che un sottoinsieme B dell’insieme A è diverso da A spesso si usa il simbolo BA (e si dice che B è contenuto propriamente in A).

Essendo arbitraria la natura degli elementi di un insieme, possiamo anche considerare insiemi i cui elementi sono a loro volta degli insiemi.

In particolare, fissato un arbitrario insieme A, possiamo costruire l’insieme delle parti di A (indicato con il simbolo P(A)), i cui elementi sono tutti i possibili sottoinsiemi di A.

Per esempio se A = {a, b, c}, l’insieme delle parti di A è l’insieme:

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

Si può notare che A contiene 3 elementi e P(A) contiene 8=2³ elementi: dimostreremo in seguito che ciò non è casuale.

Se A è un insieme fissato, possiamo descrivere in forma implicita un sottoinsieme B di A nel modo seguente:

B = { xA / P(x) } (dove P(x) è un predicato)

intendendo che gli elementi del sottoinsieme B sono tutti e soli gli elementi di A che rendono vero P(x).

Per esempio, se A è l’insieme dei numeri interi positivi pari, si ha:

B = { xA / x<10 } = {2,4,6,8}.

Antinomia di Russell

Nella teoria “ingenua” degli insiemi, il fatto che la natura degli elementi sia completamente arbitraria può portare a dei problemi logici, che furono messi in evidenza da Russell.

Partiamo da alcuni esempi: costruiamo l’insieme A i cui elementi sono tutti gli insiemi che contengono più di 2 elementi

A = { x / x è un insieme che contiene più di 2 elementi } Alcuni esempi di elementi di A sono gli insiemi {1,2,3}, {a,b,c,d,e}, {a,1,7,8,b,d}.

Poiché A stesso contiene più di 2 elementi si ha che A è elemento di sé stesso: AA.

Invece se costruiamo l’insieme B i cui elementi sono tutti gli insiemi che contengono esattamente 1 solo elemento

B = { x / x è un insieme che contiene esattamente 1 solo elemento }

poiché è ovvio che B stesso contiene più di 1 elemento (esempi di elementi di B sono {1},{a} etc..) si ha che B non è elemento di sé stesso: BB.

Abbiamo visto dunque che esistono insiemi che hanno sé stessi come elementi, ed insiemi che non hanno sé stessi come elementi.

Costruiamo allora l’insieme C i cui elementi sono tutti gli insiemi che non hanno sé stessi come elementi

C = { x / x è un insieme ed xx }

(un elemento di C è per esempio l’insieme B costruito sopra).

Domanda: CC oppure CC ?

Ma se CC allora dalla costruzione di C segue che CC; viceversa se CC allora dalla costruzione di C segue che CC: siamo in presenza di una contraddizione logica (antinomia di Russell), perché un’affermazione è vera e falsa nello stesso tempo.

Per risolvere questi problemi logici legati alla teoria “ingenua” degli insiemi si può ricorrere alla teoria “assiomatica” (più precisa dal punto di vista formale) oppure evitare la costruzione di insiemi che contengano tutti gli insiemi che soddisfano una proprietà fissata (quindi evitare frasi come “sia A l’insieme di tutti gli insiemi tali che …..).

Operazioni fra insiemi.

Sono procedimenti che, dati alcuni insiemi (operandi) costruiscono un nuovo insieme (risultato) i cui elementi dipendono dagli elementi degli insiemi operandi.

1) Unione di insiemi:

Dati gli insiemi A,B, si chiama insieme unione di A e B (indicato con AB) l’insieme degli elementi che appartengono ad almeno uno degli insiemi A,B.

Se A,B sono descritti in modo esplicito, AB è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono nell’elenco di A o nell’elenco di B o in ambedue (questi ultimi elencati 1 sola volta).

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora AB={1,2,3,4,5,6,8,9}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora AB è descritto in modo implicito dal predicato disgiunzione logica PvQ.

Per esempio se A = { x / x è intero positivo dispari }, B = { x / x è intero >12 } allora:

AB = { x / x è intero positivo dispari o x è intero >12 }

(quindi AB contiene gli interi dispari 1,3,5,7,9,11 e tutti gli interi consecutivi da 13 in poi).

Proprietà evidenti dell’unione sono le seguenti:

- dato un insieme A si ha AA=A (idempotenza)

- dati 2 insiemi A,B si ha AB=BA (proprietà commutativa)

- dati 3 insiemi A,B,C si ha (AB)C= A(BC) (proprietà associativa) (per questa terza proprietà basta notare che sia (AB)C che A(BC) coincidono con l’insieme degli elementi che appartengono ad almeno uno fra gli insiemi A,B,C)

2) Intersezione di insiemi:

Dati gli insiemi A,B, si chiama insieme intersezione di A e B (indicato con AB) l’insieme degli elementi che appartengono ad ambedue gli insiemi A,B.

Se A,B non hanno elementi in comune si ha AB= e si dice che A,B sono disgiunti.

Se A,B sono descritti in modo esplicito, AB è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono sia nell’elenco di A che nell’elenco di B.

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora AB={5,6}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora AB è descritto in modo implicito dal predicato congiunzione logica PQ.

Per esempio se A = { x / x è intero positivo dispari }, B = { x / x è intero >12 } allora:

AB = { x / x è intero positivo dispari e x è intero >12 } (quindi AB contiene tutti gli interi dispari da 13 in poi).

Proprietà evidenti dell’intersezione sono le seguenti:

- dato un insieme A si ha AA=A (idempotenza)

- dati 2 insiemi A,B si ha AB=BA (proprietà commutativa)

- dati 3 insiemi A,B,C si ha (AB)C=A(BC) (proprietà associativa) (per questa terza proprietà basta notare che sia (AB)C che A(BC) coincidono con l’insieme degli elementi che appartengono ad tutti e 3 gli insiemi A,B,C)

3) Differenza di insiemi:

Dati gli insiemi A,B, si chiama insieme differenza A meno B (indicato con A-B) l’insieme degli elementi che appartengono ad A ma non appartengono a B.

Se A,B non hanno elementi in comune si ha ovviamente A-B=A, B-A=B.

Se A,B sono descritti in modo esplicito, A-B è descritto in modo esplicito da un elenco di tutti gli elementi che compaiono nell’elenco di A ma non nell’elenco di B.

Per esempio se A={1,2,3,4,5,6}, B={8,5,6,9} allora A-B={1,2,3,4} mentre B-A={8,9}.

Se A,B sono descritti in modo implicito:

A = { x / P(x) }, B = { x / Q(x)}

allora A-B è descritto in modo implicito dal predicato P^Q congiunzione logica di P e della negazione di Q.

Per esempio se A = { x / x è intero positivo dispari }, B = { x / x è intero >12 } allora:

A-B = { x / x è intero positivo dispari ed x è intero ≤12 } = {1,3,5,7,9,11}

mentre:

B-A = { x / x è intero >12 ed x è intero positivo pari}

(quindi B-A contiene tutti gli interi pari da 14 in poi).

Dall’esempio precedente si deduce che in generale A-BB-A (dunque l’operazione differenza non soddisfa la proprietà commutativa.

4) Complementare di un sottoinsieme in un inseme:

Dati gli insiemi A,B e nel caso particolare in cui l’insieme B sia sottoinsieme dell’insieme A, la differenza A-B è detta complementare di A in B e indicata con ^cA: dunque il complementare di B in A ha come elementi tutti gli elementi di A che non appartengono a B.

Le proprietà principali del complementare sono espresse dalle leggi di DeMorgan:

se B,C sono sottoinsiemi dell’insieme A (notare che anche BC, BC sono sottoinsiemi di A e si possono considerare i 4 complementari ^cB, ^cC, ^c(BC), ^c(BC)) si ha

^c(BC)= ^cB^cC ^c(BC)= ^cB^cC

Le dimostrazione di ognuna di queste 2 proprietà comporta la dimostrazione di una doppia inclusione. Per esempio per dimostrare la prima proprietà, si devono dimostrare le 2 inclusioni:

^c(BC)^cB^cC ^cB^cC^c(BC)

Dimostriamo la prima delle 2 inclusioni (la dimostrazione della seconda é analoga): se x è un elemento generico di ^c(BC), allora, per definizione di complementare, si ha xA ma xBC, e per definizione di unione si ha xB e xC, dunque xA e xB e simultaneamente xA e xC, ossia x^cB e simultaneamente x^cC, e si può concludere che x^cB^cC.

Per concludere la trattazione delle operazioni fra insiemi, notiamo che valgono le seguenti proprietà distributive di unione e intersezione:

dati gli insiemi A,B,C si ha A(BC)=(AB)(AC) e A(BC)=(AB)(AC).

Esse si dimostrano facilmente con le doppie inclusioni.

Diagrammi di Eulero-Venn.

Sono rappresentazioni grafiche di un insieme, in cui gli elementi si rappresentano come punti del piano all’interno di una curva chiusa (spesso una circonferenza).

Esempio di diagramma di Eulero-Venn che rappresenta l’insieme A={1,2,3,4,5}:

Si possono rappresentare con tali diagrammi anche i risultati delle operazioni fra insiemi: unione, intersezione e differenza.

Per esempio per rappresentare l’intersezione AB:

A B

(l’insieme A è rappresentato con linee orizzontali, l’insieme B con righe verticali: l’insieme intersezione AB sarà rappresentato dalla quadrettatura).

Le proprietà già enunciate per le operazione fra insiemi si possono verificare graficamente sui diagrammi di Eulero-Venn..

1 2 3 4 5