LOGICA MATEMATICA

Claudia Malvenuto Canale E-O Scheda esercizi n. 3

31 ottobre 2005

Tutto, laggiù, è ordine e bellezza, lusso, calma e voluttà. ^{1}

1. Definiamo la differenza simmetrica di due insiemi A e B come

AΔB := (A \ B) ∪ (B \ A).

Si provi che AΔB = (A ∪ B) \ (A ∩ B).

2. Sia data una relazione ρ = (R, X), dove R ⊆ X × X, e sia ρ^{−1} = (R^{−1}, X) la relazione inversa, dove R^{−1} := {(a, b) : (b, a) ∈ R}. Mostrare che:

(a) R ∩ R^{−1} = ∅ ⇒ ρ antisimmetrica;

(b) non è vero il viceversa di (a) (dare un esempio!)

3. Sia ρ un ordinamento parziale. La relazione inversa ρ^{−1} è ancora un ordinamento parziale?

4. Si dica se le due seguenti relazioni ≤ e ≤′ sono ordinamenti parziali su ℤ:

(a) x ≤ y ⇔ ∃a ∈ ℤ : x + a = y

1Là, tout n’est qu’ordre et beauté,/ luxe, calme et volupté. [...] (L’invitation au voyage, di Charles Baudelaire, in ’Les fleurs du mal’)

(b) x ≤′ y ⇔ ∃a ∈ ℕ : x + a = y

5. Si calcolino elementi massimali, minimali, massimi e minimi, catene massimali dell’insieme parzialmente ordinato il cui diagramma di adiacenza (detto anche diagramma di Hasse) è dato da:

1 2  3 4 5 6 7

6. Determinare tutti i possibili ordinamenti parziali sull’insieme A = {1, 2, 3} e disegnarne il relativo diagramma di Hasse. Esiste un ordinamento parziale su A il cui diagramma di Hasse è il seguente?

12 3

7. Mostrare che

(a) in ℤ la relazione di divisibilità:

x|y ⇔ ∃k ∈ ℤ tale che xk = y

non è una relazione d’ordine (quale delle proprietà manca?).

(b) in ℕ la relazione di divisibilità:

x|y ⇔ ∃k ∈ ℕ tale che xk = y

è una relazione d’ordine, ma non totale.

8. Si costruisca il diagramma di Hasse della relazione di divisibilità sull’insieme {1, 2, 3, 4, 5, 6, 7, 8}, determinando eventuali massimi, minimi, elementi massimali e minimali.

9. Mostrare che l’insieme X := {x ∈ ℕ : x ≥ 2}, ordinato tramite la relazione di divisibilità, ha infiniti elementi minimali (quali?) ma non ha elementi massimali (perché?).

10. Dato un insieme S con almeno due elementi, nell’insieme X := P(S) la relazione di inclusione insiemistica ⊆ definisce una relazione d’ordine parziale.

(a) Mostrare che (X, ⊆) è un insieme ordinato ma non totalmente ordinato.

(b) Disegnare il diagramma di Hasse di (X, ⊆) per S = {1, 2}.

(c) Disegnare il diagramma di Hasse di (X, ⊆) per S = {1, 2, 3}.

11. Determinare, se esistono, i maggioranti, i minoranti, l’estremo superiore e l’estremo inferiore di un sottoinsieme Y di un insieme ordinato (X, ≤) nei seguenti casi

(a) X = {a, b, c, d, e, f, g, h} con l’ordinamento descritto dalla figura seguente e Y = {d, f, e}

a  b c d  e f  g h

(b) X = {a, b, c, d, e, f} con l’ordinamento descritto dalla figura seguente e Y = {b, c, d}

e  f c  d b a