Niech R będzie relacją symetryczną i przechodnią na zbiorze X. Przeprowadzamy następujące rozumowanie. Niech xRy. Ponieważ R jest symetryczna, więc yRx. Zatem na mocy przechodniości R z warunków xRy i yRx wynika xRx, czyli R jest zwrotna bo x było dowolne. Gdzie jest błąd w tym rozumowaniu?
Jacek Gancarzewicz, Algebra liniowa i jej zastosowania, WUJ, Wydanie I, 2004, strona 59, zadanie I.12.
Powtarzam sobie algebrę i natrafiłem właśnie na zadanie, którego nie mogę rozgryźć.
Wydaje mi się, że tu:
Zatem na mocy przechodniości R z warunków xRy i yRx wynika xRx, czyli R jest zwrotna bo x było dowolne
ponieważ przechodniość to:
(xRy & yRz) => xRz a nie tak jak jest napisane, że xRx
Mam pewien kontrprzykład Wibowit:
Weźmy relację bycia bratem na zbiorze mężczyzn. Zgodnie z tym rozumowaniem jeżeli X jest bratem Y to Y jest bratem X - czyli ok. Jeżeli X jest bratem Y i Y jest bratem Z to X jest bratem Z - czyli OK. Ale jeżeli X jest bratem Y, a Y jest bratem X to nie oznacza, że X jest bratem X. Nie wiem jak to przedstawić formalnie ;p
mychal:
Ta relacja nie jest przechodnia, ponieważ jeżeli X = Z i X jest bratem Y, to z przechodniości wynika, że XRY i YRZ => XRX, a więc jest przechodniość.
Poprawną odpowiedź chyba dał bodgans. Jeśli weźmiemy relację równoważności i dodamy do zbioru wartości nowe elementy, ale nie zmienimy zbioru relacji, to utracimy tylko i wyłącznie zwrotność.
Aby wykazać błąd należy odwołać się do definicji:
relacja jest** zwrotna w ZBIORZE A** jeśli dla każdego a ...
relacja jest przechodnia, symetryczna jeśli dla każdego a,b ... bla bla bla
Symetria i przechodniość są własnościami samej relacji, natomiast o zwrotności możemy mówić w stosunku do pary: relacji i zbioru w którym pole tej relacji jest zawarte, natomiast w zadaniu uogólnia się zwrotność na wszystkie zbiory.
@mychal.szczygiel, w życiu codziennym nie istnieje kwestia czy jakiś mężczyzna jest swoim bratem. Jeżeli formalnie zdefiniujemy relację w zbiorze mężczyzn tak: xRy <==> x i y maja tego samego ojca i tą samą matkę (niezależnie od tego czy x jest różne od y), to każdy mężczyzna jest swoim własnym bratem.
Problem relacji nie określiłbym jako algebry abstrakcyjnej, mimo, że w niej korzystamy często z relacji, ale może się czepiam.
Dla x-ów dla których istnieje y, że xRy mamy zwrotność, ale nie koniecznie dla wszystkich.
Wibowit napisał(a)
Poprawną odpowiedź chyba dał bodgans.
Tak, modulo relacja pusta na zbiorze pustym.
Wibowit napisał(a)
Jeśli weźmiemy relację równoważności i dodamy do zbioru wartości nowe elementy, ale nie zmienimy zbioru relacji, to utracimy tylko i wyłącznie zwrotność.
Dokładnie.