Dimostrare che (P(A

Roma, 20 ottobre 2017 Esercitazioni di algebra 1 (Damiani) 3^a lezione 1) Siano A un insieme e ⊆ la relazione “essere contenuto” definita in X = P(A).

Dimostrare che (P(A), ⊆) `e un insieme ordinato.

Provare che questo ordinamento `e un ordinamento totale se e solo se #A ≤ 1.

Provare che il minimo di (P(A), ⊆) `e ∅ e che il massimo di (P(A), ⊆) `e A.

Determinare minimali e massimali di (P(A) \ {∅, A}, ⊆).

2) Sia n ∈ N. Provare che:

i)Pn k=0

n

k
= 2ⁿ; ii)Pn

k=0(−1)^{k n}_k
= 1 se n = 0 0 altrimenti;

iii)Pn k=0

n k

2

= ²ⁿ_n
.

3) Siano n, d ∈ N. Contare il numero di monomi in n variabili di grado d, cio`e

#{(m1, ..., mn)|mi ∈ N ∀i = 1, ..., n e Pn

i=1mi = d}.

4) Provare che per ogni X insieme si ha #X < #P(X).

5) Il paradosso di Russell (l’insieme di tutti gli insiemi non esiste, ovvero la collezione di tutti gli insiemi non `e un insieme).

Supponiamo che l’insieme di tutti gli insiemi sia un insieme, cio`e che esista un insieme U definito dalla propriet`a x ∈ U ⇔ x `e un insieme.

Si consideri F = {x ∈ U |x 6∈ x}. Osservare che F ⊆ U e F ∈ U . Dire se F ∈ F .

6) Determinare il massimo comun divisore d di 45 e 7 e trovare una coppia (a, b) di numeri interi tali che d = 45a + 7b.

7) Determinare il massimo comun divisore d di 125 e 13 e trovare una coppia (a, b) di numeri interi tali che d = 125a + 13b.

8) Siano a = ma⁰, b = mb⁰, d = M CD(a, b), d⁰ = M CD(a⁰, b⁰), x, y ∈ Z.

Dimostrare che d = md⁰. Osservare che d = ax + by ⇔ d⁰ = a⁰x + b⁰y.

9) Siano a, b ∈ Z, con b 6= 0. `E ben noto che esistono q, r ∈ Z con 0 ≤ r < |b|

tali che a = bq + r.

Dimostrare che tale affermazione pu`o essere modificata nella seguente:

Esistono q, r ∈ Z con |r| ≤ ^|b|₂ tali che a = bq + r.

Esercizi da svolgere a casa che riprenderemo alla prossima lezione.

I) Sia ∼ la relazione su R definita nel modo seguente: x ∼ y ⇔ x − y ∈ Z.

Dimostrare che ∼ `e una relazione di equivalenza e determinarne classi di equivalenza e quoziente.

II) Si considerino gli insiemi X e Y definiti nel modo seguente:

X = {(m1, ..., mn)|mi ∈ N ∀i = 1, ..., n e

n

X

i=1

mi = d},

Y = {(l₁, ..., l_n−1)|0 ≤ l_i < l_i+1 < n + d − 1 ∀i = 1, ..., n − 2};

1

2

sia ϕ : X → Y definita da

ϕ(m1, ..., mn) = (l1, ..., ln−1) con li =

i

X

j=1

mj + i − 1 ∀i = 1, ..., n − 1.

Dimostrare che:

i) ϕ `e ben definita, cio`e effettivamente ϕ(m) ∈ Y ∀m ∈ X;

ii) ϕ `e biunivoca: si costruisca ψ : Y → X tale che ψ ◦ ϕ = idX e ϕ ◦ ψ = idY.