W poprzednim artykule opowiedziałem, jak – mając do dyspozycji zbiór pusty – możemy skonstruować liczby naturalne. Okazuje się jednak, że nie jest to jedyna metoda. Możemy bowiem potraktować jako fundamentalne pojęcie coś innego niż zbiór.
Oczywiście, można w tym momencie zadać (całkiem zasadne) pytanie: po co? Skoro mamy (dla celów praktycznych) reprezentację liczb naturalnych przy użyciu systemu pozycyjnego (powiedzmy, dziesiątkowego czy binarnego), a także (dla celów teoretycznych) przy użyciu zbiorów, czego jeszcze nam brakuje?
Możliwe jest kilka odpowiedzi na to pytanie. Pierwsza z nich, łatwiejsza (choć niekoniecznie fałszywa!), brzmi po prostu – dla rozrywki. Ktoś mógłby w tym momencie się oburzyć. Cóż to! Uczeni chcą się po prostu bawić za pieniądze podatników, a nie ciężko pracować nad ulepszaniem świata?
Otóż nie jest to takie proste. Wygląda bowiem na to, że bez tego pierwszego – nie ma drugiego. Być może najlepszym (a kto wie, czy nie jedynym) znanym ludzkości sposobem, by wyzwolić potencjał twórczy uczonych, jest danie im możności swobodnego zaspokajania ich ciekawości. Zabawa intelektualna (na przykład, wymyślanie dziwacznych sposobów zdefiniowania liczb naturalnych!) pozwala trenować umysł, głębiej zrozumieć znane – wydawałoby się – pojęcia. Całkiem możliwe również, że człowiek – odprężony zabawą intelektualną – ma większe szanse na wpadnięcie na genialny pomysł. Mieć pretensje do uczonych, że „tracą czas” na „jałowe spekulacje”, to trochę tak, jak mieć pretensje do piłkarzy, że na treningach podbijają po kilkadziesiąt razy piłkę w ten sposób, aby nie spadła na ziemię. Przecież w czasie meczu nie muszą umieć tego robić – a jednak treningi takie mają sens!
Na zakońcenie tej dygresji dodam, że są i głębsze powody, dla których jest sens rozważać konstrukcję, którą opiszę za chwilę – o nich jednak wspomnę na końcu.
Umysły Czytelników pewnie nurtuje już pytanie, cóż to może być za fundamentalny obiekt, na którym tym razem zamierzam oprzeć konstrukcję liczb naturalnych. Tym obiektem jest funkcja. Pojęcie to jest pewnie znane ze szkoły; nieco bardziej zaawansowani Czytelnicy wiedzą też zapewne, że funkcje można z kolei zdefiniować w terminach zbiorów. Nie to jest jednak dzisiaj dla nas ważne. Nie będziemy formalnie definiować funkcji, poprzestawszy na intuicyjnym jej rozumieniu.
Jednym z wielu sposobów myślenia o funkcji jest wyobrażenie sobie jej jako czegoś w rodzaju automatu do sprzedaży napojów. Wyobraźmy sobie maszynę, która po wrzuceniu pięćdziesięciogroszówki daje nam kubek wody, po wrzuceniu złotówki herbatę, a po wrzuceniu dwuzłotówki – kawę. Mówiąc nieco bardziej abstrakcyjnie, funkcja to coś, czemu możemy coś dać i co oddaje nam coś w zamian. Ważne jest przy tym, że to, co dostaniemy, jest jednoznacznie określone przez to, co wrzucimy (analogia z prawdziwym automatem do napojów trochę się tu załamuje) – innymi słowy, wrzucając za każdym razem to samo (np. monetę o odpowiednim nominale), za każdym razem otrzymamy to samo (np. puszkę ulubionego napoju)1.
Jak prawdopodobnie Czytelnik się domyśla, do automatu z napojami nie możemy wrzucić czegokolwiek; próba wrzucenia doń guzika, pudełka po butach albo granatu bądź nie da żadnego rezultatu, bądź w ogóle się nie uda, bądź da rezultaty raczej opłakane. To, jaki rodzaj rzeczy nadaje się do „wrzucenia” do danej funkcji nazywa się jej dziedziną. Przykładowo, możemy (przechodząc na bardziej matematyczny grunt) wyobrazić sobie funkcję, która przyjmuje wyłącznie liczby naturalne i w zamian oddaje ich kwadraty. Jeżeli wrzucimy do takiej „maszyny” dwójkę, dostaniemy czwórkę, jeżeli wrzucimy do niej zero, odda nam z powrotem zero, itp. – jednak nie da się do niej „wrzucić” liczby \(\pi\).
Nic nie stoi na przeszkodzie, aby połączyć „wylot” jednej maszyny z „wlotem” drugiej (takiej samej bądź innej) – oczywiście pod warunkiem, że „ta druga” funkcja przyjmuje rzeczy oddawane przez pierwszą. Odpowiada temu matematyczna idea składania funkcji. Przykładowo, jeżeli dysponujemy funkcją, która oddaje nam liczbę o jeden większą, niż jej daliśmy, i drugą, która oddaje nam dwukrotność wrzuconej liczby, po ich złożeniu („połączeniu”) otrzymamy funkcję, która – otrzymawszy na przykład liczbę jeden – oddaje liczbę trzy, zaś otrzymawszy liczbę dwa – oddaje pięć. Możemy też złożyć te same dwie funkcje w odwrotnej kolejności. Otrzymamy wówczas funkcję, która z jedynki zrobi cztery, z dwójki – sześć itd.
Pójdźmy teraz o krok dalej. W poprzednich akapitach rozważaliśmy funkcję, która „przyjmowała” (i „oddawała”) liczby naturalne. Zapowiedziałem jednak, że pojęcie funkcji posłuży nam do zdefiniowania tychże liczb naturalnych – nie będziemy więc mogli na razie nimi się posługiwać. Przypomnę, że gdy rozważaliśmy konstrukcję von Neumanna liczb naturalnych, jedynym obiektem, jaki posłużył nam do ich zdefiniowania, był zbiór pusty. Tym razem będzie podobnie – nie będzie nam potrzebne nic poza funkcjami. Proszę uważnie przeczytać poprzednie zdanie. Jeśli będziemy wykorzystywać wyłącznie funkcje, jakie obiekty nasze funkcje będą mogły przyjmować i oddawać? Odpowiedź jest prosta: inne funkcje.2
Aby móc wygodnie mówić o funkcjach, będziemy potrzebować nieco symboli. Wyobraźmy sobie, że wspomnianą wcześniej funkcję, która wylicza kwadraty liczb, oznaczymy literą \(f\). Wówczas fakt, że dajemy jej na przykład liczbę \(5\) i dostajemy liczbę \(25\) oznaczamy zapisem \(f(5)=25\). Nieco rzadziej używane oznaczenie tej funkcji wygląda następująco: \(x\mapsto x^2\) (symbol ten oznacza „funkcję, która z \(x\)-a robi \(x^2\)”) – możemy więc napisać i tak: \((x\mapsto x^2)(5)=25\). Oznaczenie takie jest wygodne, gdy z jakichś powodów nie chcemy wymyślać dla naszej funkcji specjalnej nazwy (jak na przykład litery \(f\)) – nic więc dziwnego, że tak oznaczone funkcje nazywa się niekiedy funkcjami anonimowymi.
Mając odpowiednią symbolikę, możemy na przykład pomyśleć o funkcji \(x\mapsto x\). Nazywa się ją niekiedy funkcją identycznościową, gdyż oddaje ona obiekt dokładnie identyczny z tym, który otrzymała. (W szkolnej notacji opisalibyśmy ją pewnie wzorem \(y=x\).) Poznawszy tę funkcję, możemy wreszcie napisać definicję liczb naturalnych w tzw. notacji Churcha. Otóż zero to funkcja, która – otrzymawszy jakąkolwiek funkcję – oddaje nam funkcję identycznościową. Jeden zaś to funkcja, która – gdy damy jej jakąś funkcję \(f\) – odda nam tę samą funkcję. Wreszcie, dwa to funkcja, która funkcję \(f\) zmienia w funkcję \(f\) złożoną z nią samą, i tak dalej.
Ponieważ może to brzmieć nieco zawile, powtórzmy powyższe definicje innymi słowami. Zero to funkcja, która dostaje jakąś funkcję \(f\) i oddaje nam funkcję, która – gdy damy jej obiekt \(x\), zwraca nam ten sam obiekt. Innymi słowy, ani razu nie przekształca go funkcją \(f\). Jeden to funkcja, która – gdy dostaje funkcję \(f\) – oddaje nam funkcję polegającą na przekształceniu dowolnego obiektu funkcją \(f\) jeden raz. Dwa to funkcja, która – dostawszy funkcję \(f\) – zwraca funkcję polegającą na dwukrotnym zastosowaniu funkcji \(f\). I tak dalej.
Zobaczmy, jak działa to dla jakiejś konkretnej funkcji. Dla uproszczenia rozważań rozważmy zwykłą funkcję liczbową – niech funkcja \(f\) podwaja daną jej liczbę całkowitą (innymi słowy, \(f(x)=2x\) dla \(x\in\mathbb{Z}\)).3 Wówczas \(1\) to funkcja, która – otrzymawszy funkcję \(f\) – oddaje tę samą funkcję. Liczba \(2\) to funkcja, która – otrzymawszy funkcję \(f\) – oddaje funkcję mnożącą przez \(4\). Liczba \(3\) to inaczej funkcja, która – gdy dostanie funkcję \(f\) – oddaje funkcję mnożącą przez \(8\).
Jeżeli pomyślimy o funkcji jako o czynności, którą możemy wykonywać, to liczebniki Churcha odpowiadają po prostu intuicji powtarzania jakiejś czynności odpowiednią liczbę razy. Na przykład, powtórzenie czynności podwajania trzykrotnie to czynność mnożenia przez 8! Jak widać, mimo całej dość abstrakcyjnej oprawy, jest to w gruncie rzeczy całkiem prostym pomysłem.
I znów w tym momencie należy dodać, że powyższa konstrukcja nie jest kompletna – brakuje w niej choćby zdefiniowania podstawowych operacji, jak branie następnika (nie wspominając o dodawaniu czy mnożeniu) czy porównywanie liczb. Są one oczywiście wykonalne, ale nieco żmudne, i wykraczają poza ramy tego artykułu, który zmierza już ku końcowi.
Obiecałem na wstępie, że wspomnę o innych przyczynach, dla których rozważanie konstrukcji Churcha może być przydatne. Jedna z wielu takich przyczyn jest związana z tzw. hipotezą Churcha–Turinga. W matematyce rozpatruje się wiele obiektów – na przykład zbiory – ale jednym z najbardziej przydatnych w zastosowaniach pojęciem matematycznym jest pojęcie funkcji. Zrobiło ono iście zawrotną karierę w fizyce i innych naukach przyrodniczych, a nawet w ekonomii czy naukach społecznych. Jest tak m.in. dlatego, że świetnie nadaje się ono do modelowania zjawisk zachodzących w czasie. W praktyce oczywiście najczęściej obliczenia dotyczące modeli matematycznych wykonuje się na komputerach. Pojawia się zatem pytanie o to, które funkcje dają się obliczyć przez komputer. Jedną z prób udzielenia odpowiedzi na to pytanie podjął Alan Turing, tworząc koncepcję tzw. „maszyny Turinga”, która jest abstrakcyjnym modelem komputera. Jest ona całkiem adekwatnym opisem działania rzeczywistych komputerów, których procesory są po prostu nieco bardziej skomplikowanym modelem maszyny Turinga. Zupełnie inną próbą jest rachunek lambda Alonzo Churcha, którego jednym z elementów jest konstrukcja liczb naturalnych zaprezentowana w niniejszym artykule. Opiera się ona nie tyle na procedurze obliczania (zwanej fachowo algorytmem), jak maszyna Turinga, ale raczej na czymś w rodzaju wzoru funkcji (a jak wiemy ze szkoły, wzory również są zwięzłymi opisami pewnych obliczeń). Ma ona tę przewagę nad maszyną Turinga, że jest bardziej elegancka matematycznie – a także stanowi teoretyczną podstawę modnych ostatnio funkcyjnych języków programowania. Hipoteza Churcha–Turinga (w jednym z wariantów) głosi, że funkcjami obliczalnymi są właśnie te, które można opisać w rachunku lambda. Dlatego właśnie jest istotne, że jesteśmy w stanie skonstruować w nim (między innymi) liczby naturalne – dzięki temu operacje na nich kwalifikują się do funkcji obliczalnych. (Więcej o hipotezie Churcha–Turinga – z jeszcze innego punktu widzenia, tzw. funkcji rekurencyjnych – można przeczytać na przykład w książce R. Murawskiego Funkcje rekurencyjne i elementy metamatematyki. Problemy zupełności, rozstrzygalności, twierdzenia Gödla.)
Oczywiście, cały wysiłek, jaki włożyliśmy w poprzednim i tym tekście, dotyczy jedynie liczb naturalnych. One jednak nam nie wystarczą – potrzebujemy prócz nich liczb całkowitych (czyli brak nam ujemnych) i wymiernych (czyli brak nam ułamków), a także rzeczywistych (w przypadku których nieco trudniej dostrzec, czego właściwie nam brakuje). To już jednak temat na osobny artykuł.
Przypisy
- Wymóg ten sprawia między innymi, że funkcje znane z informatyki nie są funkcjami dla matematyka, ale to już temat na inny artykuł!
- Jeżeli koncepcja funkcji, która przyjmuje jedną funkcję i oddaje inną wywołuje u Czytelnika zawrót głowy i wrażenie kompletnego oderwania od rzeczywistości, spieszę donieść, że pierwsze jest uzasadnione, a drugie ani trochę.
- Oczywiście, ponieważ jesteśmy dopiero na etapie definiowania liczb naturalnych – o całkowitych nie wspominając – jest to pewne oszustwo. Dla przejrzystości pozostańmy jednak przy tym przykładzie – wszak funkcje, które liczby zamieniają na inne liczby są nam dużo bliższe niż funkcje, które przyjmują i oddają funkcje.
Artykuł został sfinansowany dzięki wsparciu pozyskanemu przez Poznańską Fundację Matematyczną od Miasta Poznań na realizację projektu ,,Potęga matematyki''.