[important_sample]

Relacje i konstrukcja liczb wymiernych

#matematyka #ciekawostki #popularnonaukowe #gruparatowaniapoziomu

(Poprzedni wpis o wektorach. W komentarzach bonus o przestrzeniach dualnych i kwaternionach)

Zanim zdefiniuję czym jest relacja (odpowiednio zdefiniowaną relację wykorzystamy w konstrukcji), przypomnę podstawowe pojęcie z teorii zbiorów, żeby wpis był bardziej dostępny.

Iloczynem kartezjańskim zbiorów A×B nazywamy zbiór uporządkowanych par (a, b) takich, że a∊A oraz b∊B. Kolejność elementów jest istotna i (a, b) ≠ (b, a). Dla przykładu, niech A={1, 2} i B={a, b} wtedy A×B={(1, a), (1, b), (2, a), (2, b)}. Znanym przykładem zastosowania takiej konstrukcji jest układ współrzędnych: R^2 = R×R.

Relacją (binarną) R na zbiorze A nazywamy podzbiór iloczynu kartezjańskiego A×A, czyli R⊆A×A. Elementy zbioru x, y są ze sobą w relacji, jeśli para (x, y) należy do relacji, czyli do podzbioru R: (x, y)∊R. Często zapisuje się to za pomocą notacji infiksowej: xRy. Dla przykładu, możemy zdefiniować dla zbioru liczb A={1, 2, 3, 4} relację R "mają taką samą resztę z dzielenia przez 2". Wtedy R={(1, 1), (1, 3), (3, 1), (3, 3), (2, 4), (2, 2), (4, 2), (4, 4)}. Przykładem binarnej relacji są funkcje.

Definicja relacji jest dosyć ogólna, ale wiele przydanych relacji ma pewne własności. Do nich mogą należeć:
* zwrotność - każdy element jest w relacji z samym sobą: xRx
* symetryczność - jeśli 'x' jest w relacji z 'y' to 'y' jest w relacji z 'x': xRy -> yRx
* przechodniość - jeśli 'x' jest w relacji z 'y' a 'y' z 'z' to 'x' jest w relacji z 'z': xRy i yRz -> xRz
* antysymetryczność - jeśli 'x' jest w relacji z 'y' i jednocześnie 'y' jest w relacji z 'x' to 'x' oraz 'y' muszą być tymi samymi elementami: xRy i yRx -> x=y

Relacje równoważności to takie relacje, które są zwrotne, symetryczne i przechodnie. W pewnym sensie są one uogólnieniem relacji równości - można sprawdzić, że równość spełnia wszystkie te założenia. Zwykle relacje równoważności oznacza się symbolem ~ i zapisuje na przykład x~y. Podany wcześniej przykład relacji "mają taką samą resztę dzielenia przez 2" jest relacją równoważności. Innym przykładem może być równoległość prostych w przestrzeni Euklidesa.

Można również zdefiniować relację będącą uogólnieniem ≤, taką relację nazywamy relacją częściowego porządku. Spełnia ona własności zwrotności, przechodniości oraz antysymetryczności. Symbolem takich relacji jest często ≼. Przykładem może być zawieranie się zbiorów. Zbiór wyposażony w relację częściowego porządku (S, ≼) nazywamy zbiorem częściowo uporządkowanym (ang. poset od partially ordered set - fajna nazwa).

No dobrze to teraz przejdźmy do sedna, czyli konstrukcji liczb wymiernych. Weźmy zbiór Z×Z, czyli pary liczb całkowitych, np. (-1, 3). Elementy tego zbioru będziemy rozumieć jako ułamki, czyli (a,b) to a/b. Niestety obecnie ułamki, które reprezentują taką samą wartość to różne elementy, np. (1, 2) i (2, 4), które reprezentują kolejno 1/2 i 2/4 rozumiemy jako osobne elementy. Naprawimy to definiując odpowiednią relację równoważności.

Niech (a,b)~(c,d) jeśli ad = cb. Motywacją za taką definicją jest to, że chcemy aby te same ułamki były ze sobą równoważne, czyli jeśli a/b = c/d to ma zachodzić relacja równoważności. Niestety dzielenie nie jest zdefiniowane dla zbioru liczb całkowitych, więc zamiast tego wykorzystujemy równoważną równość, którą uzyskujemy mnożąc obie strony równania razy bd.

Możemy sprawdzić, że tak zdefiniowana relacja spełnia wszystkie własności relacji równoważności:
* zwrotność: (a,b)~(a,b) bo ab = ab
* symetryczność: Niech (a,b)~(c,d), więc ad = cb. Równość jest symetryczna, więc cb=ad, więc (c, d)~(a, b).

Przechodniość pozostawiam jako ćwiczenie ( ͡° ͜ʖ ͡°)

Teraz zdefiniujemy klasę abstrakcji relacji. Skoro wiele elementów zbioru uznajemy za równoważne, chcielibyśmy móc wszystkie te elementy opisywać jednym symbolem, którym będzie właśnie klasa abstrakcji. Klasą abstrakcji elementu x, oznaczaną [x], nazywamy więc zbiór wszystkich elementów, którą są w relacji z elementem 'x', czyli [x] = {y ∊ S : x~y}, gdzie S to zbiór, na którym zdefiniowana jest relacja. Element x klasy abstrakcji [x] nazywamy jego reprezentantem.

Dla naszego przykładu liczb wymiernych mamy: [(1, 2)] = {(1, 2), (2, 4), (4, 8), (-1, -2), ...}. Zbiór ten zawiera wszystkie zapisy ułamków, które równe są 1/2. Można dowieść, że klasy abstrakcji dowolnej relacji równoważności się nie przecinają, to znaczy, że jeśli jakiś element należy do 2 klas abstrakcji, to te klasy abstrakcji są sobie równe. Dodatkowo, cały zbiór może zostać podzielony na takie klasy.

Zbiorem wszystkich klas abstrakcji nazywamy zbiór ilorazowy relacji, oznaczany S/~.

No i tak dochodzimy do kluczowego wyniku z tego wpisu: Q = Z×Z/~. Oznacza to, że zbiór liczb wymiernych to zbiór ilorazowy relacji ~ par liczb całkowitych. Działania dodawania oraz mnożenia zdefiniowane są w naturalny sposób, czyli tak samo jak dla ułamków.

Na ogół, pracując przy zbiorach ilorazowych wypada pokazać, że działania na elementach są dobrze zdefiniowane co znaczy, że ich wynik nie jest zależny od wyboru reprezentanta klasy abstrakcji: wynik działania musi znajdować się w takiej samej klasie abstrakcji co wynik tego samego działania, wykonanego na innych elementach klasy, np. (1, 2) + (3, 2) powinno dać taki sam wynik co (2, 4) + (3, 2), ale wiemy że tak będzie bo ułamki tak działają ( ͡º ͜ʖ͡º)

Jako ćwiczenie można spróbować wykonać analogiczną konstrukcję liczb całkowitych, korzystając z liczb naturalnych.

[d.....o]

@important_sample wakacje się zaczynają ojciec

[important_sample]

@dean_corso: synek na naukę to ty zawsze powinieneś mieć czas ojciec jak był w twoim wieku to ciała skończone konstruował z twoja matką myślisz że syn sąsiada odpoczywa?? potem cię wygryzie bo on to się uczy a ty tylko w te gierki grasz skończysz w starym zakładzie wujka bogdana jak się nie będziesz uczył ヽ( ͠°෴ °)ﾉ

[d.....o]

@important_sample 48 lvl here mirku

[important_sample]

@dean_corso: A to przepraszam bardzo, proszę Pana! ( ͡° ͜ʖ ͡°)