/Studia/Podstawy matematyki/Indukcja

Relacje

Poradnik stanowi uzupełnienie poradnika o zbiorach, więc radzimy zajrzeć tam w celu przypomnienia sobie najważniejszych definicji. Definicje Ustalmy zbiory X i Y .

Relacją o dziedzinie X i przeciwdziedzinie Y nazywamy dowolny podzbiór R iloczynu kartezjańskiego X × Y .

Iloczyn kartezjański X × Y to zbiór par postaci (x,y ) , gdzie x ∈ X i y ∈ Y . Zatem wybranie podzbioru X × Y (ustanowienie relacji) polega na połączeniu w pary pewnych elementów zbioru X z elementami zbioru Y . Jeżeli elementy x i y są w relacji R to piszemy xRy .

Poniższy diagram stanowi schematyczną ilustrację relacji między dwoma zbiorami skończonymi X i Y .


ZINFO-FIGURE


Jeżeli przez X oznaczymy zbiór wszystkich książek, a przez Y zbiór wszystkich ludzi to w zbiorze X × Y mamy relację autorstwa, która łączy w pary książkę z jej autorami. Relacja ta jest dość skomplikowana, bo książki miewają wielu autorów, a autorzy często piszą wiele książek.

Osoby interesujące się informatyką z pewnością spotkały się z pojęciem relacyjnej bazy danych. Jest to sposób na przechowywanie i organizację dużych ilości danych opierający się na tabelach, których kolumny połączone są relacjami.

Bardzo ważnym przykładem relacji są funkcje.

Relację f ⊆ X × Y nazywamy funkcją jeżeli dla każdego x ∈ X jest dokładnie jeden y ∈ Y taki, że (x,y ) ∈ f . Piszemy wtedy y = f(x) .

Zauważmy, że zgodnie z powyższą definicją funkcja jest zbiorem par postaci (x,f (x)) .

Używając języka diagramów o funkcjach myślimy jak o relacjach, w których z każdego elementu zbioru X wychodzi dokładnie jedna strzałka.


ZINFO-FIGURE


Relacja przedstawiona na lewym diagramie nie jest funkcją, bo są elementy, z których nie wychodzi żadna strzałka oraz takie, z których wychodzi więcej niż jedna strzałka. Relacja z prawego diagramu jest funkcją.

Funkcjom poświęcony jest osobny poradnik, w którym znajdziecie więcej informacji na ich temat. My natomiast skoncentrujemy się teraz na innej ciekawej sytuacji, mianowicie na przypadku Y = X .

Relacją w zbiorze X nazywamy dowolny podzbiór iloczynu kartezjańskiego X × X .

Wybranie podzbioru R ⊆ X × X oznacza ustanowienie relacji R (związku) pomiędzy niektórymi elementami zbioru X . Dokładniej, xRy jeżeli (x,y) ∈ R .

Dobrze znacie kilka relacji w zbiorze X = R . Np.: ≤ , ≥ , < , > , = .
W tym przypadku relacje są podzbiorem zbioru R × R = R 2 , czyli płaszczyzny. Możemy więc rysować wykresy relacji: zaznaczamy w układzie współrzędnych wszystkie punkty, z których składa się relacja.


ZINFO-FIGURE


Na lewym diagramie naszkicowaliśmy wykres relacji „≤ ”, a na prawym wykres relacji „= ”.

W zbiorze wszystkich ludzi mamy relację znajomości: osoba A jest w relacji z B jeżeli A zna B .

W zbiorze liczb naturalnych jest bardzo ważna relacja podzielności „| ”, tzn. a |b wtedy i tylko wtedy, gdy a dzieli b .

W zbiorze prostych na płaszczyźnie mamy relacje „∥ ” i „⊥ ”.

W zbiorze wszystkich trójkątów na płaszczyźnie mamy relacje przystawania oraz podobieństwa.

Przyjęta przez nas definicja relacji jest bardzo ogólna i jak widzieliśmy podpada pod nią wiele różnych przykładów. Aby trochę tę sytuację uporządkować wyróżnia się różne cechy relacji. Relację R w zbiorze X nazywamy:

  • zwrotną jeżeli dla każdego x ∈ X mamy xRx ;

  • przechodnią jeżeli dla dowolnych x,y,z ∈ X jeżeli xRy i yRz to xRz ;

  • symetryczną jeżeli dla dowolnych x,y ∈ X jeżeli xRy to yRx ;

  • antysymetryczną jeżeli dla dowolnych x,y ∈ X jeżeli xRy i yRx to x = y .

Relacje „≤ ” i „≥ ” są zwrotne, przechodnie i słabo antysymetryczne.

Relacja „⊥ ” prostopadłości prostych na płaszczyźnie jest symetryczna.

Relacje porządku (nierówności) Jednym z powodów definiowania w zbiorze relacji jest chęć nadania mu dodatkowej struktury. Przykładem takiej struktury może być możliwość porównywania ze sobą elementów, czyli jakaś forma nierówności między elementami. Spróbujmy teraz sprecyzować co rozumiemy przez nierówność.

Relację R w zbiorze X nazywamy częściowym porządkiem jeżeli jest zwrotna, przechodnia i antysymetryczna.

Warunki definiujące częściowy porządek to minimum, jakiego oczekujemy od (słabej) nierówności.

Relację będącą częściowym porządkiem często oznacza się symbolem „≼ ”. Warunki definiujące częściowy porządek wyglądają wtedy bardzo naturalnie: dla dowolnych x ,y ,z ∈ X

x ≼ x (x ≼ y) ∧ (y ≼ z) ⇒ (x ≼ z) (x ≼ y) ∧ (y ≼ x) ⇒ x = y .

Relacja „≤ ” jest częściowym porządkiem w zbiorze R oraz w każdym jego podzbiorze.

W zbiorze 2A składającym się ze wszystkich podzbiorów zbioru A relacją częściowego porządku jest inkluzja „⊆ ”.

Spróbujmy się zastanowić jak porównywać ze sobą punkty płaszczyzny.
Pierwszą naiwną próbą mogłoby być porównywanie drugich współrzędnych, czyli relacja (x,y) ≼ (z,w ) jeżeli y ≤ w . Jak łatwo sprawdzić (zróbcie to!) relacja ta nie jest jednak antysymetryczna, więc nie jest to częściowy porządek.
Mówiąc poglądowo, relacja ta jest zła, bo jest mnóstwo punktów, które z punktu widzenia tej nierówności są równe (punkty leżące na poziomych prostych).

Jeszcze jedno podejście do uporządkowania płaszczyzny: zamiast porównywać drugie współrzędne, porównujmy obie współrzędne na raz, tzn. przyjmijmy (x,y) ≼ (z,w ) jeżeli jednocześnie x ≤ z i y ≤ w . Łatwo sprawdzić, że jest to relacja częściowego porządku.

Jak już pisaliśmy warunki definiujące częściowy porządek to minimum, jakiego oczekujemy od nierówności, jednak często jest to minimum niewystarczające. Dużym problemem w przypadku częściowego porządku jest to, że zazwyczaj są elementy, których nie możemy ze sobą porównać.

Relację „≼ ” w zbiorze X nazywamy liniowym porządkiem jeżeli jest częściowym porządkiem oraz dla dowolnych x ,y ∈ X

(x ≼ y) ∨ (y ≼ x ).

Liniowy porządek jest to więc częściowy porządek, w którym każde dwa elementy można ze sobą porównać.

Relacja inkluzji ⊆ jest częściowym porządkiem, ale nie jest liniowym porządkiem, bo np. nie można przy jej pomocy porównać zbiorów {1 ,3} i {1,2} .

Zwykła nierówność „≤ ” jest liniowym porządkiem w zbiorze R .

Widzieliśmy już, że nierówność na płaszczyźnie zdefiniowana warunkiem

(x ,y) ≼ (z,w ) ⇐ ⇒ (x ≤ z∧ y ≤ w )

jest częściowym porządkiem. Nie jest to jednak linowy porządek, bo przy jego pomocy nie da się porównać np. punktów (1,2) i (2,1) .

Czy na płaszczyźnie da się wprowadzić liniowy porządek? Tak, jest to np. porządek leksykograficzny zdefiniowany warunkiem

(x ,y) ≼ (z,w ) ⇐ ⇒ (x < z)∨ (x = z∧ y ≤ w )

(porównujemy przede wszystkim pierwsze współrzędne, a tylko gdy są równe patrzymy na drugie). Oczywiście właśnie w ten sposób szukacie haseł w słowniku.

Relacje równoważności i klasy abstrakcji

Relację, która jest jednocześnie zwrotna, przechodnia i symetryczna nazywamy relacją równoważności.

W tym przypadku relację często oznaczamy symbolem „∼ ” lub „≡ ”.

Tak jak relacja częściowego porządku stanowi uogólnienie nierówności, relacja równoważności stanowi uogólnienie równości. Różnicę między tymi dwoma pojęciami widać w definicji: mamy symetrię zamiast antysymetrii.

Relacja równoległości prostych na płaszczyźnie jest relacją równoważności.

Relacje przystawania i podobieństwa są relacjami równoważności.

Relacja równoważności ma działać jak uogólnienie równości, tzn. obiekty równoważne mają być „takie same z jakiegoś punktu widzenia”. Tak jest w podanych wyżej przykładach: w przypadku równoległości prostych relacja ustala równoważność prostych, które mają ten sam kierunek, a w przypadku podobieństwa trójkątów relacja utożsamia trójkąty, które są podobne. Przy takim rozumieniu równoważności podane wymagania, czyli zwrotność, symetria i przechodniość są dość naturalne.

Ważną cechą relacji równoważności jest to, że dzieli ona zbiór X na rozłączne podzbiory (zwane klasami abstrakcji) składające się z elementów, które są ze sobą w relacji. Zbiór składający się z klas abstrakcji oznaczamy symbolem X /∼ .

O zbiorze X /∼ myślimy jak o zbiorze mniejszym od X . Tak jest, bo tworząc X/∼ sklejamy wszystkie elementy zbioru X będące w relacji w jeden element zbioru X /∼ .


ZINFO-FIGURE

Powyższy schematyczny rysunek przedstawia zbiór X podzielony na 6 klas abstrakcji pewnej relacji równoważności „∼ ”. W takiej sytuacji zbiór X /∼ składa się z sześciu elementów.

Relacja „ten sam wzrost w cm” jest relacją równoważności w zbiorze wszystkich ludzi. Podobne relacje to np. „ten sam kolor oczu”, „wspólny pradziadek”, „to samo pierwsze imię”, „ten sam dzień urodzenia”. Każda z tych relacji dokonuje podziału zbioru wszystkich ludzi na klasy abstrakcji ze względu na interesującą nas cechę.

Jeżeli „∼ ” jest relacją „∥ ” równoległości prostych na płaszczyźnie, to zbiory elementów będących w relacji (czyli klasy abstrakcji tej relacji) to po prostu zbiory prostych, które są wzajemnie równoległe. Zbiorów tych jest tyle, ile możliwych kierunków na płaszczyźnie. Dlatego o zbiorze X/∼ myślimy jak o zbiorze kierunków.

Spróbujmy na poprzedni przykład popatrzeć z drugiej strony. Zastanówmy się co to jest kierunek prostej? Trudno powiedzieć, co to dokładnie jest, ale wiemy, że niektóre proste mają ten sam kierunek, np. y = x , y = x + 5 , y = −x + 3 . I taki właśnie jest pomysł na definicję kierunku: jeden kierunek to coś, co mają wspólnego ze sobą proste y = x , y = x + 5 , y = −x + 3 i wszystkie inne o współczynniku kierunkowym ± 1 , inny kierunek to coś, co mają ze sobą wspólnego wszystkie proste o współczynniku ± 2 itd. Jeżeli teraz popatrzycie na opis zbioru X/∼ powyżej to powinno być jasne, że jest to sposób na precyzyjną definicję zbioru kierunków na płaszczyźnie.
Przykład ten jest dość abstrakcyjny, ale dokładnie taka jest rola relacji równoważności i klas abstrakcji: pozwalają one precyzyjnie definiować abstrakcyjne pojęcia (kierunek w tym przypadku).

Jeżeli X jest zbiorem trójkątów na płaszczyźnie, a „∼ ” relacją podobieństwa, to jak wyobrazić sobie zbiór X/∼ ? Tworząc zbiór X /∼ utożsamiamy ze sobą wszystkie trójkąty podobne, więc o zbiorze X /∼ możemy myśleć jak o zbiorze wszystkich możliwych kształtów trójkątów. Np. trójkątowi równobocznemu odpowiada dokładnie jeden element zbioru X /∼ pomimo, że w zbiorze X (na płaszczyźnie) jest nieskończenie wiele trójkątów równobocznych.
Gdybyśmy zamiast podobieństwa wzięli relację przystawania, to zbiór X /∼ byłby zbiorem wszystkich możliwych kształtów z uwzględnieniem rozmiaru.

Ustalmy liczbę naturalną n ∈ N . W zbiorze liczb całkowitych Z wprowadzamy relację „∼ ” wzorem

x ∼ y ⇐ ⇒ n|x− y.

Mówiąc po ludzku: dwie liczby są w relacji wtedy i tylko wtedy, gdy dają tę samą resztę z dzielenia przez n . Zbiór Z /∼ składa się n elementów, które możemy wypisać:

{... − n, 0, n, 2n , 3n , ...} {... − n + 1, 1, n+ 1, 2n + 1, 3n + 1,...} {... − n + 2, 2, n+ 2, 2n + 2, 3n + 2,...} ... {... − n + (n − 1), n − 1, n + (n − 1), 2n + (n − 1), 3n + (n − 1),...}.

Zbiór Z /∼ oznaczamy symbolem Zn i jest to zbiór reszt z dzielenia przez n .

Jeżeli przejrzycie swoje podręczniki do matematyki to okaże się, że nie znajdziecie w nich definicji liczb wymiernych. Tak jest, bo definicja ta wymaga użycia relacji równoważności. Mówiąc dokładniej, liczb wymiernych nie można zdefiniować jako napisów postaci pq , gdzie p ,q ∈ Z,q ⁄= 0 , bo przecież każda liczba wymierna może być w ten sposób napisana na nieskończenie wiele różnych sposobów. Np. czym jest 1 2 ? Napisem 1 2 ? A może jednym z napisów

2, 3, 4,...? 4 6 8

Problem w tym przypadku jest podobny jak z definicją kierunku na płaszczyźnie: to co chcemy zdefiniować jest abstrakcyjne: ma to być „połowa całości”, a nie ten czy inny napis. Jak w takim razie zdefiniować połowę? – skoro jest to cecha wspólna wszystkich powyższych ułamków, to definiujemy 1 2 jako wszystkie te ułamki na raz.
Mówiąc bardziej precyzyjnie, w zbiorze X napisów postaci pq , gdzie p ,q ∈ Z,q ⁄= 0 (jeżeli ktoś się zastanawia co to jest „zbiór napisów”, to jest to zbiór par (p,q) pisanych w taki oryginalny sposób) wprowadzamy relację „∼ ” w następujący sposób: napisy p q i s t są w relacji „∼ ” wtedy i tylko wtedy, gdy pt = qs (jest to znany nam dobrze warunek równości ułamków). Można teraz sprawdzić, że „∼ ” jest relacją równoważności oraz z definicji Q = X /∼ .

W tym miejscu powinniście już mniej więcej kojarzyć czym są klasy abstrakcji, więc możemy sobie pozwolić na małe porządki w notacji. Wiemy, że każdemu elementowi x ∈ X odpowiada element zbioru X /∼ (jego klasa abstrakcji). Element ten oznaczamy symbolem [x ]∼ lub krótko [x] . Zbiór [x ] jest więc zbiorem wszystkich elementów zbioru X , które są w relacji z x . W takiej sytuacji mówimy, że x jest reprezentantem klasy abstrakcji [x] . Oczywiście klasa abstrakcji może mieć wiele różnych reprezentantów, jeżeli np. x ∼ y to [y] = [x] , więc y też jest reprezentantem klasy [x ] = [y ] .

Jeżeli „∼ ” jest relacją równoległości prostych na płaszczyźnie to klasa [y = 3x+ 1] oznacza zbiór wszystkich prostych na płaszczyźnie ze współczynnikiem kierunkowym ± 3 . Oczywiście ten sam zbiór możemy zapisać na wiele różnych sposobów, np.

[y = 3x + 1] = [y = − 3x− 1] = [y = 3x + 5].

Każda z prostych y = 3x + 1 , y = − 3x − 1 , y = 3x + 5 jest reprezentantem powyższej klasy abstrakcji (kierunku).

Ciągłe odróżnianie elementów od klas abstrakcji jest niewygodne, więc bardzo często pomijamy nawiasy [] i piszemy x zamiast [x] (choć są to dwie różne rzeczy).

Definiując liczby wymierne zdefiniowaliśmy „połowę” jako zbiór wszystkich ułamków postaci

{ } 1, −-1, 2, −-2, 3-,... . 2 − 2 4 − 4 6

Formalnie „połowę” powinniśmy więc oznaczać jednym z symboli: [ ] 12 , [3] 6 ,... . Tak jednak nie robimy i piszemy krótko 1 3 2, 6,... Zapis 1 3 2 = 6 należy więc rozumieć jako skrót zapisu [ ] 1 = [ 3] 2 6 .
W pewnym sensie jest to duże osiągnięcie matematyki, że możemy posługiwać się symbolami ułamków nie wiedząc nawet co one oznaczają. .

Formalnie zbiór Z 3 składa się z trzech elementów

{...− 9, −6 , − 3, 0, 3, 6, 9...} {...− 8, −5 , − 2, 1, 4, 7, 10...} {...− 7, −4 , − 1, 2, 5, 8, 11...}.

Napisy [− 3],[1],[8] są jednak niewygodne, więc wolelibyśmy pisać po prostu 3 ,−1 ,8 . Jest z tym jednak kłopot, bo np. napis [− 5] = [7] (który oznacza po prostu, że obie liczby dają tę samą resztę z dzielenia przez 3) zamienia się na − 5 = 7 , co nie wygląda zbyt dobrze. Z tego powodu używa się specjalnej notacji: zamiast [− 5] = [7 ] piszemy

− 5 ≡ 7 (m od 3)

(czytamy − 5 przystaje do 7 modulo 3). Czasami pisze się też krótko − 5 ≡ 7 3 .

Powyżej wyświetlona jest tylko pierwsza część poradnika. Druga część jest dostępna tylko dla użytkowników z wykupionym abonamentem.
Nie chcesz się rejestrować ani opłacać abonamentu? Zapłać przelewem 7,90 zł lub telefonicznie 9,90 zł, a otrzymasz dwudziestominutowy dostęp do wszystkich materiałów dostępnych w portalu.
spinner