Informatyka MIMUW

Zwrotność i symetria $\displaystyle \sim$ są trywialne. Przy dowodzie przechodniości zastosuj prawo skracania (patrz Ćwiczenie 1.8) dla liczb całkowitych.

Zwrotność relacji $\displaystyle \sim$ wynika z faktu, że dla dowolnych liczb całkowitych mamy $\displaystyle a\cdot b = a\cdot b$.

Dla dowodu symetrii załóżmy, że $\displaystyle (a,b) \sim (c,d)$. Wtedy $\displaystyle a\cdot d = c\cdot b$, czyli $\displaystyle c\cdot b=a\cdot d$, co oznacza, że $\displaystyle (c,d)\sim (a,b)$. Wykazaliśmy symetrię relacji $\displaystyle \sim$.

Aby dowieść przechodniości, ustalmy trzy dowolne elementy $\displaystyle \mathbb{Z} \times \mathbb{Z}^*$ spełniające $\displaystyle (a,b) \sim (c,d)$ oraz $\displaystyle (c,d)\sim(e,f)$. Wtedy $\displaystyle a\cdot d = c\cdot b$ oraz $\displaystyle c\cdot f = e\cdot d$, używając przemienności i łączności {Dowód łączności mnożenia liczb całkowitych zostawiamy zainteresowanym czytelnikom.} mnożenia liczb całkowitych, otrzymujemy: $\displaystyle a\cdot d\cdot f = c\cdot b\cdot f = e\cdot b\cdot d$. Korzystając z prawa skracania dla liczb całkowitych, korzystając z założenia, że $\displaystyle d\neq 0$, dostajemy: $\displaystyle a\cdot f = e\cdot b$, czyli: $\displaystyle (a,b)\sim (e,f)$, co należało wykazać.

Po pierwsze zauważmy, że $\displaystyle \bigcup\bigcup [(a,b)]_{\sim} = \{c\in\mathbb{Z}:\exists d\; (a,b)\sim (c,d) \lor (a,b)\sim (d,c) \}$. Niewątpliwie musimy więc mieć $\displaystyle (0,d)\sim(a,b)$ dla pewnego $\displaystyle d\in\mathbb{Z}$ (gdyż $\displaystyle 0$ nie może występować na drugiej współrzędnej). Definicja relacji $\displaystyle \sim$ implikuje, że $\displaystyle 0\cdot b = d\cdot a$, czyli że $\displaystyle a=0$. Co więcej dla dowolnej liczby całkowitej $\displaystyle c$ mamy $\displaystyle (0,d)\sim(0,c)$, ponieważ $\displaystyle 0\cdot c = 0\cdot d$. Tak więc jedyną klasą równoważności relacji $\displaystyle \sim$ spełniającą nasz warunek jest zbiór:

$\displaystyle \{(0,d): d\in\mathbb{Z}\setminus\{0\}\},$ który zostanie później nazwany "zerem" liczb wymiernych.

Zapisz, w jaki sposób wynik działań jest niezależny od wyboru reprezentantów.

Pierwszym działaniem, które może zależeć od reprezentantów wybranych z klasy równoważności jest branie elementu przeciwnego. Załóżmy, że $\displaystyle (a,b)\sim (c,d)$. Wtedy $\displaystyle ad=cb$ i korzystając z własności liczb całkowitych {Tylko niektóre z niezbędnych własności liczb całkowitych zostały wykazane we wcześniejszej części wykładu. Pozostawiamy dociekliwym czytelnikom możliwość dowiedzenia wszystkich faktów niezbędnych do rozumowań na liczbach wymiernych}, $\displaystyle (-1)\cdot a\cdot d = (-1)\cdot c \cdot b$ i dalej $\displaystyle -a\cdot d = -c\cdot b$, czyli $\displaystyle [(-a,b)]_{\sim}=[(-c,d)]_{\sim}$, co należało wykazać.

Aby dowieść niezależności dodawania ustalmy cztery elementy $\displaystyle \mathbb{Z}\times\mathbb{Z}^*$ takie, że $\displaystyle (a,b)\sim (e,f)$ oraz $\displaystyle (c,d)\sim(g,h)$. Natychmiast wnioskujemy, że $\displaystyle a\cdot f = e\cdot b$ oraz $\displaystyle c\cdot h = g\cdot d$ i dalej

$\displaystyle a\cdot f \cdot d \cdot h = e \cdot b \cdot d \cdot h \text{ oraz } c \cdot h \cdot b \cdot f = g \cdot d \cdot b \cdot f.$

Sumując obie równości i wyłączając wspólne czynniki, otrzymujemy:

$\displaystyle (f\cdot h)\cdot (a\cdot d + c\cdot b) = (b\cdot d)\cdot ( e\cdot h + g\cdot f),$

czyli: $\displaystyle (a\cdot d + c\cdot b, b\cdot d)\sim ( e\cdot h + g\cdot f, f\cdot h)$ i dalej:

$\displaystyle [(a,b)]_{\sim}+[(c,d)]_{\sim} = [(a\cdot d + c\cdot b,b\cdot d)]_{\sim} = [(e\cdot h + g\cdot f,f\cdot h)]_{\sim} = [(e,f)]_{\sim} + [(g,h)]_{\sim},$

co należało wykazać.

Niezależność odejmowania jest bezpośrednią konsekwencją faktów dowiedzionych powyżej. Wystarczy zauważyć, że $\displaystyle [(a,b)]_{\sim}-[(c,d)]_{\sim} = [(a,b)]_{\sim}+ (-[(c,d)]_{\sim})$, co wynika wprost z definicji odejmowania. Ponieważ dodawanie i znajdowanie elementu przeciwnego są niezależne od wyboru reprezentantów z klas, to również ich złożenie jest od niego niezależne - czego należało dowieść.

Dla dowodu mnożenia ustalmy cztery elementy $\displaystyle \mathbb{Z}\times\mathbb{Z}^*$ takie, że $\displaystyle (a,b)\sim (e,f)$ oraz $\displaystyle (c,d)\sim(g,h)$. Z założeń wnioskujemy, że $\displaystyle af = be$ oraz że $\displaystyle ch = dg$. W związku z tym $\displaystyle afch = bedg$ i korzystając z przemienności i łączności mnożenia liczb całkowitych $\displaystyle (ac,bd)\sim (eg,fh)$, czyli:

$\displaystyle [(a,b)]_{\sim}\cdot[(c,d)]_{\sim} = [(ac,bd)]_{\sim} =[(eg,fh)]_{\sim}=[(e,f)]_{\sim}\cdot[(g,h)]_{\sim},$

co należało wykazać.

Dla dowodu dzielenia zauważmy, że dla dowolnego $\displaystyle (c,d)\sim(g,h)$ ($\displaystyle c,g$ różne od $\displaystyle 0$) mamy $\displaystyle (d,c)\sim(h,g)$, ponieważ oba fakty są równoważne $\displaystyle ch=gd$ (korzystając z przemienności mnożenia liczb całkowitych). W związku z tym "zamiana miejscami" nie zależy od wyboru reprezentanta klasy równoważności. Zauważmy, że $\displaystyle [(a,b)]_{\sim}:[(c,d)]_{\sim} =[(a,b)]_{\sim}\cdot[(d,c)]_{\sim}$ i ponieważ założyliśmy $\displaystyle c\neq 0$, to dzielenie jest złożeniem dwóch operacji niezależnych od wyboru reprezentantów dla klas równoważności - co należało wykazać.

Do dowodu zastosuj własności dodawania, mnożenia i odejmowania liczb całkowitych.

Ustalmy dowolne $\displaystyle \frac{a}{b}\geq \frac{c}{d}$. Wtedy $\displaystyle (a\cdot d - b \cdot c) \cdot b \cdot d \geq 0$ jest równoważne $\displaystyle ((a\cdot d - b \cdot c)\cdot 1 -(b\cdot d)\cdot 0 )\cdot( b \cdot d)\cdot 1 \geq 0$, co z kolej znaczy, że $\displaystyle \frac{a}{b}-\frac{c}{d}\geq\frac{0}{1}$. Ponieważ wykazaliśmy wcześniej, że odejmowanie liczb wymiernych nie zależy od wyboru reprezentantów dla klasy, pozostaje wykazać, że dla $\displaystyle \frac{a}{b}=\frac{e}{f}$ mamy $\displaystyle \frac{a}{b}\geq\frac{0}{1}$ wtedy i tylko wtedy, kiedy $\displaystyle \frac{e}{f}\geq\frac{0}{1}$. Pierwsza nierówność jest prawdą wtedy i tylko wtedy, kiedy $\displaystyle (a\cdot 1 - b\cdot 0)\cdot b\cdot 1=a\cdot b\geq 0$, a druga, kiedy $\displaystyle e\cdot f \geq 0$. W świetle założenia mówiącego, że $\displaystyle \frac{a}{b}=\frac{e}{f}$, czyli że $\displaystyle a\cdot f = b\cdot e$, równoważność otrzymujemy przez analizę dodatniości $\displaystyle a,b,e$ i $\displaystyle f$.

Do dowodu zastosuj własności dodawania liczb całkowitych i porządku dla liczb całkowitych.

Zwrotność porządku na liczbach wymiernych jest trywialna. Nierówność $\displaystyle \frac{a}{b}\geq\frac{a}{b}$ oznacza $\displaystyle (ab-ba)bb\geq 0$, co jest zawsze prawdą.

Dla dowodu antysymetrii załóżmy, że $\displaystyle \frac{a}{b}\geq\frac{c}{d}$ oraz $\displaystyle \frac{c}{d}\geq \frac{a}{b}$. Wtedy $\displaystyle (ad-bc)bd\geq 0$ i $\displaystyle (cb-da)db\geq 0$. Ponieważ definicja liczb wymiernych gwarantuje, że $\displaystyle db\neq 0$, to $\displaystyle ad-bc=0$, czyli $\displaystyle ad=bc$, co jest definicją równości: $\displaystyle \frac{a}{b}=\frac{c}{d}$. Antysymetria jest pokazana.

Aby pokazać przechodniość, wybierzmy trzy liczby wymierne $\displaystyle \frac{a}{b}\geq\frac{c}{d}\geq\frac{e}{f}$. Z założeń wynika, że $\displaystyle (ad-bc)bd\geq 0$ oraz $\displaystyle (cf-de)df\geq 0$. Wnioskujemy, że

$\displaystyle adbd\geq bcbd$ oraz $\displaystyle cfdf\geq dedf,$ mnożąc nierówności przez, odpowiednio $\displaystyle ff$ i $\displaystyle bb$ (założenia gwarantują $\displaystyle f\neq 0\neq b$), otrzymujemy:

$\displaystyle adbdff\geq bcbdff$ oraz $\displaystyle cfdfbb\geq dedfbb$

i korzystając z przechodniości nierówności $\displaystyle adbdff\geq dedfbb$, co możemy przekształcić do $\displaystyle (af-be)bfdd\geq 0$. Ponieważ założenia gwarantują, że $\displaystyle d\neq 0$, to $\displaystyle (af-be)bf\geq 0$, czyli $\displaystyle \frac{a}{b}\geq\frac{e}{f}$, co należało pokazać.

Pozostała nam do wykazania spójność porządku. Bardzo łatwo zauważyć, że dla dwóch liczb wymiernych $\displaystyle \frac{a}{b}$ i $\displaystyle \frac{c}{d}$ mamy $\displaystyle (ad-bc)bd\geq 0$ lub $\displaystyle (bc-ad)db\geq 0$, co kończy dowód spójności.

Rozważ przypadki, kiedy obie liczby są dodatnie, obie ujemne, jedna dodatnia, a druga ujemna. W każdym z przypadków rozumowanie jest trywialne.

Dowód przeprowadzimy, wprowadzając podobną notację dla liczb całkowitych. Jeśli uda nam się zdefiniować funkcję moduł w ten sposób, że $\displaystyle | n+k | \leq | n | + | k |$, $\displaystyle | nk | = | n | | k |$, $\displaystyle | n | \geq 0$, dla dowolnych liczb całkowitych oraz $\displaystyle | \frac{a}{b} | =\frac{ | a | }{ | b | }$, to:

$\displaystyle | \frac{a}{b}+\frac{c}{d} | = | \frac{ad+bc}{bd} | = \frac{ | ad+bc | }{ | bd | }$

oraz:

$\displaystyle | \frac{a}{b} | + | \frac{c}{d} | = \frac{ | a | }{ | b | }+\frac{ | c | }{ | d | } = \frac{ | a | | d | + | b | | c | }{ | b | | d | }.$

Żądana nierówność będzie prawdą, jeśli uda nam się wykazać, że: <

div class="center">$\displaystyle [( | a | | d | + | b | | c | ) | bd | - | ad+bc | | b | | d | ] | b | | d | | bd | \geq 0,$

ale korzystając z właściwości modułu dla liczb całkowitych (które wkrótce wykażemy), przekształcamy wzór do:

$\displaystyle [( | ad | + | bc | - | ad+bc | ] | b | | c | | b | | d | | b | | d | \geq 0$

i ponieważ $\displaystyle | b |$ i $\displaystyle | d |$ są stale większe od zera, a $\displaystyle | ad | + | bc | \geq | ad+bc |$ w liczbach całkowitych, nierówność jest dowiedziona.

Pozostaje zdefiniować funkcję moduł w liczbach całkowitych. Definiujemy ją jako: $\displaystyle | [(n,k)]_{\approx} | = [(l,0)]_{\approx}$, gdzie $\displaystyle l$ jest unikalną liczbą naturalną taką, że $\displaystyle [(n,k)]_{\approx}=[(l,0)]_{\approx}$ lub $\displaystyle [(n,k)]_{\approx}=[(0,l)]_{\approx}$. Liczba taka istnieje na podstawie Ćwiczenia 1.3 i jest unikalna, ponieważ $\displaystyle [(l,0)]_{\approx}=[(0,p)]_{\approx}$ implikuje $\displaystyle p=l=0$, a $\displaystyle [(l,0)]_{\approx}=[(p,0)]_{\approx}$ implikuje $\displaystyle p=l$. Pozostaje wykazać wymagane fakty o funkcji moduł.

Ustalmy dwie liczby całkowite $\displaystyle [(n,k)]_{\approx}$ i $\displaystyle [(l,m)]_{\approx}$ - wykażemy, że $\displaystyle | [(n,k)]_{\approx} +[(l,m)]_{\approx} | \leq | [(n,k)]_{\approx} | + | [(l,m)]_{\approx} |$. Ponieważ zarówno dodawanie, jak i porządek nie zależą od wyboru reprezentantów dla klas równoważności, możemy założyć, że $\displaystyle n=0$ lub $\displaystyle k=0$ (i równocześnie $\displaystyle l=0$ lub $\displaystyle m=0$). Jeśli $\displaystyle k=0$ oraz $\displaystyle m=0$, to mamy $\displaystyle | [(n,k)]_{\approx} | = [(n,k)]_{\approx}$ oraz $\displaystyle | [(l,m)]_{\approx} | =[(l,m)]_{\approx}$ i nierówność jest prawdziwa. Jeśli z kolei $\displaystyle n=0$ i $\displaystyle l=0$, to:

$\displaystyle | [(n,k)]_{\approx} +[(l,m)]_{\approx} | = | [(0,k+m)]_{\approx} | = [(k+m,0)]_{\approx} =[(k,0)]_{\approx}+[(m,0)]_{\approx} = | [(0,k)]_{\approx} | + | [(0,m)]_{\approx} |$

i nierówność znowu jest spełniona. Pozostają dwa symetryczne przypadki. Bez straty ogólności możemy założyć, że $\displaystyle n=0$ i $\displaystyle m=0$. Wtedy $\displaystyle | [(n,k)]_{\approx} +[(l,m)]_\approx} | = | [(l,k)]_{\approx} |$ jest niewątpliwie mniejszy od $\displaystyle | [(k,n)]_{\approx} | + | [(l,m)]_{\approx} | = [(l+k,0)]_{\approx}$, ponieważ zgodnie z definicją modułu pierwsza współrzędna $\displaystyle | [(l,k)]_{\approx} |$ jest mniejsza lub równa większej z liczb $\displaystyle k$, $\displaystyle l$, która jest z kolei mniejsza lub równa $\displaystyle l+k$.

Aby dowieść, że w liczbach całkowitych moduł jest rozdzielny względem mnożenia, ustalmy dwie liczby $\displaystyle [(n,k)]_{\approx}$ i $\displaystyle [(l,m)]_{\approx}$ i, podobnie jak poprzednio, załóżmy, że że $\displaystyle n=0$ lub $\displaystyle k=0$ (i równocześnie $\displaystyle l=0$ lub $\displaystyle m=0$). Wtedy $\displaystyle [(n,k)]_{\approx}\cdot[(l,m)]_{\approx} = [(nl+km,lk+mn)]_{\approx}$, gdzie co najwyżej jeden z czterech sumandów jest niezerowy. Moduł otrzymanej liczby będzie liczbą całkowitą posiadającą na pierwszej współrzędnej ten właśnie sumand, a na drugiej zero. Równocześnie $\displaystyle | [(n,k)]_{\approx} | \cdot | [(l,m)]_{\approx} |$ będzie posiadał na pierwszej współrzędnej dokładnie ten sumand, a na drugiej zero, co dowodzi żądanej równości.

Aby dowieść, że $\displaystyle | [(n,k)]_{\approx} | \geq 0$, wystarczy zauważyć, że druga współrzędna pary reprezentującej liczbę jest równa zero i w związku z tym warunek nierówności jest zawsze spełniony.

Pozostaje wykazać, że $\displaystyle | \frac{a}{b} | =\frac{ | a | }{ | b | }$. Rozważmy dwa przypadki: jeśli $\displaystyle \frac{a}{b}\geq 0$, to $\displaystyle | \frac{a}{b} | = \frac{a}{b}$. W tym przypadku nierówność implikuje, że $\displaystyle (a1-b0)b1\geq 0$, czyli że $\displaystyle a$ i $\displaystyle b$ są liczbami całkowitymi tego samego znaku. To znaczy, że posiadają reprezentacje postaci $\displaystyle [(n,0)]_{\approx}$ i $\displaystyle [(k,0)]_{\approx}$ (lub $\displaystyle [(0,n)]_{\approx}$ i $\displaystyle [(0,k)]_{\approx}$). Wnioskujemy, że $\displaystyle a\cdot | b | = b\cdot | a |$, czyli $\displaystyle \frac{a}{b} = \frac{ | a | }{ | b | }$, co należało wykazać. W drugim przypadku mamy $\displaystyle \frac{a}{b} < 0$, czyli $\displaystyle (a1-b0)b1 < 0$, więc znaki $\displaystyle a$ i $\displaystyle b$ są przeciwne (posiadają reprezentacje $\displaystyle [(n,0)]_{\approx}$ i $\displaystyle [(0,k)]_{\approx}$ lub na odwrót). Wtedy mamy $\displaystyle | \frac{a}{b} | = \frac{-a}{b}$ i znowu $\displaystyle -a\cdot | b | = b\cdot | a |$ jest prawdą. Wykazaliśmy, że moduł zdefiniowany w liczbach wymiernych jest zgodny z modułem dla liczb całkowitych, co było ostatnim brakującym faktem w dowodzie.

Pamiętaj, że znaki działań i porządku (oraz $\displaystyle 0$ i $\displaystyle 1$) po prawej i po lewej stronie równości znaczą co innego. Zapisz każde z powyższych praw, ujawniając strukturę liczb wymiernych. Zauważ, że w dowodzie będą interweniowały udowodnione już prawa łączności, przemienności, prawo skreśleń i skracania oraz własności porządkowe dla liczb całkowitych.

Włożenie $\displaystyle j$ przekształca $\displaystyle 0$ w $\displaystyle 0$ i $\displaystyle 1$ w $\displaystyle 1$, co jest trywialną konsekwencją definicji funkcji $\displaystyle j$.

Aby wykazać, że włożenie jest zgodne z dodawanie, ustalmy dwie dowolne liczby całkowite $\displaystyle a$ i $\displaystyle b$. Wtedy, $\displaystyle j(a+b)= [(a+b,1)]_{\sim}=[((a1+1b)11,11)]_{\sim} = [(a,1)]_{\sim} +[(b,1)]_{\sim} = j(a) + j(b)$, co należało wykazać.

Dla dowodu różnicy ustalmy ponownie $\displaystyle a$ i $\displaystyle b$, wtedy $\displaystyle j(a-b)=[(a-b,1)]_{\sim}=[((a1-1b)11,11)]_{\sim} = [(a,1)]_{\sim} -[(b,1)]_{\sim} = j(a) - j(b)$, co kończy dowód podobnie jak w poprzednim przypadku.

Dla dowodu iloczynu, ustalmy znów $\displaystyle a$ i $\displaystyle b$, mamy $\displaystyle j(a\cdot b) = [(ab,1)]_{\sim} = [(ab,11)]_{\sim} = [(a,1)]_{\sim}\cdot[(b,1)]_{\sim} = j(a)\cdot j(b)$, co dowodzi wymaganego faktu.

Dla dowodu zgodności z porządkiem załóżmy, że $\displaystyle a\leq b$ wtedy $\displaystyle b-a\geq 0$ i dalej $\displaystyle (b1-1a)11\geq 0$, co oznacza, że $\displaystyle [(b,1)]_{\sim}\geq[(a,1)]_{\sim}$.