Esercitazione n.1(28/09/2016)

Argomenti. Operazioni tra insiemi. Leggi di De Morgan. Unioni e intersezioni di

famiglie di insiemi.

Sia U un insieme, detto “insieme universo”, e siano X ed Y due sottoinsiemi diU . L’assioma di separazione della teoria degli insiemi di Zermelo-Fraenkel (ZF)permette di definire un terzo insieme (sottoinsieme di U) come

X \ Y := u ∈ U |u ∈ X e u 6∈ Y .

X \ Y viene detto differenza di X tramite Y .E faciel vedere che per ogni sottoinsieme X di U valgono le seguenti

X \X = ∅, X \∅ = X, ∅ \X = X,

ed in generale per ogni X,Y sottoinsiemi di U si ha che

X \ Y 6= Y \X.

Si indica inoltre col simbolo CX (o Xc, oppure X) il sottoinsieme complementaredi X in U , ovvero il sottoinsieme

U \X = u ∈ U |u 6∈ X .

Proposizione 1 (Leggi di De Morgan)Se X e Y sono due arbitrari sottoinsiemi di U , allora valgono le seguenti leggi

a.1) C(X ∪ Y ) = CX ∩ CY .

a.2) C(X ∩ Y ) = CX ∪ CY .

Piu in generale se A, B e C sono tre insiemi, allora vale quanto segue

b.1) A \ (B ∪ C) = (A \B) ∩ (A \ C).

b.2) A \ (B ∩ C) = (A \B) ∪ (A \ C).

1

Dimostrazione. Si noti che i casi a.1) e a.2) sono situazioni particolari dib.1) e b.2) per la scelta rispettivamente di A := U,B := X e C := Y . Pertantoci limitiamo a provare b.1) e b.2).Una dimostrazione di b.1) si trova sulle dispense del corso. Proviamo qui b.2).Sia x ∈ A \ (B ∩ C), allora x ∈ A e x 6∈ B ∩ C. Quindi

x ∈ A e (x 6∈ B o x 6∈ C),

ovvero x ∈ A

x 6∈ Boppure

x ∈ A

x 6∈ C

ma cio significa proprio che: x ∈ A\B oppure x ∈ A\C, cioe x ∈ (A\B)∪(A\C).Data la genericita con cui e stato scelto l’elemento x in A\ (B∩C), si e provatoche:

A \ (B ∩ C) ⊆ (A \B) ∪ (A \ C).

Viceversa, sia ora x un arbitrario elemento di (A \B) ∪ (A \C), cioe x ∈ A \Boppure x ∈ A \ C. Detto altrimenti

x ∈ A

x 6∈ Boppure

x ∈ A

x 6∈ C

Ne segue che x ∈ A e (x 6∈ B o x 6∈ C). Da x 6∈ B o x 6∈ C segue x 6∈ B ∩ C,pertanto vale che x ∈ A \ (B ∩ C). Data la genericita con cui e stato sceltol’elemento x in (A \B) ∪ (A \ C), si e provato che

(A \B) ∪ (A \ C) ⊆ A \ (B ∩ C),

ovvero la tesi.

Siano ora X ed Y sono due arbitrari sottinsiemi di U . Grazie all’assiomadell’unione la seguente collezione e di nuovo un insieme, detto differenza sim-metrica di X ed Y :

X 4 Y := (X \ Y ) ∪ (Y \X).

Esercizio 1 Se X e Y sono arbitrari sottoinsiemi di U , provare che

X 4 Y = (X ∪ Y ) \ (X ∩ Y ).

Svolgimento. Presentiamo due modi per risolvere l’esercizio.

Primo modo. Sia x un arbitrario elemento di X 4 Y , allora x ∈ X \ Y oppurex ∈ Y \X, cioe

x ∈ X

x 6∈ Yoppure

x ∈ Y

x 6∈ X.

2

Ne segue che x ∈ X ∪ Y

x 6∈ X ∩ Y,

ovvero x ∈ (X ∪ Y ) \ (X ∩ Y ).Viceversa sia ora x ∈ (X ∪ Y ) \ (X ∩ Y ). Allora x ∈ X ∪ Y e x 6∈ X ∩ Y , cioe

x ∈ X

x 6∈ Yoppure

x ∈ Y

x 6∈ X,

detto in altri termini x ∈ (X \ Y ) ∪ (Y \X).

Secondo modo. Per le formule di De Morgan (formula b.2) con X ∪ Y al postodi A, X al posto di B e Y al posto di C abbiamo che

(X ∪ Y ) \ (X ∩ Y ) = ((X ∪ Y ) \X) ∪ ((X ∪ Y ) \ Y ).

Dunque

(X ∪ Y ) \ (X ∩ Y ) = ((X ∪ Y ) \X) ∪ ((X ∪ Y ) \ Y ) = (Y \X) ∪ (X \ Y ) =

= (X \ Y ) ∪ (Y \X) = X 4 Y.

Lasciamo per esercizio provare gli altri punti della seguente

Proposizione 2 Siamo A,B e C tre insiemi. Vale quanto segue

1. A4A = ∅,

2. A4∅ = A,

3. A4B = (A ∪B) \ (A ∩B),

4. A4B = B 4A,

5. (A4B)4 C = A4 (B 4 C),

6. A ∩ (B 4 C) = (A ∩B)4 (A ∩ C),

7. (A4B) ∪ C ⊇ A4 (B ∪ C) e vale “=” se e solo se A ∩ C = ∅.

3

Esercitazione n. 2(30/09/2016)

Argomenti. Esercizi sulle operazioni fra insiemi. Insieme delle parti. Proprietaaqssociativa della differenza simmetrica.

Esercizio 1 Siano A,B e B due insiemi. Provare che

A \B = B \A ⇐⇒ A = B.

Svolgimento. Proviamo prima l’implicazione “⇐= ”.Se A = B allora

A \B = A \A = ∅ = B \B = B \A.

Viceversa proviamo ora l’implicazione “ =⇒ ”. Assumiamo A \ B = B \ A,prendiamo a un generico elemento di A e proviamo che a ∈ B. Per assurdo, sea non appartenesse a B, si avrebbe che a ∈ A \B. Poiche A \B = B \A, alloraa ∈ B \ A ⊆ B, il che e assurdo. Dunque ogni elemento di A appartiene a B,cioe A ⊆ B. Similmente si prova che B ⊆ A.

Esercizio 2 Siano A e B due insiemi. Si mostri che

1. P(A) ∩ P(B) = P(A ∩B).

2. P(A) ∪ P(B) ⊆ P(A ∪B).

Mostrare con un esempio che in 2. l’inclusione puo essere stretta.

Svolgimento.1. Mostriamo l’inclusione “ ⊆ ”. Sia X ∈ P(A) ∩ P(B). Cio significa cheX ∈ P(A) e X ∈ P(B), cioe X e un sottoinsieme di A e pure di B, ovveroX ⊆ A e X ⊆ B, ovvero X ⊆ A ∩B, ovvero X ∈ P(A ∩B).Viceversa mostriamo ora l’inclusione “ ⊇ ”. Sia Y ∈ P(A∩B), cioe Y ⊆ A∩B.Allora Y ⊆ A e Y ⊆ B, ovvero Y ∈ P(A) e Y ∈ P(B), ovvero Y ∈ P(A)∩P(B).

2. Sia Y ∈ P(A) ∪ P(B), allora Y ∈ P(A) oppure Y ∈ P(B), ovvero Y ⊆ Aoppure Y ⊆ B, cioe Y ⊆ A ∪B, ovvero Y ∈ P(A ∪B).

Prendiamo A = 1 e B = 2, allora P(A) = ∅, 1 e P(B) = ∅, 2,quindi

P(A) ∪ P(B) = ∅, 1 , 2 .

1

D’altra parte si ha che

P(A ∪B) = P(1, 2) = ∅, 1 , 2 , 1, 2 6= P(A) ∪ P(B).

Esercizio 3 Siano A,B e C tre insiemi arbitrari. Provare che

(A4B)4C = A4(B4C).

Svolgimento. Sviluppo

(A4B)4C =(

(A4B) \ C)∪(C \ (A4B)

)=

(((A \B) ∪ (B \A)

)\ C)∪(C \

((A ∪B) \ (A ∩B)

)).

Ora applicando i Lemma 1 e 2 (vedi avanti), possiamo scrivere((A \B) ∪ (B \A)

)\ C =

((A \B) \ C

)∪(

(B \A) \ C)

e

C \(

(A ∪B) \ (A ∩B))

=(C \ (A ∪B)

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

)e quindi

(A4B)4C =(

(A \B) \ C)∪(

(B \A) \ C)∪(C \ (A ∪B)

)∪(C ∩A ∩B

).

Per il Lemma 3 sappiamo che

(A \B) \ C = A \ (B ∪ C)

e(B \A) \ C = B \ (A ∪ C).

Sostituendo otteniamo

(A4B)4C =

(A \ (B ∪C)

)∪(B \ (A∪C)

)∪(C \ (A∪B)

)∪(A∩B ∩C

),

che e una formula simmetrica rispetto in A, B e C: nel senso che comunquepermutiamo tra di loro questi tre insiemi la formula non cambia. Concludiamopertanto che

(A4B)4C = (B4C)4A

e per la proprieta commutativa di 4

(A4B)4C = A4(B4C).

Lemmi 1, 2, 3. Siano X,Y e Z tre insiemi arbitrari. Vale quanto segue

2

1. (X ∪ Y ) \ Z = (X \ Z) ∪ (Y \ Z)

2. X \ (Y \ Z) = (X \ Y ) ∪ (X ∩ Y ∩ Z)

3. (X \ Y ) \ Z = X \ (Y ∪ Z).

Dimostrazione. Ci limitiamo a provare 3, lasciando gli altri come esercizio.Provo prima l’inclusione “ ⊆′′, sia a tal fine r un arbitrario elemento di(X \ Y ) \ Z. Allora r ∈ X \ Y e r 6∈ Z, ovvero

r ∈ X \ Yr 6∈ Z

cioe r ∈ X

r 6∈ Y

r 6∈ Z

ne segue che r ∈ X \ (Y ∪ Z), provando cosı l’inclusione

(X \ Y ) \ Z ⊆ X \ (Y ∪ Z).

Viceversa proviamo “ ⊇′′. Prendiamo t arbitrariamente in X \ (Y ∪Z). Ovverot ∈ X e t 6∈ Y ∪ Z, cioe

t ∈ X

r 6∈ Y

r 6∈ Z

ovvero t ∈ X \ Yt 6∈ Z

Detto in altri termini, t ∈ (X \ Y ) \Z, provando cosı anche l’altra inclusione.

3

Esercitazione n. 3(05/10/2016)

Argomenti. Esercizi sulle funzioni iniettive e suriettive.

Esercizio 1 Si provi che l’applicazione

f : Z× Z −→ Z× Z(x, y) 7−→ (2x− y, 4x + 5y)

e iniettiva ma non suriettiva.Si provi che

g : Q×Q −→ Q×Q(x, y) 7−→ (2x− y, 4x + 5y)

e biunivoca.

Svolgimento. Proviamo che f e iniettiva.Siano (x, y) ed (a, b) due elementi di Z× Z tali che

f((x, y)) = f((a, b))

e mostriamo che (x, y) = (a, b). Abbiamo che

f((x, y)) = (2x− y, 4x + 5y) = (2a− b, 4a + 5b) = f((a, b)),

ovvero 2x− y = 2a− b4x + 5y = 4a + 5b

Sottraendo dalla seconda equazione due volte la prima si ottiene

7y = 7b,

da cui y = b che risostituita nella prima da x = y e pertanto (x, y) = (a, b).Mostriamo ora che f non e suriettiva. Osserviamo che se lo fosse, avremmo chepreso un arbitrario elemento (u, v) ∈ Z × Z esiste un (x, y) ∈ Z × Z tale chef((x, y)) = (u, v), ovvero

2x− y = u4x + 5y = v

1

Ricavando la y dalla prima equazione e sostituendola nella seconda si ottieney = 2x− u14x = 5u + v

Ora l’equazione 14x = 5u+v e irrisolvibile in Z se 14 non divide 5u+v. Ne segueche se prendiamo (u, v) in Z × Z tale che 5u + v non e divisibile 14 allora taleelemento non ammette preimmagine tramite f . Ad esempio l’elemento (0, 1) hapreimmagine vuota, quindi (0, 1) 6∈ f(Z× Z) 6= Z× Z.

Esercizio 2 Sia f : A −→ B. Si provi che

1. Per ogni X ⊆ A vale X ⊆ f−1(f(X)).

2. Per ogni Y ⊆ B vale f(f−1(Y )) ⊆ Y .

3. f e iniettiva se e solo se X = f−1(f(X)), ∀X ⊆ A.

4. f e suriettiva se e solo se Y = f(f−1(Y )), ∀Y ⊆ B.

Svolgimento. 1) Sia X un sottoinsieme arbitrario di A, per definizione diretroimmagine e di insieme immagine tramite una funzione, abbiamo che

f−1(f(X)) = a ∈ A| f(a) ∈ f(X) =

= a ∈ A| ∃x ∈ X tale che f(a) = f(x) ,

da cui segue immediatamente che X ⊆ f−1(f(X)).

2) Sia Y un sottoinsieme arbitrario di B, per definizione si ha

f(f−1(Y )) =f(w)|w ∈ f−1(Y )

,

ora w ∈ f−1(Y ) significa proprio che f(w) ∈ Y e quindi f(f−1(Y )) e contenutoin Y .

3) Mostriamo “⇒ ”. Sia f iniettiva; in virtu del punto 1), limitiamoci a provareche per ogni X ⊆ A vale X ⊇ f−1(f(X)). Sia pertanto a ∈ f−1(f(X)), cioea ∈ A e f(a) ∈ f(X). Quindi, per definizione di f(X), esiste un elemento x ∈ Xtale che f(a) = f(x). Ora f iniettiva implica che a = x, quindi a ∈ X, comevolevasi.Mostriamo ora l’altra implicazione. Siano a tal fine a1 e a2 due elementi distintidi A tali che f(a1) = f(a2). Prendiamo X1 := a1 e X2 := a2, allora

f(X1) = f(a1) = f(a2) = f(X2)

quindiX1 = f−1(f(X1)) = f−1(f(X2)) = X2,

cioe a1 = a2.

2

4) “⇒ ”. Sia f suriettiva e proviamo che per ogni Y ⊆ B vale Y ⊆ f(f−1(Y )).Se y ∈ Y , poiche f e suriettiva, esiste a ∈ A tale che y = f(a). Pertanto perdefinizione di f−1(Y ), a ∈ f−1(Y ), quindi y = f(a) ∈ f(f−1(Y )).Viceversa, basta scegliere Y = B, per ipotesi abbiamo che B = f(f−1(B)). Maper definizione f−1(B) = A, quindi B = f(A), ovvero f e suriettiva.

3

Esercitazione n. 4(07/10/2016)

Argomenti. Esercizi sulle funzioni biunivoche e sulla composizione di applicazioni.

Esercizio 1 Siano f e g due applicazioni da N in N, cosı definite per ognin ∈ N

f(n) =

n + 5 se n ≤ 4

n− 5 se n ≥ 5g(n) = n + 5.

Calcolare f g e g f e dire se sono iniettive, suriettive, biettive.Dire se esiste h : N −→ N tale che h f = iN.

Svolgimento. Preso n ∈ N abbiamo che

(f g)(n) = f(n + 5) = n,

essendo n + 5 ≥ 5 per ogni n ∈ N. Dunque

f g = idN

e pertanto e iniettiva e suriettiva, ovvero biettiva.Invece

(g f)(n) = g(f(n)) =

g(n + 5) se n ≤ 4

g(n− 5) se n ≥ 5=

(n + 5) + 5 se n ≤ 4

(n− 5) + 5 se n ≥ 5

ovvero

(g f)(n) =

n + 10 se n ≤ 4

n se n ≥ 5

In particolare g f non e iniettiva, essendo (g f)(0) = 10 = (g f)(10), e0 6= 10. Neppure g f e suriettiva, non essendoci nessuna retroimmagine adesempio per n = 0.

Supponiamo ora che esista una funzione h da N in se tale che h f = iN.Allora poiche f(0) = f(10) = 5, si avrebbe da un lato che

h(5) = h(f(0)) = (h f)(0) = iN(0) = 0,

1

e dall’altro che

h(5) = h(f(10)) = (h f)(10) = iN(10) = 10.

Pertanto una simile applicazione non puo esistere.

Esercizio 2 Sia X un insieme non vuoto ed Y un fissato sottoinsieme di X.Si consideri la seguente applicazione tra i sottoinsiemi di X

f : P(X) −→ P(X)

A 7−→ A4 Y

Si provi che f e biettiva. Descrivere f f .

Svolgimento.Proviamo che f e iniettiva.Siano A1 6= A2 due distinti sottoinsiemi di X, e, ragionando per assurdo,assumiamo che f(A1) = f(A2). Troviamo una contraddizione.Senza perdere in genericita, possiamo supporre A1 6⊆ A2 (altrimenti scambiamoA1 con A2). Sia quindi a ∈ A1 e a 6∈ A2. Si possono presentare due casi: a 6∈ Ye a ∈ Y .Nel primo caso, a ∈ A1 \ Y , quindi a ∈ A1 4 Y . Ma A1 4 Y = A2 4 Y , quindiabbiamo che a ∈ A2 4 Y = (A2 \ Y ) ∪ (Y \ A2) e, poiche a 6∈ Y , a ∈ A2 \ Y edunque a ∈ A2, assurdo.Sia ora a ∈ Y . Poiche a ∈ A1 segue che a 6∈ A1 4 Y = (A1 ∪ Y ) \ (A1 ∩ Y ).Allora a 6∈ A2 4 Y = (A2 ∪ Y ) \ (A2 ∩ Y ). Essendo a ∈ Y , necessariamentea ∈ A2, altrimenti a ∈ (A2 ∪ Y ) \ (A2 ∩ Y ). Quindi a ∈ A2, assurdo.Proviamo che f e suriettiva.Sia B un arbitrario elemento di P(X) e mostriamo che esiste un C ∈ P(X) taleche f(C) = B, ovvero C 4 Y = B. Prendiamo C := B 4 Y e calcoliamo f(C).Abbiamo che

f(C) = f(B 4 Y ) = (B 4 Y )4 Y = B 4 (Y 4 Y ) = B 4∅ = B.

Dal fatto che per ogni B ⊆ X si ha f(B) = B 4 Y e f(B 4 Y ) = B, segue che

(f f)(B) = f(f(B)) = f(B 4 Y ) = B,

e quindi f f = idP(X), la funzione identita su P(X).

2

Esercitazione n. 5(11/10/2016)

Argomenti. Esercizi sulla composizione di applicazioni.

Il prossimo esercizio tratta del comportamento di funzioni iniettive/suriettivesotto la legge di composizione.

Esercizio 1 Siano A, B e C tre insiemi e siano date le seguenti funzioni

f : A −→ B e g : B −→ C.

Si provi quanto segue.

1. Se f e g sono suriettive, allora g f e suriettiva.

2. Se g f e suriettiva, allora g e suriettiva, mentre f puo non esserlo.

3. Se g e suriettiva, allora g f puo non esserlo.

4. Se f e g sono iniettive, allora g f e iniettiva.

5. Se g f e iniettiva, allora f e iniettiva, mentre g puo non esserlo.

6. Se f e iniettiva, allora g f puo non esserlo.

Svolgimento. 1) Preso c ∈ C proviamo che esiste un a ∈ A tale che (gf)(a) =c. Poiche g e suriettiva, esiste un b ∈ B tale che g(b) = c . Poiche f e suriettivaesiste un a ∈ A tale che f(a) = b. Pertanto abbiamo che

(g f)(a) = g(f(a)) = g(b) = c,

ovvero la funzione g f e suriettiva.

2) Sia g f suriettiva e sia c un generico elemento di C. Allora esiste un a ∈ Atale che (g f)(a) = g(f(a)) = c, quindi f(a) e una preimmagine in B tramiteg di c, percio g e suriettiva.Mostriamo con un esempio che f puo non essere suriettiva. Siano A = a,B = b1, b2 e C = c e siano f : a 7−→ b1, g : b1 7−→ c e g : b2 7−→ c. Allorag f : a 7−→ c, pertanto g f e suriettiva su C = c, mentre f non e suriettiva

1

essendo f−1(b2) = ∅.

3) Mostriamo un esempio dove g e suriettiva e g f no. Siano A = a,B = b1, b2 e C = c1, c2 e siano f : a 7−→ b1, g : b1 7−→ c1, g : b2 7−→ c2.Allora g e suriettiva, e (g f)−1(c2) = ∅, dunque g f non e suriettiva.

4) Siano a1 6= a2 in A. Poiche f e iniettiva, allora f(a1) 6= f(a2). Poiche g einiettiva, allora g(f(a1)) 6= g(f(a2)), cioe (g f)(a1) 6= (g f)(a2). Dunque g fe iniettiva.

5) Sia g f iniettiva e siano a1 6= a2 due elementi distinti di A. Ora se fossef(a1) = f(a2), si avrebbe (g f)(a1) = g(f(a1)) = g(f(a2)) = (g f)(a2),contrariamente al fatto che g f e una funzione iniettiva. Quindi f(a1) 6= f(a2)ed f e iniettiva.Mostriamo con un esempio che g puo non essere iniettiva. Siano A = a,B = b1, b2 e C = c e siano f : a 7−→ b1, g : b1 7−→ c e g : b2 7−→ c. Allorag f : a 7−→ c, pertanto g f e banalmente iniettiva, mentre g(b1) = g(b2) none iniettiva.

6) Mostriamo un esempio dove f e iniettiva ed g f no. Siano A = B = C =a1, a2 (a1 6= a2) e siano f la funzione identita (f : a1 7−→ a1, f : a2 7−→ a2) eg la funzione costante in a1 (g : a1 7−→ a1, g : a2 7−→ a1). Allora f e iniettiva,mentre (g f)(a1) = (g f)(a2), dunque g f non e iniettiva.

2

Esercitazione n. 6(14/10/2016)

Argomenti. Esercizi sulla composizione di applicazioni.

Esercizio 1 Sia f un’applicazione f : A −→ B e siano X,Y ⊆ B. Si provi che

1. f−1(X ∪ Y ) = f−1(X) ∪ f−1(Y ).

2. f−1(X ∩ Y ) = f−1(X) ∩ f−1(Y ).

3. f−1(X \ Y ) = f−1(X) \ f−1(Y ).

4. f−1(X4Y ) = f−1(X)4f−1(Y ).

Svolgimento. Proviamo qui solo il punto 1., lasciando gli altri punti comeesercizio.Sia a ∈ f−1(X ∪ Y ) allora, per definizione di retroimmagine si ha che f(a) ∈X ∪ Y. Pertanto f(a) e un elemento di X oppure di Y . Se f(a) ∈ X alloraa ∈ f−1(X), invece se f(a) ∈ Y allora a ∈ f−1(Y ); in ogni caso a ∈ f−1(X) ∪f−1(Y ), dunque, vista la genericita con cui e stato scelto a, abbiamo provatoche f−1(X ∪ Y ) ⊆ f−1(X) ∪ f−1(Y ). Viceversa, poiche X ⊆ X ∪ Y , si ha chef−1(X) ⊆ f−1(X ∪ Y ). Similmente f−1(Y ) ⊆ f−1(X ∪ Y ), dunque f−1(X) ∪f−1(Y ) ⊆ f−1(X ∪ Y ).

Proposizione 1 Siano A e B due insiemi finiti di cardinalita rispettivamenten ed m. Indichiamo un BA l’insieme di tutte le applicazioni da A in B. Allora

la cardinalita di BA e∣∣BA

∣∣ = |B||A| = mn.

Dimostrazione. La dimostrazione e riportata a pagina 49 delle dispensedel corso.

Proposizione 2 Sia A un insieme finito di cardinalita n. Allora l’insieme delleparti di A contiene esattamente 2n elementi, ovvero |P(A)| = 2n.

Dimostrazione.I modo. La dimostrazione “standard” e per induzione su n ed e riportata apagina 48 delle dispense (Proposizione 2.8).II modo. Facciamo uso dell’esercio predecente per fornire una dimostrazione

1

alternativa. Per ogni sottoinsieme B di A indichiamo con χB la funzione carat-teristica di B, ovvero la funzione cosı definita

χB : A −→ 0, 1

a 7−→

1 se a ∈ B0 se a 6∈ B

Consideriamo ora l’applicazione θ definita da P(A) nell’insieme di tutte le fun-zioni da A in 0, 1, che ad ogni sootinsieme B di A associa la sua funzionecaratteristica χB , ovvero

θ : P(A) −→ 0, 1A

B 7−→ χB

Tale applicazione θ e biunivoca. Infatti:θ e iniettiva. Se B e C sono due sottoinsiemi distinti di A allora esiste un ele-mento, diciamo x, che sta in uno e non nell’altro, supponiamo che sia x ∈ B ex 6∈ C. Ma allora χB(x) = 1 e χC(x) = 0, pertanto le funzioni χB e χC sonodiverse, ovvero θ(B) 6= θ(C).

θ e suriettiva. Se f e un qualunque elemento di 0, 1A, postoD := a ∈ A|f(a) = 1si vede immediatamente che f = χD, ovvero f = θ(D).

Essendo θ biunivoca si ha che |P(A)| =∣∣∣0, 1A∣∣∣ = |0, 1||A| = 2n, in virtu

dell’esercizio precedente.

2

Esercitazioni n. 7 e 8(21/10/2016)

Argomenti. Esercizi vari di combinatoria, sull’induzione e sulle rappresentazioni b-

adiche.

Ricordiamo che il coefficiente binomiale n su k e definito come(nk

):=

n!

k!(n− k)!=n(n− 1) . . . (n− k + 1)

k!,

per ogni n ≥ k ≥ 0.Si ricordi che n! = n · (n − 1) · (n − 2) · . . . · 3 · 2 · 1 e che 0! = 1; pertanto per

k = 0 si ha

(n0

)= 1, per ogni n ∈ N.

Esercizio 1 Siano A un insieme finito di n elementi e k un intero 0 ≤ k ≤ n.Indichiamo con Pk(A) l’insieme di tutti i sottoinsiemi di A di cardinalita esat-tamente k, ovvero

Pk(A) := X ∈ P(A)| |X| = k .

Si provi che |Pk(A)| =(nk

).

Dimostrazione. Proviamo l’asserto per induzione su n.Se n = 0, allora necessariamente k = 0, e A = ∅ ha un solo sottoinsiemedi cardinalita 0, A stesso. Quindi |P0(A)| = 1 che giustamente coincide con(

00

)= 1.

Assumiamo ora che l’enunciato valga per n − 1, ovvero che ogni volta che B e

un insieme di n− 1 elementi, vale che |Pk(B)| =(n− 1k

), per ogni k ≤ n− 1.

Il nostro scopo e provare la formula analoga per |A| = n.Se 2 = n il risultato e banale, poiche esiste un unico sottoinsieme di A dicardinalita n, ed e A stesso.Sia k ≤ n − 1 e scegliamo un elemento a ∈ A. Notiamo che i sottoinsiemi diA aventi cardinalita k si dividono in due tipi a seconda che contengano o noncontengano l’elemento a. In particolare

Pk(A) = X t Y,

1

dove il simbolo t indica l’unione disgiunta e

X := R ∈ Pk(A)|a 6∈ R e Y := S ∈ Pk(A)|a ∈ S .

E facile riconoscere che X = Pk(B), dove B = A \ a. Quindi per ipotesiinduttiva

|X | = |Pk(B)| =(n− 1k

).

Inoltre, e altresı facile provare che l’applicazione seguente e una biezione fra Ye Pk−1(B):

f : Y −→ Pk−1(B)

S 7−→ S \ a

Pertanto per ipotesi induttiva vale |Y| = |Pk−1(B)| =(n− 1k − 1

). Ne segue che

|Pk(A)| = |X |+ |Y| =(n− 1k

)+

(n− 1k − 1

).

Infine si noti che(n− 1k

)+

(n− 1k − 1

)=

(n− 1)!

k!(n− 1− k)!+

(n− 1)!

(k − 1)!(n− 1− (k − 1))!

=(n− 1)!

k(k − 1)!(n− k − 1)!+

(n− 1)!

(k − 1)!(n− k)(n− k − 1)!

=(n− 1)!

(k − 1)!(n− k − 1)!

(1

k+

1

n− k

)=

(n− 1)!

(k − 1)!(n− k − 1)!

(n− k + k

k(n− k)

)=

n!

k!(n− k)!=

(nk

).

Esercizio 2 Siano X := 1, 2, 3, 4, 5 ed Y := 1, 2, 3. Rispondere alle seguentidomande.

a) Quanti sono i sottoinsiemi di X che contengono l’elemento 1?

b) Quanti sono i sottoinsiemi A di X che contengono l’elemento 1 e tali cheA ∩ 2, 3 6= ∅?

c) Quante sono le applicazioni iniettive da X in Y ?

d) Quante sono le applicazioni iniettive da Y in X?

e) Quante sono le applicazioni suriettive da X in Y ?

2

Svolgimento.a) Sia Ω l’insieme di tutti i sottoinsiemi di X che contengono l’elemento 1,ovvero

Ω := A ⊆ X|1 ∈ A .

E immediato constatare che Ω e in corrispondenza biunivoca con l’insieme delleparti di X \ 1, mediante l’applicazione seguente

φ : Ω −→ P(X \ 1)A 7−→ A \ 1

Ne segue che |Ω| = |P(X \ 1)| = 2|X\1| = 24 = 16.

b) Indichiamo con Θ il seguente insieme

Θ := A ⊆ X|1 ∈ A e A ∩ 2, 3 6= ∅ .

Osserviamo che Θ e l’unione insiemistica di Λ e ∆, dove

Λ := A ⊆ X|1 ∈ A e 2 ∈ A , ∆ := A ⊆ X|1 ∈ A e 3 ∈ A .

Pertanto Θ = Λ ∪∆. Ragionando come nella parte a), si ha che

|Λ| = |∆| = 23 = 8.

Inoltre Λ ∩∆ := A ⊆ X| 1, 2, 3 ⊆ A, e quindi

|Λ ∩∆| = 22 = 4.

Siamo percio in grado di calcolare con esattezza il numero degli elementi diΘ, tramite la formula P.I.E. (Principio di Inclusione/Esclusione: |A ∪B| =|A|+ |B| − |A ∩B|, vd. pag. 49 delle dispense)

|Θ| = |Λ ∪∆| = |Λ|+ |∆| − |Λ ∩∆| .

Risulta |Θ| = 12.c) Se f e una funzione iniettiva da X in Y , allora |X| = |f(X)|, ma f(X) ⊆ Yed Y contiene solo tre elementi, mentre |f(X)| = 5, quindi una tale funzionenon puo esistere.

d) Il numero di funzioni iniettive da Y in X coincide con il numero di terne dielementi distinti di X. Ora se (x1, x2, x3) ∈ X3 e una terna fatta da coordinatetutte distinte si puo scegliere x1 in esattamente 5 modi, x2 in 5 − 1 = 4 modie x3 in 5− 2 = 3 modi. In conclusione si hanno 5 · 4 · 3 = 60 terne di elementidistinti e quindi 60 funzioni iniettive da Y in X.Si veda anche la Proposizione 2.11 a pagina 50 delle dispense del corso.

e) Indichiamo come sempre con Y X l’insieme di tutte le funzioni da X in Y esia S il sottoinsieme di Y X costituito dalle funzioni suriettive. Inoltre per ogni

3

y ∈ Y , cioe per ogni y ∈ 1, 2, 3, indichiamo con Ay il sottoinsieme di Y X

definito da

Ay :=f ∈ Y X |y 6∈ f(X)

=f ∈ Y X |f−1(y) = ∅

.

Una funzione f e pertanto suriettiva se e solo se non appartiene a nessun Ay,per ogni y = 1, 2, 3, ovvero abbiamo che

S = Y X \ (A1 ∪A2 ∪A3).

Ne segue che|S| =

∣∣Y X∣∣− |A1 ∪A2 ∪A3| .

Sappiamo che∣∣Y X

∣∣ = |Y ||X| = 35. Utilizziamo P.I.E. (vedi oltre) per calcolare|A1 ∪A2 ∪A3|.Osserviamo che per ogni funzione f ∈ A1 vale che f(X) ⊆ 2, 3, pertantoper tali funzioni l’insieme dei valori ammissibili e 2, 3, detto in altri termini

A1 = 2, 3X . Ne segue che il numero di elementi di A1 e dato da 25. Similmente|A2| = |A3| = |A1| = 25. Ora, ci si accorge subito che l’insieme A1∩A2 contienesolo la funzione costante c3 : x 7−→ 3, per ogni x ∈ X, e, similmente A1 ∩A3 =c2, A2 ∩ A3 = c1. In particolare |A1 ∩A2| = |A1 ∩A3| = |A2 ∩A3| = 1.Mentre A1 ∩A2 ∩A3 = ∅. Applicando il principio P.I.E. otteniamo infine che

|A1 ∪A2 ∪A3| = |A1|+ |A2|+ |A3|− |A1 ∩A2| − |A1 ∩A3| − |A2 ∩A3|+ |A1 ∩A2 ∩A3| =3 · 25 + 3 · 1− 0 = 3(25 − 1) = 3 · 31,

ne segue che

|S| =∣∣Y X

∣∣− |A1 ∪A2 ∪A3| = 35 − 3 · 31 = 3(34 − 31) = 3(81− 31) = 150.

A questo punto apriamo una parentesi sul principio di inclusione ed esclu-sione, detto “P.I.E.”

Proposizione 1 (Principio di Inclusione/Esclusione)

Sia X un insieme finito e sia Aiki=1 una famiglia di sottoinsiemi di X. Alloravale quanto segue.

|A1 ∪A2| = |A1|+ |A2| − |A1 ∩A2|

|A1 ∪A2 ∪A3| = |A1|+ |A2|+ |A3|− |A1 ∩A2| − |A1 ∩A3| − |A2 ∩A3|+ |A1 ∩A2 ∩A3| .

4

In generale si ha che∣∣∣∣∣k⋃

i=1

Ai

∣∣∣∣∣ =∑

∅6=J⊆1,2,...,k

(−1)|J|+1

∣∣∣∣∣∣⋂j∈J

Aj

∣∣∣∣∣∣ .Esercizio 3 Trovare e dimostrare la formula generale per il numero delle fun-zioni suriettive tra due insiemi finiti di cardinalita rispettivamente n ed m(n ≥ m).

Esercizio 4 Scrivere il numero 2579 nelle basi: 2, 7, 9 e 12.

Svolgimento.b = 2. La massima potenza di 2 che e minore o uguale a 2579 e 211 = 2048, erisulta

2579 = 1 · 211 + 531.

Ora vado a cercare la massima potenza di 2 minore o uguale a 531. E 29 = 512,e risulta

531 = 1 · 29 + 19.

Ripeto il ragionamento per 19, ottengo 24 = 16 e

19 = 1 · 24 + 3.

Infine per 3,3 = 1 · 21 + 1.

Pertanto

2579 = 1·211+0·210+1·29+0·28+0·27+0·26+0·25+1·24+0·23+0·22+1·21+1·20

e la scrittura in base 2 e101000010011.

b = 7. Ragiono come sopra e vedo che 74 = 2401 e la massima potenza di 7minore o uguale a 2579 (infatti 75 > 2579). Si ha

2579 = 1 · 74 + 178.

Ora 178 e divisibile con resto per 72 (e non per 73 = 343 > 178), essendo

178 = 3 · 72 + 31.

Infine31 = 4 · 7 + 3.

Quindi2579 = 1 · 74 + 0 · 73 + 3 · 72 + 4 · 71 + 3 · 70,

5

cioe in base 7 il nostro numero si scrive nel seguente modo

10343.

b = 9. Si verifichi che la scrittura corretta e: 3475.b = 12. Poiche 12 > 10 c’e bisogno di aggiungere due simboli per rappresentare inumeri 10 e 11. Siano questi rispettivamente A e B. Pertanto le cifre del nostroalfabeto numerico sono

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,B.

Si provi che

2579 = 1728 + 5 · 144 + 120 + 11 =

= 1 · 123 + 5 · 122 + 10 · 121 + 11 · 120,

dunque la scrittura in base 12 e: 15AB.

6

Esercitazione n. 9(25/10/2016)

Argomenti. Esercizi sulle rappresentazioni b-adiche e sui numeri primi.

Esercizio 1 Sia n un intero naturale. Si provi che n, n + 2 e n + 4 sono tuttinumeri primi se e solo se n = 3.

Svolgimento. Se n = 3 i tre numeri sono: 3, 5 e 7, pertanto si tratta di trenumeri primi.Viceversa assumiamo che n, n + 2 ed n + 4 siano tutti primi. Allora n non e2, altrimenti avremmo che n + 2 = 4, che non e primo. Pertanto n e un primodispari. Se n non e 3, dividendo n per 3, si avra n = 3q + r con q ≥ 1 e restor = 1 oppure r = 2. Se r = 1, allora n+ 2 = 3q + 1 + 2 = 3q + 3 = 3(q + 1) ed edivisibile per 3, quindi non puo essere primo. Assurdo. Quindi si ha che r = 2;ma allora n + 4 = 3q + 2 + 4 = 3q + 6 = 3(q + 2) e divisibile propriamente per3, pertanto non e primo. Assurdo. Ne consegue che n = 3.

Esercizio 2 Determinare per quali basi b, 2 ≤ b ≤ 10 il numero 1785 ammetteuna rappresentazione palindroma (ovvero della forma: abcde . . . edcba).

Svolgimento.Supponiamo che il nostro numero 1785 ammetta la seguente scrittura in base b

1785 = ak · bk + ak−1 · bk−1 + . . . + a1 · b1 + a0 · b0,

affinche tale scrittura sia palindroma una condizione necessaria e che

ak = a0,

ovvero il resto della divisione di 1785 per b, cioe a0, deve essere uguale al primocoefficiente della scrittura. In particolare, a0 non deve essere nullo! In questomodo si scartano subito le basi b che dividono 1785, ovvero: b = 3, b = 5 e b = 7(1785 = 32 · 52 · 7).Ora se b = 6, la massima potenza di 6 non superiore a 1785 e 64 = 1296 che econtenuta una sola volta in 1785, dunque la scrittura in base 6 parte con a4 = 1,mentre il resto della divisione per 6 e a0 = 3 (1785 = 297 · 6 + 3). Quindi perb = 6 la scrittura non e palindroma.Similmente per b = 8, si ha ak = a3 = 3 e a0 = 1 (83 = 512, 1785 = 223 · 8 + 1).E per b = 9, ak = a3 = 2, a0 = 3.Nella seguente tabella sono riportate tutte le diverse scritture. Solo per b = 4si ha una scrittura palindroma

1

b=2 11011111001b=3 2110010b=4 123321b=5 24120b=6 12133b=7 5130b=8 3371b=9 2403b=10 1785

Esercizio 3 1. Provare che per ogni intero n ≥ 3, esiste un b < n tale chela rappresentazione b−adica di n e palindroma.

2. Mostrare che non esiste b tale che la rappresentazione b−adica del numero39 e palindroma e composta da almeno tre cifre.

Svolgimento.1. Dato n, scelgo b = n − 1 allora n = 1 · b1 + 1 · b0, cioe il numero n si scrivecome 11 in base n− 1, e quindi in modo palindromo.2. Poiche si chiedono almeno tre cifre e poiche 72 = 49 > 39, le sole basi daprendere in considerazione sono: 2, 3, 4, 5 e 6.Rispetto tali basi le scritture sono

b=2 100111b=3 1110b=4 213b=5 124b=6 103

e quindi non esiste nessuna scrittura palindroma.

2

Esercitazione n. 10(28/10/2016)

Argomenti. Esercizi sui numeri primi, sul principio di induzione e sul MCD.

Esercizio 1 Provare che(3n2n

)≥ 4n, per ogni n ≥ 3.

Svolgimento. Facciamo induzione su n.Se n = 3, abbiamo (

9

6

)=

9 · 8 · 73 · 2 · 1

= 84 > 64 = 43,

vero.Sia n ≥ 3, assumiamo il risultato vero per n e dimostriamolo per n + 1.(

3(n + 1)

2(n + 1)

)=

(3n + 3

2n + 2

)=

(3n + 3)!

(2n + 2)!(n + 1)!

=(3n + 3)(3n + 2)(3n + 1)(3n)!

(2n + 2)(2n + 1)(2n)!(n + 1)n!

=

(3n

2n

)· 3

2· (3n + 2)(3n + 1)

(2n + 1)(n + 1)

≥ 4n · 3

2· (3n + 2)(3n + 1)

(2n + 1)(n + 1)

dove nell’ultimo passaggio abbiamo utilizzato l’ipotesi induttiva(3n2n

)≥ 4n. La

tesi risulta pertanto provata una volta che dimostriamo che vale

3

2· (3n + 2)(3n + 1)

(2n + 1)(n + 1)≥ 4

per ogni n ≥ 3. Cio equivale a provare che

3(3n + 2)(3n + 1) ≥ 8(2n + 1)(n + 1),

ovvero, facendo i dovuti passaggi, che

11n2 + 3n− 2 ≥ 0,

la qual cosa e certamente vera per ogni n ≥ 3.

1

Esercizio 2 Siano a, b, c ∈ Z \ 0 tali che c|a e c|b. Provare che(a

c,b

c

)=

(a, b)

c.

In particolare si osservi che se d = (a, b), allora (ad ,

bd ) = 1.

Svolgimento.

Lasciamo il lettore riflettere su questi due esercizi particolarmente significa-tivi, le cui dimostrazioni non sono banali.

Esercizio 3 Siano X ed Y due insiemi finiti di cardinalita rispettivamente ned m. Determinare il numero di funzioni suriettive da X in Y .

Esercizio 4 Siano a1, a2, . . . , an numeri reali non-negativi. Dimostrare che

n√a1 · a2 · . . . · an ≤

a1 + a1 + . . . + ann

.

2

Esercitazione n. 11(2/11/2016)

Argomenti. Esercizi sul calcolo del MCD e del mcm.

Esercizio 1 Calcolare (3696, 1530) utilizzando l’algoritmo euclideo e determinarei combinatori α, β ∈ Z tali che

(3696, 1530) = 3696 · α+ 1530 · β.

Svolgimento. Procediamo con l’algoritmo di Euclide calcolando le divisionisuccessive.

3696 = 1530 · 2 + 636

1530 = 636 · 2 + 258

636 = 258 · 2 + 120

258 = 120 · 2 + 18

120 = 18 · 6 + 12

18 = 12 · 1 + 6

12 = 6 · 2 + 0

Ne segue che l’ultimo resto non nullo, ovvero 6 e un MCD tra 3696 e 1530,ovvero (3696, 130) = 6.Per determinare i combinatori α e β occorre scrivere i resti delle divisioni suc-cessive come combinazione lineare di a = 3696 e b = 1530. Abbiamo che

636 = 3696− 2(1530) = a− 2b

258 = 1530− 2(636) = b− 2(a− 2b) = −2a+ 5b

120 = 636− 2(258) = (a− 2b)− 2(−2a+ 5b) = 5a− 12b

18 = 258− 2(120) = −2a+ 5b− 2(5a− 12b) = −12a+ 29b

12 = 120− 6(18) = 5a− 12b− 6(−12a+ 29b) = 77a− 186b

6 = 18− 12 = −12a+ 29b− (77a− 186b) = −89a+ 215b.

Pertanto α = −89 e β = 215.

Esercizio 2 Provare che (2n− 1, 1− n) ∈ 1, 3, per ogni n ∈ N.

1

Svolgimento. Utilizzo le proprieta del MCD, in particolare (a, b) = (a,−b) ese a = bc+ d (a, b) = (d, b). Abbiamo che

(2n+ 1, 1− n) = (2n+ 1, n− 1) = (2(n− 1) + 3, n− 1) = (3, n− 1),

essendo 3 un numero primo allora (3, n − 1), dovendo dividere 3, puo essere o1 o 3 (oppure −1, −3). Tutti i casi sono possibili, infatti per n = 5 abbiamo(11,−4) = 1, mentre per n = 4 abbiamo (9,−3) = 3.

Esercizio 3 Siano a, b due numeri naturali positivi. Provare che

[a, b] =a · b(a, b)

.

Svolgimento. Sia m = a·b(a,b) . Poiche (a, b)|a esiste u ∈ Z tale che a = (a, b)u

e quindi m = (a,b)·u·b(a,b) = ub, ovvero b|m. Ragionando in modo simile da (a, b)|b

segue che a|m.Sia adesso t un multiplo comune di a e b e mostriamo che m divide t. Poichea|t e b|t esistono c, d ∈ Z tali che

t = ac = bd.

Inoltre per definizione di MCD esistono e, f ∈ Z tali che

(a, b) = aα+ bβ.

Allora abbiamo che

(a, b) · t = aαt+ bβt = αabd+ βbac

= ab(dα+ cβ),

da cui segue che

t =a · b(a, b)

· (dα+ cβ) = m · (dα+ cβ),

cioe m|t, e quindi per definizione m = [a, b].

Esercizio 4 Siano a, b, c, d ∈ N. Se a = cd e (b, c) = 1, allora (a, b) = (d, b).

Svolgimento. Siano x = (a, b) ed y = (d, b), mostriamo che x = ±y provandoche y|x e x|y.Dal fatto che y e massimo comun divisore fra d e b, abbiamo in particolare chey divide sia d che b. Inoltre per ipotesi d divide a, pertanto anche y dividea. Dalla definizione di massimo comun divisore segue in particolare che ognielemento che divide sia a che b, divide anche x = (a, b), quindi abbiamo provatoche y|x.

2

Viceversa, ragionando come sopra, per provare che x|y, occorre e basta verificareche x|d. Ora essendo (c, b) = 1 si ha che esistono degli opportuni interi α e βper cui

1 = αc+ βb.

Moltiplicando per d, abbiamo

d = αcd+ βbd = αa+ (βd)b,

e poiche x divide sia a che b, segue che x divide anche d, da cui la tesi: x|d ex|b implica x|(d, b) = y.

3

Esercitazione n. 15(23/11/2016)

Argomenti. Relazioni d’ordine e di equivalenza.

Esercizio 1 Sia S = N× N e si definisca su S la seguente relazione

(a, b)σ(c, d) se e solo se ab = cd

per ogni (a, b) e (c, d) elementi di S. Si provi che

1. σ e di equivalenza su S.

2. Esiste un’unica classe d’equivalenza di σ che contiene infiniti elementi.

3. Per ogni intero positivo n, esistono infinite classi d’equivalenza di σ con-tenenti n elementi.

Svolgimento.1. Proviamo che σ e riflessiva, simmetrica e transitiva.σ e riflessiva. Preso un arbitrario elemento (a, b) di S e banale che (a, b)σ(a, b).σ e simmetrica. Se (a, b) e (c, d) sono due arbitrari elementi di S tali che(a, b)σ(c, d) allora ab = cd, ovvero cd = ab, cioe (c, d)σ(a, b).σ e transitiva. Siano (a, b), (c, d) ed (e, f) tre elementi di S tali che (a, b)σ(c, d)e (c, d)σ(e, f); allora ab = cd e cd = ef , da cui segue che ab = ef , ovvero(a, b)σ(e, f).2. Consideriamo la classe contenente l’elemento (0, 0). Per definizione di classed’equivalenza abbiamo che

[(0, 0)]σ = (a, b) ∈ S| (a, b)σ(0, 0)= (a, b) ∈ S| ab = 0= (a, b) ∈ S| a = 0, oppure b = 0= (a, 0)| a ∈ N ∪ (0, b)| b ∈ N ,

Quindi [(0, 0)]σ contiene infiniti elementi.Mostriamo ora che ogni altra σ-classe contiene un numero finito di elementi. Sia[(a, b)]σ una classe d’equivalenza diversa dalla classe [(0, 0)]σ, allora le due classisono disgiunte e pertanto ab e un intero diverso da zero, che possiamo chiamarem. Ora gli elementi di [(a, b)]σ sono esattamente

[(a, b)]σ = (c, d) ∈ S|cd = m ,

1

pertanto gli interi c e d sono entrambi divisori di m. Poiche i divisori di m sonoin numero finito, c’e solo un numero finito di scelte possibili per c e d, e quindianche per la coppia (c, d) ∈ [(a, b)]σ.3. Prendiamo p un qualunque numero primo e consideriamo la classe contenentel’elemento (1, pn−1). Si ha che

[(1, pn−1)]σ =

(a, b) ∈ S| ab = pn−1

=

(pi, pj) ∈ S| pi+j = pn−1,

essendo p un numero primo, i divisori di pn−1 sono solamente gli interi pk, conk = 0, 1, 2, . . . , n− 1. Allora

[(1, pn−1)]σ =

(pi, pn−1−i) ∈ S|i = 0, 1, 2, . . . , n− 1,

che pertanto contiene n elementi. Ovviamente se p e q sono due primi distinti leclassi [(1, pn−1)]σ e [(1, qn−1)]σ sono elementi distinti dell’insieme quoziente S/σ.Essendoci infiniti numeri primi, pj , ci sono infinite classi [(1, pn−1j )]σ, ciacunadi cardinalita n.

Esercizio 2 (3.46 delle dispense) Sia X un insieme finito ed Y un fissatosottoinsieme di X. Sull’insieme P(X) definiamo la relazione ρ ponendo, perogni S, T ∈ mathcalP (X)

SρT ⇐⇒ S \ Y = T \ Y.

1. Si provi che ρ e una relazione d’equivalenza.

2. Per ogni S ∈ P(X), si descriva la classe di equivalenza [S]ρ e si determini|[S]ρ|.

3. Si calcoli∣∣∣P(X)

ρ

∣∣∣ .Svolgimento.1. E banale osservare che ρ e riflessiva e simmetrica. Limitiamoci a provareche ρ e transitiva. A tal fine siano R,S e T tre arbitrari elementi di P(X) eassumiamo che valgano RρS ed SρT . Allora si ha R\Y = S\Y ed S\Y = T \Y ,pertanto anche

R \ Y = T \ Y,

ovvero per definizione RρT .

2. Sia S ∈ P(X) e ricordiamo che

[S]ρ = T ∈ P(X)|TρS= T ∈ P(X)|T \ Y = S \ Y .

Ora scritto il generico sottoinsieme T di X come T = (T \Y )∪(T ∩Y ), abbiamoche T appartiene ad [S]ρ, precisamente quando T \ Y = S \ Y . Pertanto gli

2

elementi di [S]ρ sono esattamente i sottoinsiemi di X della forma T = (S \Y )∪(T ∩ Y ), ovvero

[S]ρ = T ∈ P(X)|T = (S \ Y ) ∪ (T ∩ Y ) .

Ora, due elementi T1 e T2 di questo insieme sono distinti se e solo se T1 ∩ Y 6=T2 ∩ Y . Pertanto il numero di elementi distinti di [S]ρ e

|[S]ρ| = |P(Y )| = 2|Y |.

3. Dal punto 2. segue che ogni classe [S]ρ puo essere rappresentata dall’elementoS \ Y , cioe [S]ρ = [S \ Y ]ρ. Allora un sistema di rappresentanti per le classid’equivalenza di ρ su P(X) e dato da

τ := T |T ⊆ X \ Y = P(X \ Y ).

Ne segue che ∣∣∣∣P(X)

ρ

∣∣∣∣ = |τ | = |P(X \ Y )| = 2|X|−|Y |.

Esercizio 3 Siano A e B due insiemi entrambi non vuoti e sia |B| ≥ 2. Siaf : A −→ B una funzione da A in B. Posto Ω := P(B) \ ∅, B sia ρ unarelazione su Ω cosı definita

X,Y ∈ Ω, XρY se e solo se f−1(X) ∪ f−1(Y ) 6= A.

Provare quanto segue

1. ρ e riflessiva se e solo se f e suriettiva.

2. Se |f(A)| ≥ 3 allora ρ non e transitiva.

Svolgimento.1) Assumiamo ρ riflessiva e proviamo che f e suriettiva.Sia b un arbitrario elemento di B. Prendiamo X := B \ b e osserviamo cheX ∈ Ω, infatti X 6= B e ovvio, e X 6= ∅, poiche per ipotesi B contiene almenodue elementi. Essendo ρ una relazione riflessiva, vale in particolare che XρX, equindi f−1(X) ∪ f−1(X) = f−1(X) 6= A, cioe

f−1(B \ b) 6= A,

ne segue che esiste un a ∈ A \(f−1(B \ b)

), ovvero esiste a ∈ A tale che

f(a) 6∈ B \ b, cioe f(a) = b, che e quanto volevamo provare.Assumiamo ora che f e suriettiva e proviamo che ρ e riflessiva.Sia Y arbitrario in Ω, allora Y 6= ∅ e Y 6= B. In particolare, preso un b ∈ B \Y ,poiche f e suriettiva esiste un a ∈ A tale che f(a) = b, quindi a ∈ A \ f−1(Y ),

3

ne segue che f−1(Y ) 6= A, ovvero per definizione Y ρY .

2) Siano bi = f(ai), per i = 1, 2, 3, tre elementi distinti di f(A). PrendiamoX := B \ b1, b2, Y := B \ b2, b3 e Z := B \ b3. Allora e facile vedere cheX,Y, Z ∈ Ω, inoltre

f−1(X)∪ f−1(Y ) = f−1(B \ b1, b2)∪ f−1(B \ b2, b3) = f−1(B \ b2) 6= A,

poiche a2 ∈ A \(f−1(B \ b2)

), e quindi vale XρY . Similmente abbiamo che

f−1(Y ) ∪ f−1(Z) = f−1(B \ b2, b3) ∪ f−1(B \ b3) = f−1(B \ b3) 6= A,

poiche a3 ∈ A \(f−1(B \ b3)

), e quindi vale Y ρZ. Ma.

f−1(X) ∪ f−1(Z) = f−1(B \ b1, b2) ∪ f−1(B \ b3) = A,

cioe NON vale XρZ, dunque ρ non e transitiva.

4

Esercitazione n. 16(25/11/2016)

Argomenti. Relazioni d’ordine e di equivalenza.

Esercizio 1 Consideriamo l’insieme N dotato della relazione d’ordine parziale“|′′ di divisione:

a b⇐⇒ a divide b.

Determinare rispettivamente maggioranti/minoranti, sup/inf, elementi massi-mali/minimali ed eventuali massimo/minimo dei seguenti sottoinsiemi dell’insiemeparzialmente ordinato (N, |),

T1 := 3, 5, 6, 15 , T2 := 2, 4, 6, 8 ,

T3 := 2n, 3m, 6|n,m ∈ N∗ , T4 := 2, 3, 4, 7, 8, 9, 10, 20, 50 .

Rappresentare graficamente ogni Ti.

Svolgimento.Caso T1.Maggioranti: multipli di 30,minoranti: 1,sup(T1) = 30, mentre inf(T1) = 1.Massimali di T1: 6, 15,minimali di T1: 3, 5,non esiste massimo, ne minimo.

Caso T2.Maggioranti: multipli di 24,minoranti: 1, 2,sup(T2) = 24, mentre inf(T2) = 2.Massimali di T2: 6, 8,minimali di T2: 2,non esiste massimo, mentre T2 ha minimo = 2.

Caso T3.Per T3 l’insieme dei maggioranti e vuoto, in quanto non esiste nessun numero

1

naturale m che e divibile da ogni potenza di 2.Minoranti: 1,6 ∃ sup(T3), mentre inf(T3) = 1.Massimali di T3: 3 (unico elemento massimale).minimali di T3: 2, 3.Non esiste minimo, ne massimo poiche l’unico massimale, 3, non e divisibile perle potenze di 2.

Caso T4.Maggioranti: multipli di 6300,minoranti: 1,sup(T4) = 6300, mentre inf(T4) = 1.Massimali di T4: 7, 8, 9, 20, 50,minimali di T4: 2, 3, 7,non esiste massimo, ne minimo.

Esercizio 2 Siano A e B due insiemi entrambi non vuoti e sia |B| ≥ 2. Siaf : A −→ B una funzione da A in B. Posto Ω := P(B) \ ∅, B sia ρ unarelazione su Ω cosı definita

X,Y ∈ Ω, XρY se e solo se f−1(X) ∪ f−1(Y ) 6= A.

Provare quanto segue

1. ρ e riflessiva se e solo se f e suriettiva.

2. Se |f(A)| ≥ 3 allora ρ non e transitiva.

Svolgimento.1) Assumiamo ρ riflessiva e proviamo che f e suriettiva.Sia b un arbitrario elemento di B. Prendiamo X := B \ b e osserviamo cheX ∈ Ω, infatti X 6= B e ovvio, e X 6= ∅, poiche per ipotesi B contiene almenodue elementi. Essendo ρ una relazione riflessiva, vale in particolare che XρX, equindi f−1(X) ∪ f−1(X) = f−1(X) 6= A, cioe

f−1(B \ b) 6= A,

ne segue che esiste un a ∈ A \(f−1(B \ b)

), ovvero esiste a ∈ A tale che

f(a) 6∈ B \ b, cioe f(a) = b, che e quanto volevamo provare.Assumiamo ora che f e suriettiva e proviamo che ρ e riflessiva.Sia Y arbitrario in Ω, allora Y 6= ∅ e Y 6= B. In particolare, preso un b ∈ B \Y ,poiche f e suriettiva esiste un a ∈ A tale che f(a) = b, quindi a ∈ A \ f−1(Y ),ne segue che f−1(Y ) 6= A, ovvero per definizione Y ρY .

2) Siano bi = f(ai), per i = 1, 2, 3, tre elementi distinti di f(A). PrendiamoX := B \ b1, b2, Y := B \ b2, b3 e Z := B \ b3. Allora e facile vedere cheX,Y, Z ∈ Ω, inoltre

f−1(X)∪ f−1(Y ) = f−1(B \ b1, b2)∪ f−1(B \ b2, b3) = f−1(B \ b2) 6= A,

2

poiche a2 ∈ A \(f−1(B \ b2)

), e quindi vale XρY . Similmente abbiamo che

f−1(Y ) ∪ f−1(Z) = f−1(B \ b2, b3) ∪ f−1(B \ b3) = f−1(B \ b3) 6= A,

poiche a3 ∈ A \(f−1(B \ b3)

), e quindi vale Y ρZ. Ma.

f−1(X) ∪ f−1(Z) = f−1(B \ b1, b2) ∪ f−1(B \ b3) = A,

cioe NON vale XρZ, dunque ρ non e transitiva.

Esercizio 3 Sull’insieme N × N si definisca la relazione E ponendo, per ogni(a, b), (c, d)N ∈ N× N,

(a, b) E (c, d) se a 6= c, a|c oppure a = c, b ≤ d.

1. Si provi che E e una relazione d’ordine su N× N.

2. Si trovino, se esistono, massimo, minimo, elementi minimali ed elementimassimali di (N× N,E).

Svolgimento. 1) Tralascio la verifica che tale relazione e d’ordine. L’ordine none totale poiche ad esempio i due elementi (2, 0) e (3, 0) non sono confrontabilitra di loro.

2) Non esistono elementi massimali (e pertanto non esiste massimo), poicheper ogni (a, b) ∈ A abbiamo che (a, b) C (a, b+ 1).Sia ora (c, d) un elemento minimale. Allora d = 0 altrimenti (c, d− 1) C (c, d).Ora se fosse a 6= 1 si avrebbe che (1, 0) C (c, 0) che contraddice la minimalitadi (c, 0), quindi l’unico possibile elemento minimale e (1, 0). Proviamo che essoe effettivamente minimale, anzi e il minimo dell’insieme ordinato (A,E). Presoun generico (a, b) ∈ A abbiamo che se a 6= 1, allora 1|a e quindi (1, 0) E (a, b).Se invece a = 1 allora 0 ≤ b e quindi ancora (1, 0) E (a, b), dunque abbiamoprovato che (1, 0) E (a, b) per ogni (a, b) ∈ A.

3

Esercitazione n. 17(02/12/2016)

Argomenti. Esercizi sulle congruenze.

Ricordiamo il Teorema dimostrato a lezione.

Teorema 1 (Teorema 4.6 delle dispense) Sia n ≥ 1 e siano a, b, c, d ∈ Ztali che

a ≡ b (modn)

c ≡ d (modn)

Allora a + c ≡ b + d (modn) e ac ≡ bd (modn).

Esercizio 1 (criterio di divisibilita per 3) Si provi nell’ordine quanto segue.

1. Per ogni n ∈ N si ha 10n ≡ 1 (mod 9).

2. Ogni intero n ∈ N modulo 9 e congruo alla somma delle cifre della suarappresentazione decimale.

3. Un intero n e divisibile per 3 se e solo se la somma delle sue cifre decimalie divisibile per 3.

Svolgimento. 1. Dimostriamolo per induzione su n.Se n = 0, allora 100 = 1 ≡ 1 (mod 9), ok!Sia vero per n e proviamolo per n + 1. Allora

10n+1 = 10n · 10 ≡ 1 · 10 ≡ 1 · 1 ≡ 1 (mod 9).

2. Scritto n in forma decimale

n = am10m + am−110m−1 + . . . + a110 + a0

e utilizzando il punto precedente [10t ≡ 1 (mod 9) per ogni t ] abbiamo che

n ≡ am · 1 + am−1 · 1 + . . . a1 · 1 + a0 ≡m∑i=0

ai (mod 9).

3. Sia ora n un arbitrario numero intero e sia

n = am10m + am−110m−1 + . . . + a110 + a0

1

la sua rappresentazione in base 10. Mostriamo quanto segue

3 |n⇐⇒ 3∣∣∣ m∑

i=0

ai,

ovvero

n ≡ 0 (mod 3) ⇐⇒m∑i=0

ai ≡ 0 (mod 3). (1)

Per il punto precedente, modulo 9, n e congruo a∑m

i=0 ai, ovvero

9

∣∣∣∣n− m∑i=0

ai

Ma allora, per la transitivita della relazione di divisione, anche

3

∣∣∣∣n− m∑i=0

ai,

ovvero

n ≡m∑i=0

ai (mod 3).

Ne segue che (1) e presto dimostrata.

Esercizio 2 (criterio di divisibilita per 11) Un intero positivo n e divisi-bile per 11 se e solo se la somma delle cifre decimali di posto pari di n e congruamodulo 11 alla somma delle cifre decimali di posto dispari.

Svolgimento. Si vedano le dispense del corso.

Esercizio 3 Provare che per ogni numero naturale n ≥ 1 esiste un numero diFibonacci uk divisibile per n.

Svolgimento. Ricordiamo che la successione di Fibonacci e definita dalla ri-correnza

u0 = 1

u1 = 1

uk+1 = uk + uk−1 per ogni k ≥ 1.

Sia assegnato n ≥ 1, e consideriamo l’insieme T = Z/nZ × Z/nZ. Allora Tcontiene esattamente n2 < ∞ elementi. Per ogni numero intero a indichiamocon a la sua classe dei resti modulo n, ovvero, dato a ∈ Z sia

a := a + nZ ∈ ZnZ

.

2

Ora per ogni indice i ≥ 0, gli elementi (ui, ui+1) ∈ T . Poiche si tratta di infinitielementi che si collocano in un numero finito, n2, di posti, per il Principio deicassetti, esistono un i ≥ 0 e un j > 0 tali che

(ui, ui+1) = (ui+j , ui+j+1). (?)

Indichiamo con l il piu piccolo intero naturale per cui un’occorrenza del tipo (?)si verifica. Proviamo che l = 0. Se fosse per assurdo l > 0, allora l − 1 ≥ 0 e siavrebbe che

ul−1 = ul+1 − ul e ul+j−1 = ul+j+1 − ul+j .

Da cui segue che

ul−1 = ul+1 − ui = ul+1 − ul =

= ul+j+1 − ul+j = ul+j+1 − ul+j =

= ul+j−1,

e dunque(ul−1, ul) = (ul−1+j , ul+j),

ovvero l’occorrenza (?) si verifica anche per l− 1, al posto di l. La nostra sceltaminimale di l fa sı che cio sia un assurdo, e quindi necessariamente abbiamoche l = 0. Questo significa che esiste un opportuno j > 0 per cui

(uj , uj+1) = (u0, u1) = (1, 1).

Ma allora abbiamo che

uj−1 = uj+1 − uj = 1− 1 = 0,

cioe uj−1 ≡ 0 (modn), i.e. n divide il numero di Fibonacci uj−1.

3

Esercitazioni n. 18 e 19(05/12/2016)

Argomenti. Esercizi sulle congruenze.

Esercizio 1 Stabilire la classe di congruenza modulo 7 di

a = 31(118 − 167) + 912 − 135.

Svolgimento. Poiche 31 ≡ 3 (mod 7), 167 ≡ 6 ≡ −1 (mod 7) e 135 ≡ 2 (mod7), abbiamo che

a ≡ 3(118 + 1) + 912 − 2 (mod 7).

Essendo 11 e 9 coprimi con 7 possiamo applicare il piccolo Teorema di Fermat,ottenendo che

118 = 116+2 = 116 · 112 ≡ 1 · 121 ≡ 2 (mod 7)

912 = 92·6 = (96)2 ≡ 1 (mod 7).

Pertanto si ha che

a ≡ 3(2 + 1) + 1− 2 ≡ 8 ≡ 1 (mod 7).

Esercizio 2 Determinare la classe di congruenza di

m = 5912787 + 211 (mod 13).

Svolgimento. Si ha che 59 ≡ 7 (mod 13). Inoltre poiche 13 e un numero primoogni intero a, non divisibile per 13, e tale che a12 ≡ 1 (mod 13) (per il PiccoloTeorema di Fermat). Pertanto abbiamo che

5912787 ≡ 71065·12+7 ≡ (712)1065 · 77

≡ 11065 · 77 ≡ 77 = (72)3 · 7≡ 493 · 7 ≡ 103 · 7≡ 7000 ≡ 6 (mod 13).

1

Inoltre

211 ≡ (25)2 · 2 ≡ 322 · 2≡ 62 · 2 ≡ 10 · 2≡ 20 ≡ 7 (mod 13).

Pertanto la congruenza di m e 6 + 7 = 0.

Esercizio 3 Determinare le soluzioni della congruenza 3x ≡ 5 (mod 8).

Svolgimento. Sappiamo che la congruenza ammette soluzioni intere poiche(3, 8) = 1 divide 5. Per determinarne una scrivo (3, 8) come combinazionelineare di 3 ed 8: si ha che

(3, 8) = 1 = 3 · 3 + (−1) · 8.

Moltiplicando per 5 abbiamo che

5 = 15 · 3− 5 · 8

e quindi 3 · 15 ≡ 5 (mod 8), ovvero ogni numero intero congruo a 15 (e cioecongruo a 7) modulo 8 e soluzione della congruenza di sopra. Dalla teoriasappiamo poi che l’insieme di tutte le soluzioni e costituito dagli interi congrui(modulo 8) a

x0 + t · 8

(3, 8)= 7 + 8t

al variare di 0 ≤ t < (3, 8) = 1. Pertanto solo per t = 0 si hanno soluzioni equeste sono dunque tutti e soli gli interi congrui a 7 modulo 8, in altri terminil’insieme delle soluzioni e costituito dagli elementi della classe di congruenza 7modulo 8, ovvero 7 + 8Z.

Esercizio 4 Si determinino le soluzioni della congruenza 87x ≡ 27 (mod 12).

Svolgimento. Applicando Euclide abbiamo che 87 = 7 · 12 + 3 e 12 = 4 · 3 + 0pertanto

(87, 12) = 3 = 1 · 87− 7 · 12.

Poiche 3 divide 27 abbiamo che la congruenza ammette soluzioni. Inoltre,

27 = 9 · 3 = 9 · (1 · 87− 7 · 12) = (9) · 87 + (−63) · 12.

Dunque 9 e una soluzione e tale e anche ogni intero congruo a 9 modulo 12. Lealtre eventuali soluzioni, modulo 12, sono date da

9 + t · 12

(87, 12)= 9 + t · 4

con 0 ≤ t < (87, 12) = 3, e pertanto le soluzioni modulo 12 della congruenza dipartenza sono: [9]12, [13]12 = [1]12 e [17]12 = [5]12.

2

Esercizio 5 Si determinino le soluzioni della congruenza x2 ≡ 5 (mod 6).

Svolgimento. Conviene costruire una tabella che esprime i quadrati modulo 6.Per ogni intero a ∈ Z indichiamo per semplicita con a la classe [a]6 contenentea. Allora poiche a2 = a2, abbiamo che

a a2

0 01 12 43 9 = 34 16 = 45 25 = 1

Si vede pertanto che la classe 5 non compare tra i quadrati e quindi x2 ≡ 5(mod 6) non ha soluzioni intere.

Esercizio 6 Risolvere il seguente sistema di congruenze.x ≡ 11 (mod 60)

x ≡ −1 (mod 18)

Svolgimento. Ricordiamo che tale sistema di congruenze ammette soluzioni see solo se

d | 11− (−1) = 12,

dove d e il massimo comun divisore d = (60, 18). Si ha che

d = (60, 18) = (22 · 3 · 5, 2 · 32) = 2 · 3 = 6,

che divide 12, quindi il sistema ammette soluzioni.Dalla teoria sappiamo che le soluzioni del sistema sono della forma

x = x0 + t ·m.c.m(60, 18) = x0 + 180t,

al variare di t ∈ Z e dove x0 e un’arbitraria soluzione. Occorre pertanto oratrovare una soluzione x0. A tal fine ricordiamo che se il sistema si rappresentanella forma

x ≡ a (modm1)

x ≡ b (modm2)

allora una soluzione (quando esiste) e ad esempio

x0 = a− αm1

dove α e dato da a − b = α ·m1 + βm2. Occorre pertanto esplicitare a − b =11− (−1) = 12 come combinazione lineare in Z di m1 = 60 ed m2 = 18. Dopoaver applicato l’algoritmo di Euclide si ottiene

12 = 2 · (60)− 6 · (18),

3

ovvero α = 2 e x0 = a− αm1 = 11− 2 · (60) = −109. L’insieme di tutte e solele soluzioni e pertanto

S = −109 + 180t | t ∈ Z .

Esercizio 7 Sia n ∈ N. Si risolva in Z la seguente congruenza

x2(n+1) + x2n + 3 ≡ 0 (mod 5).

Svolgimento. Ponendo y = x2 la congruenza di partenza e equivalente alsistema

y ≡ x2 (mod 5)

yn+1 + yn + 3 ≡ 0 (mod 5)

Esaminiamo prima quali sono i possibili quadrati modulo 5:

x x2

0 01 12 4 = −13 9 = −14 16 = 1

Pertanto y ≡ −1, 0, 1 (mod 5). Trattando singolarmente ogni caso si ha chesolo per y ≡ 1 (mod 5) la congruenza yn+1 + yn + 3 ≡ 0 e soddisfatta, dunquele soluzioni intere della congruenza di partenza sono tutti e soli gli elementi di[1]5 ∪ [4]5.

Esercizio 8 Risolvere il seguente sistema di congruenze.

(∗)

x ≡ 3 (mod 5)

x ≡ 5 (mod 9)

x ≡ 6 (mod 11)

Svolgimento. Risolviamo per prima cosa il sistema costituito dalle prime duecongruenze, ovvero il sistema

(∗∗)

x ≡ 3 (mod 5)

x ≡ 5 (mod 9)

Poiche 5 e 9 sono numeri coprimi, (∗∗) ammette soluzioni, e queste sono tutti esoli i numeri x ∈ Z della forma

x = (a− αm1) + t ·m.c.m(m1,m2),

4

al variare di t ∈ Z, e dove, in questo caso, m1 = 5,m2 = 9, a = 3 ed α e dato daa−b = αm1+βm2, ovvero −2 = α·5+β ·9. Applicando l’algoritmo di Euclide siricava che 1 = 2 ·5+(−1) ·9, da cui, moltiplicando per −2, −2 = (−4) ·5+(2) ·9.Ne segue che le soluzioni di (∗, ∗) sono gli

x = 3− (−4) · 5 + t · 45 = 23 + 45t,

al variare di t ∈ Z, cioe gli

x ≡ 23 (mod 45).

A questo punto le soluzioni del sistema (∗) sono tutte e sole quelle del sistema

(∗ ∗ ∗)

x ≡ 23 (mod 45)

x ≡ 6 (mod 11)

Procedendo in modo simile a quanto fatto sopra, abbiamo come soluzione finale

x ≡ −742 (mod 495) ≡ 248 (mod 495).

Esercizio 9 Risolvere il seguente sistema di congruenze.2x+ 3y ≡ 1 (mod 11)

−x+ 7y ≡ −1 (mod 11)

Svolgimento. Ricaviamo dalla seconda equazione la x e sostituiamola nellaprima, otteniamo

14y + 2 + 3y ≡ 1 (mod 11)

x ≡ 7y + 1 (mod 11)

ovvero, ragionando modulo 11,6y ≡ −1 (mod 11)

x ≡ 7y + 1 (mod 11)

Ora, la prima equazione ammette come soluzione

y ≡ −2 ≡ 9 (mod 11),

che, una volta sostituita nella seconda, comporta

x ≡ −13 ≡ 9 (mod 11),

pertanto il sistema ammette un’unica soluzione modulo 11, ed e

x ≡ y ≡ 9 (mod 11).

5

Esercizio 10 Trovare le soluzioni intere, x, y ∈ Z, del seguente sistema dicongruenze

x721 − 721y ≡ 0 (mod 5)

(x2y)721 ≡ 993 (mod 5)

Svolgimento. Poiche 721 ≡ 1 (mod 5) e 993 ≡ 3 (mod 5) il sistema e equiva-lente al seguente

x721 ≡ y (mod 5)

(x2y)721 ≡ 3 (mod 5)

Poiche la seconda equazione non e soddisfatta se x o y sono congrui a zero mod-ulo 5, possiamo di certo assumere che x 6≡ 0 (mod 5) cosı come x2y 6≡ 0 (mod5). Siamo allora nelle ipotesi per applicare il Teorema di Fermat. Dividendo721 per 4 si ottiene: 721 = 4 · 180 + 1 e, per il Teorema di Fermat, abbiamo cheil sistema di congruenze e equivalente a

x ≡ y (mod 5)

x2y ≡ 3 (mod 5)

ovvero x ≡ y (mod 5)

x3 ≡ 3 (mod 5)

Pertanto tutte e sole le soluzioni del sistema sono x ≡ y ≡ 2 (mod 5).

Esercizio 11 (Tema d’esame 14/7/2014)1. Si provi che porre, per ogni a, b ∈ Z,

f(a+ 5Z, b+ 7Z) = 15b− 14a+ 35Z

definisce un’applicazione f : Z/5Z× Z/7Z −→ Z/35Z.2. Si dica se f e iniettiva e/o suriettiva.3. Si determini la controimmagine f−1(1 + 35Z).

Svolgimento. 1. Proviamo che f e ben definita. Siano (a + 5Z, b + 7Z) =(c+ 5Z, d+ 7Z) ∈ Z/5Z× Z/7Z, allora 5|a− c e 7|b− d. Ne segue allora che

15(b− d) ≡ 14(a− c) ≡ 0 (mod 35)

cioe15b− 14a ≡ 15d− 14c (mod 35)

ovvero 15b− 14a+ 35Z = 15d− 14c+ 35Z e cio prova che f non dipende dallascelta dei rappresentanti.2. f e iniettiva.Assumiamo che sia f(a+ 5Z, b+ 7Z) = f(x+ 5Z, y + 7Z), ovvero

15b− 14a+ 35Z = 15y − 14x+ 35Z.

6

Allora15b− 14a ≡ 15y − 14x (mod 35)

e quindi15(b− y) ≡ 14(a− x) (mod 35).

Poiche 35 e il prodotto dei primi 5 e 7, la congruenza di sopra e equivalente alsistema

15(b− y) ≡ 14(a− x) (mod 5)

15(b− y) ≡ 14(a− x) (mod 7)

ovvero a 0 ≡ −(a− x) (mod 5)

b− y ≡ 0 (mod 7)

da cui si ricava a ≡ x (mod 5)

b ≡ y (mod 7)

e quindi (a+ 5Z, b+ 7Z) = (x+ 5Z, y + 7Z), provando cosı che f e iniettiva.f e suriettiva.Preso arbitrariamente un elemento z + 35Z ∈ Z/35Z ci chiediamo se esiste unacoppia (a + 5Z, b + 7Z) ∈ Z/5Z × Z/7Z per cui f(a + 5Z, b + 7Z) = z + 35Z,ovvero

15b− 14a ≡ z (mod 35).

Come sopra, questa congruenza equivale a15b− 14a ≡ z (mod 5)

15b− 14a ≡ z (mod 7)

ovvero a ≡ z (mod 5)

b ≡ z (mod 7)

e pertanto una (l’unica essendo f iniettiva) retroimmagine di z+35Z e la coppia(z + 5Z, z + 7Z) ∈ Z/5Z× Z/7Z.3. Per quanto appena detto

f−1(1 + 35Z) = (1 + 5Z, 1 + 7Z) .

Esercizio 12 Siano n ed m due interi positivi tali chen+m = 63

[n,m] = 962

Si determinino n ed m.

7

Svolgimento. Poniamo d = (n,m) e quindi [n,m] = nmd , il sistema da risolvere

e pertanto n+m = 63

nm = 962d

Ora dalla prima equazione si trova che m = n− 63, e per le proprieta del MCDabbiamo

d = (n,m) = (n, 63− n) = (n, 63) = (n, 32 · 7) ∈ ±1,±3,±7,±9,±21,±63 ,

essendo d un divisore di 63. Inoltre m ed n sono per ipotesi due interi pos-itivi, dalla seconda equazione segue allora immediatamente che anche d > 0,quindi d ∈ 1, 3, 7, 9, 21, 63. Sostituendo m = n− 63 nella seconda equazione eriordinando otteniamo

n2 − 63n+ 962d = 0,

di cui cerchiamo soluzioni, n, intere. Ne segue che il discriminante

∆ = (−63)2 − 4(962d) = 3969− 3848d

deve essere un quadrato perfetto. Ora al variare di tutti i possibili valori di din 1, 3, 7, 9, 21, 63, si ha che l’unico caso possibile e

∆ = 121 = 112 per d = 1,

ovvero (n,m) = 1 ed n e radice naturale di n2−63n+962 = 0, cioe n = 63±112 ∈

26, 37 e quindi

(n,m) = (n, 63− n) ∈ (26, 37), (37, 26) .

Ovviamente poiche il sistema ed simmetrico rispetto ad n ed m, l’insieme dellesoluzioni non poteva che essere altrettanto.

8