Relacja (matematyka)
Z Wikipedii
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: coś o relacjach między wieloma zbiorami, choćby to, że się ich nie rozpatruje :). Dokładniejsze informacje o tym, co należy poprawić, być może znajdziesz na stronie dyskusji tego artykułu. Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
Spis treści |
Relacja – dowolny podzbiór iloczynu kartezjańskiego zbiorów. Intuicyjnie, oznacza pewien związek pomiędzy elementami tych zbiorów.
[edytuj] Intuicje
Językiem relacji można opisywać wiele zjawisk życia codziennego. Przyjrzyjmy się społeczności wszystkich Polaków P (relacja na jednym zbiorze) i wprowadźmy pewne zależności.
Niech S będzie relacją między dwoma członkami społeczności P (relacja dwuargumentowa) określoną następująco:
- x jest w relacji S z y wtedy i tylko wtedy, gdy x posiada samochód tej samej marki co y.
Relacja S jest:
- zwrotna, ponieważ osoba x ma samochód tej samej marki co ona sama,
- symetryczna, gdyż jeśli x ma samochód tej samej marki co y, to oczywiście y ma samochód tej samej marki co x.
Relacja ta pozwala wyróżnić w społeczności grupy osób (podzbiory): posiadaczy Roverów, Fiatów, Syren, itp. Grupy te nie muszą być rozłączne, ta sama osoba może posiadać kilka samochodów różnych marek i wówczas należy do kilku odpowiednich grup. Pozostaje ona wówczas w relacji S z osobami, które mogą nie być ze sobą w relacji S, a więc relacja nie jest przechodnia.
Gdyby jednak każdy członek społeczności posiadał samochody co najwyżej jednej marki, to relacja S byłaby przechodnia i wobec tego byłaby relacją równoważności, czyli wprowadzałaby podział społeczności P ze względu na markę samochodu (podzieliłaby ją na tzw. klasy abstrakcji).
Wprowadźmy inną relację na P:
- osoba x jest w relacji F (relacja jednoargumentowa), jeśli posiada Ferrari.
Relacja ta wyróżnia podzbiór Polaków będących posiadaczami Ferrari.
Rozważmy zbiór kobiet X oraz mężczyzn Y będących członkami społeczności P (podział ten można otrzymać dzięki zastosowaniu odpowiedniej relacji równoważności) oraz zbiór M wszystkich marek samochodów. W iloczynie kartezjańskim można wprowadzić relację (trójargumentową) T taką, że:
- trójka (x,y,s) jest w relacji T wtedy i tylko wtedy, gdy x jest żoną y i małżeństwo to posiada Fiata.
Wówczas żadna samotna osoba będąca posiadaczem Fiata nie ma szans "dostać się" do relacji T, dopóki nie znajdzie drugiej "połówki", małżeństwo natomiast – dopóki nie wejdzie w posiadanie Fiata.
[edytuj] Definicja
Niech dane będą dowolne zbiory . Relacją n-członową (n-argumentową, n-arną) nazywamy dowolny podzbiór ich iloczynu kartezjańskiego
- .
[edytuj] Relacje jednego zbioru
Szczególnym przypadkiem są relacje zawarte w n-tej potędze kartezjańskiej jednego zbioru X, czyli relacje typu
Jeżeli przez oznaczymy zbiór wszystkich relacji n-członowych w zbiorze X, to moc tego zbioru dana jest wzorem
Nad takim relacjami skupimy się w dalszej części artykułu.
[edytuj] Relacje zeroargumentowe
Pod względem formalnym interesujący jest przypadek tzw. relacji zeroargumentowych, które zawarte są w zbiorze:
Istnieją tylko dwie takie relacje, to jest oraz . Są one użyteczne w rozważaniach teoretycznych, ale trudno je zrozumieć intuicyjnie.
[edytuj] Relacje jednoargumentowe
Częściej używanymi relacjami są relacje jednoargumentowe (jednoczłonowe, unarne), czyli podzbiory zbioru X. Zwykle rola takiej relacji sprowadza się do wskazania pewnego podzbioru lub elementu należącego do zbioru X.
[edytuj] Przykłady
W zbiorze liczb rzeczywistych relacjami jednoargumentowymi są:
- zbiór liczb wymiernych ,
- zbiór liczb parzystych,
- przedział (0,1).
[edytuj] Relacje dwuargumentowe
W praktyce najpopularniejsze i najszerzej stosowane są relacje dwuargumentowe (dwuczłonowe, binarne), zwykle nazywane po prostu relacjami.
Relacje te są zbiorami par uporządkowanych elementów postaci . Zgodnie z tradycją zamiast pisze się zazwyczaj i czyta „”.
Zbiór wszystkich tych elementów X, które występują jako poprzedniki w parach należących do pewnej relacji (tzn. występują na pierwszych miejscach w parach) nazywamy dziedziną , a zbiór następników (elementów na drugim miejscu) – obrazem tej relacji.
[edytuj] Przykłady
Typowymi przykładami relacji binarnych są:
- relacja pusta równa zbiorowi pustemu,
- relacja pełna, równa oraz
- przekątna, czyli zbiór par .
W zbiorze liczb rzeczywistych :
- łatwo zauważyć, że ich interpretacją są figury płaskie. W tym przypadku relację pełną przedstawia cała płaszczyzna, przekątną natomiast prosta y = x.
- najczęściej wykorzystywanymi relacjami binarnymi są:
- relacja równości = będąca relacją równoważności na tym zbiorze,
- relacja mniejsze-równe będąca relacją porządku liniowego na .
W zbiorze liczb naturalnych :
- relacja podzielności, tj. zbiór wszystkich par liczb naturalnych (m,n) takich, że n = km dla pewnej liczby naturalnej k. Para (m,n) jest elementem tej relacji wtedy i tylko wtedy, gdy liczba m dzieli liczbę n. Dlatego
- (2,4) jest elementem relacji podzielności,
- (2,5) nie należy do tej relacji.
[edytuj] Zobacz też
[edytuj] Ważniejsze relacje
własności
- relacja zwrotna,
- relacja symetryczna,
- relacja antysymetryczna,
- relacja przeciwsymetryczna,
- relacja równoważności,
- relacja przechodnia,
- relacja dobrze ufundowana,
- relacja słabo konfluentna,
- relacja silnie konfluentna,
- relacja spójna;
- relacja liniowo porządkująca zbiór
porządki
rodzaje