Liczby całkowite

W poprzednim wykładzie skonstruowaliśmy przy pomocy aksjomatu nieskończoności liczby naturalne. Określiliśmy dla nich podstawowe operacje, takie jak dodawanie i mnożenie. Teraz własności tych operacji będą użyte do dalszych konstrukcji liczbowych. Pokażemy, że mając liczby naturalne zbudowane na bazie liczby

$\displaystyle 0$ , czyli zbioru pustego, możemy definiować bardziej skomplikowane twory liczbowe takie, jak liczby całkowite, wymierne i w końcu liczby rzeczywiste. Wszystkie te obiekty mają ogromne zastosowanie w praktyce matematycznej i informatycznej. Będziemy później w innych wykładach odwoływać się do niebanalnej reprezentacji tych obiektów, które stworzymy w tym rozdziale.

Konstrukcja liczb całkowitych

Definicja 1.1.

Niech $\displaystyle \approx$ będzie relacją określoną na $\displaystyle \mathbb{N} \times \mathbb{N}$ następująco:

$\displaystyle (n,k)\approx (p,q)$ wtw $\displaystyle n+q = k+p.$

Ćwiczenie 1.2

Relacja $\displaystyle \approx$ jest relacją równoważności o polu $\displaystyle \mathbb{N} \times \mathbb{N}$ .

Rozwiązanie

Wykażemy, że relacja

$\displaystyle \approx$ jest relacją równoważności na

$\displaystyle \mathbb{N} \times \mathbb{N}$ . Dla dowolnych liczb naturalnych

$\displaystyle n$ i

$\displaystyle k$ mamy

$\displaystyle (n,k)\approx (n,k)$ ponieważ

$\displaystyle n+k = n+k$ , więc relacja jest zwrotna. Podobnie, dla dowolnych liczb

$\displaystyle n, k, p, q$ jeśli

$\displaystyle (n,k)\approx(p,q)$ , to

$\displaystyle n+q = k+p$ i korzystając z przemienności dodawania, otrzymujemy

$\displaystyle p+k = q+n$ , czyli

$\displaystyle (p,q)\approx(n,k)$ i relacja jest symetryczna.

Aby wykazać przechodniość, ustalmy trzy dowolne pary $\displaystyle (n,k),(p,q)$ i $\displaystyle (m,l)$ spełniające $\displaystyle (n,k)\approx (p,q)$ oraz $\displaystyle (p,q)\approx (m,l)$ . Wtedy $\displaystyle n+q = k+p$ oraz $\displaystyle p+l=q+m$ , więc $\displaystyle (n+q)+(p+l) = (k+p)+(q+m)$ i na mocy łączności i przemienności dodawania w liczbach naturalnych otrzymujemy $\displaystyle (n+l) + (q+p) = (k+m)+(q+p)$ . Skracamy czynnik $\displaystyle (p+q)$ (na mocy własności skracania dla dodawanie) i otrzymujemy $\displaystyle n+l=k+m$ , czyli $\displaystyle (n,k)\approx (m,l)$ , co dowodzi przechodniości relacji $\displaystyle \approx$ . Wykazaliśmy, że $\displaystyle \approx$ jest relacją równoważności.

Ćwiczenie 1.3

Wykaż, że dla dowolnej pary $\displaystyle (n,k)\in\mathbb{N}\times \mathbb{N}$ istnieje para $\displaystyle (p,q)\in \mathbb{N}\times \mathbb{N}$ taka, że $\displaystyle (n,k)\approx (p,q)$ oraz $\displaystyle p=0$ lub $\displaystyle q=0$ .

Rozwiązanie

Ustalmy dowolną parę

$\displaystyle (n,k)\in\mathbb{N}\times \mathbb{N}$ . Jeśli

$\displaystyle n=k$ , to mamy

$\displaystyle (n,k)\approx(0,0)$ i warunek jest spełniony. Jeśli

$\displaystyle n\neq k$ , to, na mocy własności liczb naturalnych, istnieje liczba naturalna

$\displaystyle l$ taka, że

$\displaystyle n=k+l$ (lub że

$\displaystyle n+l =k$ ). Wtedy

$\displaystyle n+0=k+l$ (lub

$\displaystyle n+l = k+0$ ), czyli

$\displaystyle (n,k)\approx(l,0)$ (lub

$\displaystyle (n,k)\approx(0,l)$ ), co należało dowieść.

Definicja 1.4.

Niech $\displaystyle \mathbb{Z} = \mathbb{N} \times\mathbb{N} / \approx$

Ćwiczenie1.5

Które z liczb całkowitych $\displaystyle [(n,k)]_{\approx}$ są relacjami równoważności na $\displaystyle \mathbb{N}$ ?

Rozwiązanie

Aby liczb całkowita była relacją równoważności, koniecznym jest

$\displaystyle (0,0)\in[(k,n)]_{\approx}$ , a więc jedynym kandydatem na liczbę będącą relacją równoważności na

$\displaystyle \mathbb{N}$ jest

$\displaystyle [(0,0)]_{\approx}$ . Weźmy teraz dowolną parę liczb naturalnych

$\displaystyle (n,k)$ , jeśli

$\displaystyle (0,0)\approx(n,k)$ , to

$\displaystyle 0+k = n+0$ , czyli

$\displaystyle n=k$ . Liczba całkowita

$\displaystyle [(0,0)]_{\approx}$ jest relacją równoważności na

$\displaystyle \mathbb{N}$ i żadna inna liczba całkowita nie jest relacją równoważności.

Definicja 1.6.

Element zero $\displaystyle 0 \in \mathbb{Z}$ to element $\displaystyle [ (0,0) ]_{\approx}$ .
Element przeciwny do danego: jeżeli $\displaystyle x = [ (n,k) ]_{\approx}$ , to przez $\displaystyle -x = [ (k,n) ]_{\approx}$

Dodawanie: $\displaystyle [ (n,k) ]_{\approx} + [ (p,q) ]_{\approx} = [ (n+p,k+q) ]_{\approx}$ .

Mnożenie: $\displaystyle [ (n,k) ]_{\approx} \cdot [ (p,q) ]_{\approx} = [ (n \cdot p + k \cdot q \;,\; n \cdot q + k \cdot p ) ]_{\approx}$ {Dla przejrzystości zapisu będziemy czasami pomijać znak $\displaystyle \cdot$ , pisząc $\displaystyle xy$ , zamiast $\displaystyle x\cdot y$ }.

Odejmowanie: $\displaystyle x-y = x+ (-y)$

Proszę o zwrócenie uwagi na pewną kolizję oznaczeń. Po lewej stronie definicji (dodawania, mnożenia i odejmowania) używamy tych samych znaków działań co po stronie prawej. Jest to ewidentna kolizja oznaczeń, którą wykonujemy z pełną świadomością. W praktyce matematycznej i informatycznej przyjęło się używać te same znaki działań, wiedząc, że mają one zgoła inne znaczenie. Również element $\displaystyle 0$ będziemy oznaczać identycznie jak $\displaystyle 0$ w liczbach naturalnych, pomimo że jest to zupełnie inny zbiór. Pod koniec tej konstrukcji podamy naturalne włożenie (iniekcje wkładającą liczby naturalne w całkowite) takie, które zachowuje działania na liczbach, co upewni nas, że stosowanie tych samych oznaczeń nie grozi konfliktem.

Ćwiczenie 1.7

Pokazać, że działania na liczbach całkowitych są dobrze określone. To znaczy pokazać, że zbiory (klasy równoważności) będące wynikiem działań nie zależą od wyboru reprezentantów:

Wskazówka

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

Rozwiązanie

Dla dowodu wykazującego dobre zdefiniowanie operacji na liczbach całkowitych ustalmy dowolne pary

$\displaystyle (n,k),(p,q),(m,l),(r,s)$ spełniające

$\displaystyle (n,k)\approx (m,l)$ oraz

$\displaystyle (p,q)\approx (r,s)$ .

Dla dowodu dobrego zdefiniowania elementów przeciwnych musimy wykazać, że $\displaystyle -[(n,k)]_{\approx} = -[(m,l)]_{\approx}$ , czyli że $\displaystyle [(k,n)]_{\approx} =[(l,m)]_{\approx}$ . Potrzebujemy $\displaystyle (k,n)\approx(l,m)$ , co jest równoważne stwierdzeniu, że $\displaystyle k+m = n+l$ , który to fakt jest oczywistą konsekwencją $\displaystyle (n,k)\approx (m,l)$ . Wykazaliśmy, że definicja elementu przeciwnego nie zależy od wyboru reprezentantów dla klas.

Analogiczny dowód przeprowadzamy dla dodawania. Musimy wykazać, że

$\displaystyle [(n,k)]_{\approx}+[(p,q)]_{\approx} = [(m,l)]_{\approx} + [(r,s)]_{\approx}$ . Równość ta jest prawdą wtedy i tylko wtedy, kiedy $\displaystyle [(n+p,k+q)]_{\approx} =[(m+r,l+s)]_{\approx}$ , czyli kiedy $\displaystyle (n+p,k+q)\approx(m+r,l+s)$ . Korzystając z definicji relacji $\displaystyle \approx$ , potrzebujemy $\displaystyle (n+p)+(l+s) = (k+q)+(m+r)$ . Z założeń wynika, że $\displaystyle n+l=k+m$ oraz $\displaystyle p+s = q+r$ - dodając te równości stronami i korzystając z łączności i przemienności dodawania w liczbach naturalnych, otrzymujemy żądany fakt.

Wykażemy, że mnożenie dwóch liczb całkowitych nie zależy od wyboru reprezentantów w klasach równoważności. Niewątpliwie, używając założeń i przemienności, łączności i definicji mnożenia, mamy:

$\displaystyle (n+l+k+m)(q+r) = 2 (k+m)(q+r) = 2(q+r)(k+m) = (p+s+q+r)(k+m)$ i dalej, używając rozdzielności mnożenia:

$\displaystyle n(q+r)+l(q+r)+k(q+r)+m(q+r) = p(k+m)+s(k+m)+q(k+m)+r(k+m).$

Używamy raz jeszcze założeń i dostajemy:

$\displaystyle n(p+s)+l(q+r)+k(q+r)+m(p+s) = p(k+m) + s(l+n) +q(l+n)+r(k+m)$ co, po wymnożeniu daje:

$\displaystyle np + ns + lq + lr + kq + kr +mp + ms = pk + pm + sl +sn + ql +qn +rk+rm.$

Stosujemy prawo skracania dla liczb naturalnych do $\displaystyle ns + lq + kr +mp$ i dostajemy:

$\displaystyle np+lr +kq + ms = pk + sl + qn + rm$

co, używając przemienności mnożenia i przemienności i łączności dodawania, daje:

$\displaystyle (np +kq, nq + kp)\approx (mr +ls, ms +lr).$

Wywnioskowaliśmy, że $\displaystyle [(n,k)]_{\approx}\cdot [(p,q)]_{\approx} = [(m,l)]_{\approx}\cdot [(r,s)]_{\approx}$ , co oznacza, że definicja mnożenia nie zależy od wyboru reprezentantów dla klas.

Ćwiczenie 1.8

Pokaż własności działań dodawania i mnożenia. Dla dowolnych liczb całkowitych $\displaystyle x,y,z$ zachodzą równości:

$\displaystyle x+y = y+x$ (przemienność dodawania),
$\displaystyle x \cdot y = y \cdot x$ (przemienność mnożenia),
$\displaystyle x \cdot y = z \cdot y$ oraz $\displaystyle y\neq 0$ to $\displaystyle x=z$ (prawo skracania),
$\displaystyle x \cdot(y+z) = x\cdot y + x\cdot z$ (rozdzielność).

Wskazówka

Zapisz każde z powyższych praw, ujawniając strukturę liczb całkowitych. Zauważ, że w dowodzie będą interweniowały udowodnione już prawa łączności, przemienności i prawo skreśleń i skracania dla liczb naturalnych.

Rozwiązanie

Dla dowodu powyższych własności ustalmy dowolne liczby całkowite

$\displaystyle [(n,k)]_{\approx},[(p,q)]_{\approx},[(m,l)]_{\approx}$ .

Dla dowodu przemienności dodawania zauważmy, że $\displaystyle [(n,k)]_{\approx} + [(p,q)]_{\approx} = [(n+p,k+q)]_{\approx}$ i korzystając z przemienności dodawania dla liczb naturalnych, otrzymujemy $\displaystyle [(n+p,k+q)]_{\approx} = [(p+n,q+k)]_{\approx} =[(p,q)]_{\approx}+[(n,k)]_{\approx}$ . Wykazaliśmy, że dodawanie liczb całkowitych jest przemienne.
Podobne rozumowanie stosujemy dla mnożenia $\displaystyle [(n,k)]_{\approx}\cdot[(p,q)]_{\approx} = [(np+kq,nq+kp)]_{\approx}$ i, stosując przemienność mnożenia i dodawania $\displaystyle [(np+kq,nq+kp)]_{\approx} = [(pn+qk,pk+qn)]_{\approx} =[(p,q)]_{\approx}\cdot[(n,k)]_{\approx}$ , co należało wykazać.
Dla dowodu prawa skracania dla liczb całkowitych załóżmy, że $\displaystyle [(n,k)]_{\approx}\cdot[(p,q)]_{\approx}=[(m,l)]_{\approx}\cdot[(p,q)]_{\approx}$ , oraz że dokładnie jedna z liczb $\displaystyle p, q$ jest równa zero. Na mocy Ćwiczenia 1.3 reprezentacja taka istnieje dla każdej, różnej od zera, liczby całkowitej. Wnioskujemy, że $\displaystyle [(np+kq,nq+kp)]_{\approx}=[(mp+lq,mq+lp)]_{\approx}$ . Wnioskujemy stąd, że $\displaystyle (np+kq,nq+kp)\approx(mp+lq,mq+lp)$ , czyli że $\displaystyle np+kq+mq+lp = nq+kp+mp+lq$ . Jeśli $\displaystyle p=0$ , to otrzymujemy, korzystając z rozdzielności, $\displaystyle (k+m)q = (n+l)q$ i korzystając z prawa skracania dla liczb naturalnych $\displaystyle k+m =n+l$ , czyli $\displaystyle [(k,l)]_{\approx}=[(m,l)]_{\approx}$ , co należało dowieść. Podobnie, jeśli $\displaystyle q=0$ , to $\displaystyle (n+l)p = (k+m)p$ i, podobnie jak w poprzednim przypadku, $\displaystyle [(k,l)]_{\approx}=[(m,l)]_{\approx}$ . Wykazaliśmy, że mnożenie liczb całkowitych jest skracalne.
Dla dowodu rozdzielności postępujemy następująco. Liczby $\displaystyle [(n,k)]_{\approx}\cdot([(p,q)]_{\approx}+[(m,l)]_{\approx})=[(n(p+m) + k(q+l),n(q+l)+k(p+m))]_{\approx}$ . Korzystając z rozdzielności, przemienności i łączności działań na liczbach naturalnych, dostajemy, $\displaystyle [(n(p+m) + k(q+l),n(q+l)+k(p+m))]_{\approx}= [((np + kq) + (nm+kl),(nq+kp)+(nl+km)]_{\approx}=[(np+kq,nq+kp)]_{\approx}+[(nm+kl,nl+km)]_{\approx}$ , co równa się $\displaystyle [(n,k)]_{\approx}\cdot [(p,q)]_{\approx}+[(n,k)]_{\approx}\cdot[(m,l)]_{\approx}$ , co należało wykazać.

Porządek liczb całkowitych

Definicja 1.9.

Liczba $\displaystyle [ (n,k) ]_{\approx} \leq [ (p,q) ]_{\approx}$ zachodzi, gdy $\displaystyle n+q \leq p+k$ .

Ćwiczenie 1.10

Pokaż, że definicja porządku nie jest zależna od wyboru reprezentanta. <

Wskazówka

Do dowodu zastosuj własności dodawania liczb naturalnych.

Niech $\displaystyle (n,k),(m,l),(p,q),(r,s)$ będą parami liczb naturalnych takimi, że $\displaystyle (n,k)\approx (m,l)$ oraz $\displaystyle (p,q)\approx (r,s)$ . Załóżmy dodatkowo, że $\displaystyle [(n,k)]_{\approx}\leq[(p,q)]_{\approx}$ . Wykażemy, iż w takim przypadku również $\displaystyle [(m,l)]_{\approx}\leq [(r,s)]_{\approx}$ , czyli że porządek na liczbach całkowitych jest niezależny od wyboru reprezentantów dla klas równoważności. Skoro $\displaystyle [(n,k)]_{\approx}\leq[(p,q)]_{\approx}$ , to $\displaystyle n+q \leq p+k$ i z wykładu o liczbach naturalnych wiemy, że istnieje liczba naturalna $\displaystyle t$ taka, że $\displaystyle n+q+t = p+k$ . Równocześnie nasze założenia gwarantują, że $\displaystyle n+l=k+m$ i $\displaystyle p+s=q+r$ , czyli że:

$\displaystyle n+l+q+r = k+m+p+s.$

Korzystając z udowodnionej własności $\displaystyle t$ podstawiamy liczby do wzoru, otrzymując:

$\displaystyle n+l+q+r=n+m+q+t+s,$

co z kolei możemy skrócić przez $\displaystyle n+q$ , otrzymując:

$\displaystyle l+r = m+s+t \text{ co oznacza } l+r\geq m+s.$

Czyli $\displaystyle [(m,l)]_{\approx}\leq[(r,s)]_{\approx}$ , co należało wykazać.

Ćwiczenie 1.11

Pokaż, że porządek liczb całkowitych spełnia postulaty porządku liniowego, to znaczy jest zwrotny, antysymetryczny, przechodni i spójny.

Wskazówka

Do dowodu zastosuj własności dodawania liczb naturalnych i porządku liczb naturalnych.

Rozwiązanie 2

Porządek na liczbach całkowitych jest zwrotny. Dla dowolnej liczby całkowitej

$\displaystyle [(n,k)]_{\approx}$ mamy

$\displaystyle [(n,k)]_{\approx}\leq [(n,k)]_{\approx}$ , ponieważ

$\displaystyle n+k\leq n+k$ .

Dla dowodu antysymetrii załóżmy, że dla dwu liczb całkowitych mamy $\displaystyle [(n,k)]_{\approx}\leq [(p,q)]_{\approx}$ oraz $\displaystyle [(p,q)]_{\approx}\leq [(n,k)]_{\approx}$ . Wnioskujemy natychmiast, że $\displaystyle n+q\leq k+p$ oraz, że $\displaystyle p+k \leq q+n$ . Korzystając z przemienności dodawania, przechodniości i antysymetrii porządku na liczbach naturalnych, dostajemy: $\displaystyle n+q = k+p$ , czyli $\displaystyle (n,k)\approx(p,q)$ , co należało wykazać.

Aby wykazać przechodniość, ustalmy trzy dowolne liczby całkowite takie, że $\displaystyle [(n,k)]_{\approx}\leq [(p,q)]_{\approx}\leq [(m,l)]_{\approx}$ . Definicja porządku gwarantuje, że:

$\displaystyle n+q\leq k+p \text{ oraz, że } p+l\leq q+m.$

Operując ćwiczeniami z wykładu "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje" możemy łatwo pokazać, że jeśli dodamy do obu stron nierówności tę samą liczbę, to nierówność pozostanie zachowana. W związku z tym:

$\displaystyle n+q+l\leq k+p+l \text{ oraz, że } p+l+k\leq q+m+k$

i używając przechodniości, dostajemy: $\displaystyle n+q+l\leq q+m+k$ . Jeszcze raz wykorzystując ćwiczenia dotyczące liczb naturalnych, możemy skrócić $\displaystyle q$ i otrzymać $\displaystyle n+l\leq m+k$ , czyli $\displaystyle [(n,k)]_{\approx}\leq [(m,l)]_{\approx}$ , co należało wykazać.

Dowód spójności porządku na liczbach całkowitych jest trywialną konsekwencją faktu, że dla dowolnych dwóch par liczb naturalnych $\displaystyle (n,k)$ i $\displaystyle (p,q)$ mamy $\displaystyle n+q\leq p+k$ lub $\displaystyle p+k\leq q+n$ .

Definicja 1.12.

Rozważmy funkcje $\displaystyle i:\mathbb{N} arrow \mathbb{Z}$ zadaną wzorem:

$\displaystyle i(n) = [ (n,0)]_{\approx}.$

Funkcja ta jest naturalnym włożeniem zbioru $\displaystyle \mathbb{N}$ w zbiór $\displaystyle \mathbb{Z}$ . Jako ćwiczenie pokażemy, że funkcja $\displaystyle i$ jest iniektywna i zgodna z działaniami. Dzięki włożeniu $\displaystyle i$ będziemy utożsamiali liczbę naturalną $\displaystyle n$ z odpowiadającą jej liczbą całkowitą $\displaystyle i(n)$ . W ten sposób każdą liczbę naturalną możemy traktować jak całkowitą.

Ćwiczenie 1.13

Pokaż, że funkcja $\displaystyle i$ jest iniekcją. Pokaż, że $\displaystyle i$ jest zgodne z działaniami i porządkiem, to znaczy:

$\displaystyle i(0) =0$ ,
$\displaystyle i(n+m) = i(n)+i(m)$ ,
$\displaystyle i(n \cdot m) = i(n) \cdot i(m)$ ,
jeżeli $\displaystyle n \leq k$ , to $\displaystyle i(n) \leq i(k)$ .

Wskazówka

Pamiętaj, że znaki działań i porządku (oraz

$\displaystyle 0$ ) po prawej i po lewej stronie równości znaczą co innego. Zapisz każde z powyższych praw, ujawniając strukturę liczb całkowitych. 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 naturalnych.

Rozwiązanie

Aby wykazać iniektywność funkcji

$\displaystyle i$ , wybierzmy dwie dowolne liczby naturalne

$\displaystyle m,n$ . Jeśli

$\displaystyle i(n)=i(m)$ , to

$\displaystyle [(n,0)]_{\approx}=[(m,0)]_{\approx}$ , czyli

$\displaystyle n+0=m+0$ i używając prawa skracania dla liczb naturalnych, dostajemy:

$\displaystyle n=m$ , co należało wykazać. Nasze rozumowanie wykazało, że funkcja

$\displaystyle i$ jest iniekcją. Przechodzimy teraz do dowodu własności funkcji

$\displaystyle i$ .

Oczywiście $\displaystyle i(0)=0$ , ponieważ $\displaystyle i(0)=[(0,0)]_{\approx} = 0$ .
Dla dowolnych dwóch liczb naturalnych $\displaystyle n,m$ mamy $\displaystyle i(n+m) = [(n+m,0)]_{\approx} = [(n,0)]_{\approx}+[(m,0)]_{\approx} = i(n) +i(m)$ , co należało wykazać.
Podobnie jak w poprzednim przypadku ustalmy dowolne dwie liczby naturalne $\displaystyle n$ i $\displaystyle m$ . Wtedy, używając całego arsenału identyczności prawdziwych dla liczb naturalnych, mamy $\displaystyle i(n\cdot m) = [(nm,0)]_{\approx} = [(nm+00,n0+0m)]_{\approx} = [(n,0)]_{\approx}\cdot[(m,0)]_{\approx} = i(n)\cdot i(m)$ , co należało wykazać.
Jeśli $\displaystyle n\leq k$ , to niewątpliwie $\displaystyle n+0\leq k+0$ , czyli $\displaystyle [(n,0)]_{\approx}\leq [(k,0)]_{\approx}$ , co oznacza, że $\displaystyle i(n)\leq i(k)$ . Dowód jest zakończony.