Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek

Liczby całkowite

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} \).

Ć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 \).

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} \)?

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:


Ć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:

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


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. <

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.


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:

  1. \( \displaystyle i(0) =0 \),
  2. \( \displaystyle i(n+m) = i(n)+i(m) \),
  3. \( \displaystyle i(n \cdot m) = i(n) \cdot i(m) \),
  4. jeżeli \( \displaystyle n \leq k \), to \( \displaystyle i(n) \leq i(k) \).


Liczby wymierne

Liczby wymierne



Niech \( \displaystyle \mathbb{Z}^* = \mathbb{Z} \setminus \{\emptyset\} \). Określamy relację \( \displaystyle \sim \) na zbiorze \( \displaystyle \mathbb{Z} \times \mathbb{Z}^* \) następująco:

\( \displaystyle (a,b) \sim (c,d) \) wtw \( \displaystyle a \cdot d = c \cdot b. \)

Ćwiczenie 2.1

Relacja \( \displaystyle \sim \) jest równoważnością.


Definicja 2.2.

Niech \( \displaystyle \mathbb{Q} = \mathbb{Z} \times\mathbb{Z}^* / \sim. \)

OZNACZENIE: Będziemy tradycyjne oznaczać ułamek \( \displaystyle \frac{a}{b} \). Oznacza on zbiór \( \displaystyle [ (a,b) ]_{\sim} \).

Ćwiczenie 2.3

Dla jakich liczb wymiernych \( \displaystyle [(a,b)]_{\sim} \) mamy \( \displaystyle \bigcup\bigcup [(a,b)]_{\sim} = \mathbb{Z} \)?

Działania na ułamkach

Definiujemy stałe i standardowe działania na ułamkach.

  • Zero w liczbach wymiernych \( \displaystyle 0 \in \mathbb{Q} \) to \( \displaystyle [(0, 1) ]_{\sim} \).
  • Jedynka w liczbach wymiernych \( \displaystyle 1 \in \mathbb{Q} \) to ułamek \( \displaystyle [(1, 1) ]_{\sim} \).
  • \( \displaystyle - [ (a,b) ]_{\sim} = [(-a, b) ]_{\sim}. \)
  • Dodawanie \( \displaystyle [ (a,b) ]_{\sim} + [ (c,d) ]_{\sim} = [(ad +bc, bd) ]_{\sim} \).
  • Odejmowanie \( \displaystyle [ (a,b) ]_{\sim} - [ (c,d) ]_{\sim} = [(ad - bc, bd)]_{\sim} \).
  • Mnożenie \( \displaystyle [ (a,b) ]_{\sim} \cdot [ (c,d) ]_{\sim} = [(ac, bd) ]_{\sim} \).
  • Dzielenie, \( \displaystyle [ (a,b) ]_{\sim} : [ (c,d) ]_{\sim} = [(ad, bc) ]_{\sim} \) gdy \( \displaystyle [ (c,d) ]_{\sim} \neq [(0, d) ]_{\sim} \).

Tak jak poprzednio w przypadku liczb całkowitych będziemy starali się utożsamiać liczby całkowite z pewnymi ułamkami.

Proszę tak jak poprzednio o zwrócenie uwagi na kolizję oznaczeń. Jest to zamierzona kolizja oznaczeń, którą wprowadzamy z pełną świadomością. Po lewej stronie definicji (dodawania, mnożenia, odejmowania i liczby przeciwnej) używamy tych samych znaków działań co po stronie prawej. Pod koniec tej konstrukcji podamy naturalne włożenie (iniekcje wkładającą liczby całkowite w wymierne) takie, które zachowuje działania na liczbach. Upewni nas to, że stosowanie tych samych oznaczeń de facto nie grozi konfliktem.

Ćwiczenie 2.4

Pokazać, że działania na liczbach wymiernych 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:


Porządek ułamków.

Definicja 2.5.

\( \displaystyle \frac{a}{b} \geq \frac{c}{d} \), gdy \( \displaystyle (a\cdot d - b \cdot c) \cdot b \cdot d \geq 0. \)

Ćwiczenie 2.6

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


Ćwiczenie 2.7

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


Do rozważań nad konstrukcją liczb rzeczywistych potrzebna nam będzie definicja wartości bezwzględnej

Definicja 2.8.

\( \displaystyle | x |\ = \left\{ \begin{array}{rll} x, & \text{ gdy } x\geq 0, \\ -x, & \text{ w przeciwnym przypadku}. \end{array}\right. \)

Ćwiczenie 2.9

Pokaż warunek trójkąta, czyli:

\( \displaystyle | x+y | \leq | x | + | y |. \)


Definicja 2.10.

Rozważmy teraz funkcje \( \displaystyle j:\mathbb{Z} arrow \mathbb{Q} \) identyfikującą liczby całkowite jako pewne specjalne liczby wymierne zadaną wzorem:

\( \displaystyle j(a) = [ (a,1)]_{\sim}. \)

Funkcja ta jest naturalnym włożeniem zbioru \( \displaystyle \mathbb{Z} \) w zbiór \( \displaystyle \mathbb{Q} \). Jest iniektywna, zgodna z działaniami i zachowująca stałe. Pokazanie tych własności będzie treścią następnego ćwiczenia.

Ćwiczenie 2.11

Pokaż własności włożenia \( \displaystyle j \):

  1. \( \displaystyle j(0) = 0 \),
  2. \( \displaystyle j(1)=1 \),
  3. \( \displaystyle j(a+b) = j(a)+j(b) \),
  4. \( \displaystyle j(a-b) = j(a)-j(b) \),
  5. \( \displaystyle j(a \cdot b) = j(a) \cdot j(b) \),
  6. jeżeli \( \displaystyle x \leq y \), to \( \displaystyle j(x) \leq j(y) \).


Dzięki włożeniu \( \displaystyle j \) będziemy utożsamiali liczbę całkowitą \( \displaystyle a \) z odpowiadającą jej liczbą wymierną \( \displaystyle j(a) = [ (a,1)]_{\sim} \).

Konstrukcja Cantora liczb rzeczywistych

Konstrukcja Cantora liczb rzeczywistych



Definicja 3.1.

Ciągiem elementów zbioru \( \displaystyle A \) nazywamy każdą funkcje \( \displaystyle a: \mathbb{N} \rightarrow A \). Przez \( \displaystyle a_n \) oznaczamy element ciągu \( \displaystyle a(n) \).

Konstrukcja liczb rzeczywistych pochodzi od Georga Cantora. Genialny pomysł Georga Cantora polega na rozważaniu nieskończonych ciągów liczb wymiernych spełniających warunek Augustina Louis Cauchy'ego. Wiemy z analizy (patrz wykład Szeregi liczbowe), że ciągi takie są zbieżne. Dlatego ciąg ten można uważać za aproksymacje liczby rzeczywistej. Będziemy za liczbę rzeczywistą brać wszystkie takie ciągi aproksymacji, które w sensie poniższych definicji będą dowolnie bliskie siebie.

Definicja 3.2.

Ciągiem Cauchy'ego zbioru liczb wymiernych \( \displaystyle \mathbb{Q} \) nazywamy każdy taki ciąg \( \displaystyle a: \mathbb{N} \rightarrow \mathbb{Q} \) który spełnia warunek (Cauchy'ego):

\( \displaystyle \forall_{\varepsilon \in \mathbb{Q} \hspace{0.1mm} \wedge \varepsilon >0} \;\; \exists_{n_0 \in \mathbb{N}} \;\; \forall_{p,k \in \mathbb{N}} \;\; ( p>n_0 \wedge k >n_0 \hspace{0.1mm} \Rightarrow | a_p - a_k | < \varepsilon ) \)

Definicja 3.3.

Ciąg \( \displaystyle a: \mathbb{N} \rightarrow \mathbb{Q} \) nazywamy ograniczonym, gdy spełnia:

\( \displaystyle \exists_{M>0} \;\; \forall_{n \in \mathbb{N}} \;\; | a_n | < M \)

Fakt 1

Ciągi Cauchy'ego są ograniczone.

Dowód

Do ciągu Cauchy'ego \( \displaystyle a \) będziemy dobierać ograniczenie \( \displaystyle M \). Weźmy dodatnią liczbę wymierną \( \displaystyle \varepsilon \). Dla niej, zgodnie z Definicją 3.2, znajdziemy tak duże \( \displaystyle n_0 \), że dla wszystkich liczb naturalnych \( \displaystyle p,k \), poczynając od \( \displaystyle n_0 +1 \) będzie zachodzić: \( \displaystyle | a_p - a_k | < \varepsilon \). Połóżmy za \( \displaystyle M \) największą z pośród liczb \( \displaystyle | a_0 | ,\ldots | a_{n_0} | \) oraz \( \displaystyle | a_{n_0 +1} | + \varepsilon \) powiększoną o \( \displaystyle 1 \). Łatwo sprawdzić, że tak zdefiniowane \( \displaystyle M \) majoryzuje moduły wszystkich liczb ciągu.

Poniżej wprowadzimy relacje równoważności na zborze ciągów Cauchy'ego, taką która skleja ciągi, które leżą dowolnie blisko. Każdy taki ciąg będzie inną aproksymacją tej samej liczby rzeczywistej. Zbiór wszystkich takich aproksymacji będzie dla nas właśnie liczbą rzeczywistą.

Definicja 3.4.

Niech \( \displaystyle X=\{ a: \mathbb{N} \rightarrow \mathbb{Q} : a \) jest ciągiem Cauchy'ego \( \displaystyle \} \).

Definicja 3.5.

Na zbiorze \( \displaystyle X \) ciągów Cauchy'ego określamy relację następująco: dwa ciągi \( \displaystyle a \) i \( \displaystyle b \) są równoważne, co zapisujemy jako \( \displaystyle a \simeq b \), gdy:

\( \displaystyle \forall_{\varepsilon >0} \;\; \exists_{n_0 \in \mathbb{N}} \;\; \forall_{n \in \mathbb{N}} \;\; ( n>n_0 \hspace{0.1mm} \Rightarrow | a_n - b_n | < \varepsilon ). \)

Twierdzenie 3.6.

Relacja \( \displaystyle \simeq \) określona na \( \displaystyle X \) jest relacją równoważności.

Dowód

Zwrotność i symetria relacji \( \displaystyle \simeq \) są oczywiste. Zajmijmy się dowodem przechodniości. Niech \( \displaystyle a \simeq b \) oraz \( \displaystyle b\simeq c \). Oznacza to:

\( \displaystyle \begin{align*} \forall_{\varepsilon >0} \;\; \exists_{n_1 \in \mathbb{N}} \;\; \forall_{n \in \mathbb{N}} \;\; ( n>n_1 \hspace{0.1mm} \Rightarrow | a_n - b_n | < \varepsilon ) \quad \mbox{(3.1)} \\ \forall_{\varepsilon >0} \;\; \exists_{n_2 \in \mathbb{N}} \;\; \forall_{n \in \mathbb{N}} \;\; ( n>n_0 \hspace{0.1mm} \Rightarrow | b_n - c_n | < \varepsilon ) \quad \mbox{(3.2)} \end{align*} \)

Weźmy \( \displaystyle \varepsilon >0 \). Będziemy dobierać niezależnie liczby \( \displaystyle n_1 \) i \( \displaystyle n_2 \) do \( \displaystyle \varepsilon /2 \) dla pierwszej i drugiej pary ciągów. Mamy zatem parę nierówności: dla \( \displaystyle n>n_1 \) zachodzi \( \displaystyle | a_n - b_n | < \varepsilon/2 \) oraz dla \( \displaystyle n>n_2 \) zachodzi \( \displaystyle | b_n - c_n | < \varepsilon/2 \). Biorąc większą z tych dwóch liczb, będziemy oczywiście jednocześnie spełniać obie nierówności. Zatem dla \( \displaystyle n>\max(n_1 , n_2) \) zachodzą \( \displaystyle | a_n - b_n | < \varepsilon/2 \) oraz \( \displaystyle | b_n - c_n | < \varepsilon/2 \). Używając nierówności trójkąta, mamy:

\( \displaystyle | a_n - c_n | \leq | a_n - b_n | + | b_n - c_n | < \varepsilon/2 + \varepsilon/2 = \varepsilon, \)

co kończy dowód.

Definicja 3.7.

Przez liczby rzeczywiste będziemy rozumieli zbiór \( \displaystyle X/\simeq \) i oznaczamy przez \( \displaystyle \mathbb{R} \).

Liczbą rzeczywistą jest zatem zbiór ciągów Cauchy'ego, które leżą dowolnie blisko siebie. Na każdy taki ciąg można patrzeć jak na pewną aproksymację danej liczby rzeczywistej.

Ćwiczenie 3.8

Ile razy należy poprzedzić znakiem \( \displaystyle \bigcup \) zbiór \( \displaystyle \mathbb{R} \), aby otrzymać \( \displaystyle \mathbb{N} \)?

Działania na \( \displaystyle \mathbb{R} \)

Definicja 3.9.

Dla ciągów \( \displaystyle a \) i \( \displaystyle b \) ciąg \( \displaystyle a+ b \) oraz \( \displaystyle a \cdot b \) oznaczają ciągi zadane jako \( \displaystyle (a +b)(i) = a(i) + b(i) \), dla każdego \( \displaystyle i \). Tak samo definiujemy mnożenie: \( \displaystyle (a \cdot b)(i) = a(i) \cdot b(i) \).

Definicja 3.10.

Dodawanie i mnożenie ciągów liczb wymiernych definiujemy po współrzędnych, to znaczy:

  • dodawanie \( \displaystyle [ a ]_{\simeq} + [b]_{\simeq} = [a+b]_{\simeq} \),
  • mnożenie \( \displaystyle [ a ]_{\simeq} \cdot [b]_{\simeq} = [a \cdot b]_{\simeq} \).

Ćwiczenie 3.11

Poniższe ćwiczenie odpowiada dowodowi ciągłości dodawania i mnożenia. W innej wersji będziecie państwo zapoznawać się z tym zagadnieniem na wykładzie 8 analizy matematycznej "Granica i ciągłość funkcji". Pokazać, że definicja dodawania i mnożenia liczb rzeczywistych jest poprawna i niezależna od wyboru reprezentantów:


Porządek na \( \displaystyle \mathbb {R} \)

Definicja 3.12.

Relacja \( \displaystyle [ a ]_{\simeq} < [b]_{\simeq} \) na zbiorze liczb rzeczywistych \( \displaystyle \mathbb{R} \) jest zdefiniowana jako:

\( \displaystyle \exists_{\varepsilon > 0} \;\; \exists_{n_0 \in \mathbb{N}} \;\; \forall_{k>n_0} \;\; a_k +\varepsilon < b_k. \)

Będziemy mówili, że liczba wymierna \( \displaystyle \varepsilon > 0 \) rozdziela dwa ciągi Cauchy'ego, poczynając od elementu \( \displaystyle a_{n_0 +1} \).

Definicja 3.13.

Słaby porządek definiujemy tak jak zazwyczaj: dla liczb rzeczywistych \( \displaystyle x \leq y \), gdy \( \displaystyle x < y \) (patrz definicja 3.12.) lub gdy \( \displaystyle x=y \) (patrz Definicja 3.5).

Twierdzenie 3.14.

Porządek na \( \displaystyle \mathbb{R} \) jest liniowy.

Dowód

Pokażemy, że dla dowolnych ciągów Cauchy'ego \( \displaystyle a \) i \( \displaystyle b \), jeżeli \( \displaystyle [ a ]_{\simeq} \neq [b]_{\simeq} \) to \( \displaystyle [ a ]_{\simeq} < [b]_{\simeq} \) lub \( \displaystyle [ a ]_{\simeq} > [b]_{\simeq} \). Niech zatem \( \displaystyle [ a ]_{\simeq} \neq [b]_{\simeq} \). Zgodnie z definicją \( \displaystyle \simeq \) oznacza to:

\( \displaystyle \exists_{\varepsilon>0} \;\; \forall_{n\in\mathbb{N}} \;\; \exists_{p\in\mathbb{N}} \;\; p>n \hspace{0.1mm} \wedge | a_p -b_p | \geq \varepsilon. \)

Dobierzmy do \( \displaystyle \varepsilon/3 \) liczby \( \displaystyle n_a \) i \( \displaystyle n_b \) odpowiednio dla ciągów \( \displaystyle a \) i \( \displaystyle b \) tak, aby dla wszystkich \( \displaystyle k,r > \max(n_a ,n_b) \) zachodziło \( \displaystyle | a_k - a_r | < \varepsilon/3 \) oraz \( \displaystyle | b_k - b_r | < \varepsilon/3 \). Zgodnie z formulą powyżej dla \( \displaystyle \max(n_a ,n_b) \) musi istnieć \( \displaystyle p_0 > \max(n_a ,n_b) \) takie, że \( \displaystyle | a_{p_0} -b_{p_0} | \geq \varepsilon \). Ustalmy, że to \( \displaystyle a_{p_0} < b_{p_0} \) (gdy będzie odwrotnie rozumowania jest identyczne). Weźmy zatem dowolne \( \displaystyle k>p_0 \). Zachodzą następujące nierówności:

\( \displaystyle \begin{align*} a_{p_0} + \varepsilon & \leq b_{p_0}, \quad \mbox{(3.3)} \\ a_k - \varepsilon/3 & < a_{p_0} < a_k + \varepsilon/3, \quad \mbox{(3.4)} \\ b_k - \varepsilon/3 & < b_{p_0} < b_k + \varepsilon/3, \quad \mbox{(3.5)} \end{align*} \)

Łatwo pokazać, stosując powyższe nierówności, że poczynając od \( \displaystyle p_0 \) liczba wymierna \( \displaystyle \varepsilon/3 \), będzie rozdzielała obydwa ciągi Cauchy'ego. Mianowicie:

\( \displaystyle a_k + \varepsilon/3 < a_{p_0} + 2 \varepsilon/3 \leq b_{p_0} - \varepsilon/3 < b_{p_0}. \)

Włożenie \( \displaystyle \mathbb{Q} \) w \( \displaystyle \mathbb{R} \)

Rozważmy funkcje \( \displaystyle k:\mathbb{Q} \rightarrow \mathbb{R} \) zadaną następująco: dla liczby wymiernej \( \displaystyle q\in \mathbb{Q} \) liczba rzeczywista \( \displaystyle k(q) \) jest klasą równoważności ciągu stale równego \( \displaystyle q \), czyli \( \displaystyle k(q) = [b]_{\simeq} \), gdzie \( \displaystyle b(n) = q \). Tak więc liczby wymierne stają się częścią liczb rzeczywistych. Funkcja \( \displaystyle k \) jest naturalnym włożeniem zbioru \( \displaystyle \mathbb{Q} \) w zbiór \( \displaystyle \mathbb{R} \). Jest ona iniektywna i zgodna z działaniami i porządkiem:

  1. \( \displaystyle k(a+b) = k(a)+k(b) \),
  2. \( \displaystyle k(a-b) = k(a)-k(b) \),
  3. \( \displaystyle k(a \cdot b) = k(a) \cdot k(b) \),
  4. jeżeli \( \displaystyle a < b \), to \( \displaystyle k(a) < k(b) \).

Dzięki włożeniu \( \displaystyle k \) będziemy utożsamiali liczbę wymierną \( \displaystyle q \) z odpowiadającą jej liczbą rzeczywistą \( \displaystyle k(q) \).

Rozwijanie liczb rzeczywistych przy podstawie \( \displaystyle 2 \)

Twierdzenie 3.15.

Dla każdej liczby rzeczywistej \( \displaystyle 0\leq x < 1 \) istnieje ciąg \( \displaystyle a_x \in 2^{\mathbb{N}} \) taki, że ciąg jego sum częściowych \( \displaystyle b_x: \mathbb{N} \rightarrow
\mathbb{Q} \), dany jako \( \displaystyle b_k = \sum_{i=0}^{k} \frac{a_i}{2^{i+1}} \), spełnia:

  1. \( \displaystyle b_x \) jest ciągiem Cauchy'ego,
  2. \( \displaystyle [ b_x ]_{\simeq} = x \).

Taki ciąg \( \displaystyle a_x \) nazywamy rozwinięciem liczby \( \displaystyle x \) przy podstawie \( \displaystyle 2 \).

Dowód

Dla liczby rzeczywistej \( \displaystyle x \) podamy indukcyjną konstrukcję ciągu \( \displaystyle a \) będącego rozwinięciem dwójkowym liczby \( \displaystyle x \) i równolegle ciągu \( \displaystyle b \) jego sum częściowych. Jeżeli \( \displaystyle 0 \leq x < 1/2 \), to definiujemy \( \displaystyle a_0 = 0 \), w przeciwnym wypadku, to znaczy kiedy \( \displaystyle 1/2 \leq x < 1 \), definiujemy \( \displaystyle a_0 =1 \). Załóżmy, że mamy zdefiniowany ciąg \( \displaystyle a \) do wyrazu \( \displaystyle k \). Wyraz \( \displaystyle k+1 \) definiujemy:

  1. \( \displaystyle a_{k+1} = 1, \) jeżeli \( \displaystyle \sum_{i=0}^{k} \frac{a_i}{2^{i+1}} + \frac{1}{2^{k+2}} \leq x \),
  2. \( \displaystyle a_{k+1} = 0, \) jeżeli \( \displaystyle \sum_{i=0}^{k} \frac{a_i}{2^{i+1} }+ \frac{1}{2^{k+2}} > x \).

Ciąg \( \displaystyle b \) definiujemy tak jak w tezie twierdzenia, to znaczy \( \displaystyle b_k = \sum_{i=0}^{k} \frac{a_i}{2^{i+1}} \).

Pokażemy indukcyjnie, że dla każdego \( \displaystyle k \) zachodzi:

\( \displaystyle \sum_{i=0}^{k} \frac{a_i}{2^{i+1}} \leq x \leq \sum_{i=0}^{k} \frac{a_i}{2^{i+1}} + \frac{1}{2^{k+1}}. \quad \mbox{(3.6)} \)

Dowód tego faktu pozostawimy jako Ćwiczenie 3.16. Z powyższej nierówności mamy pierwszy fakt, a mianowicie: ciąg sum częściowych \( \displaystyle b \) jest ciągiem Cauchy'ego.

Ćwiczenie 3.16

Uzupełnij dowód indukcyjny nierówności 3.6 pierwszej części tezy Twierdzenia 3.15. Wykonaj dowód drugiej części tezy Twierdzenia 3.15. poprzedzającego to ćwiczenie.

Konstrukcja przedstawiona powyżej rozwija liczbę rzeczywistą z przedziału \( \displaystyle [0,1) \) przy podstawie \( \displaystyle 2 \). Na każdym etapie konstrukcji sprawdzamy, czy w przedziale, w którym pracujemy aktualnie, liczba znajduje się w lewej czy też prawej połówce przedziału. Stosownie do tego wybieramy cyfrę \( \displaystyle 0 \) lub \( \displaystyle 1 \) rozwinięcia. Jak łatwo można przypuścić podobną konstrukcję jak w Twierdzeniu 3.15 można wykonać przy dowolnej innej podstawie \( \displaystyle k\geq 2 \). W takim wypadku aktualny analizowany przedział dzielilibyśmy na \( \displaystyle k \) podprzedziałów i stosownie do położenia liczby wybieralibyśmy jedną z \( \displaystyle k \) cyfr ze zbioru \( \displaystyle \{0,\ldots k-1\} \). Przykładowo, gdy za \( \displaystyle k \) wybierzemy \( \displaystyle k=10 \), dostaniemy przy pomocy takiej konstrukcji rozwinięcie dziesiętne danej liczby rzeczywistej.

Twierdzenie poniżej upewni nas o pewnej ciekawej własności rozwinięć. Otóż rozwinięcie przy podstawie \( \displaystyle k=2 \) otrzymane przy pomocy Twierdzenia 3.15 zawsze jest takie, że zera w tym rozwinięciu występują dowolnie daleko. Innymi słowy, nie jest możliwe, aby w rozwinięciu od pewnego miejsca występowały same jedynki. W przykładzie dotyczącym rozwinięcia dziesiętnego liczby odpowiada to sytuacji, w której nie występują ciągi, które stale od pewnego miejsca mają cyfrę \( \displaystyle 9 \). <

Twierdzenie 3.17.

Rozwinięcia \( \displaystyle a \) uzyskane przy pomocy konstrukcji twierdzenia 3.15 dla liczby \( \displaystyle 0\leq x < 1 \) jest zawsze takie, że:

\( \displaystyle \forall_{k} \;\; \exists_{n>k} \;\; a_n = 0. \)

Dowód

Przypuśćmy, że jest przeciwnie, niż mówi teza, czyli \( \displaystyle \exists_{k} \;\; \forall_{n>k} \;\; a_n = 0 \). Weźmy najmniejsze takie \( \displaystyle k \) i nazwijmy \( \displaystyle k_0 \). Mamy zatem \( \displaystyle a_{k_0} = 0 \) oraz wszystkie późniejsze wyrazy \( \displaystyle a_i =1 \) dla \( \displaystyle i>k_0 \). Rozwijana liczba \( \displaystyle x \) spełniać będzie dla każdego \( \displaystyle p\geq 1 \) nierówność 3.6, czyli zachodzić będzie:

\( \displaystyle b_{k_0 -1} + \frac{1}{2^{k_0 +2}} + \ldots +\frac{1}{2^{k_0 +p+1}} \leq x \leq b_{k_0 -1} + \frac{1}{2^{k_0 +2}} + \ldots +\frac{1}{2^{k_0+ p+1}} + \;\; \frac{1}{2^{k_0 p+ 1}}. \)

Liczbą, która spełnia wszystkie te nierówności jest: \( \displaystyle b_{k_0 -1} + \frac{1}{2^{k_0 +1}} \). Mamy zatem zamiast rozwinięcia, które nieformalnie zapiszemy jako \( \displaystyle a_0 \ldots a_{k_0 -1} 0 1 1 1 \ldots \) rozwinięcie \( \displaystyle a_0 \ldots a_{k_0 -1} 1 0 0 0 \ldots \). To właśnie to drugie rozwinięcie zostanie znalezione przez procedurę rekurencyjną przedstawioną w Twierdzeniu 3.15

Twierdzenie 3.18.

Istnieje bijekcja pomiędzy odcinkiem \( \displaystyle [0;1) \) a zbiorem \( \displaystyle \{a\in 2^{\mathbb{N}}: \forall_{k} \;\; \exists_{n>k} \;\; a_n = 0\} \)

Dowód

Bijekcja jest zdefiniowana przy pomocy techniki wprowadzonej w Twierdzeniu 3.15. Istnienie funkcji przypisującej liczbie rzeczywistej \( \displaystyle x \) jej rozwinięcie dwójkowe zostało tam opisane. Własność tego rozwinięcia \( \displaystyle \forall_{k} \;\; \exists_{n>k} \;\; a_n = 0 \) została pokazana w Twierdzeniu 3.17. Pozostaje uzasadnić iniektywność takiego przypisania. Niech \( \displaystyle x \neq y \). Załóżmy, że \( \displaystyle x < y \). Rozważmy zatem ciągi \( \displaystyle a \) oraz \( \displaystyle a' \) rozwinięć dwójkowych \( \displaystyle x \) i \( \displaystyle y \). Nazwijmy ciągi ich sum częściowych, odpowiednio przez \( \displaystyle b \) i \( \displaystyle b' \). Ciągi sum wyznaczają te liczby, czyli \( \displaystyle [ b ]_{\simeq} = x , [b']_{\simeq} = y \). Ciągi \( \displaystyle b \) i \( \displaystyle b' \) muszą być różne, bo inaczej wyznaczałyby te same liczby. W takim razie ciągi rozwinięć \( \displaystyle a \) i \( \displaystyle a' \) muszą być różne.

Powyższe twierdzenie będzie miało fundamentalne znaczenie w teorii mocy, o którym mowa będzie w wykładzie "Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum". Pokazuje bowiem, że liczby rzeczywiste są równoliczne ze zbiorem \( \displaystyle 2^\mathbb{N} \).