Relazioni di equivalenza e dordine

Page 1

Definizione 1. Siano A e B insiemi. Si definisce prodotto cartesiano l’insieme: A × B = {(a, b ) : a ∈ A ∧ b ∈ B}. Osservazione 1. Si osservi che nella Definizione 1. le coppie sono ordinate, vale a dire ( x, y ) ̸= ( y, x ) se x ̸= y. `E quindi chiaro che A × B ̸= B × A, se A ̸= B. Risulta inoltre: A × ∅ = ∅ × A = ∅. Definizione 2. Siano A e B insiemi. Si dice relazione tra gli A elementi di A e gli elementi di B un qualunque sottoinsieme del prodotto cartesiano A × B. Se A = B, si parla semplicemente di relazione tra gli elementi di A; quindi, in questo caso, R ⊆ A × A. Esempio 1. L’insieme R = {(x, y ) ∈ N × Z : y = −x} ` e una relazione tra gli elementi di N e Z. Si ha R = {(0, 0), (1, −1), (2, −2), (3, −3), . . . }. Esempio 2. L’insieme R′= {(x, y ) ∈ Z × Z : y = −x} ` e una relazione tra gli elementi di Z. Risulta R′= {. . . , (−2, 2), (−1, 1), (0, 0), (1, −1), (2, −2), . . . }. Definizione 3. Siano A un insieme non vuoto, R una relazione tra gli elementi di A. Si dice che R ` eriflessiva se ` e verificata la sequente condizione: (∀a ∈ A) (( a, a ) ∈ R). Osservazione 2. Ovviamente, perch` eR non sia riflessiva, basta che esista un solo elemento x ∈ A tale che ( x, x ) /∈ A. Esempio 3. Non ha senso chiedersi se la relazione R dell’Esempio 1 sia riflessiva, visto che si tratta di una relazione tra elementi di due insiemi diversi. Esempi 1. Delle relazioni sull’insieme A = {α, β, γ } R1 = {(α, α ), (β, β ), (γ, γ ), (α, β ), (α, γ )} R2 = {(α, α ), (β, β ), (α, β ), (β, γ )} R3 = {(α, β ), (β, α ), (γ, β ), (β, γ ), (γ, γ )} R4 = {(α, β ), (β, α ), (α, γ )} R5 = {(α, α ), (β, β ), (γ, γ ), (α, β ), (β, α )} sono riflessive R1 e R5, mentre R2, R3, R4 non sono riflessive. Definizione 4. Siano A un insieme non vuoto, R una relazione tra gli elementi di A. Si dice che R `…