Matematica discreta - Insiemi

Matematico tedesco G. Cantorha introdotto il concetto di set. Aveva definito un insieme come una raccolta di oggetti definiti e distinguibili selezionati per mezzo di determinate regole o descrizioni.

Setla teoria costituisce la base di molti altri campi di studio come la teoria dei conteggi, le relazioni, la teoria dei grafi e le macchine a stati finiti. In questo capitolo tratteremo i diversi aspetti diSet Theory.

Set - Definizione

Un set è una raccolta non ordinata di elementi diversi. Un set può essere scritto esplicitamente elencando i suoi elementi usando la parentesi di set. Se l'ordine degli elementi viene modificato o viene ripetuto qualsiasi elemento di un set, non vengono apportate modifiche al set.

Alcuni esempi di set

  • Un insieme di tutti i numeri interi positivi
  • Un insieme di tutti i pianeti del sistema solare
  • Un insieme di tutti gli stati dell'India
  • Un insieme di tutte le lettere minuscole dell'alfabeto

Rappresentazione di un set

Gli insiemi possono essere rappresentati in due modi:

  • Elenco o forma tabulare
  • Imposta la notazione del costruttore

Elenco o forma tabulare

L'insieme è rappresentato elencando tutti gli elementi che lo compongono. Gli elementi sono racchiusi tra parentesi graffe e separati da virgole.

Example 1 - Set di vocali in alfabeto inglese, $ A = \ lbrace a, e, i, o, u \ rbrace $

Example 2 - Insieme di numeri dispari inferiori a 10, $ B = \ lbrace 1,3,5,7,9 \ rbrace $

Imposta la notazione del costruttore

L'insieme è definito specificando una proprietà che gli elementi dell'insieme hanno in comune. L'insieme è descritto come $ A = \ lbrace x: p (x) \ rbrace $

Example 1 - L'insieme $ \ lbrace a, e, i, o, u \ rbrace $ è scritto come -

$ A = \ lbrace x: \ text {x è una vocale in alfabeto inglese} \ rbrace $

Example 2 - L'insieme $ \ lbrace 1,3,5,7,9 \ rbrace $ è scritto come -

$ B = \ lbraccia x: 1 \ le x \ lt 10 \ e \ (x \% 2) \ ne 0 \ rbrace $

Se un elemento x è un membro di qualsiasi insieme S, è denotato da $ x \ in S $ e se un elemento y non è un membro dell'insieme S, è denotato da $ y \ non in S $.

Example- Se $ S = \ lbrace1, 1.2, 1.7, 2 \ rbrace, 1 \ in S $ ma $ 1.5 \ non in S $

Alcuni set importanti

N - l'insieme di tutti i numeri naturali = $ \ lbrace1, 2, 3, 4, ..... \ rbrace $

Z - l'insieme di tutti i numeri interi = $ \ lbrace ....., -3, -2, -1, 0, 1, 2, 3, ..... \ rbrace $

Z+ - l'insieme di tutti i numeri interi positivi

Q - l'insieme di tutti i numeri razionali

R - l'insieme di tutti i numeri reali

W - l'insieme di tutti i numeri interi

Cardinalità di un set

La cardinalità di un insieme S, indicata con $ | S | $, è il numero di elementi dell'insieme. Il numero è indicato anche come numero cardinale. Se un insieme ha un numero infinito di elementi, la sua cardinalità è $ \ infty $.

Example- $ | \ lbraccia 1, 4, 3, 5 \ rbrace | = 4, | \ lbrace 1, 2, 3, 4, 5, \ dots \ rbrace | = \ infty $

Se ci sono due insiemi X e Y,

  • $ | X | = | Y | $ denota due insiemi X e Y aventi la stessa cardinalità. Si verifica quando il numero di elementi in X è esattamente uguale al numero di elementi in Y. In questo caso, esiste una funzione biiettiva "f" da X a Y.

  • $ | X | \ le | Y | $ denota che la cardinalità dell'insieme X è minore o uguale alla cardinalità dell'insieme Y. Si verifica quando il numero di elementi in X è minore o uguale a quello di Y. Qui esiste una funzione iniettiva 'f' da X a Y.

  • $ | X | \ lt | Y | $ denota che la cardinalità dell'insieme X è minore della cardinalità dell'insieme Y. Si verifica quando il numero di elementi in X è inferiore a quello di Y. Qui, la funzione 'f' da X a Y è una funzione iniettiva ma non biiettiva.

  • $ Se \ | X | \ le | Y | $ e $ | X | \ ge | Y | $ poi $ | X | = | Y | $. Gli insiemi X e Y sono comunemente indicati come insiemi equivalenti.

Tipi di set

I set possono essere classificati in molti tipi. Alcuni dei quali sono finiti, infiniti, sottoinsiemi, universali, propri, singoli, ecc.

Insieme finito

Un insieme che contiene un numero definito di elementi è chiamato insieme finito.

Example- $ S = \ lbrace x \: | \: x \ in N $ e $ 70 \ gt x \ gt 50 \ rbrace $

Set infinito

Un insieme che contiene un numero infinito di elementi è chiamato un insieme infinito.

Example- $ S = \ lbrace x \: | \: x \ in N $ e $ x \ gt 10 \ rbrace $

Sottoinsieme

Un insieme X è un sottoinsieme dell'insieme Y (scritto come $ X \ subseteq Y $) se ogni elemento di X è un elemento dell'insieme Y.

Example 1- Siano $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ e $ Y = \ lbrace 1, 2 \ rbrace $. Qui l'insieme Y è un sottoinsieme dell'insieme X poiché tutti gli elementi dell'insieme Y sono nell'insieme X. Quindi, possiamo scrivere $ Y \ subseteq X $.

Example 2- Siano $ X = \ lbrace 1, 2, 3 \ rbrace $ e $ Y = \ lbrace 1, 2, 3 \ rbrace $. Qui l'insieme Y è un sottoinsieme (non un sottoinsieme appropriato) dell'insieme X poiché tutti gli elementi dell'insieme Y sono nell'insieme X. Quindi, possiamo scrivere $ Y \ subseteq X $.

Sottoinsieme proprio

Il termine "sottoinsieme proprio" può essere definito come "sottoinsieme di ma non uguale a". Un insieme X è un sottoinsieme appropriato dell'insieme Y (scritto come $ X \ sottoinsieme Y $) se ogni elemento di X è un elemento dell'insieme Y e $ | X | \ lt | Y | $.

Example- Siano $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ e $ Y = \ lbrace 1, 2 \ rbrace $. Qui imposta $ Y \ sottoinsieme X $ poiché tutti gli elementi in $ Y $ sono contenuti anche in $ X $ e $ X $ ha almeno un elemento è più di $ Y $ impostato.

Set universale

È una raccolta di tutti gli elementi in un particolare contesto o applicazione. Tutti gli insiemi in quel contesto o applicazione sono essenzialmente sottoinsiemi di questo insieme universale. Gli insiemi universali sono rappresentati come $ U $.

Example- Possiamo definire $ U $ come l'insieme di tutti gli animali sulla terra. In questo caso, l'insieme di tutti i mammiferi è un sottoinsieme di $ U $, l'insieme di tutti i pesci è un sottoinsieme di $ U $, l'insieme di tutti gli insetti è un sottoinsieme di $ U $ e così via.

Insieme vuoto o insieme nullo

Un set vuoto non contiene elementi. È indicato da $ \ emptyset $. Poiché il numero di elementi in un insieme vuoto è finito, l'insieme vuoto è un insieme finito. La cardinalità dell'insieme vuoto o dell'insieme nullo è zero.

Example- $ S = \ lbrace x \: | \: x \ in N $ e $ 7 \ lt x \ lt 8 \ rbrace = \ emptyset $

Set Singleton o Set di unità

L'insieme singleton o l'insieme di unità contiene solo un elemento. Un insieme singleton è indicato da $ \ lbrace s \ rbrace $.

Example- $ S = \ lbrace x \: | \: x \ in N, \ 7 \ lt x \ lt 9 \ rbrace $ = $ \ lbrace 8 \ rbrace $

Set uguale

Se due insiemi contengono gli stessi elementi si dice che sono uguali.

Example - Se $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 6, 1, 2 \ rbrace $, sono uguali in quanto ogni elemento dell'insieme A è un elemento dell'insieme B e ogni elemento dell'insieme B è un elemento dell'insieme A.

Set equivalente

Se le cardinalità di due insiemi sono le stesse, vengono chiamate insiemi equivalenti.

Example- Se $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 16, 17, 22 \ rbrace $, sono equivalenti in quanto la cardinalità di A è uguale alla cardinalità di B. cioè $ | A | = | B | = 3 $

Set sovrapposti

Due insiemi che hanno almeno un elemento comune sono chiamati insiemi sovrapposti.

In caso di serie sovrapposte -

  • $ n (A \ cup B) = n (A) + n (B) - n (A \ cap B) $

  • $ n (A \ cup B) = n (A - B) + n (B - A) + n (A \ cap B) $

  • $ n (A) = n (A - B) + n (A \ cap B) $

  • $ n (B) = n (B - A) + n (A \ cap B) $

Example- Siano $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 6, 12, 42 \ rbrace $. C'è un elemento comune "6", quindi questi insiemi sono insiemi sovrapposti.

Insieme disgiunto

Due insiemi A e B sono chiamati insiemi disgiunti se non hanno nemmeno un elemento in comune. Pertanto, gli insiemi disgiunti hanno le seguenti proprietà:

  • $ n (A \ cap B) = \ emptyset $

  • $ n (A \ cup B) = n (A) + n (B) $

Example - Sia $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 7, 9, 14 \ rbrace $, non c'è un singolo elemento comune, quindi questi insiemi sono insiemi sovrapposti.

Diagrammi di Venn

Il diagramma di Venn, inventato nel 1880 da John Venn, è un diagramma schematico che mostra tutte le possibili relazioni logiche tra diversi insiemi matematici.

Examples

Imposta operazioni

Le operazioni di gruppo includono Unione di gruppi, Intersezione di gruppo, Differenza di gruppo, Complemento di gruppo e Prodotto cartesiano.

Set Union

L'unione degli insiemi A e B (indicata con $ A \ cup B $) è l'insieme di elementi che si trovano in A, in B, o sia in A che in B. Quindi, $ A \ cup B = \ lbrace x \: | \: x \ in A \ OR \ x \ in B \ rbrace $.

Example- Se $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ e B = $ \ lbrace 13, 14, 15 \ rbrace $, allora $ A \ cup B = \ lbrace 10, 11, 12, 13, 14 , 15 \ rbraccia $. (L'elemento comune si verifica una sola volta)

Imposta intersezione

L'intersezione degli insiemi A e B (indicata da $ A \ cap B $) è l'insieme di elementi che si trovano sia in A che in B. Quindi, $ A \ cap B = \ lbrace x \: | \: x \ in A \ AND \ x \ in B \ rbrace $.

Example - Se $ A = \ lbrace 11, 12, 13 \ rbrace $ e $ B = \ lbrace 13, 14, 15 \ rbrace $, allora $ A \ cap B = \ lbrace 13 \ rbrace $.

Imposta differenza / complemento relativo

La differenza di insiemi degli insiemi A e B (indicata con $ A - B $) è l'insieme di elementi che si trovano solo in A ma non in B. Quindi, $ A - B = \ lbrace x \: | \: x \ in A \ AND \ x \ notin B \ rbrace $.

Example- Se $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ e $ B = \ lbrace 13, 14, 15 \ rbrace $, allora $ (A - B) = \ lbrace 10, 11, 12 \ rbrace $ e $ (B - A) = \ lbrace 14, 15 \ rbrace $. Qui possiamo vedere $ (A - B) \ ne (B - A) $

Complemento di un set

Il complemento di un insieme A (indicato con $ A '$) è l'insieme di elementi che non sono nell'insieme A. Quindi, $ A' = \ lbrace x | x \ notin A \ rbrace $.

Più specificamente, $ A '= (U - A) $ dove $ U $ è un insieme universale che contiene tutti gli oggetti.

Example- Se $ A = \ lbrace x \: | \: x \ \: {appartiene \: a \: set \: di \: dispari \: interi} \ rbrace $ poi $ A '= \ lbrace y \: | \: y \ \: {non \: non \: appartiene \: a \: set \: di \: dispari \: interi} \ rbrace $

Prodotto cartesiano / Prodotto incrociato

Il prodotto cartesiano di n numero di insiemi $ A_1, A_2, \ dots A_n $ indicato come $ A_1 \ times A_2 \ dots \ times A_n $ può essere definito come tutte le possibili coppie ordinate $ (x_1, x_2, \ dots x_n) $ dove $ x_1 \ in A_1, x_2 \ in A_2, \ punti x_n \ in A_n $

Example - Se prendiamo due set $ A = \ lbrace a, b \ rbrace $ e $ B = \ lbrace 1, 2 \ rbrace $,

Il prodotto cartesiano di A e B è scritto come - $ A \ times B = \ lbrace (a, 1), (a, 2), (b, 1), (b, 2) \ rbrace $

Il prodotto cartesiano di B e A è scritto come - $ B \ times A = \ lbrace (1, a), (1, b), (2, a), (2, b) \ rbrace $

Power Set

Insieme di potenza di un insieme S è l'insieme di tutti i sottoinsiemi di S compreso l'insieme vuoto. La cardinalità di un insieme di potenze di un insieme S di cardinalità n è $ 2 ^ n $. Il set di alimentazione è indicato come $ P (S) $.

Example −

Per un insieme $ S = \ lbrace a, b, c, d \ rbrace $ calcoliamo i sottoinsiemi -

  • Sottoinsiemi con 0 elementi - $ \ lbrace \ emptyset \ rbrace $ (l'insieme vuoto)

  • Sottoinsiemi con 1 elemento: $ \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace c \ rbrace, \ lbrace d \ rbrace $

  • Sottoinsiemi con 2 elementi: $ \ lbrace a, b \ rbrace, \ lbrace a, c \ rbrace, \ lbrace a, d \ rbrace, \ lbrace b, c \ rbrace, \ lbrace b, d \ rbrace, \ lbrace c, d \ rbraccia $

  • Sottoinsiemi con 3 elementi: $ \ lbrace a, b, c \ rbrace, \ lbrace a, b, d \ rbrace, \ lbrace a, c, d \ rbrace, \ lbrace b, c, d \ rbrace $

  • Sottoinsiemi con 4 elementi: $ \ lbrace a, b, c, d \ rbrace $

Quindi, $ P (S) = $

$ \ lbrace \ quad \ lbrace \ emptyset \ rbrace, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace c \ rbrace, \ lbrace d \ rbrace, \ lbrace a, b \ rbrace, \ lbrace a, c \ rbrace, \ lbrace a, d \ rbrace, \ lbrace b, c \ rbrace, \ lbrace b, d \ rbrace, \ lbrace c, d \ rbrace, \ lbrace a, b, c \ rbrace, \ lbrace a, b, d \ rbrace, \ lbrace a, c, d \ rbrace, \ lbrace b, c, d \ rbrace, \ lbrace a, b, c, d \ rbrace \ quad \ rbrace $

$ | P (S) | = 2 ^ 4 = 16 $

Note - Anche il power set di un set vuoto è un set vuoto.

$ | P (\ lbrace \ emptyset \ rbrace) | = 2 ^ 0 = 1 $

Partizionamento di un set

La partizione di un insieme, diciamo S , è una raccolta di n sottoinsiemi disgiunti, diciamo $ P_1, P_2, \ dots P_n $ che soddisfa le seguenti tre condizioni:

  • $ P_i $ non contiene l'insieme vuoto.

    $ \ lbrack P_i \ ne \ lbrace \ emptyset \ rbrace \ for \ all \ 0 \ lt i \ le n \ rbrack $

  • L'unione dei sottoinsiemi deve essere uguale all'intero insieme originale.

    $ \ lbrack P_1 \ cup P_2 \ cup \ dots \ cup P_n = S \ rbrack $

  • L'intersezione di due insiemi distinti è vuota.

    $ \ lbrack P_a \ cap P_b = \ lbrace \ emptyset \ rbrace, \ for \ a \ ne b \ where \ n \ ge a, \: b \ ge 0 \ rbrack $

Example

Sia $ S = \ lbraccia a, b, c, d, e, f, g, h \ rbrace $

Un probabile partizionamento è $ \ lbrace a \ rbrace, \ lbrace b, c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $

Un altro probabile partizionamento è $ \ lbrace a, b \ rbrace, \ lbrace c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $

Numeri di campana

I numeri di campana forniscono il conteggio del numero di modi per partizionare un set. Sono indicati con $ B_n $ dove n è la cardinalità dell'insieme.

Example -

Sia $ S = \ lbraccia 1, 2, 3 \ rbrace $, $ n = | S | = 3 $

Le partizioni alternative sono:

1. $ \ emptyset, \ lbrace 1, 2, 3 \ rbrace $

2. $ \ lbrace 1 \ rbrace, \ lbrace 2, 3 \ rbrace $

3. $ \ lbrace 1, 2 \ rbrace, \ lbrace 3 \ rbrace $

4. $ \ lbrace 1, 3 \ rbrace, \ lbrace 2 \ rbrace $

5. $ \ lbrace 1 \ rbrace, \ lbrace 2 \ rbrace, \ lbrace 3 \ rbrace $

Quindi $ B_3 = 5 $