Appunti di Logica e Fondamenti di matematica

Relazioni

Definizione 1.25: Una relazione R su un insieme A è riflessiva se per ogni x appartenente ad A, xRx.

Definizione 1.26: Una relazione R su un insieme A è riflessiva se per ogni x appartenente ad A, xRx.

Definizione 1.27: Una relazione R su un insieme A è simmetrica se per ogni x e y tali che xRy, allora yRx.

Definizione 1.28: Una relazione R su un insieme A è transitiva se per ogni x, y e z tali che xRy e yRz, allora xRz.

Definizione 1.29: Una relazione R su un insieme A è una relazione di equivalenza se è riflessiva, simmetrica e transitiva.

Definizione 1.30: Una relazione binaria R su un insieme A è riflessiva su A se per ogni x appartenente ad A, xRx.

simmetrica e transitiva, allora si dice A, R relazione di equivalenza su A.

su 1.1 (Esempio di relazione di equivalenza che non è una relazione di equivalenza su un Esempio insieme). L'insieme vuoto è una relazione di equivalenza ma non è una relazione di equivalenza su qualsiasi insieme non vuoto.

R R fld R.

Lemma 1.5. Sia R una relazione, allora è una relazione binaria su ⊆ × ⊆.

R R dom R ran R fld R.

Proprietà 1.6. Sia R una relazione, allora ⊆ A R A, fld R A.

Proprietà 1.7. Siano un insieme A e sia R una relazione binaria su A, allora R R.

Teorema 1.8. Sia R una relazione simmetrica e transitiva, allora è una relazione di equivalenza fld R.

su 1.13. Nota che se hai che R è una relazione binaria su A tale che è simmetrica R A,

Osservazione e transitiva, non è detto che sia una relazione di equivalenza su perché abbiamo osservato R A,

(Teorema 1.7) che in generale 6fld R = A. R dom R = ran R = fld

R.Proprietà 1.9. Sia una relazione simmetrica, alloraSia allora esiste tale che ma per la simmetria si ha∈x dom R, y xRy, yRx,Dimostrazione.allora quindi Analogamente si vede che per cui∈ ⊆ ⊆x ran R, dom R ran R. ran R dom R,dom R = ran R = fld R. A R A, A = fld R.

Proprietà 1.10. Siano un insieme e sia una relazione riflessiva su allora5Per (Teorema 1.7), si ha che Sia allora e⊆ ∈ ∈ ⊆fld R A. a A, aRa a dom R∩ran RDimostrazione. quindi⊆ ⊆dom R fld R, A fld R.

Proprietà 1.11. Sia una relazione, allora∅ ⇐⇒ ∅ ⇐⇒ ∅R = dom R = ran R =Sia se per assurdo allora esiste e tali che∅, 6 ∅, ∈R = dom R = x dom R yDimostrazione. .hx, ∈ ∅yi R =Sia se fosse per assurdo allora esiste e∅, 6 ∅, hx, ∈ ∈ ∅dom R = R = yi R x dom R =. A R A,

Corollario 1.11.1. Siano un insieme e sia una relazione riflessiva su allora∅ ⇐⇒

∅A = R =Se allora, per le proprietà precedenti, allora∅, ⊆ ⊆ ∅, ∅.A = dom R fld R A = R =Dimostrazione.Sia allora e ma per (Teorema 1.10)∅, ∅ ∅, ∅.R = dom R = ran R = fld R = A = fld R =(Classe di equivalenza). Sia una relazione di equivalenza, per ogni ∈R x fld RDefinizione 1.31si dice l’insiemex Rclasse di equivalenza di modulo {y ∈:=[x] fld R : xRy}R1.14. Nota che vale ancheOsservazione {y ∈ {y ∈[x] = dom R : yRx} = ran R : xRy}R1.15. Nota che se è non vuoto, per ogni si ha quindi∈ ∈ 6 ∅.A a A aRa, a [a] =Osservazione R∈A R A, x, y A,Lemma 1.12. Siano un insieme e una relazione di equivalenza su siano allora⇐⇒xRy [x] = [y]R R(Partizione di un insieme). Sia un insieme e sia un insieme di insiemi nonA ΠDefinizione 1.32vuoti tale che l’unione dei suoi elementi sia e che suoi elementi distinti siano disgiunti.A[∀x(x ∈ → 6 ∅)

∧ ∧ ∀x∀y((x ∈ ∧ ∈ → ∨ ∩ ∅))Π x = Π = A Π y Π) (x = y x y =1.16. Nota che l’unica partizione del vuoto è il vuoto.


Osservazione (Insieme quoziente). Siano un insieme e una relazione di equivalenza su A R


Definizione 1.33allora si dice l’insieme A, A Rinsieme quoziente di modulo {[x] ∈ P(A) ∈:=A/R : x A}R


A R A,


Lemma 1.13. Siano un insieme e una relazione di equivalenza su allora l’insieme A/R A.


quoziente è una partizione di


(Applicazione canonica). Siano un insieme e una relazione di equivalenza A R


Definizione 1.34su l’applicazione tale che è una funzione chiamata→ 7→A, ϕ : A A/R a [a] applicazione canonica.


R1.17. Puoi scrivere anche


Osservazione {hx, ∈ × P(A) }ϕ = yi A : y = [x] R


(Relazione antiriflessiva su un insieme). Siano un insieme e sia una relazione A R


Definizione 1.35binaria su tale che per ogni si ha allora si dice∈ 6A x A x R x R

A.relazione antiriflessiva su(Relazione asimmetrica). Sia una relazione, se per ogni e tali che eR x y xRyDefinizione 1.36si ha allora si diceyRx x = y, R relazione asimmetrica.

∀x∀y((xRy ∧ →yRx) x = y)(Relazione d’ordine stretto su un insieme). Siano un insieme e sia unaA RDefinizione 1.37relazione binaria su tale che è antiriflessiva su e transitiva, allora si diceA R A R relazione diA.ordine stretto su 6(Relazione d’ordine largo su un insieme). Siano un insieme e sia unaA RDefinizione 1.38relazione binaria su tale che è riflessiva su asimmetrica e transitiva, allora si diceA R A, RA.relazione d’ordine largo su(Diagonale di un insieme). Sia un insieme si definisce laA ADefinizione 1.39 diagonale dil’insieme {hx, ∈ ×:=diag A yi A A : x = y} 0A R R =Proposizione 1.14. Siano un insieme e sia una relazione d’ordine stretto, allora∪R diag A è una relazione di ordine largo.(Relazione di ordine totale,

Definizione 1.40: Siano un insieme A e una relazione d'ordine < su A. Se per ogni coppia di elementi x, y in A si ha che x < y implica y ∉ x, allora si dice che < è una relazione d'ordine parziale. Se inoltre per ogni coppia di elementi x, y in A si ha che x < y oppure y < x oppure x = y, allora si dice che < è una relazione d'ordine totale.

Definizione 1.41: Alla coppia ordinata (A, <) si dice ordine su A. Un insieme ordinato è una struttura d'ordine.

Definizione 1.42: Se (A, <) è un insieme ordinato e < è una relazione d'ordine totale su A, allora si dice che (A, <) è un insieme totalmente ordinato. Se invece < è una relazione d'ordine parziale, allora si dice che (A, <) è un insieme parzialmente ordinato.

Notazione 1.43: Sia A un insieme. Dire che (A, <) è un insieme ordinato, è abbreviato come A è ordinato.

un'abbreviazione per indicare che esiste una relazione d'ordine (che implicitamente denotiamo con su<) A. (Elemento minimale, elemento massimale). Sia un insieme ordinato e sia A

Definizione 1.44

se ∈x A, ∀y(y ∈ → →A (y < x y = x)) allora si dice di Se invece x A. elemento minimale ∀y(y ∈ → →A (x < y y = x)) allora si dice di x A. elemento massimale (Elemento minimo, elemento massimo). Sia un insieme ordinato e sia ∈A x A,

Definizione 1.45

se ∀y(y ∈ → ∨A (y = x x < y)) allora si dice di x A. minimo Se invece ∀y(y ∈ → ∨A (y = x y < x)) allora si dice di x A. massimo

1.18. Se esiste il minimo o il massimo esso è unico.

Osservazione (Relazione d'ordine indotta). Sia un insieme ordinato e sia sihA, i ⊆< B A,

Definizione 1.46

Adice la relazione d'ordine ∩B ×A B, < =< B. relazione d'ordine indotta da su B A

1.19. Devi dimostrare che è una

relazione d'ordine su< B.

Osservazione B hA, i,B <Proprietà 1.15.

Si può definire il minimo di un sottoinsieme di un insieme ordinato AA B.

mediante la relazione relazione d'ordine indotta da su(Minorante/maggiorante per un sottoinsieme).

Siano un insieme ordinato eADefinizione 1.47e sia se⊆ ∈B A x A, ∀y(y ∈ → ∨B (x = y x < y))allora si dice che x B.è minorante perSe invece ∀y(y ∈ → ∨B (x = y y < x))allora si dice che x B.è maggiorante per(Insieme inferiormente limitato, insieme superiormente limitato).

Siano ADefinizione 1.48un insieme ordinato e se esistono dei minoranti/maggioranti per allora si dice⊆B A, B, Binferiormente/superiormente limitato. 7(Estremo superiore, estremo inferiore).

Siano un insieme ordinato e ⊆A B ADefinizione 1.49se esistono, si dicono il minimo dei maggioranti di eB Bestremo superiore di estremo inferiore diil massimo dei minoranti diB B.(Segmento

1. Un insieme ordinato, un sottoinsieme di S, si dice segmento iniziale di S se per ogni x e y, se x appartiene a S e y appartiene a S e y è minore di x, allora y appartiene anche al segmento iniziale di S.
2. In parole povere, puoi dire che un insieme è segmento iniziale di S se contiene tutti gli elementi di S che sono più piccoli di x.
3. Nota che in generale la relazione d'ordine è parziale, quindi ci potrebbero essere elementi non confrontabili (e quindi per definizione non deve per forza contenerli).
4. Per ogni insieme esistono sempre i segmenti iniziali e finali di S.
5. Osservazione (Segmento iniziale proprio). Sia un insieme