Matematyka dyskretna Klaudia : Zbadać, które działania w zbiorze relacji zachowują własności relacji. Niech R, S będą relacjami określonymi w niepustym zbiorze X × X. (a) Suma dwóch relacji zwrotnych jest relacją zwrotną. (b) Suma dwóch relacji symetrycznych jest relacją symetryczną. (c) Suma dwóch relacji antyzwrotnych jest relacją antyzwrotną. (d) Suma relacji antysymetrycznych nie musi być relacją antysymetryczną. (e) Suma relacji słabo antysymetrycznych nie musi być relacją słabo antysymetryczną. (f) Suma dwóch relacji przechodnich nie musi być relacją przechodnią. (g) Przekrój dwóch relacji zwrotnych jest relacją zwrotną. (h) Przekrój dwóch relacji antyzwrotnych jest relacją antyzwrotną. (i) Przekrój dwóch relacji symetrycznych jest relacją symetryczną. (j) Przekrój dwóch relacji antysymetrycznych jest relacją antysymetryczną. (k) Przekrój dwóch relacji przechodnich jest relacją przechodnią.

ite: Pytasz o wskazówki do rozwiązywania?

Klaudia : Tak szczególnie o przekrój relacji myśle ze gdybym miała zrobiony jeden podpunkt wiedziała bym już dalej

Klaudia : Albo gdzie ktoś to zadanie dobrze wytłumaczy

Adamm: Zakładam, że zamiast relacji "antyzwrotnej" chodzi tu o przeciwzwrotną. Niech Δ = {(x, x) : x∊X}. Niech R' = {(y, x) : (x, y)∊R}. Zauważmy, że (R∪S)' = R'∪S', (R∩S)' = R'∩S' dla dowolnych S, R, oraz R'' = R. Również z R⊆S wynika R'⊆S'. Jeśli R, S to dowolne relacje, to R o S = {(x, z)∊X x X : ∃_y∊X (x, y)∊R, (y, z)∊S}. Niech R, S, T to relacje, wtedy R o (S∪T) = (R o S) ∪ (R o T). Mamy również wtedy R o (S∩T) ⊆ (R o S) ∩ (R o T). Mamy następujące charakteryzacje: R jest zwrotna ⇔ Δ⊆R R jest symetryczna ⇔ R' = R R jest przeciwzwrotna ⇔ Δ∩R = ∅ R jest antysymetryczna ⇔ R∩R' = ∅ R jest słabo antysymetryczna ⇔ R∩R'⊆Δ R jest przechodnia ⇔ R o R⊆R a) wystarczy by jedna była zwrotna Jeśli R jest zwrotna, to Δ⊆R, więc tym bardziej Δ⊆R∪S b) Jeśli R i S są symetryczne, to (R∪S)' = R'∪S' = R∪S, więc R∪S jest symetryczna. c) nawet mamy tutaj równoważność Δ∩(R∪S) = (Δ∩R)∪(Δ∩S) Jeśli R, S są przeciwzwrotne, to Δ∩(R∪S) = ∅∪∅ = ∅. d) Weźmy dowolną relację antysymetryczną R. Wtedy R' również jest antysymetryczna (bo R'' = R), ale (R∪R')' = R∪R', więc R∪R' jest symetryczna. Gdyby R∪R' była również antysymetryczna, to R∪R' = ∅, więc R = ∅. A zatem ta konstrukcja daje nam kontrprzykład w przypadku gdy istnieje nietrywialna relacja antysymetryczna. Jeśli X zawiera 0 lub 1 elementów, to łatwo widzieć, że jedyną relacją antysymetryczną jest ∅. Wtedy suma dwóch dowolnych relacji antysymetrycznych jest zbiorem pustym, więc relacją antysymetryczną. Załóżmy więc, że X ma co najmniej dwa różne elementy x, y. Wtedy relacja R = {(x, y)} jest antysymetryczna i nietrywialna. e) Podobnie jak w podpunkcie d), mając dowolną relację słabo antysymetryczną R, rozważamy relację symetryczną R∪R'. Wtedy R' jest słabo antysymetryczna, bo R'' = R. Ta relacja jest słabo antysymetryczna wtedy i tylko wtedy gdy R∪R'⊆Δ, zatem R⊆Δ. Ale z drugiej strony, jeśli R⊆Δ, to R' = R, więc R∪R'⊆Δ. Zatem, podobnie jak w podpunkcie d), jeśli istnieje relacja słabo antysymetryczna nie będąca podzbiorem Δ, to otrzymaliśmy kontrprzykład. Podobnie jak wcześniej, jeśli X ma 0 lub 1 elementów, to taka relacja nie istnieje, bo wtedy dowolna relacja jest podzbiorem Δ. Ale ponieważ każda relacja antysymetryczna jest słabo antysymetryczna, to z podpunktu d) kontrprzykład istnieje gdy X ma co najmniej 2 różne elementy. f) Jeśli R ⊆ Δ, to R o R = R, więc R jest przechodnia. Zatem kontrprzykładów nie ma dla gdy X liczy 0 lub 1 element. Jeśli w X istnieją co najmniej dwa różne elementy x, y, to R = {(x, x), (x, y)}, S = {(x, x), (y, x)}, to R, S są przechodnie, ale ich suma R∪S = {(x, x), (x, y), (y, x)} nie jest przechodnia, bo (y, y)∉R∪S. g) zachodzi tutaj równoważność Jeśli R, S są zwrotne, to Δ⊆R, Δ⊆S, zatem Δ⊆R∩S. h) wystarczy założyć, że tylko jedna z tych relacji jest przeciwzwrotna Jeśli R jest przeciwzwrotna, to Δ∩(R∩S) = (Δ∩R)∩S = ∅∩S = ∅. i) Jeśli R, S są symetryczne, to (R∩S)' = R'∩S' = R∩S. j) wystarczy założyć, że jedna z nich jest antysymetryczna Jeśli R jest antysymetryczna, to (R∩S)∩(R∩S)' = R∩S∩R'∩S' = ∅∩S∩S' = ∅. k) Jeśli R, S są przechodnie, to (R∩S) o (R∩S) ⊆ (R o R)∩(R o S)∩(S o R)∩(S o S) ⊆ (R o R)∩(S o S) ⊆ R∩S.