Esercizi-Insiemi - Esercizi svolti su insiemi PDF

Preview

Summary

Esercizi svolti su insiemi...

Description

MATEMATICA DISCRETA - AULA A (ESERCIZI SVOLTI SU INSIEMI) ALESSANDRO ARDIZZONI

Le soluzioni date per questi esercizi non sono necessariamente le uniche possibili. Nel seguito le lettere A, B, C indicheranno degli insiemi arbitrari. Ricordiamo anche che il metodo usuale con cui si dimostra che due insiemi A e B sono uguali `e quello di verificare la doppia inclusione, cio`e far vedere che ciascuno dei due insiemi `e contenuto nell’altro, in simboli A ⊆ B e B ⊆ A. Invece per dimostrare che un certo insieme `e vuoto (l’insieme vuoto si denota col simbolo ∅) conviene in genere ragionare per assurdo, cio´e supporre che non sia vuoto e dedurne una contraddizione. Esercizio 1. Dimostrare che A ⊆ A ∪ B e che B ⊆ A ∪ B . Soluz.: In realt`a c’`e ben poco da dimostrare. Infatti, per definizione si ha A ∪ B = {x | x ∈ A oppure x ∈ B} . Pertanto se a ∈ A si ha in automatico a ∈ A ∪ B e questo significa che A ⊆ A ∪ B. In modo analogo si verifica B ⊆ A ∪ B.

che che che 

Esercizio 2. Dimostrare che A ∩ B ⊆ A e che A ∩ B ⊆ B . Soluz.: Dimostriamo solo la prima inclusione (la seconda si fa similmente). Se x ∈ A ∩ B allora x ∈ A e x ∈ B. In particolare x ∈ A. Quindi abbiamo dimostrato che (x ∈ A ∩ B ⇒ x ∈ A) vale a dire che A ∩ B ⊆ A.  Esercizio 3. Dimostrare che A ∪ B = B ∪ A e che A ∩ B = B ∩ A. Dimostrazione. Si ha che A ∪ B = {x | x ∈ A oppure x ∈ B} = {x | x ∈ B oppure x ∈ A} = B ∪ A, A ∩ B = {x | x ∈ A e x ∈ B} = {x | x ∈ B e x ∈ A} = B ∩ A.  Esercizio 4. Dimostrare che A ∪ B = A ⇔ B ⊆ A. Dimostrare anche che A ∩ B = A ⇔ A ⊆ B. Soluz.: Dimostriamo solo che A ∪ B = A ⇔ B ⊆ A (l’altra propriet`a si verifica in modo analogo). Si procede dimostrando le due implicazini: i) (A ∪ B = A ⇒ B ⊆ A) e ii) (B ⊆ A ⇒ A ∪ B = A) . i) Supponiamo che valga A ∪ B = A e dobbiamo dimostrare che vale B ⊆ A. Grazie ad Esercizio 1, sappiamo che B ⊆ A ∪ B. Poich`e stiamo supponendo A ∪ B = A, possiamo concludere che B ⊆ A. Date: A.A. 2013-2014; versione del 9 ottobre 2013. 1

2

ALESSANDRO ARDIZZONI

ii) Supponiamo che valga B ⊆ A e dobbiamo dimostrare che vale A ∪ B = A. Dimostrare A ∪ B = A `e equivalente a dimostrare la doppia inclusione, cio`e che A ∪ B ⊆ A e che A ⊆ A ∪ B (dimostreremo proprio queste due propriet`a). La seconda di queste due propriet`a vale sempre grazie ad Esercizio 1. Dobbiamo quindi dimostrare solo la prima propriet`a. Se x ∈ A ∪ B allora x ∈ A oppure x ∈ B. Nel primo caso abbiamo x ∈ A e nel secondo, poich´e B ⊆ A, abbiamo ancora x ∈ A. Abbiamo cos`ı dimostrato che se x ∈ A ∪ B allora x ∈ A e cio´e che A ∪ B ⊆ A.  Esercizio 5. Dimostrare che A ∪ B = ∅ ⇔ A = ∅ e B = ∅. Soluz.: Si procede dimostrando le due implicazini i) (A ∪ B = ∅ ⇒ A = ∅ e B = ∅) e ii) (A = ∅ e B = ∅ ⇒ A ∪ B = ∅) . i) Supponiamo che valga A ∪ B = ∅ e dimostriamo che A = ∅ e B = ∅. Possiamo farlo in due modi. MODO 1) Per Esercizio 1 sappiamo che A ⊆ A ∪ B. Dato che A ∪ B = ∅, deduciamo che A ⊆ ∅. Dato che ∅ `e contenuto in ogni insieme, si ha pure che ∅ ⊆ A. Ma le propriet`a A ⊆ ∅ e ∅ ⊆ A ci dicono proprio che A = ∅. In modo analogo si vede che B = ∅. N.B.: questo metodo di risoluzione, pur essendo corretto, pu`o portare a facili errori nel momento in cui si cercasse di dimostrare con gli elementi (e noi abbiamo evitato di farlo) la validit` a dell’inclusione A ⊆ ∅ (il fatto `e che ∅, per come e` definito, non pu` o contenere alcun elemento). MODO 2) Supponiamo per assurdo che A = ∅. Allora esiste a ∈ A. Per Esercizio 1 sappiamo che A ⊆ A ∪ B e quindi a ∈ A implica a ∈ A ∪ B. Questo significa che A ∪ B = ∅ il che contraddice la condizione A ∪ B = ∅ che stiamo supponendo dall’inizio essere vera. Pertanto non `e vero che A = ∅. In altre parole deve essere A = ∅. In modo analogo si vede che B = ∅. ii) Supponiamo che valga A = ∅ e B = ∅ e dimostriamo che A ∪ B = ∅. Possiamo farlo in due modi. MODO 1) Notiamo che A ⊆ B perch´e sono entrambi vuoti. Pertanto, per Esercizio 4, possiamo affermare che A ∪ B = A e quindi A ∪ B = ∅. MODO 2) Supponiamo per assurdo che A ∪ B = ∅. Allora esiste x tale che x ∈ A oppure x ∈ B: nel primo caso otteniamo A = ∅ e nel secondo otteniamo B = ∅. Entrambi i casi portano a contraddire il fatto che A = ∅ e B = ∅. Quindi non `e vero che A ∪ B = ∅.In altre parole deve essere A ∪ B = ∅.  Esercizio 6. Dimostrare che (A ∪ B) ∪ C = A ∪ (B ∪ C ). Soluz.: Si procede dimostrando la doppia inclusione: i) (A ∪ B) ∪ C ⊆ A ∪ (B ∪ C) e ii) A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C. i) Prendiamo x in (A ∪ B) ∪ C e dimostraimo che x sta necessariamente in A ∪ (B ∪ C). Poich´e x ∈ (A ∪ B) ∪ C allora, per definizione dell’unione, abbiamo che x ∈ A ∪ B oppure x ∈ C. Consideriamo questi due casi separatamente (cercando in entrambi i casi di arrivare a dimostrare che x ∈ A ∪ (B ∪ C)).

MATEMATICA DISCRETA - AULA A

(ESERCIZI SVOLTI SU INSIEMI)

3

iA) x ∈ A ∪ B. In questo caso si ha che x ∈ A oppure x ∈ B. Di nuovo dobbiamo distinguere due casi. Se x ∈ A possiamo applicare Esercizio 1 per dire che A ⊆ A ∪ (B ∪ C) per concludere che x ∈ A ∪ (B ∪ C) . Se invece x ∈ B, allora possiamo applicare due volte Esercizio 1 per dire che Es. 1

Es. 1

B ⊆ B ∪ C ⊆ A ∪ (B ∪ C) e quindi x ∈ B ⇒ x ∈ A ∪ (B ∪ C). In tutti i casi arriviamo a concludere che x ∈ A ∪ (B ∪ C) come volevamo. iB) x ∈ C. Applicando due volte Esercizio 1 abbiamo Es. 1

Es. 1

C ⊆ B ∪ C ⊆ A ∪ (B ∪ C) e quindi x ∈ C ⇒ x ∈ A ∪ (B ∪ C). Quindi sia in iA) che in iB) concludiamo che x ∈ A ∪ (B ∪ C) come volevamo. ii) Si fa in modo analogo.  Esercizio 7. Dimostrare che (A ∩ B) ∩ C = A ∩ (B ∩ C ). Soluz.: Si procede dimostrando la doppia inclusione. Vediamo ad esempio che (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C) (l’altra inclusione si vede analogamente). Valgono le seguenti implicazioni x ∈

(A ∩ B) ∩ C ⇒ x ∈ (A ∩ B) e x ∈ C ⇒ (x ∈ A e x ∈ B) e x ∈ C

⇒ x ∈ A e (x ∈ B e x ∈ C) ⇒ x ∈ A e x ∈ B ∩ C ⇒ x ∈ A ∩ (B ∩ C) e quindi x ∈ (A ∩ B) ∩ C ⇒ x ∈ A ∩ (B ∩ C) . Ci` o dimostra che (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C). Notiamo che non essendoce unioni non abbiamo dovuto distinguere il ragionamento in casi diversi.  Esercizio 8. Dimostrare che A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Soluz.: Si procede dimostrando la doppia inclusione: i) A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C) e ii) (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C). i) Se x ∈ A ∩ (B ∪ C) allora x ∈ A e x ∈ B ∪ C. Distinguiamo due casi a seconda che x ∈ B oppure x ∈ / B. CASO x ∈ B) In tal caso, dato che x ∈ A, otteniamo che x ∈ A ∩ B. Quindi, a maggior ragione, si ha che x ∈ (A ∩ B) ∪ (A ∩ C) in questo caso. CASO x ∈ / B) Siccome x ∈ / B, dato che x ∈ B ∪ C, deve essere x ∈ C. In tal caso, dato che x ∈ A, otteniamo che x ∈ A ∩ C. Quindi, a maggior ragione, si ha che x ∈ (A ∩ B) ∪ (A ∩ C) in questo caso. Abbiamo cos`ı dimostrato che x ∈ (A ∩ B) ∪ (A ∩ C) in entrambi i casi. Si `e quindi verificato che A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C) . ii) Se x ∈ (A ∩ B) ∪ (A ∩ C) possono accadere due casi: che x ∈ A ∩ B oppure che x ∈ A ∩ C. CASO x ∈ A ∩ B) In questo caso x ∈ A ed x ∈ B. Quindi x ∈ A e x ∈ B ∪ C. Se ne deduce che in questo caso x ∈ A ∩ (B ∪ C) .

4

ALESSANDRO ARDIZZONI

CASO x ∈ A ∩ C) In questo caso x ∈ A ed x ∈ C. Quindi x ∈ A e x ∈ B ∪ C. Se ne deduce che in questo caso x ∈ A ∩ (B ∪ C) . Pertanto in entrambi i casi x ∈ A ∩ (B ∪ C). Abbiamo cos`ı dimostrato che (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).  Esercizio 9. Dimostrare che A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) . Soluz.: Si pu` o dimostrare in modo analogo ad Esercizio 9. Possiamo per`o anche usare gli esercizi precedenti nel modo seguente: Es. 8

(A ∪ B) ∩ (A ∪ C) = ((A ∪ B) ∩ A) ∪ ((A ∪ B) ∩ C ) Es. 3

= (A ∩ (A ∪ B)) ∪ (C ∩ (A ∪ B))

Es. 8

= ((A ∩ A) ∪ (A ∩ B)) ∪ ((C ∩ A) ∪ (C ∩ B ))

Es. 4

= (A ∪ (A ∩ B)) ∪ ((C ∩ A) ∪ (C ∩ B ))

Es. 2+4

=

A ∪ ((C ∩ A) ∪ (C ∩ B ))

Es. 6

= (A ∪ (C ∩ A)) ∪ (C ∩ B )

Es. 2+4

=

A ∪ (C ∩ B)

Es. 3

= A ∪ (B ∩ C) .

La catena di uguaglianze mi dice che il primo e l’ultimo insieme della catena coincidono, cio´e (A ∪ B) ∩ (A ∪ C) = A ∪ (B ∩ C).  Esercizio 10. Dimostrare che A\ (B ∪ C) = (A\B) ∩ (A\C) . Soluz.: Si procede dimostrando la doppia inclusione: i) A\ (B ∪ C) ⊆ (A\B) ∩ (A\C) e ii) (A\B) ∩ (A\C) ⊆ A\ (B ∪ C). i) Se x ∈ A\ (B ∪ C) allora x ∈ A e x ∈ / B ∪ C. Da Esercizio 1, sappiamo che B ⊆ B ∪ C. Pertanto x non pu` o appartenere a B (altrimenti dovrebbe appartenere anche a B ∪ C e questo `e falso). Quindi x ∈ / B. Dato che x ∈ A, otteniamo che x ∈ A\B. Similmente, lavorando con C, si ottiene anche che x ∈ A\C. Abbiamo cos`ı dimostrato che x ∈ (A\B) ∩ (A\C). ii) Se x ∈ (A\B) ∩ (A\C) allora x ∈ A\B e x ∈ A\C. Quindi x ∈ A, x ∈ / B e x∈ / C. Se x stesse in B ∪ C, allora x dovrebbe stare anche in uno dei due insiemi B e C, il che `e falso. Pertanto x ∈ / B ∪ C. Dato che x ∈ A concludiamo che x ∈ A\ (B ∪ C).  Esercizio 11. Dimostrare che A\ (B ∩ C) = (A\B) ∪ (A\C) . Soluz.: Si procede dimostrando la doppia inclusione: i) A\ (B ∩ C) ⊆ (A\B) ∪ (A\C) e ii) (A\B) ∪ (A\C) ⊆ A\ (B ∩ C). i) Se x ∈ A\ (B ∩ C) allora x ∈ A e x ∈ / B ∩ C. Distinguiamo due casi a seconda che x ∈ / B oppure x ∈ B.

MATEMATICA DISCRETA - AULA A

(ESERCIZI SVOLTI SU INSIEMI)

5

CASO x ∈ / B) In questo caso, da x ∈ A deduciamo quindi che x ∈ A\B e quindi a maggior ragione x ∈ (A\B) ∪ (A\C) . CASO x ∈ B) In questo caso dovr` a essere x ∈ / C (altrimenti x apparterrebbe a B ∩ C il che non `e vero). Da x ∈ A deduciamo quindi che x ∈ A\C e quindi a maggior ragione x ∈ (A\B) ∪ (A\C) . Abbiamo cos`ı dimostrato che x ∈ (A\B) ∪ (A\C) in entrambi i casi. Si `e quindi verificato che A\ (B ∩ C) ⊆ (A\B) ∪ (A\C) . ii) Se x ∈ (A\B) ∪ (A\C) possono accadere due casi: che x ∈ A\B oppure che x ∈ A\C. CASO x ∈ A\B) In questo caso, x ∈ A e x ∈ / B. Se avessimo x ∈ B ∩ C, dato che B ∩ C ⊆ B dovremmo avere x ∈ B, il che non `e vero. Pertanto deve essere che x∈ / B ∩ C. Da x ∈ A deduciamo quindi che x ∈ A\ (B ∩ C). CASO x ∈ A\C) In modo analogo al caso precedente si arriva a dimostrare che x ∈ A\ (B ∩ C). Abbiamo cos`ı dimostrato che x ∈ A\ (B ∩ C) in entrambi i casi. Si `e quindi verificato che (A\B) ∪ (A\C) ⊆ A\ (B ∩ C) .  Esercizio 12. Dimostrare che (B ∪ C) \A = (B\A) ∪ (C\A) . Soluz.: Si procede dimostrando la doppia inclusione: i) (B ∪ C) \A ⊆ (B\A) ∪ (C\A) e ii) (B\A) ∪ (C\A) ⊆ (B ∪ C) \A. i) Se x ∈ (B ∪ C) \A allora x ∈ B ∪ C e x ∈ / A. Distinguiamo due casi a seconda che x ∈ B oppure x ∈ / B. CASO x ∈ B) In questo caso, da x ∈ / A, deduciamo che x ∈ B\A e quindi a maggior ragione x ∈ (B\A) ∪ (C\A) . CASO x ∈ / B) In questo caso, da x ∈ B ∪ C, deduciamo che x ∈ C. Quindi , da x∈ / A, deduciamo che x ∈ C\A e quindi a maggior ragione x ∈ (B\A) ∪ (C\A) . Abbiamo cos`ı dimostrato che x ∈ (B\A) ∪ (C\A) in entrambi i casi. ii) Se x ∈ (B\A) ∪ (C\A) possono accadere due casi: che x ∈ B\A oppure che x ∈ C\A. CASO x ∈ B\A) In questo caso, x ∈ B e x ∈ / A. Quindi x ∈ B ∪ C e x ∈ / A. Ci`o significa x ∈ (B ∪ C) \A. CASO x ∈ C\A) In questo caso, x ∈ C e x ∈ / A. Quindi x ∈ B ∪ C e x ∈ / A. Ci`o significa x ∈ (B ∪ C) \A. Abbiamo cos`ı dimostrato che x ∈ (B ∪ C) \A in entrambi i casi.  Esercizio 13. Dimostrare che (B ∩ C) \A = (B\A) ∩ (C\A) . Soluz.: Si procede dimostrando la doppia inclusione: i) (B ∩ C) \A ⊆ (B\A) ∩ (C\A) e ii) (B\A) ∩ (C\A) ⊆ (B ∩ C) \A. i) Abbiamo la seguente catena di implicazioni x ∈ (B ∩ C) \A ⇒ x ∈ B ∩ C e x ∈ / A ⇒ (x ∈ B e x ∈ C) e x ∈ /A ⇒ (x ∈ B e x ∈ / A) e (x ∈ B e x ∈ / A) ⇒ x ∈ B\A e x ∈ C\A ⇒ x ∈ (B\A) ∩ (C \A) .

6

ALESSANDRO ARDIZZONI

ii) Abbiamo la seguente catena di implicazioni x ∈ (B \A) ∩ (C\A) ⇒ x ∈ B \A e x ∈ C\A ⇒ (x ∈ B e x ∈ / A) e (x ∈ B e x ∈ / A) ⇒ (x ∈ B e x ∈ C) e x ∈ /A ⇒ x∈B∩C e x∈ / A ⇒ x ∈ (B ∩ C) \A.  ` di Torino, Dipartimento di Matematica “G. Peano”, via Carlo Alberto Universita 10, 10123 Torino E-mail address : [email protected] URL: www.unito.it/persone/alessandro.ardizzoni...