Matematica - teoria elementare degli insiemi - Appunti

Lezioni di Matematica 3 - Implicazione

Siano P e Q due proposizioni. Diremo che P implica Q se ogni volta che P è vera lo è anche Q, e scriveremo P → Q. Tale scrittura si legge equivalentemente nei modi seguenti: P implica Q, oppure da P segue Q, oppure C.N. perché sia P vera è che lo sia Q, oppure C.S. perché Q sia vera è che lo sia P.

Se P → Q e Q → P si scrive P ⇔ Q e si dice che P equivale a Q (oppure C.N.S. affinché P sia vera è che Q sia vera, P vale se e solo se vale Q). In alcuni casi si usa anche scrivere P sse Q, intendendo con questo P è vera è vera Q, se e solo se.

Quantificatori:

∀: per ogni, qualunque sia.

∃: esiste (almeno un).

La negazione è sempre data dal segno / sopra il simbolo in questione. ∄ significa non esiste (alcun); analogamente la negazione di...

uguaglianza è indicata con il simbolo =.

University of Catania Lezioni di Matematica 4

Il Metodo della Matematica

Il metodo comunemente usato in matematica consiste nel precisare senza ambiguità i presupposti (le regole del gioco), che non possono essere cambiati nel corso dell'elaborazione della teoria, e dedurre, con passaggi logici, da tali presupposti il maggior numero di informazioni.

I presupposti vengono chiamati postulati o Assiomi;

Da questi, mediante dimostrazioni logiche, vengono dedotti i risultati nella forma di teoremi (corollari, proposizioni).

Lezione 1

Slide 7 Teoria elementare degli Insiemi

University of Catania Lezioni di Matematica 5

Insiemi

La nozione di insieme viene spesso utilizzata nella vita di tutti i giorni; si parla dell'insieme:

• degli iscritti ad un corso di laurea
• delle stelle in cielo
• dei punti di un piano

Un insieme è semplicemente una collezione di oggetti detti elementi dell'insieme.

Gli insiemi sono

La grafica di un insieme consiste nel racchiudere i suoi elementi in una linea chiusa.

Esempio 1. L'insieme A costituito dalle cifre del numero 1100 ha la seguente rappresentazione grafica:

Slide 11 University of Catania Lezioni di Matematica 7

Esempio 2. L'insieme B formato dalle vocali dell'alfabeto italiano ha la seguente rappresentazione grafica:

Slide 12 Rappresentazione caratteristica

La rappresentazione caratteristica di un insieme consiste nel caratterizzare i suoi elementi con una proprietà comune detta appunto proprietà caratteristica.

Slide 13 Esempio 1. L'insieme A costituito dalle cifre del numero 1100 ha la seguente rappresentazione caratteristica:

{ }A = numeri interi compresi tra 0 e 2 o equivalentemente {x ≤ ≤ }A = numeri interi, 0 x 2

University of Catania Lezioni di Matematica 8

Esempio 2. L'insieme B formato dalle vocali dell'alfabeto italiano ha la seguente rappresentazione grafica:

Slide 14 { }A = vocali dell'alfabeto italiano

equivalentemente {x: }A = vocale dell’alfabeto italiano

Insiemi: Definizioni

U.L’Universo

È bene fissare di volta in volta un universo di oggetti. denotato diU.solito con Gli insiemi che verranno considerati conterranno soloelementi di tale universo.

Tipiche scelte per universo sono:

Slide 15 N l’insieme dei numeri naturali (cioé 0, 1, . . .).

Z N −1, −2,l’insieme dei numeri interi (cioé tutto piú . . .)

Q Q Q+, , , l’insieme dei numeri razionali, l’insieme dei numeri−razionali positivi, e l’insieme dei numeri razionali negativi.

(N.B. I numeri positivi sono strettamente maggiori di 0. Innumeri negativi strettamente minori di 0).

University of Catania Lezioni di Matematica 9∅

L’insieme vuoto• Definizione. Si definisce insieme vuoto l’insieme privo diSlide 16 ∅.elementi che si indica col simbolo

(Nota Nel caso degenere in cui l’universo é vuoto allora essocoincide con l’insieme vuoto.

Relazioni tra Insiemi: Simboli e significato

• Il simbolo di appartenenza: Quando a denota un elemento e Q un insieme, scriveremo a ∈ Q per dire che a appartiene a Q. Scriveremo a ∉ Q per dire che a non appartiene a Q.
• Scriveremo a, b ∈ Q per abbreviare: a ∈ Q e b ∈ Q.

Insiemi Uguali

• Definizione: Due insiemi A e B si dicono uguali quando sono costituiti dagli stessi elementi, cioè ogni elemento di uno è anche elemento dell'altro. In questo caso si scrive: A = B.
• Definizione: Se due insiemi A e B non sono uguali allora si dice che A e B sono diversi e si scrive: A ≠ B.

Insiemi disgiunti

• Definizione: Se nessun elemento di A sta in B, allora si dice che A e B sono disgiunti.

Esempio 1: A = {r, {t, → A = t}} e B = {r}. A = B.

Esempio 2: A = {a, {a, → A = b, c}} e B = {d, e}. A ≠ B.

Esempio 3: A = {a, {m, → A = n, t}} e B = {n, t}. A e B

Sono esempi di insiemi disgiunti. ⊆L'inclusione - simbolo. Diremo che B è un sottoinsieme di A se ogni elemento di B appartiene anche a A. Si dice anche che B è incluso in A. ⊆Scriveremo B ⊆ A. Slide 19 *Per dire che B non è un sottoinsieme di A scriveremo B ⊈ A. University of Catania Lezioni di Matematica 11⊆ ⊆Talvolta per dire che A ⊆ B e B ⊆ C si scrive per brevità una ⊆ ⊆catena di inclusioni A ⊆ B ⊆ C. Slide 20 Uguaglianza e doppia inclusione ⊆ ⊆Si noti che se A = B allora ovviamente A ⊆ B e B ⊆ A. ⊆ ⊆Viceversa, se si ha simultaneamente A ⊆ B e B ⊆ A allora A e B hanno gli stessi elementi e quindi, per il principio di Slide 21 estensionalità, A = B. ⊆ ⊆Abbiamo quindi che A ⊆ B e A ⊇ B se e solo se A = B. La espressione "se e solo se" viene spesso abbreviata con "sse" o ⇔.

Inclusioni banali U⊆ ⊆È immediato verificare che le inclusioni A ⊆ A e A ⊇ A valgono per ogni insieme.

University of Catania Lezioni di Matematica 12

A.∅ ⊆Anche A vale anche per qualsiasi insieme A.

∅Infatti A significa che ogni elemento di ∅ è un elemento di A. Se ciò non fosse vero dovremmo essere in grado di trovare un controesempio, cioè un elemento di ∅ che non appartiene a A. Ma ∅ non ha elementi sicché tale controesempio non può esistere.

⇓Ogni insieme possiede sicuramente due sottoinsiemi: se stesso e l'insieme vuoto.

⊂Inclusione stretta, Definizione: Si definisce sottoinsieme proprio di un insieme A ogni suo sottoinsieme non vuoto e distinto da A.

Il generico insieme B = si dirà quindi sottoinsieme proprio di A,

⊂e si scriverà B ⊆ A, se ⊆ 6B ⊆ A e B ≠ A.

Si può anche dire che: ∀b ∈ B ⇒ b ∈ A e ∃a ∈ A : a ∉ B ∧.

Nota. Il termine ∧ indica AND o equivalentemente

University of Catania Lezioni di Matematica 13

Operazioni Booleane

I principali operatori booleani binari sugli insiemi

sono: ∗ ∩ ∗ : Intersezione ∪ ∗ : Unione

Slide 24 ∗ \ ∗ : Differenza ∗ ∆ : Differenza simmetrica

Il principale operatore unario è ¬ ∗ : il complemento Intersezione

• Si definisce intersezione tra due insiemi A e B:

Definizione: l'insieme formato dagli elementi comuni ad A e B.

L'intersezione è un operatore binario tra insiemi che viene indicato con il simbolo ∩.

Slide 25 ∩ {x ∈ A ∩ B = : x ∈ A e x ∈ B}

University of Catania Lezioni di Matematica 14

Unione

• Si definisce unione tra due insiemi A e B:

Definizione: l'insieme formato dagli elementi che appartengono ad A o che appartengono a B.

L'unione è un operatore binario tra insiemi che viene indicato con il simbolo ∪.

Slide 26 ∪ {x ∈ A ∪ B = : x ∈ A o x ∈ B}

Ovviamente:

• ∩ ∅

Se A e B non hanno elementi comuni allora A ∩ B =

• ∪ ⊆ ∪ ⊆ A ∩ B A e A ∩ B B

• ∩ ⊂ ∩_eA B A e A B BUniversity of Catania Lezioni di Matematica 15Differenza^• Definizione. Si definisce insieme differenza tra due insiemi A e B, l'insieme formato dagli elementi che appartengono ad A e che non appartengono a B. La differenza è un operatore binario tra insiemi che viene indicato con il simbolo {x ∈ A\B = : x ∈ A e x ∉ B}Slide 28 In termini di operazioni booleane tra insiemi si può scrivere:∩A\B = A (¬B)Differenza Simmetrica^• Definizione. La differenza simmetrica tra A e B è l'insieme degli elementi che: appartengono a A e non appartengono a B o che appartengono a B ma non appartengono ad A. Viene denotata △ con A △ B.△ {x ∈ A △ B = : x ∈ A e x ∉ B, o , x ∈ B e x ∉ A}. Valgono, come si vede banalmente dalla figura, le due relazioniSlide 29 seguenti:△ ∪ △ ∪ ∩A B = (A\B) ∪ (B\A) A △ B = (A ∪ B)\(B ∪ A)University of Catania Lezioni di Matematica 16Differenza complementare^• Definizione. Si definisceLa differenza complementare tra due insiemi, l'insieme A ed un secondo insieme B, è indicata come A - B.