Arytmetyka – ujęcie aksjomatyczne (1)

Wprowadzę obecnie aksjomaty liczb naturalnych. Będzie to ujęcie Peano. Odnośnie języka, będę używać rachunku predykatów pierwszego rzędu. Przyjmę, że mam do dyspozycji nieskończoną (przeliczalną) ilość symboli stałych, symboli funkcyjnych i zmiennych. Nie będę się przejmować za bardzo składnią zapisu, o ile będzie jednoznaczne, co przedstawiam. Czytelnik przekona się sam, że nie przeszkadza to ścisłości wywodu, a jedynie zabezpiecza nas przed tysiącami zbędnych zastrzeżeń. Aby zapisać aksjomaty wyszczególniam dwa symbole stałe \{0,1\} i dwa symbole funkcyjne dwuargumentowe \{+, \cdot\}.

A1. \forall(x) x + 1 \not= 0.
A2. \forall(x,y) x + 1 = y + 1 \to x = y.
A3. \forall(x) x + 0 = x.
A4. \forall(x,y) x + (y + 1) = (x + y) + 1.
A5. \forall(x) x \cdot 0 = 0.
A6. \forall(x,y) x\cdot(y+1) = x \cdot y + x.

Następnie określimy rodzinę aksjomatów

AI. Dla każdej formuły \phi(y_1, \dots, y_n, x) następująca formuła jest aksjomatem \forall(\vec{y}) (\phi(\vec{y}, 0) \wedge (\forall(n) \phi(\vec{y}, n) \to \phi(\vec{y}, n + 1)) \to (\forall(x)\phi(\vec{y}, x)), gdzie \vec{y} jest skrótem (meta-symbolem), który oznacza y_1, \dots, y_n (będziemy jeszcze stosować tę notację).

Reguła tworzenia aksjomatów AI, to oczywiście ‘indukcja matematyczna’. Jak więc widać system Peano zawiera nieskończenie wiele aksjomatów.
Do zapisania aksjomatów użyłem symboli stałych \{0, 1\} i dwóch symboli funkcyjnych \{+, \cdot\}. Co z resztą symboli stałych i funkcyjnych, które sobie zarezerwowałem powyżej?
Przystanę na konwencje:

K1. Jeżeli formuła \exists(x)p(x) jest twierdzeniem arytmetyki, gdzie p nie zawiera innych symboli stałych niż \{0, 1\} i innych symboli funkcyjnych niż \{+, \cdot\}, to istnieje taki symbol stały C_p, że p(C_p).

K2. Jeżeli formuła \forall(\vec{y})\exists(x) p(\vec{y}, x) jest twierdzeniem arytmetyki, gdzie p nie zawiera innych symboli stałych niż \{0, 1\} i innych symboli funkcyjnych niż \{+, \cdot\}, to istnieje taki symbol funkcyjny F_p, że \forall(\vec{y}) p(\vec{y}, F_p(\vec{y})).

Dla kompletności możemy dodać sobie konwencję K3.

K3. Nie istnieją inne symbole stałe niż uzyskane za pomocą konwencji K1 i nie istnieją inne symbole funkcyjne niż uzyskane przez konwencję K2.

Uważny czytelnik zauważy, że K1 i K2 dodają nam dwie nowe przeliczalne klasy aksjomatów. Akjsomaty te nie wnoszą żadnej nowej treści, są usatnowione jedynie w tym celu, abyśmy mogli używać wygodnie nowych fukncji i stałych, które będziemy chcieli wprowadzić. Należy również zauważyć, że K1 i K2 będą nam służyły wyłącznie dla wygody. Każdą formułę zapisaną z użyciem ‘nowych’ symboli stałych i funkcyjnych da się przepisać do równoważnej używając jedynie \{0, 1, +, \cdot\} i symboli logicznych.

Podam teraz kilka twierdzeń, które bardzo łatwo można wyprowadzić z aksjomatów:
T1. \forall(x) x\cdot 1 = x.
T2. \forall(x,y) x + y = y + x.
T3. \forall(x,y) x\cdot y = y \cdot x.
T4. \forall(x,y,z) x\cdot(y + z) = x\cdot y + x\cdot y.

Począwszy od tego miejsa, jeśli to możliwe będę opuszczał znak \cdot a zatem xy będzie oznaczało x\cdot y. Ogólnie dwa termy zapisane bezpośrednio obok siebie będą oznaczały mnożenie.

Wprowadzimy teraz kilka meta-symboli, aby ułatwić sobie zapis
D1. x \leq y będzie skrótem formuły \exists(k) x + k = y.
D2. x < y będzie skrótem formuły (x \leq y) \wedge x \not= y.
D3. x|y będzie skrótem formuły \exists(k) x\cdot k = y.

Chciałbym tutaj zwrócić uwagę na analogie pomiędzy x < y, a x|y. Proszę zobaczyć, że formuły te różnią się tylko zamianą symbolu funkcyjnego z + na \cdot. Tak więc można powiedzieć, że relacja podzielności jest dla mnożenia tym, czym relacja mniejszości dla dodawania. O ile jednak bardziej skomplikowany porządek wprowadza |!

Proszę zauważyć, że liczby naturalne w tradycyjnym zapisie dziesiętnym możemy traktować jako nazwy stałych. Na mocy konwencji K1 istnieje stała dla formuły \exists(y) y = 1 + 1, będziemy ją po prostu zapisywać jako 2, podobnie istnieje stała dla formuły \exists(y) y = (1 + 1) + 1, będziemy ją nazywać 3 i tak dalej.

Czy istnieje symbol funkcyjny odpowiadający potęgowaniu?

Tak naprawdę pierwszym poważnym wyzwaniem, który staje przed naszą arytmetyką jest problem istnienia operatora potęgowania. Intuicja potęgowania jest jasna. Aby obliczyć x^y należy y razy pomnożyć przez siebie x. Jednak na razie mamy do dyspozycji jedynie operatory \{+, \cdot\}. Bystry czytelnik zauważy, że potęgowanie ma się do mnożenia tak, jak mnożenie do dodawania. xy oznacza przecież y-krotne dodanie do siebie x. Jak wyrażone zostało to w aksjomatyce? Poprzez dwa aksjomaty:

A5. \forall(x) x \cdot 0 = 0.
A6. \forall(x,y) x\cdot(y+1) = x \cdot y + x.

Pojawia się więc naturalny pomysł, aby określić operator potęgowania następująco:

\forall(x) x^0 = 1.
\forall(x,y) x^{y+1} = x^y\cdot x.

Nie możemy jednak tak zrobić. Mimo, że jest to klarownie zapisana definicja indukcyjna nie jest ona poprawna w języku arytmetyki Peano. Nie istnieje taka reguła wprowadzania symboli funkcyjnych. Ktoś mógłby pomyśleć, że AI jest taką regułą. Proszę spróbować! Nie jest. Aby ją zastosować musimy mieć jakąś formułę \phi. Nie możemy w niej zawrzeć symbolu potęgowania, bo ciągle nie wiemy, czy należy on do naszego języka. Nie możemy zapisać tych zdań jako definicji potęgowania, bez uznania ich za dodatkowe aksjomaty, wiążące nowy symbol funkcyjny. Ktoś mógłby zasugerować, że możemy dodać te aksjomaty i nowy symbol funkcyjny. Możemy. Ale nie chcemy. Będę bowiem chciał pokazać, że nie trzeba ich dodawać, bo symbol potęgowania już istnieje w języku dzięki konwencji K2.

Pokażemy więc, że istnieje formuła POW(x,y,a), którą da się zapisać używając wyłącznie \{0,1,+,\cdot\} oraz symboli logicznych, która jest prawdziwa wtedy i tylko wtedy, gdy y-krotne pomnożenie x przez siebie, daje nam a. Okaże się, że arytmetyka Peano z dodawaniem i mnożeniem jest na tyle bogata, że istnieje w niej również operacja potęgowania. O tym jednak czytelnik przekona się w następnej części cyklu Arytmetyka – ujęcie aksjomatyczne.

KOMENTARZE (1)

  1. Michał Stanisław Wójcik2012-12-04 13:50:47

    Tak sobie myślę na tymi konwencjami K1 i K2. Przez K1 zapewniłem sobie nieco sztucznie $\omega-$niesprzeczność arytemetyki, jeżeli jest niesprzeczna.

    Jeżeli bowiem dane $p(.)$ jest udowonione dla wszystkich symboli stałych w języku i równocześnie byłoby udowodnione $\exists(x) \neg p(x)$, czyli byłaby $\omega-sprzeczność$, to wtedy oczywiście mamy stałą $C_{\neg p}$ taką, że $\neg p(C_{\neg p})$ jest aksjomatem na mocy K1, ale przecież $p(C_{\neg p})$ jest udowodnione (bo jest udowodnione dla wszystkich stałych). To przeczyłoby zwykłej niesprzeczności. Czyli mamy $\omega-niesprzeczność$.

    Dzieje się to jednak kosztem zupełności. Arytmetyka z K1 już od początku bowiem jest niezupełna. Niech $p(x) = ‘x|2′$, wtedy mamy stałą $C_p$ taką, że $p(C_p)$ i banalna formuła $C_p = 1$ jest już niedowodliwa. Można wykazać jedynie $C_p = 0 \vee C_p = 1 \vee C_p = 2$.

    Trzeba będzie więc pamiętać, że K1 i K2 zostały przyjęte wyłącznie dla wygody i gdy będzie potrzeba jakichś twierdzeń o samej PA trzeba będzie wracać do postaci PA jedynie z $\{0, 1, +, \cdot\}$.

  2. Podgląd live
    Nie opublikowałeś jeszcze tego komentarza! Aby opublikować naciśnij przycisk Opublikuj Komentarz.

Dodaj komentarz