Relacja równoważności

Relacja równoważności Rodzaje relacji Niech: Zwrotna: Przeciwzwrotna: Symetryczna: Przeciwsymetryczna: Antysymetryczna: Przechodnie: Spójna: Definicja relacji równoważności i w arunki jej równowa ż ne Mówimy, że relacja R zawarta w X jest relacją równoważności, gdy R - jest zwrotna, symetryczna i przechodnia
Jeżeli: i R - relacja równoważności wtedy, gdy dowód: Jeżeli: i R - relacja równoważności wtedy, gdy dowód: Klasa równowa ż no ś ci Jeżeli R - relacja równoważności to zbiór nazywamy klasą równoważności/abstrakcji elementu a względem relacji R.
Zbiór ilorazowy Jeżeli R - relacja równoważności to zbiór nazywamy ilorazowym/ilorazem zbioru X przez relację R.
Podział Niech Podziałem zbioru X nazywamy rodzinę taką że:
Zasada abstrakcji Jeżeli i R - relacja równoważności to jest podziałem zbioru X
Jeżeli jest podziałem zbioru X to jest relacją równoważności.
Dowód:
Konstrukcja liczb całkowitych i wymiernych Liczby całkowite Liczby wymierne Twierdzenia o sumie i złożeniu relacji równowa ż no ś ci Jeżeli R,S - relacje równoważności w X to - relacja równoważności dowód: Jeżeli R,S - relacje równoważności w X to - relacja równoważności dowód: Uogólnione przeci ę cie relacji równoważno ś ci Niech: Wtedy: Dowód: Re lacja równowa ż no ś ci generowana przez dowoln ą relacj ę Niech: R - dowolna relacja określona w R Wtedy: Relacją generowaną przez relację R nazywamy relację: Twierdzenie 1: jest najmniejszą relacją równoważności zawierającą R dowód: - relacja równoważności bo , gdzie -suma relacji równoważności Niech: T - relacja równoważności zawierająca R Twierdzenie 2: dowód: pokazujemy że - najmniejsza relacja równoważności zawierająca R Tranzytywne domkni ę cie relacji Niech R - dowolna relacja określona w R Wtedy: Tranzytywnym (przechodnim) domknięciem relacji R nazywamy relację: , gdzie Twierdzenie: jest najmniejszą relacją przechodnią zawierającą relację R co jest równoważne, ze dowód: Iloraz relacji równowa ż no ś ci Niech: R, S - relacja równoważności na X i Wtedy: Ilorazem relacji R prymy relację S nazywamy relację: taką że: Sprawdzamy czy definicja jest dobrze określona (należy sprawdzać dla zbiorów i klas równoważności) - czy ... zobacz całą notatkę