Relacja (matematyka)

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Spis treści

1 Intuicje
2 Definicja
3 Relacje jednego zbioru
4 Zobacz też
- 4.1 Ważniejsze relacje

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.

Jeżeli 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.

Jest to oczywiście obejmująca tylko i wyłącznie 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 $X \times Y \times M$ 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 żaden samotny mężczyzna (ani kobieta) 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 $X_1, X_2, \dots, X_n$ . Relacją n-członową (n-argumentową, n-arną) nazywamy dowolny podzbiór ich iloczynu kartezjańskiego

$\varrho \subseteq X_1 \times X_2 \times \dots \times X_n$ .

[edytuj] Relacje jednego zbioru

Szczególnym przypadkiem są relacje zawarte w $n$ -tej potędze kartezjańskiej jednego zbioru $X$ , czyli relacje typu $\varrho \subseteq X \times X \times \dots \times X = X^n$

Jeżeli przez $\operatorname{Rel}_n(X)$ oznaczymy zbiór wszystkich relacji n-członowych w zbiorze $X$ , to moc tego zbioru dana jest wzorem

$|\operatorname{Rel}_n(X)| = 2^{|X|^n}$

Nad takim relacjami skupimy się w dalszej części artykułu.

[edytuj] Relacje zeroargumentowe

Zobacz więcej w osobnych artykułach: funkcja pusta, działanie zeroargumentowe.

Pod względem formalnym interesujący jest przypadek tzw. relacji zeroargumentowych, które zawarte są w zbiorze:

$X^0 = \{\varnothing\}$

Istnieją tylko dwie takie relacje, to jest $\varnothing$ oraz $\{\varnothing\}$ . Są one użyteczne w rozważaniach teoretycznych, ale trudno je zrozumieć intuicyjnie.

[edytuj] Relacje jednoargumentowe

Zobacz więcej w osobnym artykule: działanie zeroargumentowe.

Częściej używanymi relacjami są relacje jednoargumentowe (jednoczłonowe, unarne), czyli podzbiory zbioru $X$ . Zwykle taka rola takiej relacji sprowadza się do wskazania pewnego podzbioru czy elementu należącego do zbioru $X$ .

[edytuj] Przykłady

W zbiorze liczb rzeczywistych $\mathbb R$ relacjami jednoargumentowymi są:

zbiór liczb wymiernych $\mathbb Q$ ,
zbiór liczb parzystych,
przedział $(0,1)$ .

[edytuj] Relacje dwuargumentowe

Zobacz więcej w osobnych artykułach: funkcja (matematyka), działanie jednoargumentowe.

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 $(x, y) \in X \times X$ . Zgodnie z tradycją zamiast $(x, y) \in \varrho$ pisze się zazwyczaj $x\; \varrho\; y$ i czyta „ $x \mbox{ jest w relacji } \varrho \mbox{ z } y$ ”.

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 $X \times X$ oraz
przekątna, czyli zbiór par $\{(x, x): x \in X\}$ .

W zbiorze liczb rzeczywistych $\mathbb R$ :

ł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 $\le$ będąca relacją porządku liniowego na $\mathbb R$ .

W zbiorze liczb naturalnych $\mathbb N$ :

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.