Aksjomaty Peano

W matematyce , że aksjomaty Peano są aksjomaty dla arytmetyka początkowo zaproponowane w końcu XIX e wieku przez Giuseppe Peano , a które znamy dzisiaj kilka prezentacji, które nie są równoważne, zgodnie z podstawowej teorii , teoria zbiorów , drugiego rzędu lub logika wyższego rzędu lub logika pierwszego rzędu . Richard Dedekind zaproponował dość podobną formalizację, w formie nieaksjomatycznej.

Aksjomaty

Aksjomatyczną definicję liczb całkowitych Peano można opisać za pomocą pięciu aksjomatów:

Element o nazwie zero i oznaczony jako $0$ jest liczbą naturalną.
Każda liczba naturalna $n$ ma niepowtarzalnego następcę, oznaczoną $s ( n )$ lub $Sn,$ która jest liczbą naturalną.
Żadna liczba naturalna nie ma następcy $0$ .
Dwie liczby naturalne z tym samym następnikiem są równe.
Jeśli zbiór liczb naturalnych zawiera $0$ i zawiera następcę każdego z jego elementów, to ten zbiór to N .

Pierwszy aksjomat pozwala przyjąć, że zbiór N liczb naturalnych nie jest pusty , trzeci, że ma pierwszy element, a piąty, że weryfikuje zasadę powtarzalności .

Bardziej formalnie, powiedzieć o $( E , c , f )$ , że spełnia ona aksjomaty Peano, to powiedzieć, że spełnia on następujące własności:

E to zbiór mający c dla elementu,
f jest funkcją samego E ,
c ∉ Im ( f ) ,
f jest iniektywną ,
Dowolna część F z E zawierająca c i stabilne f (to znaczy takie, że f ( F ) ⊂ F ) jest równe E .

Sformułowanie własności 5 zawiera kwantyzację części E : mówi się, że taka własność jest drugiego rzędu . Taka struktura jest modelem aksjomatów Peano, postrzeganych jako aksjomaty w logice drugiego rzędu.

Pierwotne sformułowanie Peano zawierało inne aksjomaty, na przykład dotyczące równości, które dziś są postrzegane jako część leżącej u ich podstaw logiki.

Arytmetyka Peano

Arytmetyka Peano często odnosi się do „ograniczenia” aksjomatów Peano do języka arytmetyki pierwszego rzędu, czyli rachunku orzeczników egalitarnych z sygnaturą {0, s , +, ∙}. Zmienne języka wyznaczają przedmioty w dziedzinie interpretacji, tu liczby całkowite. W tym języku pierwszego rzędu nie mamy zmiennych dla zbiorów liczb całkowitych i nie możemy określić ilościowo tych zbiorów. Nie możemy zatem bezpośrednio wyrazić powtarzalności za pomocą stwierdzenia takiego jak w poprzednim akapicie („dowolny podzbiór…”). Rozważamy wtedy, że podzbiór N jest wyrażony przez właściwość jego elementów, właściwość, którą piszemy w języku arytmetyki.

Aksjomaty Peano stają się wtedy następującymi aksjomatami:

$\ forall x \ l nie (sx = 0)$
${\ displaystyle \ forall x \ lewo (x = 0 \ lor \ istnieje y \ lewo (x = s (y) \ prawo) \ prawo)}$
${\ displaystyle \ forall x \ forall y (sx = sy \ Rightarrow x = y)}$
$\ forall x (x + 0 = x)$
$\ forall x \ forall y (x + sy = s (x + y))$
$\ forall x (x \ cdot 0 = 0)$
$\ forall x \ forall y (x \ cdot sy = (x \ cdot y) + x)$
Dla dowolnej formuły z n + 1 wolnymi zmiennymi, $\ phi (x, x_ {1}, \ ldots, x_ {n})$ ${\ displaystyle \ forall x_ {1} \ ldots \ forall x_ {n} \ lewy (\ lewy (\ phi \ lewy (0, x_ {1}, \ ldots, x_ {n} \ prawy) \ klin \ lewy ( \ forall x \ left (\ phi \ left (x, x_ {1}, \ ldots, x_ {n} \ right) \ Rightarrow \ phi \ left (sx, x_ {1}, \ ldots, x_ {n} \ prawo) \ prawo) \ prawo) \ prawo) \ prawostrzałka \ forall x \ phi \ lewo (x, x_ {1}, \ ldots, x_ {n} \ prawo) \ prawo)}$

Punkt 8 powyżej jest diagramem aksjomatów , który reprezentuje policzalną nieskończoność aksjomatów, po jednym dla każdej formuły . Schemat aksjomatu wyraża powtarzalność : we wzorze zmienne są parametrami, które można zastąpić dowolnymi liczbami całkowitymi . Aksjomat formuły staje się stosowany do : $\ phi (x, x_ {1}, \ ldots, x_ {n})$ $\ phi (x, x_ {1}, \ ldots, x_ {n})$ $(x_ {1}, \ ldots, x_ {n})$ $(p_ {1}, \ ldots, p_ {n})$ $\ phi (x, x_ {1}, \ ldots, x_ {n})$ $(p_ {1}, \ ldots, p_ {n})$

${\ displaystyle \ lewy (\ lewy (\ phi \ lewy (0, p_ {1}, \ ldots, p_ {n} \ prawy) \ klin \ lewy (\ forall x \ lewy (\ phi \ lewy (x, p_ {1}, \ ldots, p_ {n} \ prawo) \ prawostrzałka \ phi \ lewo (sx, p_ {1}, \ ldots, p_ {n} \ prawo) \ prawo) \ prawo) \ prawo) \ prawostrzałka \ forall x \ phi \ lewy (x, p_ {1}, \ ldots, p_ {n} \ prawy) \ prawy)}$

Wyraża to, że jeśli zbiór zawiera $0$ i zawiera następcę każdego z jego elementów, N . $\ lewo \ {x \ in \ mathbb {N} \ mid \ phi \ lewo (x, p_ {1}, \ ldots, p_ {n} \ prawo) \ prawo \}$

Jednak wzór aksjomatów nie daje już tej własności dla podzbiorów N, które są zdefiniowane w języku arytmetyki pierwszego rzędu: policzalnej nieskończoności podzbiorów N .

Aksjomat 2 mógłby zostać wyeliminowany: dowodzi tego rekurencja, raczej osobliwa rekurencja, ponieważ jeśli trzeba odróżnić przypadek 0 od przypadku następcy, w tym drugim przypadku hipoteza rekurencyjna nie jest użyteczna.

Arytmetyka Peano nie jest skończenie aksjomatyzowalna . Rozszerzając jednak język o zmienne drugiego rzędu (zmienne predykatów) i ograniczając rozumienie do formuł pierwszego rzędu, można uzyskać w tym nowym języku skończony system aksjomatów, który ma takie same konsekwencje jak arytmetyka Peano w oryginale. język (podobny do teorii mnogości von Neumanna-Bernaysa-Gödla vis-à-vis teorii mnogości Zermelo-Fraenkla ).

Istnienie i wyjątkowość

Istnienie modelu aksjomatów Peano (w drugiej kolejności) można ustalić za pomocą bardzo typowej konstrukcji w ramach teorii mnogości :

Ustawiamy 0 = ∅.
Definiujemy „funkcja” (intuicyjny sens) następcy s wywoławcza, za każdy zestaw posiada ,

s ( a ) = a { a }.

Zbiór N jest przecięciem wszystkich zbiorów, do których należy 0 i które są zamknięte następnikiem; Zamknięte pod następcy, gdy wszystko jest częścią A , jego następca s ( ) jest nadal częścią A . Aby ta definicja była poprawna, musi istnieć przynajmniej jeden taki zbiór, co zapewnia aksjomat nieskończoności .

Zauważamy, że dla wszystkich elementów i b od N :

s ( a ) 0; s ( a ) = s ( b ) ⇒ a = b .

Struktura ( N , 0, s N ), gdzie s N jest ograniczeniem od s do N , spełnia wspomniane aksjomaty. Możemy zdefiniować N jako zbiór liczb naturalnych.

Ten zestaw jest również zbiór liczb porządkowych od von Neumanna gotowych. Taka konstrukcja N nie jest tak naprawdę kanoniczna, najważniejsze jest to, że 0 nigdy nie jest następcą i że następca jest iniektywny na otrzymanym zbiorze, ale pozwala zbudować w prosty i jednolity sposób zbiór reprezentujący każdą skończoną moc (liczba całkowita Tak skonstruowane n ma, jako zbiór, dla kardynalnego n ), aksjomat nieskończoności pozwalający dowieść, że tworzą one zbiór.

Dwie struktury ( X , a , f ) i ( Y , b , g ) są uważane za izomorficzne, jeśli istnieje bijekcja ϕ z X na Y taka, że ϕ ( a ) = b i ϕ ∘ f = g ∘ ϕ. Możemy pokazać, że jeśli te dwie struktury spełniają aksjomaty Peano, z powtarzalnością drugiego rzędu, to są one izomorficzne. Jest to konsekwencja zasady definiowania przez indukcję, która jest pokazana w wersji drugiego rzędu aksjomatów Peano. Staje się fałszywy dla arytmetyki Peano (pierwszego rzędu).

Operacje i porządek

Dodawanie nad N jest definiowane rekurencyjnie przez aksjomaty 4 i 5 arytmetyki Peano. ( N , + ) jest więc monoidem przemiennym , z neutralnym elementem $0$ . Ten monoid można zanurzyć w grupie . Najmniejsza grupa zawierająca go to względne liczby całkowite .

Ustawiając s (0) = 1, następcą b jest b + 1 ( b + s (0) = s ( b + 0) = s ( b )).

Podobnie, zakładając, że zdefiniowano dodawanie, mnożenie przez N jest określone przez aksjomaty 6 i 7 arytmetyki Peano. ( N , ∙) jest więc monoidem przemiennym, z elementem neutralnym $1$ .

Możliwe jest wreszcie zdefiniowanie porządku całkowitego na N , przez predykat binarny nie należący do języka, ale zdefiniowany na jego podstawie, który ani nie definiuje przedmiotu N, a zatem należy do metajęzyka (przynajmniej do pierwszego rzędu) który jest tutaj zbiorem, ustalając, że a ≤ b wtedy i tylko wtedy, gdy istnieje liczba c taka, że a + c = b . Wtedy N obdarzone tym porządkiem jest zbiorem dobrze uporządkowanym : każdy niepusty zbiór liczb naturalnych ma mniejszy element .

Konsystencja

Na mocy drugiego twierdzenia Gödla o niezupełności niesprzeczność tych aksjomatów między nimi nie jest konsekwencją samych tych aksjomatów: nie można udowodnić zgodności arytmetyki w arytmetyce.

Powyższa konstrukcja zapewnia fortiori modelu z Peano arytmetycznych, a więc dowód spójności tę teorię w stosunku do wydajności teoretycznej, w którym można określić te struktury, i formalnego dowód poprawności, na przykład z teorii zbiorów przez Ernst Zermelo . Istnieją inne dowody względnej spójności, w tym (w) od Gerhard Gentzen który zapewnia bardziej dokładny pomiar „siły” arytmetyka: wystarczy dodać zasadę indukcji do porządkowy przeliczalny ε₀ (en) , aby móc wykazać spójność arytmetyki.

Modele niestandardowe

Model arytmetyki Peano, który nie jest izomorficzny z N, jest uważany za „niestandardowy”.

Każdy niestandardowy model arytmetyki zawiera naturalne liczby całkowite, które następnie nazywa się „standardowymi” liczbami całkowitymi i które są elementami modelu, które można określić za pomocą terminów językowych, pozostałe elementy modelu są wtedy nazywane nie- standardowe liczby całkowite.

Dokładniej, jeśli N' jest niestandardowym modelem arytmetyki, to istnieje unikalny wstrzyknięcie f z N do N' tak, że:

f (0) = 0
∀ n , f ( s ( n )) = s ( f ( n ))

a obraz f jest tym, co nazywamy zbiorem standardowych liczb całkowitych modelu.

Nie jest możliwe odróżnienie standardowych liczb całkowitych od niestandardowych w języku arytmetyki, ponieważ gdyby predykat umożliwiał charakteryzację standardowych liczb całkowitych, wzorzec powtarzalności charakterystyczny dla tego predykatu nie byłby prawidłowy. Dlatego „porzucamy” arytmetykę Peano, gdy tylko rozumujemy te pojęcia w niestandardowym modelu. Ale możemy wykorzystać fakt, że aksjomaty Peano zachowują ważność w tym modelu. Na przykład można łatwo wykazać, że niestandardowa liczba całkowita jest z konieczności większa niż standardowa liczba całkowita. Całe zamówienie (zdefiniowane przez dodanie, patrz wyżej ) pozostaje ważne. Gdyby niestandardowa liczba całkowita była mniejsza niż standardowa liczba całkowita, wykazalibyśmy przez injektywność i indukcję następcy, że istnieje niestandardowa liczba całkowita mniejsza niż 0, a 0 byłoby następcą. Mówiąc prościej, pokazujemy, że nie może być mniejszej niestandardowej liczby całkowitej, ponieważ każda niezerowa liczba całkowita jest następcą.

Istnienie niestandardowych modeli

Twierdzenie zwartość i twierdzenie löwenheima-skolema zapewnić policzalne niestandardowych modeli arytmetyki Peano, które dokładnie spełniają ten sam zestaw pierwszej kolejności, N . Abraham Robinson opiera niestandardową analizę na modelu arytmetycznym spełniającym w szczególności ten warunek.
Istnieją również modele niestandardowe, które spełniają fałszywe zdania pierwszego rzędu w N (dodatkowo, pamiętajmy, do wszystkich twierdzeń dowodliwych w Peano, z definicji pojęcia modelu). Prawdziwe stwierdzenie w N nie jest udowodnione w arytmetyce Peano, wtedy i tylko wtedy, gdy istnieje niestandardowy model, w którym to zdanie jest fałszywe. Niekompletność twierdzenia Gödla tym samym doprowadziły do istnienia takich modeli (np istnieją modele, które spełniają oświadczenie wyrażające że arytmetyka Peano jest niezgodne!). I odwrotnie, możemy użyć takich modeli, aby pokazać, że pewnych stwierdzeń nie da się udowodnić w arytmetyce Peano (patrz na przykład twierdzenie Goodsteina ).

Presburger Aksjomatyczny

Arytmetyka Presburgera jest ograniczeniem arytmetyki Peano, gdzie eliminujemy mnożenie, ale pozostajemy następcą i dodawaniem (dlatego binarny predykat porządku jest zawsze definiowalny, a język może używać stałej 1 zamiast funkcji następnika s ). Jest znacznie mniej wyrazisty, ale kompletny i rozstrzygający .

Ma następujące aksjomaty (zmienne wolne są domyślnie skwantowane uniwersalnie):

¬ (0 = s x )
sx = s y → x = y
x + 0 = x
s ( x + y ) = x + sy
Niech P ( x ) będzie formułą logiczną pierwszego rzędu (w języku arytmetyki Presburgera, bez symbolu funkcji innego niż dodawanie) z wolną zmienną x (i ewentualnie innymi wolnymi zmiennymi). Wtedy następujący wzór jest aksjomatem:

( P (0) ∧ ∀ x ( P ( x ) → P (s x ))) → P ( y ).

Bibliografia

Prace historyczne Historical

(de) Richard Dedekind , Czy sind und was sollen die Zahlen? [" Liczby. Czym są i do czego służą? "], Brunszwik, Vieweg,1888( przeczytaj online ).
(la) Giuseppe Peano , Arithmetices principia, nova methodo exposita ["Zasady arytmetyki, nowa metoda ekspozycji"], Turyn, Bocca,1889( przeczytaj online ).

Nowoczesne prezentacje

(pl) Yiannis Moschovakis , Uwagi o teorii mnogości , Springer,2006, 2 II wyd. ( 1 st ed. 1993) ( ISBN 978-0-387-28723-2 ) (Aksjomaty Peano w kontekście teorii mnogości).

Bibliografia

Peano 1889 .
Dedekind 1888 .
Pierre Colmez , Elementy analizy i algebry (oraz teorii liczb) , Éditions École Polytechnique,2009( czytaj online ) , s. 87.
Dokładniej, jest to tak zwany „full” modelu, to znaczy, że części F uważane są rzeczywiście wszystkie części w sensie naiwny.
Wykazał to Czesław Ryll-Nardzewski w 1952, (w) Czesław Ryll-Nardzewski , „ Rola aksjomatu indukcji w elementarnej arytmetyce ” , Fundamenta Mathematicae , t. 39, n o 1,1952, s. 239-263 ( ISSN 0016-2736 , czytaj online , dostęp 29 października 2018 )Zobacz (w) Richard W. Kaye , Modele arytmetyki Peano , Oxford: Clarendon Press; Nowy Jork: Oxford University Press,1991( ISBN 978-0-19-853213-2 ) , s. 132, praca, która zawiera również dowód wyniku.
Ten wynik to głównie zasługa Dedekind, dedekind 1888 .
W przypadku aksjomatyzacji arytmetyki drugiego rzędu jako systemu formalnego, który koniecznie wspiera rozumienie , można uzyskać pojedynczy model aż do izomorfizmu tylko ograniczając się do modeli pełnych, czyli takich, w których zmienne orzekające na N mogą być interpretowane przez każdego ten podzbiór N .
Gentzen, Die Widerspruchsfreiheit der reinen Zahlentheorie , Math. Ann., 112 (1936), 493-565. Tłumaczenie Francuski Konsystencja elementarnej arytmetyki przez Jean Largeault , w intuicjonizmu i teoria demonstracyjnych stronach 285-357 Paryż, Vrin, 1992

Powiązane artykuły