Relacja równoważności Paweł: Pokazać, że relacja xRp ⇔ 4 | x+3y, x,y ∊ Z jest relacją równoważności.Wyznaczyć klasę abstakcji [−3].

ICSP: Relacja równoważności to relacja zwrotna, symetryczna, przechodnia : 1^o Zwrotność : ∀_x∊A xRx 2^o Symetryczność ∀_{x,y ∊ A} [xRy ⇒ yRx ] 3^o Przechodniość ∀_{x,y,z ∊A} [ (xRy ∧ yRz ) ⇒ xRz ] Oczywiście A ≠ ∅ oraz R ⊂ A x A x R y ⇔ 4 |x + 3y Czyli x jest w relacji z y wtedy gdy x + 3y jest podzielne przez 4 1^o Zwrotność xRx ⇔ 4 | x + 3x ⇔ 4 | 4x − prawda Relacja jest zwrotna. 2^o Symetryczność xRy ⇔ 4 | x + 3y ⇔ 4 | −(x+3y) ⇔ 4 | −x − 3y ⇔ 4 | −x − 3y + 4(x+y) ⇔ ⇔ 4 | 3x + y ⇔ y Rx Relacja jest symetryczna. 3^o Przechodniość xRy ∧ yRz ⇔ [ 4|x+3y ⋀ 4|y + 3z ] ⇔ [∃_k∊Z x + 3y = 4k ⋀ ∃_k1∊Z y + 3z = 4k₁ ] ⇒ [∃_{k,k1 ∊ Z} 4k + 4k₁ = x +3y + y + 3z ] ⇔ ∃_{k,k1 ∊ Z} 4k + 4k₁−4y = x + 3z ] ⇔ ⇔ ∃_{k,k1 ∊ Z} 4(k + k₁−y) = x + 3z ] ⇔ 4 | x + 3z ⇔ x R z Relacja jest przechodnia. Relacja jest zwrotna, symetryczna, przechodnia, zatem jest relacją równoważności. Klasa abstrakcji: Def : [a]_R = { x ∊ A : x R a } Dla naszej relacji : [−3]_R = {x ∊ Z : x R −3} = { x ∊ Z : 4 | x − 9} = = {4k + 1 , k ∊Z }