Wstęp do Teorii Informacji. Cz.1

Czysta nauka zajmuje się abstrahowaniem i ekstrahowaniem ze skomplikowanej rzeczywistości prostych modeli. Z czasem, gdy prosty model jest dostatecznie zbadany, a istnieje potrzeba lepszego przybliżenia rzeczywistości, tworzy się modele bardziej zaawansowane. Toczy się nieustanna walka mikrochaosu z porządkiem. Ta walka jest częścią chaosu.

Zastosowania nauki są sztuką, a ten który naukę stosuje powinien być artystą, który w zastanej, niejasnej sytuacji potrafii rozpoznać jej strukturę, potrafi oddzielić mało ważne elementy od ważnych, po czym stosuje właściwy dział teorii, powiedzmy właściwy model. Przeciętny wyrobnik "stosuje" teorię, którą powierzchownie narzuca mu sformułowanie problemu lub szef.

Tak czy inaczej, będę rozpatrywał bardzo proste, aż fikcyjne kanały komunikacyjne. Celem będzie wyczucie (zrozumienie) pojęcia informacji.

---

Pewien serwer na swojej frontowej stronie internetowej wyświetla każdego dnia jeden z dwóch losowo wybranych obrazów, każdy z nich ma 1000x1000 = milion kropek. Gdy kolegę poinformuję, który z dwóch RGB-obrazów dziś jest wyświetlany, to czy przekazuję mu informację wartą miliona kropek (32 milionów bitów)? Nie - przekazałem informację jednobitową, jak odpowiedź na pytanie "0 czy 1?".

Powyższa fikcyjna anegdotka daje przedsmak znaczenia słowa informacja. Informacja istnieje nie absolutnie, lecz w kontekście. Inżynierzy mawiają nawet: co jest szumem dla jednego, jest informacją dla drugiego.

---

Rozpatrzmy kanał, który na wejściu i wyjściu przyjmuje i przekazuje tylko dwa sygnały: 0 i 1. Niech to będzie kanał dyskretny także w czasie. Działa wiecznie, zawsze, i co jedną stutysięczną sekundy przekazuje sygnal. Gdy sami nic w tej sprawie nie czynimy, to przekazuje szum, przypadkowe 0 lub 1. Na dodatek niech to będzie kanał idealny: gdy otrzymuje 0 to przekazuje na wyjściu 0, gdy 1, to 1, bez przekłamań.

Niech eksperyment lub pomiar fizyczny daje ciąg losowy dwóch możliwości, jakby Orzeł i Reszka. Prawdopodobienstwo każdej wynosi 1/2. Wiadomo, że chcemy przekazać 10 milionów kolejnych wyników, coś jakby

        OOORORRORRRRROOROOO...


Zakładamy, że wiadomo, kiedy zaczynamy nadawanie, ale musimy podać metodę na rozpoznanie końca transmisji (kanał przecież zawsze coś nadaje, nie wyłącza się). Metodę przekazu musimy ustalić zawczasu. Pytanie: jaka jest najszybsza metoda kodowania (przekazująca jak najmniej znaków, które potem trzeba i można jednoznacznie odkodować)?

Co to znaczy najszybsza, gdy dla różnych ciągów wynik może być a priori różny, w zależności od ciągu (i od ustalonej metody)? Szybkość jest odwrotnie proporcjonalna do czasu transmisji, czyli do długości mierzonej liczbą nadanych sygnałów.

Jedna z odpowiedzi może w danym przykładzie brzmieć "długością procedury nazywamy średnią liczbę przekazów sygnałów". Czyli jest to suma liczb sygnałów potrzebnych dla jednorazowego przekazania każdego możliwego ciągu [;c;], podzielona przez liczbę tych ciągów:

        [;\frac{\sum_c\,L(c)}{2^{{10}^7}};]

gdzie [;L(c);] jest liczbą sygnałów (bitów 0 1), potrzebną dla przesyłki ciągu [;c;]. W kontekście ogólnym teorii, to samo można ująć jako wartość spodziewaną długości transmisji czyli tak: każdy ciąg Orłów i Reszek, długości [;10^7;], ma prawdopodobieństwo wystąpienia równe

        [;p(c) := 1/2^{{10}^7};]

Wtedy wartość oczekiwana jest zdefiniowana za pomocą wzoru:


        [;\sum_c\,(L(c)\cdot p(c));]

Widzimy, że w danym przypadku obie definicje dają tę samą długość, więc i szybkość, przekazu, bo prawdopodobieństwa [;p(c);] są wszystkie równe.

UWAGA 0  Na ogół, przy innych zadaniach, prawdopodobieństwa [;p(c);] są różne, zależą od [;c;]. Wtedy teoria na ogół stosuje definicję z prawdopodobieństwami, gdyż właśnie ta ma znaczenie praktyczne. Definicja ze średnią arytmetyczną i tak jest jej specjalnym przypadkiem, gdy prawdopodobieństwa są równe.

---

Najprostsze kodowanie w powyższym przypadku przesyłania informacji o ciągu 10 milionów Orłów i Reszek wygląda tak: z góry zapowiadamy raz na zawsze, że przesyłka będzie miała 10 milionów sygnałów - dzięki temu wiadomo kiedy transmisja skończy się, przy czym każdego Orła kodujemy jako 0, oraz każdą Reszkę jako 1. Żeby było to jasnym, gdyby chodziło o ciąg dugości 6, jak ROOORR, to przekazalibyśmy 100011. Przy wyjściu, adresat (odbiorca) sam już sobie przetłumaczy (zdekoduje) każde 0 na Orła, i każde 1 na Reszkę. Jest to najprostsza procedura. Mądrość powszechna mówi, że jest to najlepsza procedura, że szybszej już nie ma. Nawiedzeni uważają to za oczywiste. Wcale to nie jest oczywiste! Każde sensowne uściślenie tego "twierdzenia" oznacza prawdziwe twierdzenie, i wtedy mądrość powszechna jest podtrzymana, ze ścisłym omówieniem "nasza procedura jest najszybsza w danym sensie. Zauważmy, że nie mówimy o przesłaniu jednego ciągu, lecz o losowym, czyli o przesyłaniu wszystkich.

Długość transmisji liczona jako wartość oczekiwana liczby sygnałów oczywiście wynosi dokładnie 10 milionów, [;10^7;].

Mądrość ludowa o optymalnośći powyższej najprostszej procedury zostałaby podważona, gdyby nie założenie, że a propos nie wiadomo, kiedy transmisja kończy się (kanał działa wiecznie, nie milknie). W przeciwnym wypadku, gdyby kanał milknął, to nie musielibyśmy wysyłać na przykład ostatniego odcinka zer, co w połowie wypadków dałoby zysk co najmniej jednego sygnału. Wartość oczekiwana długości transmisji zmniejszyłaby się co najmniej o połowę sygnału.

Spróbujmy podważyć mądrość ludową "legalnie". Umówmy się z adresatem, że zero 0 na pierwszym miejscu oznacza koniec transmisji, oraz że cały ciąg składa się wtedy wyłącznie z Orłów (zer). Gdy pierwszym wysłanym sygnałem jest 1, to po nim wysyłamy 10 milionów sygnałów po staremu, jakby się właśnie zaczęła transmisja. Może, bądźmy skąpi, gdy mamy przekazać same Orły czyli zera, a Reszkę czyli 1 jedynie na samym końcu, to sobie ten ostatni sygnał darujmy, czyli w sumie znowu wyślemy tylko 10 milionów sygnałów, zamiast 10 milionów + jeden. Jest to prawidłowa procedura, gdyż adresat za każdym razem jest w stanie rozpoznać koniec naszej transmisji.

Policzmy oczekiwaną szybkość tej procedury. Z jednej strony wspaniale zyskaliśmy przy ciągu zerowym, a z drugiej ponieśliśmy niewielką stratę przy wszystkich pozostałych ciągach poza jednym. Jaki jest bilans? Oczekiwana długość transmisji wynosi

[;1\cdot 1\cdot p + (2^L-2)\cdot (L+1)\cdot p + 1\cdot L\cdot p;]

    [;=\ (2^L\cdot L + (1 + 2^L - 2\cdot(L+1) + L)\cdot p;]

        [;=\ L\ +\ 1\ -\ (L+1)\cdot p\ \ >\ \ L;]

gdzie  [;L := 10^7;]  jest długością ciągu Orłów i Reszek, oraz

        [;p := \frac{1}{2^L} = \frac{1}{2^{{10}^7}};]

jest prawdopodobieństwem jednego ciągu, dowolnego. Widzimy, że średnia długość transmisji wzrosła prawie o jeden sygnał - niewiele, ale jednak.

---

Powróćmy do niepoprawnej procedury ucinania ogona zer. Poszło o drobiazg :-). Gdybyśmy mogli zaznaczyć jakoś koniec transmisji, to wszystko byłoby w porządku. Wystarczyłoby na koniec dać sygnał 2. Oznaczałoby to jednak inny, bardziej złożony (droższy) kanał, zdolny do przesyłania trójkowych bitów (0 1 2) zamiast dwójkowych (0 1).

W ramach naszego zwykłego kanału binarnego można próbować zakodować koniec transmisji jako specjalny ciąg kilku 0 i 1. Wtedy jednak płacimy karę, bo na koniec przesyłamy ten dodatkowy kod. Co gorsza, w trakcje transmisji musimy unikać przesłania kodu końca transmisji przedwcześnie, co powoduje dodatkowe wydłużanie kodu. Tymczasem zysk z ucinania ogona, gdy nie martwimy się o zaznaczenie końca transmisji, wynosi dokładnie jeden sygnał minus [;1/2^L;] (przeciętnie). Niełatwo zmieścić kod końca transmisji w ramach jednego sygnału minus [;1/2^L;], a nawet jest to niemożliwe - zresztą próbujcie, bo to może być dobre ćwiczenie.

Wstęp do Teorii Informacji. Cz.0

Wiadomo, że człowiek kulturalny, to taki, który ma solidne wykształcenie humanistyczne. Mało kto uważa, że także matematyczne. Od wynalezienia szpiegostwa, radio, telegrafu, telefonu, tv, lingwistyki, komputerów, plików komputerowych, dysków komputerowych, komunikacji satelitarnej i sond kosmicznych, internetu, baz danych... chyba wypada osobie kulturalnej także wiedzieć czym jest bit informacji, entropia, czym są różne kodowania. Krótko mówiąc, wypada wiedzieć coś niecoś z zakresu Teorii Informacji - uprzedzam, że nie chodzi wyłącznie o służby specjalne, donosicielstwo i lustrację.

Teoria Informacji jest częścią inżynierii i informatyki, ale dla mnie głównie matematyki, po czym stosuje się ją do innych dziedzin. Występuje też w fizyce.

Teoria Informacji jest nowoczesna. Stworzył ją i rozwinął jeden genialny człowiek - Claude Shannon. Sam jeden! - co jest niezwykłe i unikatowe. Wśród pierwszych, którzy docenili Shannona, i zastosowali jego idee twórczo, był wielki A.N.Kołmogorow. Po nich włączyły się setki i tysiące.

---

Teoria Informacji skupia się na badaniu kanału informacyjnego, a ściślej mówiąc na przygotowaniu informacji przed wejściem do kanału, i na interpretacji tego co z kanału wychodzi. Natomiast inżynierzy i fizycy mogą też zajmować się samym kanałem, badaniem go lub wymyślaniem lepszego. Matematyk zakłada, że własności kanału będą mu podane na talerzu. Co prawda matematyk też może rozwijać teorię badania kanału. Byłyby to badania o naturze statystycznej.

Kanał otrzymuje od świata pewnego rodzaju sygnały u swojego wejścia, przy czym może otrzymywać je z pewną prędkością, i nie szybciej. Podobnie, przekazuje sygnały światu u swojego wyjścia, znowu z pewną ograniczoną szybkością. Na ogół zakłada się, że rodzaj sygnałów i szybkość jest ta sama na obu końcach. Dodatkowo kanał może charakteryzować swoisty szum, który powoduje stratę lub deformację części sygnałów. Celem Teorii Informacji jest uzyskanie takich metod kodowania informacji przed wejściem do kanału, i dekodowania sygnałów po opuszczeniu kanału, by w miarę szybko, prosto i pełnie przekaz informacji był jak najwierniejszy - chcemy odzyskać informację, która została nadana u wejścia. Stąd potrzeba kodów, które wykrywają i poprawiają błędy. Wymagają one kodowania i dekodowania.

Ponieważ używanie kanału może być drogie, to często staramy się informację skondensować, by nasza przesyłka wykorzystywała jak najmniejszą część zdolności kanału (by inni mogli z niego korzystać jednocześnie), i by trwała jak najkrócej.

Ponieważ źli ludzie podsłuchują dobrych, to istnieje potrzeba enkrypcji i dekrypcji, czyli sekretnego kodowania i dekodowania - ta część Teorii Informacji nazywa się kryptografią. Połowę tej teorii, czyli sztukę niezrozumiałego wyrażania się, opanowali politycy.

Trzy cele Teorii Informacji: niezawodność, szybkość (w tym skrótowość), i sekretność przesyłki stwarzają napięcie, gdyż przeczą sobie nawzajem. Potrzeba specjalisty i naukowca, żeby je godził możliwie harmonijnie. Zresztą każdy z tych trzech kierunków teorii zasługuje także i przede wszystkim na odrębne badania, i tak się czyni. Mamy więc trzy powiązane teorie:

• kody wykrywające i poprawiające błędy;


• kompresja danych;


• enkrypcja

przy czym za każdym razem występuje kodowanie i dekodowanie.

prawa poezji sikają na kiepskie wiersze

poetry laws piss on poor poems
(Long live alliterations! :-)

                do laws of physics constrain physics?


                without laws there would be no physics and no physicists

                (the same holds for poetry and poets)


wh,
2010-12-19

---

Przetłumaczę:


                czy prawa fizyki ograniczają fizykę?


                bez praw fizyki nie byłoby ani fizyki ani fizyków

                (podobnie z poezją i poetami)


wh,
2010-12-19

Nieskończoność w topologii ogólnej

Przestrzenie topologiczne i T₁-przestrzenie

Rodzinę [;\mathbf F;] podzbiorów zbioru [;X;] nazywam fermologią, gdy spełnia następujące warunki:

1. Jeżeli  [;\emptyset \ne \mathbf{H}\subseteq \mathbf{F};],  to   [;\cap \mathbf{H}\in\mathbf{F};].


2. [;\forall_{\,A\,B\,\in\,\mathbf{F}}\ A\cup B\,\in\,\mathbf{F};]


3. [;\emptyset\ X\,\in \mathbf{F};]

Parę  [;(X\ \mathbf{F});],  gdzie [;\mathbf{F};] jest fermologią w [;X;], nazywamy przestrzenią topologiczną. Zbiory należące do [;\mathbf{F};] nazywamy domkniętymi. Jeżeli w przestrzeni topologicznej  [;(X\ \mathbf{F});]  każdy jednoelementowy podzbiór zbioru [;X;] jest domknięty to taką przestrzeń nazywamy T₁-przestrzenią, a jej fermologię T₁-fermologią.

Dowolną przestrzeń topologiczną  [;(X\ \mathbf{F});]  nazywamy dyskretną, a jej fermologię też dyskretną, gdy  [;\mathbf{F};]  jest rodziną wszystkich podzbiorów zbioru  [;X;]. Jest tak   [;\Leftarrow:\Rightarrow\quad\forall_{\,x\in X}\, X\backslash\{x\}\in\mathbf{F};]. Gdy przestrzeń lub fermologia nie jest dyskretna, to mówimy, że jest niedyskretna.

TWIERDZENIE 0  Zbiór X jest nieskończony [;\Leftarrow:\Rightarrow;] istnieje w X T₁-fermologia niedyskretna.

Zauważmy jeszcze, że przecięcie wszystkich T₁-fermologii w zbiorze X jest T₁-fermologią w X. Taka fermologia nazywana jest najsłabszą T₁-fermologią w X. Jeżeli w X istnieje niedyskretna T₁-fermologia, to będzie nią także ta najsłabsza.

Zbiory gęste

Zbiór [;A\subseteq X;] nazywamy gęstym w przestrzeni topologicznej   [;\Leftarrow:\Rightarrow\quad X;] jest jedynym zbiorem domkniętym, zawierającym [;A;].

TWIERDZENIE 1  Zbiór X jest nieskończony [;\Leftarrow:\Rightarrow;] istnieje w X taka T₁-fermologia, że w powstalej przestrzeni topologicznej istnieje podzbiór gęsty, różny od X.

Powyższe twierdzenie brzmi różnie od poprzedniego, ale gdy mu się przyjrzeć, to różnicy istotnej nie ma. Chodzi o to, że w zakresie T₁-fermologii, niedyskretne pokrywają się z tym, które dopuszczają podzbiór gęsty, różny od całego zbioru X.

Przestrzenie spójne

Przestrzeń topologiczną  [;(X\ \mathbf{F});]  nazywamy spójną [;\Leftarrow:\Rightarrow;] dopełnienie [;X\backslash A;] dowolnego niepustego zbioru domkniętego [;A;], różnego od [;X;], nie jest domknięte.

TWIERDZENIE 2  Zbiór [;X;] jest nieskończony   [;\Leftarrow:\Rightarrow\quad X;] ma co najmniej dwa różne elementy oraz istnieje w [;X;] taka T₁-fermologia, że powstała przestrzeń topologiczna jest spójna.

Tym razem dla nieskończonego [;X;] rodzina T₁-fermologii dających przestrzeń spójną różni się od rodziny wszystkich niedyskretnych (jest mniejsza). Wciąż jednak wystarczy sprawdzić T₁-fermologię najsłabszą.

Uwaga końcowa

Powyższe wyniki są rozbrajająco proste i naiwne. Celem tej notki było przede wszystkim wzbudzenie zainteresowania topologia, i dania powodu przynajmniej do zapamiętania pojęć jak zbiory domknięte, gęste, oraz spójność. Ta ostatnia ma już charakter geometryczny.

Nieskończoność w teorii mnogości

Wstęp

Definicje nieskończoności są w teorii mnogości przede wszystkim dwóch rodzajów: albo wprowadzają uporządkowanie, względem którego nie ma elementu naj (największego lub najmniejszego), albo w duchu Cantora mówią nam, że całość może być równoważna swojej części.

Pojawia się też nieskończoność świeżo w ogólnej topologii, ale to już jednak jest materiał na następny post.

NOTACJA  i  TERMINOLOGIA

Przyda nam się niewielki słowniczek pojęć:

• Iniekcja - jest to funkcja [;f : X \rightarrow Y;], która każde dwa różne argumenty odwzorowuje w różne wartości, czyli spełnia warunek:
  
  [;*\quad\quad\forall_{\,x'\,x''\in X}\ \left(f(x')=f(x'')\ \Rightarrow\ x'=x''\right);]
  
  (można skracać przez [;f;]).


• Surjekcja - jest to funkcja [;f : X \rightarrow Y;], która odwzorowuje [;X;] na całe [;Y;], czyli spełnia warunek:
  
  [;*\quad\quad\forall_{\,y\in Y}\,\exists_{\,x\in X}\ f(x) = y;]
  


• Bijekcja - jest to funkcja [;f : X \rightarrow Y;], która jednocześnie jest iniekcją i surjekcją.


• Relacja - w niniejszej nocie relacją w zbiorze [;X;] nazywamy dowolny podzbiór [;M\subseteq X^2;] kwadratu kartezjańskiego [;X^2 := X\times X;]. Dla relacji często zamiast
  
  [;*\quad\quad (x\ y)\ \in\ M;]
  
  piszemy
  
  [;*\quad\quad x\,M\,y;]
  
  
• Element prawy - Elementem prawym relacji [;M;] w [;X;] nazywamy każdy element [;x\in X;], dla którego nie istnieje [;y\in X;], spełniające:
  
  [;*\quad\quad x\,M\,y;]
  
  
• Element lewy - Elementem prawym relacji [;M;] w [;X;] nazywamy każdy element [;x\in X;], dla którego nie istnieje [;y\in X;], spełniające:
  
  [;*\quad\quad y\,M\,x;]
  
  
• Relacja przechodnia - relację [;M;] w [;X;] nazywamy przechodnią [;\Leftarrow:\Rightarrow;]
  
  [;*\quad\quad \forall_{x\,y\,z\,\in X}\ \left(\left(x\,M\,y\quad\&\quad y\,M\,z\right)\quad\Rightarrow \quad x\,M\,z\right);]
  
  W przypadku relacji przechodniej elementy prawe nazywamy często maksymalnymi, a elementy lewe - minimalnymi. Relacje przechodnie oznaczamy często symbolami typu [;<;] lub [;\le;]. W przypadku symboli typu odwróconego, jak [;>;], umawiamy się na opak, że prawe elementy są minimalne, a lewe - maksymalne (zwłaszcza, gdy relacja [;>;] jest odwrotnością relacji [;<;]).


• Relacja antysymetryczna - relację [;M;] w [;X;] nazywamy antysymetryczną [;\Leftarrow:\Rightarrow;] nie istnieje żadna para elementów  [;x\,y\in M;], spełniająca oba warunki: [;x\,M\,y\quad\&\quad y\,M\,x;].


• Porządek ostry - relację [;M;] w [;X;] nazywamy (częściowym) porządkiem ostrym [;\Leftarrow:\Rightarrow;] [;M;] jest przechodnie i antysymetryczne.

Mnogościowa charakteryzacja nieskończoności

Następujące własności zbioru X są równoważne. Zbiór X, z definicji, jest nieskończony [;\Leftarrow:\Rightarrow;] X posiada dowolną (a więc wszystkie) z następujących równoważnych własności:

1. Istnieje niepusta rodzina S podzbiorów zbioru X, taka że dla każdego zbioru A, należącego do S, istnieje zbiór B, należący do S\{A}, taki że B zawiera A - takie S nie ma elementu maksymalnego.


2. Istnieje niepusta rodzina S podzbiorów zbioru X, taka że dla każdego zbioru A. należącego do S, istnieje zbiór B, należący do S\{A}, taki że A zawiera B - takie S nie ma elementu minimalnego.


3. Istnieje iniekcja [;f : X\rightarrow X;], które nie jest surjekcją.


4. Istnieje surjekcja [;f : X \rightarrow Y;], która nie jest iniekcją.
   
5. Istnieje niepusty porządek ostry [;M;] w [;X;], nieposiadająca elementu prawego (tj. maksymalnego).


6. Istnieje niepusty porządek ostry [;M;] w [;X;], nieposiadający elementu lewego (tj. minimalnego).


7. Istnieje niepusta rodzina S niepustych podzbiorów zbioru X, taka że z jednej strony jej przecięcie jest puste, a z drugiej przecięcie dowolnych dwóch jej elementów zawiera inny element tejże rodziny S.


8. Istnieje rodzina S podzbiorów zbioru X, różnych od X, i taka że z jednej strony jej unia jest całym X, a z drugiej unia dowolnych dwóch jej elementów jest zawarta w innym elemencie tejże rodziny S.

Warunki dotyczące rodziny podzbiorów S są pokrewne warunkom dotyczących ostrego porządku. Gdy się chwilę zastanowić, to także warunek dotyczący iniekcji jest im pokrewny. Warunek dotyczący surjekcji jest równoważny warunkowi dotyczącemu iniekcji ze względu na aksjomat wyboru.

We własnościach, w których występuje istnienie ostrego porządku, można było żądać, żeby taka relacja istniała w podzbiorze. Wtedy podzbiór byłby nieskończony, a więc także cały zbiór (takie oczywiste "a więc" należy w matematyce uzasadniać). Równoważność takich wariacji z podanymi warunkami wymaga umiejętności przedłużania porządku z podzbioru na całość, co czyni się z pomocą aksjomatu wyboru (lub przynajmmniej pewnej jego osłabionej wersji).

Analogi warunków w terminach iniekcji i surjekcji można z łatwością sformułować w dowolnej kategorii - wystarczy te terminy zastąpić przez monomorfizm i epimorfizm. Daje to atrakcyjne podejście do nieskończoności w dowolnych kategoriach. Podobnie można postąpić w przypadku rodziny podzbiorów S - w kategoriach ogólnych można mówić o rodinie podobiektów. Trudniej o przeniesienie na kategorie ogólne relacji ostrego porządku.

Nieskończoność w logice matematycznej

Nieskończoność (potencjalna) metateorii jest w swojej naturze czymś fizycznym. Jest to część świata materialnego, przynajmniej według naszej interpretacji.

W samej logice, nieskończoności większość autorów nie wprowadza, dopiero czyni to przy okazji matematyki: arytmetyki lub - najczęściej - teorii mnogości. Ale na przykład logik Stephen Cole Kleene wolał z miejsca zanurzyć teorię liczb naturalnych, a więc także nieskończoność, w logice. Czyni się to następująco:

Predykat Nat(x) oznacza, że x jest liczbą naturalna (co może być prawdą lub fałszem, w zależności od tego co za x podstawimy). Wprowadza się do teorii stałą 1 oraz konstrukcję syntaktyczną Nxt(x) - to nie jest predykat, lecz w wyniku aksjomatów to będzie funkcja następnika x+1 liczby naturalnej x. Następnie do logiki wklucza się kilka dodatkowych, specjalnych aksjomatów, w tym aksjomaty Peano (wyrażenie =' oznacza "nierówne"):

(i) Nat(1)
(ii) Nat(x) to Nat(Nxt(x))
(iii) x=y to Nxt(x) = Nxt(y)
(iv) Nxt(x) = Nxt(y) to x=y
(v) Nat(x) to Nxt(x) =' 1
(vi) x =' 1 to EXISTS y ( Nxt(y) = x)

(VII) Dla każdego predykatu T(x) zachodzi następujący aksjomat vii_T (zapisany dla przejrzystości w trzech linijkach):

    (T(1) AND FORALL x ((Nat(x) AND T(x)) to T(Nxt(x))))

            to

                        FORALL x (T(x))

Tak więc mamy nieskończenie wiele aksjomatów vii_T ,  które łącznie dają schemat aksjomatyczny zwany aksjomatem indukcji matematycznej. Zdaje się, że chociaż sama nieskończoność niby nie wymaga nieskończonego schematu aksjomatów, to wymaga go teoria, w której ta nieskończoność żyje i ma sens. Tak jest w przypadku teorii liczb naturalnych, i tak jest także z teorią mnogości. Bez nieskończonych schematów teorie, mimo dopuszczenia nieskończoności, byłyby dosyć płytkie i ograniczone (pustawe).

Znaczenie powyższych aksjomatów jest następujące: operacja Nxt pozwala nam w nieskończoność iść do przodu. Aksjomat (v) mówi, że nie kręcimy się w kółko (co mogłoby sytuację uczynić skończoną). Indukcja (VII) mówi, że zbiór wszystkich liczb naturalnych tworzy (spójną jakby) ścieżkę, zaczynająca się od 1, krok po kroku zawierającą wszystkie liczby naturalne:

        1   Nxt(1)   Nxt(Nxt(1))   Nxt(Nxt(Nxt(1))) ...

Innych liczb naturalnych, według aksjomatu indukcji, nie ma. Czyli, dla uzyskania nieskończoności, aksjomatu indukcji nie potrzebujemy. Potrzebujemy go dla rozwinięcia teorii głębokiej.

Co prawda sytuacja jest subtelna. W sensie metateoretycznym możemy twierdzić, że uzyskaliśmy konstrukcję nieskonczona. Jest to oczywiste. Ale bez indukcji nie możemy dowieść, że tak naprawdę jest, bowiem nie możemy pokazać, że z czasem, poczynająć od 1, nie zaczneimy się kręcić w kółko - należy dowieść, że x jest różne na przykład od Nxt(Nxt(Nxt(x))). Jest to "materialnie" oczywiste dla nieskończonego podzbioru "liczb naturalnych" (bezindukcyjnych), ale nie mamy tego jak pokazać bez indukcji matematycznej (lub podobnego schematu), bo nawet Nxt(x) = x dla pewnych x może zachodzić, gdy indukcji się nie założy.

UWAGA: W metamatematyce, nawet bez indukcji matematycznej, i tak stosuje się to, co Profesor Andrzej Mostowski nazywał przesłanką indukcyjną. Chodzi o to, że predykaty i inne wyrażenia buduje się rekursyjnie (indukcyjnie). Kończy się konstrukcje takich wyrażeń aksjomatem: innych wyrażeń naszego (właśnie definiowanego) typu, poza wyżej podanymi, nie ma. To właśnie pozwala na dowody indukcukcyjne, tak powszechne także w informatyce.

Pierwszy kontakt z nieskończonością

Przede wszystkim nieskończoność występuje w metamatematyce. Po prostu mamy potencjalnie nieskończenie wiele różnych zapisów, w szczególności predykatów, gdzie predykat rozumiem w sensie logiki matematycznej. Poświęcę temu kilka słów.

Niektórzy autorzy, definiując teorię matematyczną, zaczynają od tego, że ma nieskończony alfabet, po czym dają przykład:

    x x' x'' x''' ...

Wolałbym, żeby zbioru tak złożonych wyrażeń, jak x'''', nie nazywali alfabetem. Prawdziwa teoria powinna zaczynać od skończonego zbioru znaków, przy tym niewielkiego, łatwego do ogarnięcia wzrokiem, tak by każde dwa różne znaki można było z łatwościę odróżnić. Można na przykład, przynajmniej celem ścisłego wprowadzenia danej teorii, do zbioru znaków wyjściowych zaliczyć 26 liter małych i 26 dużych alfabetu angielskiego, cyfry dziesiętne 0 ... 9, nawiasy ( ), prim ', oraz ' + - * =. Razem powiedzmy 60 znaków (teoretycznie dwa wystarczyłyby). Dopiero na następnym etapie buduje się wyrażenia oznaczające na przykład zmienne, jak wymienione wyrażenia: x x' x'' x''' ... (które kolejno składają się z 1 2 3 ... znaków - nie są pojedynczymi znakami). Można mieć też konstrukcje definiujące nowe pojęcia, jak powiedzmy SUMA, których syntaks znowu używa podane wyjściowe znaki (tu: A M S U).

UWAGA 0: Odstęp  " "  należy do metateorii (nie jest znakiem teorii). W każdym razie możemy tak się rozsądnie umówić.

UWAGA 1: Można teorię stworzyć dla komputera, żeby komputer ją uprawiał. Znowu wyjściowych "znaków" powinno być skończenie wiele, i powinny być łatwo przez komputer rozróżniane. Z tego powodu stosuje się tylko dwa znaki wewnątrz komputera, o których ludzie na ogół mówią 0 oraz 1. Próbowano więcej "znaków", ale z powodów technologicznych wtedy kłopoty z błędami tak wzrastały, że w zasadzie z tych prób zrezygnowano, prawie.

---

Kilka słów o predykatach: są to ciągi znaków (struny czyli po angielsku strings), w których jednoznacznie można wyróżnić zmienne (jeżeli występują). Gdy za zmienne podstawimy konkretne wartości stałe, to powinniśmy otrzymać zdanie (w sensie formalnej definicji danej teorii), czyli coś, co jest albo prawdziwe albo fałszywe. Czyli predykat jest funkcją logiczną, której wartościami są Prawda i Fałsz. Na przykład słynny jest predykat Fermata, z jego tak zwanego Ostatniego Twierdzenia:

    EXP(x n) + EXP(y n) = EXP(z n)

gdzie EXP(a b) oznacza [;a^b;], ale dla ilustracji chciałem się ograniczyć do wcześniej wspomnianych 60 znaków. Fermat wyraził przypuszczenie, że ten predykat jest zawsze fałszywy, gdy x y z n są liczbami naturalnymi 1 2 ..., takimi że n > 2. Dowód zajął ponad trzysta lat.