Istituzioni matematiche I

Gli insiemi

Esistono insiemi

- Per caratteristica: hanno una caratteristica comune (bambini della classe A)
Caratteristica A = {x: x è un bambino della classe A}

- Per elencazione: insiemi in cui gli elementi non hanno nulla in comune (nessuna caratteristica evidente) se non quello di essere inseriti nell'insieme A.
Elencazione: A = {1,2,3..} L’ordine degli elementi non ha importanza

Non si può dare una definizione matematica di insieme perché è un concetto primitivo. Un insieme A è dato ogni volta che, preso un oggetto, so dire se tale oggetto è un elemento oppure no dell’insieme A. Appartenenza e elemento (di un insieme) sono anch’essi concetti primitivi. X è un elemento di A vuol dire che X appartiene ad A => x ad A ∈. L’ordine con cui vengono scritti gli elementi per elencazione non ha importanza. Gli insiemistici possono essere rappresentati graficamente (ovale con dentro puntini) A = {1,2,3,4}.

Definizione di sottoinsieme

Un insieme A è sottoinsieme di un insieme B se ogni elemento di A è anche elemento di B. X∈A => x∈B. A è contenuto (⊆) o contenuto uguale (⊆) a B => A è sottoinsieme di B che non coincide con B oppure che coincide con B. A B⊆⊆.

Numeri primi sono un sottoinsieme dei numeri interi (graficamente un ovale dentro un ovale). Rappresentazione grafica di insiemi e sottoinsiemi. Tutti gli insiemi hanno sempre 2 sottoinsiemi, uno è l’insieme stesso e l’altro è l’insieme vuoto (∅).

Definizione di insieme vuoto

(∅): insieme che non ha elementi ed è il sottoinsieme di qualunque insieme. X∈∅ => x∈A => ∅∈A. Se x appartiene all'insieme vuoto allora X appartiene all’insieme A (perché l’insieme vuoto è sottoinsieme di qualsiasi insieme e quindi anche dell’insieme). Di conseguenza l’insieme ∅ appartiene ad A.

Se vale P allora vale Q.. questa è falsa solo se P (premessa) è vera e Q (la conseguenza) è falsa se no negli altri casi è sempre vera:

• Se sono tutte e due vere
• Se P è falsa e Q è vera
• Se sono tutte e due false

Esempio: Se passo aritmetica ti porto a cena.. passo e non ti porto a cena .. qui è falsa, negli altri casi è vera. Ogni mio gatto è nero. È falsa se ho almeno un gatto e non è nero. Se un gatto viene preso tra i miei gatti allora deve essere nero. Anche se io non ho gatti continua ad essere vera perché sto parlando di qualcosa che non c’è. => l’insieme vuoto infatti è sottoinsieme di ogni insieme.

Definizione di cardinalità

La cardinalità dell'insieme A è il numero dei suoi elementi e si indica con |A|. A= {a,3,mercurio, pera} => |A| = 4. C = => |C| = 0. ∅ ∞.

N = numeri naturali => |N| = (vale anche per i numeri primi). La cardinalità di un sottoinsieme è sicuramente minore o uguale a quella dell’insieme. A B => |A| ≤ |B| ⊆.

Definizione di insiemi equipotenti finiti

Due insiemi di cardinalità finita A è B si dicono equipotenti se hanno lo stesso numero di elementi => |A| = |B|.

Insiemi i cui elementi sono insiemi

Gli insiemi possono avere come elementi oggetti di ogni tipo e quindi possono anche avere come elementi alcuni altri insiemi. Se gli elementi sono le classi, le classi sono insiemi di bambini e al tempo stesso elementi dell’insieme classe.

Problema: contare i sottoinsiemi

Devo dividere i bambini in gruppo, quante possibilità ho di scegliere? (Dividere in gruppo è come contare sottoinsiemi). Per contare i sottoinsiemi delle persone in aula bisogna contare l’insieme vuoto, l’insieme stesso, le persone singole (24 persone), tutte le coppie, le terzine, le quaterne.

Definizione di insieme delle parti di un insieme

Dato un insieme A, l’insieme i cui elementi sono i sottoinsiemi di A si chiama insieme delle parti di A e si scrive P(A).

Esempio: A=(a,b,c)
P(A) = {∅, {a,b,c}, {a}, {b}, {c}, {ab}, {bc}, {ca} }
Non importa l’ordine con cui si scrivono gli elementi infatti {a,c} o {c,a} è uguale. L’insieme vuoto ha un solo sottoinsieme (se stesso), l’insieme con un solo elemento ha due sottoinsiemi (se stesso e ∅), l’insieme con tre elementi ha otto sottoinsiemi, l’insieme con quattro elementi ha 16 sottoinsiemi. I sottoinsiemi sono sempre pari tranne nel primo caso e, ogni volta che viene aggiunto un elemento, i sottoinsiemi raddoppiano.

Formula per i sottoinsiemi

Se un insieme A è tale che la sua cardinalità |A| = n allora |P(A)| = 2ⁿ. Questa proprietà si può dimostrare in diversi modi.

Dimostrazione I

L’insieme A è fatto da N elementi (scatole). Per contare i sottoinsiemi basta dire per ogni scatola o elemento se lo voglio nel mio sottoinsieme o no. Ogni mia scelta corrisponde a dire sì oppure no all’elemento (da qui deriva il 2 dell’elevazione).

Dimostrazione II

Di solito fare scelte è come costruire un albero le cui terminazioni sono tante quante sono i sottoinsiemi. Le scelte sono sempre due (destra no sinistra sì) e a ogni livello c’è una duplicazione: da qui deriva 2ⁿ.

Operazioni insiemistiche

Dati due insiemi se ne può definire un terzo frutto di un’operazione. Si parla di operazioni binarie perché l’operazione richiede due insiemi come input e risulta un insieme come output.

Definizione di unione A U B

L’insieme unione di A e B è l’insieme che ha per elementi tutti gli elementi di A e tutti gli elementi di B. E quindi l’elemento è di A o di B oppure di entrambi.
A U B = {x: x∈A ∨ x∈B}

Definizione di intersezione A ∩ B

L’insieme intersezione di A e B è l’insieme che ha per elementi tutti gli elementi che appartengono sia ad A che a B.
A ∩ B = {x: x∈A ∧ x∈B}

Definizione di insiemi disgiunti

A ∩ B = ∅

Definizione di differenza A\B

L’insieme differenza di A e B è l’insieme che ha per elementi tutti gli elementi che appartengono ad A e non appartengono a B.
A\B = {x∈A: x∉B}

Definizione di complementare rispetto ad un altro insieme A^C o Ā

L’insieme differenza Ω \ A viene a volte chiamato complementare di A in (Ω). A volte si lascia sottinteso chi è l’insieme Ω.

Definizione di differenza simmetrica A Δ B

L’insieme differenza simmetrica di A e B è l’insieme che ha per elementi tutti gli elementi che appartengono ad A e non appartengono a B, oppure che appartengono a B e non ad A.
A Δ B = {x: (x∈A ∧ x∉B) ∨ (x∉A ∧ x∈B)} = (A\B) U (B\A)

Leggi di De Morgan

Dati due insiemi A e B e scrivendo i complementari rispetto ad un unico insieme Ω, valgono:

• Unione dei complementari uguale all'intersezione dei complementari
• Due insiemi presentati diversamente sono la stessa cosa

Come mostrare che due insiemi coincidono

Per mostrare che due insiemi sono in realtà lo stesso insieme cioè A=B si possono mostrare i due fatti:

• A ⊆ B
• B ⊆ A

Proprietà delle operazioni insiemistiche

Unione uguale alla somma
Intersezioni affinità con il prodotto

• Commutatività nell’unione (non importa l’ordine dei fattori). A U B = B U A
• Commutativa nell’intersezione A ∩ B = B ∩ A
• Associativa dell'unione (non importa cosa sommo per prima 7+3+5 è più comodo di 5+3+7). (A U B) U C = A U(C U B)
• Associativa intersezione. (A ∩ B) ∩ C = A ∩(C ∩ B)
• Distributiva intersezione rispetto all’unione (se faccio 2x (5+3) posso sommare e poi moltiplicare o moltiplicare entrambi i numeri e poi sommarli) A ∩(C U B) = (A ∩B) U(A ∩ C)
• Distributiva unione rispetto intersezione A U(C ∩ B) = (A U B) ∩(A U C)
• Elemento neutro unione A U ∅ = A, per ogni (∀)A
• Elemento neutro intersezione. A ∩ Ω = A, ∀A

Prodotto cartesiano di due insiemi (A x B)

L’insieme prodotto di A e B è l’insieme che ha per elementi tutte le coppie ordinate (a, b) dove a ∈A e b ∈ B. In questo caso l’ordine nella coppia è importante.

Esempio: A = {1,2,3}
B = {a, b}
A x B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

Gli elementi del prodotto di A per B lo si trovano facendo due (elementi in B) per tre (elementi in A). A x B = 2x3 = 6. L’insieme prodotto si può rappresentare tramite:

• Piano cartesiano
• Tabella

Cardinalità del prodotto

Se |A| = n e |B| = m, allora |A x B| = n x m.

Contare i sottoinsiemi

Una classe ha 12 bambini, in quanti modi posso scegliere un suo sottoinsieme? E se il sottoinsieme non deve essere vuoto?

• Il numero dei sottoinsiemi si trova con la formula 2 alla 12 = 4096.
• Per la seconda domanda basta togliere l’insieme vuoto = 4095.

Contare solo i sottoinsiemi con un certo numero di elementi
Ho un insieme con n elementi quanti sono i sottoinsiemi che ne hanno k? (Problemi di conteggio => cardinalità di sottoinsiemi)

Esempio: ho un insieme di 24 elementi ma voglio un gruppo di 3 persone. Ci sono tre caselline: in una metto la prima persona, nella seconda metto la seconda e nella terza la terza. Nella prima tabellina ho 24 scelte per la prima persona, per la seconda persone invece ho 23 scelte perché una è già nel primo, alla terza scelta ho 22 scelte. Sembrerebbe 24x23x22 ma in questo caso a me non importa metterli in ordine uno dopo l’altro. Se scelgo Maria Piero e Paolo o Pietro Paolo e Maria o Paolo Maria Piero è la stessa cosa. Questo gruppo può comparire in diversi modi e devo contare quanti modi ho. Ci sono 3x2x1 = 6 modi diversi di mettere in fila tre persone. Calcolo = 24x23x22 / 6 = 2024.

Se ho un insieme con N elementi, quanti sono i suoi sottoinsiemi con k elementi? Sì ogni sottoinsieme è contato tante volte quanti sono i modi per allineare K oggetti:

• N scelte per il primo elemento
• N scelte - 1 per il secondo
• N scelte -2 per il terzo

Formula totale: n x (n-1) x (n-2)…(n-k+1)
Se invece ho K oggetti, i modi per allinearli sono:
Formula: K x (k-1) x (k-2)…2x1
Questa formula va divisa a quella prima quando non voglio allineare. Quanti modi ho di mettere in fila 5 oggetti? = 5x4x3x2x1 =120.

Tornando al problema: Se ho un insieme con n elementi, quanti sono i suoi sottoinsiemi con k elementi?
Formula generale: n x (n-1) x (n-2)…(n-k+1) / K x (k-1) x (k-2)…2x1
Esempio: I sottoinsiemi di 3 oggetti di un insieme di 7 elementi: 7x6x5 / 3x2x1.

Contare la cardinalità (elementi) di sottoinsiemi

Esempio: in una classe ci sono 10 bambine e 12 bambini e devo scegliere una bambina e un bambino. Quante possibilità ho? 10 x 12 non c’è il fratto 2 perché l’ordine in questo caso è rilevante.

Esercizi da wims

• E = {ω, ω (-4…,3) e cardinalità (ω) = 4}⊆
  Qual è la cardinalità dell’insieme E (ossia insieme degli omega) in cui però omega è un sottoinsieme (⊆) da -4 a 3 (quindi sono 8 elementi) ma l'insieme ne deve contenere solo 4 (card=4).
  Calcolo: 8x7x6x5 / 4x3x2x1 =70
• E = {-14,…,11}²
  Qual è la cardinalità dell’insieme E?
  Prodotto (-14..11) x (-14..11)
  Calcolo: 26x26
• E = {(x₁,…,x₆) {0,1}⁶, x₁ + x₂ + x₃ + x₄ + x₅ = 4} ∈ (0,1) x(0,1) x(0,1) x(0,1)x(0,1) x(0,1) = (000000) (001000)..
  Delle prime 5 coordinate 4 sono 1 e l'altra zero mentre la sesta è libera:
  • Nella sesta ho 2 scelte
  • Le prime 5 basta scegliere dove mettere lo zero e gli altri sono 1. Posso mentre lo zero in 5 posizioni (5 scelte)
  Calcolo: 5x2=10
• E= {(x₁,…,x₇) {-2,…,5}⁷, x₁ <…< x₇} ∈
  Qual è la cardinalità di E? Sottoinsiemi di sette elementi di un insieme da otto. In questo caso basta anche scegliere chi non viene con me: ho 8 possibilità di escludere una persona.
  Calcolo: 8
• E= {(x₁,…,x₇) {-2,…,7}⁷ : x₁ <...< x₇} ∈
  Ho 10 numeri e devo scegliere un sottoinsieme da 7 elementi. Se non avessi avuto vincoli avevo 10 scelte per ogni elemento (10 alla settima) ma qui ho i simboli minori perciò ho 10 scelte per il primo, 9 per la seconda… fratto 7 x 6.. perché non c’è l’ordine
  Calcolo: 10 x 9 x 8 x7 x6 x5 x 4 / 7 x 6 x 5 x 4 x 3 x 2 x 1 = 120

Le funzioni

Introduzione alle funzioni

Cosa facciamo quando contiamo? (Lo sviluppo del senso del numero lo hanno anche gli animali). Associamo un numero a ogni elemento creando delle corrispondenze (12 pasticcini) => questa è una funzione. Anche associare a ogni individuo i pasticcini che mangia (Marco numero 1, Giulia 2..) è una corrispondenza. La rappresentazione grafica è con delle frecce.

Definizione di corrispondenza

Una corrispondenza dall'insieme A all’insieme B è un sottoinsieme dell’insieme prodotto A x B. A = graffa Maria, Giovanni B 1,2,3,4. Graficamente si può rappresentare con le frecce, con le coppie, con un piano cartesiano che ha sull’asse orizzontale le persone e sull’asse verticale i numeri di pasticcini (quindi in realtà non sono veri numeri e non è un vero piano cartesiano). Corrispondenza: (Maria, 1), (Maria 7), (Giovanni 10).

Se viene chiesto un esempio di funzioni tra insiemi si possono usare i bambini che usano un gioco, i bambini che si siedono su una sedia.

Definizione di funzione

Una funzione f da A a B è una corrispondenza tale che ogni elemento di a è associato uno e uno solo elemento di B → simboli : f: A B. Ma non tutte le corrispondenze sono funzioni:

• Non possono esserci elementi di A da cui non partono frecce => non esiste nessun elemento di A senza corrispondenze di B (non può esserci qualcuno che non mangia i pasticcini).
• Da ogni elemento di A non possono partire più frecce => ad ogni elemento di A è associato un solo elemento di B. Se io conosco la partenza conosco anche l’arrivo, tutta la scienza dell’essere umano è basata su ciò (la temperatura che imposto creerà una certa situazione). Esempio il bambino che lancia oggetti per vedere che cade a terra.

Definizione di dominio e codominio (partenza e arrivo)

Se ho una funzione f da A a B:

• A si chiama dominio della funzione f
• B è il codominio della funzione f

Esempio grafico

Definizione di immagine (di un elemento del dominio)
Se ho una funzione f da A a B e x ∈ A - con f(x) si indica l'elemento di B che è associato a x, che si chiama immagine di x.

Esempio grafico

Definizione di controimmagine
Se ho una funzione f da A a B e y ∈ B (codominio) - con f^-1(y) si indica il sottoinsieme A i cui elementi hanno immagine y e lo si chiama controimmagine di y. Quando vado a percorrere la freccia al contrario trovo un sottoinsieme che può essere composto da uno, zero o più elementi (controimmagine).

Esempio grafico

Funzione composta

Le funzioni le posso continuare se abbiamo una funzione da A a B e una da B a C otteniamo una funzione da A a C. Esempio:

• A = bambini scuola Manzoni
• B = donne
• C = uomini

Definizione di funzione composta

Date f: A B e g: B C, la funzione composta di g composto f è una funzione h: A C che associa ad ogni elemento x ∈ A l’elemento z ∈ C definito come z = g(f(x)).
Esempio: al bambino associo la madre (f(X)), poi unisco i nonni (g).
Simboli: h(x) = g(f(x)) ∀x ∈ A

Proprietà di alcune funzioni

Definizione di funzione suriettiva (non ci sono elementi che non sono colpiti da frecce)
Una funzione f: A B è suriettiva se per ogni y elemento di B, il suo insieme controimmagine non è vuoto. ∀y ∈ B, f^-1(y) ≠ ∅.

Come mostrare che è suriettiva/non è suriettiva

Se ho h: A B:

• Per far vedere che è suriettiva devo fare vedere che comunque io prenda y ∈ B esiste un x ∈ A per cui f(x) = y.
• Per far vedere che non è suriettiva basta fare vedere che c’è almeno un punto senza controimmagine: y ∈ B che non è immagine di nessuno x ∈ A (controesempio).

Come mostrare proprietà generali

Per mostrare che una relazione è sempre vera bisogna fare una dimostrazione per tutti gli oggetti di cui sto parlando (se è infinita?): ad esempio “tutti i numeri la cui somma delle cifre è multiplo di 3 sono multipli di 3 loro stessi” non basta qualche esempio. Se invece devo dire che una dimostrazione non è vera basta trovare un esempio che non corrisponde: “tutti i gatti sono rossi” ne porto uno nero.

Definizione di funzione iniettiva

Una funzione f: A B è iniettiva se per ogni coppia di elementi diversi x₁ e x₂ di A, le loro immagini sono diverse. Non ci sono elementi in B su cui arrivi più di una freccia.
Simboli: ∀x₁, x₂ ∈ A: f(x₁) ≠ f(x₂)

Posso dirlo usando la controimmagine: ∀y ∈ B, |f^-1(y)| ≤ 1. L'insieme controimmagine è sempre minore o uguale a 1.