teoria degli insiemi

• i) Se ϕ e ψ sono iniettive, allora ψ ∘ ϕ è iniettiva.
• ii) Se ϕ e ψ sono suriettive, allora ψ ∘ ϕ è suriettiva.
• iii) Se ϕ e ψ sono biiettive, allora ψ ∘ ϕ è biiettiva.

Dimostrazione: i) Siano ϕ e ψ iniettive, se x e x' ∈ X, e (ψ ∘ ϕ)(x) = (ψ ∘ ϕ)(x') per l’iniettività di ψ, ψ(ϕ(x)) = ψ(ϕ(x')) implica ϕ(x) = ϕ(x') ed essendo ϕ iniettiva si ha x = x'.

ii) Se z ∈ Z esiste y ∈ Y tale che ψ(y) = z, ma, essendo anche ϕ suriettiva, esiste x ∈ X tale che ϕ(x) = y, quindi (ψ ∘ ϕ)(x) = ψ(ϕ(x)) = z, cioè ψ ∘ ϕ è suriettiva.

iii) Discende direttamente da i) e ii).

Teorema 2.2.: Siano ϕ: X → Y e ψ: Y → Z due applicazioni. Allora:

• i) Se ψ ∘ ϕ è iniettiva allora ϕ è iniettiva.
• ii) Se ψ ∘ ϕ è suriettiva allora ψ è suriettiva.
• iii) Se ψ ∘ ϕ è biiettiva allora ϕ è iniettiva e ψ è suriettiva.

Dimostrazione: i) Siano x e x' ∈ X, se ϕ(x) = ϕ(x'), per l’iniettività di ψ ∘ ϕ, (ψ ∘ ϕ)(x) = (ψ ∘ ϕ)(x') implica x = x' quindi ϕ è iniettiva.

ii) Se z ∈ Z esiste x ∈ X tale che (ψ ∘ ϕ)(x) = z, e, posto y = ϕ(x), si ha ψ(y) = z quindi ψ è suriettiva.

iii) Discende direttamente da i) e ii).

Si prova facilmente che la composizione di applicazioni è associativa, cioè se ϕ: X → Y, ψ: Y → Z e ω: Z → T sono applicazioni, allora ω ∘ (ψ ∘ ϕ) = (ω ∘ ψ) ∘ ϕ.

Sia X un insieme, chiamiamo applicazione identica (o identità) su X, l’applicazione i: X → X definita da i(x) = x per ogni x ∈ X.

Si prova subito che data un’applicazione ϕ: X → Y, se i_X: X → X e i_Y: Y → Y sono le applicazioni identiche rispettivamente su X e Y, allora i_Y ∘ ϕ = ϕ = ϕ ∘ i_X. Si provano anche facilmente i seguenti:

Teorema 2.3.: Sia ϕ: X → Y un’applicazione iniettiva, allora esiste un’applicazione ψ: Y → X tale che ψ ∘ ϕ = i_X.

Teorema 2.4.: Sia ϕ: X → Y un’applicazione suriettiva, allora esiste un’applicazione ψ: Y → X tale che ϕ ∘ ψ = i_Y.

Teorema 2.5.: Sia ϕ: X → Y un’applicazione, supponiamo che esistano due applicazioni ψ₁: Y → X e ψ₂: Y → X tali che ψ₁ ∘ ϕ = i_X e ϕ ∘ ψ₂ = i_Y allora ψ₁ = ψ₂.

3. Principio di induzione

È spesso utile in alcuni tipi di dimostrazioni fare ricorso al cosiddetto principio di induzione.

Principio di induzione aritmetica: Sia n₀ ∈ Z e sia P(n) un’affermazione sui numeri interi n ≥ n₀. Supponiamo siano soddisfatte le seguenti due condizioni:

• i) P(n₀) è vera.
• ii) Per ogni intero n > n₀, se P(n) è vera per il numero n - 1 allora è vera per il numero n.

Allora è vera per ogni numero intero n ≥ n₀.

Esempi:

3.1. Proviamo che per ogni numero reale q, q ≠ 1 la somma delle sue prime n potenze (n = 0, 1 ...) 1 + q + q² + ... + qⁿ è (qⁿ⁺¹ - 1) / (q - 1). L’affermazione è banalmente vera per n = 0, supponiamola vera per n e proviamola per n + 1, ovvero aggiungiamo ai due membri dell’uguaglianza qⁿ⁺¹, avremo che:

1 + q + q² + ... + qⁿ = (qⁿ⁺¹ - 1) / (q - 1)

da cui la tesi.

3.2. Proviamo che per ogni numero intero n ≥ 2 si ha 1 - 1/2 + 1/3 - ... + 1/n = 1/n. L’affermazione è vera per n = 2, infatti 1 - 1/2 = 1/2, supponiamola vera per n e proviamola per n + 1. Moltiplicando ambo i membri dell’uguaglianza per 1/n si ottiene la tesi.

3.3. Denotiamo 0! = 1, n! = 1 × 2 × ... × n per n > 0. Provare per induzione il Teorema binomiale:

Sia n un qualunque intero ≥ 1, si ha:

(x + y)ⁿ = ∑_r=0ⁿ (n_r) x^n-r y^r

dove (n_r) = n! / (r!(n-r)!). Sarà utile nel seguito la seguente formulazione del Principio di Induzione:

Principio di induzione aritmetica (2): Sia n₀ ∈ Z e sia P(n) un’affermazione sui numeri interi n ≥ n₀. Supponiamo siano soddisfatte le seguenti due condizioni:

• i) P(n₀) è vera.
• ii) Per ogni intero n > n₀, se P(m) è vera per ogni intero m tale che n₀ ≤ m < n, allora è vera per il numero n.

Allora è vera per ogni numero intero n ≥ n₀.

Si può provare che il Principio di induzione è equivalente al Principio del buon ordinamento:

Principio del buon ordinamento: Sia n₀ un intero qualunque. Un qualunque insieme di interi n ≥ n₀ ha un elemento minimo.

4. Relazioni di equivalenza

Sia R una corrispondenza tra un insieme A e se stesso, scriveremo xRy invece di (x, y) ∈ R.

Definizione 4.1.: Una corrispondenza si dice relazione di equivalenza se verifica le seguenti proprietà:

• i) Proprietà riflessiva: ∀x ∈ A, si ha xRx.
• ii) Proprietà simmetrica: ∀x, y ∈ A tali che xRy, si ha yRx.
• iii) Proprietà transitiva: ∀x, y, z ∈ A per cui xRy e yRz, si ha xRz.

Una relazione di equivalenza si indica di solito con ∼ oppure ≡. Se ∼ è una relazione di equivalenza diremo che x è equivalente a y se x ∼ y.

Esempi:

4.1) Sia A un insieme, definiamo x ∼ x' se x = x'. Si ha una relazione di equivalenza detta uguaglianza.

4.2) Sia data in N la relazione m ∼ n se m + n è pari, è una relazione di equivalenza.

4.3) Fissato un intero n > 0, sia data in Z la relazione x ∼ y se x − y è un multiplo intero di n, si verifica che è una relazione di equivalenza.

4.4) Relazione di equivalenza associata ad un’applicazione: sia f: A → B una applicazione, definiamo su A la seguente relazione: x ∼ y se f(x) = f(y). Si verifica facilmente che ∼_f è una relazione di equivalenza che si dice relazione di equivalenza associata a f.

Sia ora ∼ una relazione di equivalenza in un insieme A. Sia a un elemento di A, indichiamo con [a] o a la classe di equivalenza di a modulo ∼ (in particolare a ∼ a). Si osservi che a è anche la classe di equivalenza individuata da un qualsiasi elemento equivalente ad a; inoltre due distinte classi di equivalenza sono sempre disgiunte.

L’insieme di tutte le classi di equivalenza si dice insieme quoziente di A modulo ∼ e si indica con A/∼.

Sia ∼ la relazione di equivalenza definita nell’esempio 4.3, si verifica che x ≡ y se il resto della divisione di x per n è uguale al resto della divisione di y per n. L’insieme Z_n è detto insieme delle classi di resto modulo n e denotato con Z_n. In particolare Z_n = {0, 1, ..., n-1}.

L’applicazione (surgettiva) π: A → A/∼ che associa ad ogni elemento di A la sua classe di equivalenza si dice proiezione canonica.

Osserviamo che l’insieme quoziente A/∼ è una partizione di A, più precisamente la partizione di A nelle classi di equivalenza modulo ∼, cioè ad ogni equivalenza è associata, in modo naturale, la partizione A/∼.

Viceversa, data una partizione di A, si può associare ad una equivalenza in A. Sia {A_i | A_i ⊆ A} una partizione di A. Associamo ad {A_i} la seguente relazione:

• x ∼ y se esiste j tale che x, y ∈ A_j, questa è la relazione di equivalenza associata alla partizione {A_i}.

Una famiglia di sottoinsiemi non vuoti di A si dice partizione di A se i sottoinsiemi sono a due a due disgiunti e se la loro unione è tutto A.

Gli interi

1. Fattorialità in Z

1.1. Algoritmo euclideo

La proprietà fondamentale di Z che useremo per tutto il capitolo è il Teorema di divisione. Dati due interi a > 0 e b ≥ 0 esistono due interi, unicamente determinati q ≥ 0 e r, 0 ≤ r < a, tali che b = qa + r.

Dimostrazione: Per induzione.

Dato un divisore a = 0 dimostreremo che per ogni b ≥ 0 esistono un quoziente q ed un resto r con 0 ≤ r < a tali che b = qa + r. Intanto 0 = a × 0 + 0, quindi, quando b = 0 possiamo porre q = r = 0. Per b > 0 usiamo l’induzione.

Supponiamo che per ogni c, 0 ≤ c < b esistano q_o, r_o con 0 ≤ r_o < a e c = q_oa + r_o. Consideriamo ora b. Se b < a allora b = 0 × a + b, possiamo quindi porre q = 0, r = b.

Se b ≥ a, sia c = b - a. Allora 0 ≤ c < b. Per induzione si ha c = q_oa + r_o per opportuni q_o ed r_o con 0 ≤ r_o < a. Ma allora b = a + c = a + (q_oa + r_o) = a(q_o + 1) + r_o e 0 ≤ r_o < a. Basta allora porre q = q_o + 1, r = r_o.

Per induzione quindi ogni b ≥ 0 può essere scritto come b = qa + r con 0 ≤ r < a.

Per provare l’unicità supponiamo di avere q e r con b = qa + r e 0 ≤ r < a, e supponiamo anche di avere b = q'a + r' e 0 ≤ r' < a con q' e r' eventualmente diversi da q e r. Vogliamo provare che r = r' e q = q'.

Supponiamo r ≠ r' e sottraiamo r' - r da b = aq + r, otterremo a(q - q') + (r - r') = 0, ovvero a(q - q') = r - r', poiché r, r' ≥ 0 ed a > 0 si ha q - q' ≥ 0. Ora |r - r'| < a, quindi a|q - q'| < a pertanto |q - q'| < 1. Essendo q - q' un numero intero necessariamente avremo q - q' = 0, cioè q = q' da cui r - r' = a(q - q') = 0 ovvero r = r'.

Dati due interi a e b, diremo che a divide b se b = aq per qualche intero q e scriveremo a|b se a divide b. Se a e b sono interi, un divisore comune di a e b è un intero e che divide sia a che b. Un numero d è il massimo comune divisore (MCD) di a e b se:

• i) d|a e d|b;
• ii) se e è un divisore comune di a e b allora e divide d.

Infine a e b si dicono coprimi se il loro MCD è 1. Se non c'è ambiguità, il massimo comune divisore di a e b si denota con (a, b).

La soluzione del problema di trovare il massimo comune divisore di due numeri è stata data da Euclide (circa 300 a.C.).

Supponiamo di avere due numeri a e b con b ≤ a. Se b divide a allora b è il massimo comune divisore di a e b. Se b non divide a, sottraendo continuamente il minore dei due numeri dal maggiore, resterà infine un numero che dividerà quello che lo precede, questo numero è il massimo comune divisore di a e b.

Esempio. Consideriamo i numeri 78 e 32. Sottraiamo 32 da 78, otterremo 46 e 32. Sottraendo 32 da 46 si ha 14 e 32. Sottraiamo 14 da 32 e avremo 18 e 14. Sottraendo 14 da 18 abbiamo 4 e 14. Sottraiamo 4 da 14, otteniamo 10 e 4. Sottraiamo 4 da 10, otteniamo 6 e 4. Sottraiamo 4 da 6 e otteniamo 2 e 4. Ora 2 divide 4 quindi 2 è il massimo comune divisore di 78 e 32.

Possiamo descrivere l’algoritmo in forma compatta usando il teorema di divisione:

• 78 = 32 × 2 + 14
• 32 = 14 × 2 + 4
• 14 = 4 × 3 + 2
• 4 = 2 × 2 + 0

È facile vedere che 2 è il massimo comune divisore di 32 e 78, ma possiamo motivare in questo modo: 2 divide 4, quindi divide 4 × 3 + 2 = 14, quindi 14 × 2 + 4 = ...