LOGICA MATEMATICA

Claudia Malvenuto Canale E-O Scheda esercizi n. 4

31 ottobre 2005

Sí, tutto con eccesso! la luce, la vita, il mare! Plurale tutto, plurale, luci, vite e mari. Che salgano, che ascendano da dozzine a centinaia, da centinaia a migliaia, in un’esultante ripetizione infinita, del tuo amore, unità. [...] (La voce a te dovuta, Pedro Salinas)

1. Quando una relazione non è riflessiva? quando non è simmetrica? antisimmetrica? transitiva?

2. Trovare tutte le partizioni (insiemistiche) dell’insieme A = {a, b, c} a 3 elementi.

3. Trovare tutte le partizioni dell’insieme a 4 elementi A = {a, b, c, d}.

4. Sia ρ una relazione simmetrica e transitiva su un insieme A. Si provi che ρ è una relazione di equivalenza se e solo se vale la seguente proprietà:

∀a ∈ A ∃ b ∈ A : aρb.

5. Sia P l’insieme dei punti del piano. Sia ρ la relazione su P così definita: p_{1}ρp_{2} se e solo se i punti p_{1} e p_{2} sono equidistanti da un fissato punto O. Si provi che ρ è una relazione d’equivalenza su P e si determini l’insieme quoziente P/ρ.

6. Definizione costruttiva di ℤ a partire da ℕ Definiamo in ℕ × ℕ la relazione

(m, n) ∼ (m′, n′) ⇔ m + n′ = n + m′.

(a) Verificare che ∼ è una relazione d’equivalenza.

(b) Verificare che le coppie del tipo (m, 0), (0, n), (0, 0), con m, n ≠ 0 sono un insieme di rappresentanti per le classi di ∼–equivalenza.

(c) Sia ℤ := ℕ × ℕ/ ∼. Si definisca in ℤ un’operazione di somma

ponendo

[(x, y)] + [(x′, y′)] := [(x + x′, y + y′)].

Si dimostri che l’operazione di somma è ben definita (ovvero, pur essendo definita sui rappresentanti delle classi, non dipende dalla scelta di tali rappresentanti).

7. Definizione costruttiva di ℚ a partire da ℤ Definiamo in ℤ × ℤ^{∗} (dove ℤ^{∗} = ℤ \ {0}) la relazione

(m, n) ∼ (m′, n′) ⇔ mn′ = nm′.

(a) Verificare che ∼ è una relazione d’equivalenza.

(b) Verificare che le coppie del tipo (m, n) ∈ ℤ × ℤ^{∗}, con m ed n primi tra loro, sono un insieme di rappresentanti per le classi di ∼–equivalenza.

(c) Sia ℚ := ℤ × ℤ^{∗}/ ∼. Si definisca in ℚ un’operazione di somma

ponendo

[(x, y)] + [(x′, y′)] := [(xy′ + x′y, yy′)].

Si dimostri che l’operazione di somma è ben definita (ovvero, pur essendo definita sui rappresentanti delle classi, non dipende dalla scelta di tali rappresentanti).

(d) Si definisca in ℚ un’operazione di prodotto ponendo

[(x, y)] · [(x′, y′)] := [(xx′, yy′)].

Si dimostri che l’operazione di prodotto è ben definita (ovvero, pur essendo definita sui rappresentanti delle classi, non dipende dalla scelta di tali rappresentanti).

8. Mostrare che se {X_{i} : i ∈ I} è una partizione di un insieme X e {Y_{j} : j ∈ J} è una partizione di un insieme Y, allora {X_{i}×Y_{j} : (i, j) ∈ I ×J} è una partizione di X × Y.

9. Mostrare che le seguenti relazioni sono relazioni d’equivalenza, descriverne il relativo insieme quoziente e un insieme di rappresentanti per il quoziente:

(a) in ℤ, la relazione xρx′ ⇔ |x| = |x′|;

(b) in ℤ, la relazione: x ha la stessa parità di x′ (cioè o sono entrambi pari, o entrambi dispari);

(c) in ℝ la relazione: x differisce per un multiplo intero di 2π da x′ (cioè, x = x′ + 2kπ, per qualche k ∈ ℤ);

(d) in ℝ, la relazione: x ha la stessa parte intera inferiore di x′ (cioè ⌊x⌋ = ⌊x′⌋);

(e) in ℝ, la relazione x differisce per un intero da x′ (cioè x = x′ + k, per qualche k ∈ ℤ);

(f) fissato un insieme S finito e non vuoto, in X = P(S) la relazione x ha lo stesso numero di elementi di x′.

10. Sia ρ = (R, X) una relazione. Mostrare che ρ è una relazione di equivalenza se e solo se ρ^{−1} è una relazione di equivalenza.

11. Determinare tutte le relazioni di equivalenza dell’insieme A = {a, b, c}.

12. Trovare il più piccolo intero naturale congruo a ciascuno dei seguenti numeri, modulo l’intero indicato: 16(modulo 3); 16(modulo 7); 35(modulo 2); 117(modulo 32); 121(modulo 111); 312(modulo 60).

13. Sia n ≥ 2 e siano a, b ∈ ℤ. Mostrare che le seguenti affermazioni sono equivalenti:

(a) a ≡ b(mod n);

(b) a e b hanno lo stesso resto nella divisione per n;

(c) b ∈ {a + nk : k ∈ ℤ};

(d) {a + nk : k ∈ ℤ} = {b + nh : h ∈ ℤ}.

14. Sia n ≥ 2 fissato. Mostrare che:

(a) a ≡ b(mod n), c ≡ d(mod n) ⇒ a + c ≡ b + d(mod n);

(b) a ≡ b(mod n), c ≡ d(mod n) ⇒ ac ≡ bd(mod n);

(c) a ≡ b(mod n) ⇒ a^{k} ≡ b^{k}(mod n) per ogni k ∈ ℕ;

(d) a ≡ b(mod n), m | n ⇒ a ≡ b(mod m);

(e) a ≡ b(mod n), m ≠ 0 ⇒ am ≡ bm(mod mn);

(f) a ≡ b(mod n), d ≠ 0, d | a, d | b, d | n ⇒ a/d ≡ b/d(mod n/d);

(g) ac ≡ bc(mod n), d = MCD(c, n) ⇒ a ≡ b(mod n/d);

(h) ac ≡ bc(mod n), MCD(c, n) = 1 ⇒ a ≡ b(mod n);

(i) ac ≡ bc(mod p), p primo, p non divide c ⇒ a ≡ b(mod p);

(j) a ≡ b(mod n), a ≡ b(mod m) ⇒ a ≡ b(mod mcm(n, m)). Si noti che, in (h), la condizione sul MCD è essenziale per effettuare la cancellazione (dare un esempio in cui non si può effettuare la cancellazione).

15. Verificare che (a) il quadrato di ogni intero è congruo a 0 oppure a 1 (mod 4);

(b) il quadrato di ogni intero è congruo a 0, oppure a 1, oppure a 4

(mod 8).

16. Fissati n ≥ 2 ed a ∈ ℤ, si dice inverso aritmetico di a(mod n) un elemento a^{∗} ∈ ℤ (se esiste) tale che

aa^{∗} ≡ 1(mod n).

Mostrare che a ammette inverso aritmetico (mod n) ⇔ MCD(a, n) = 1.