Aksjomat indukcji a zasada minimum i maksimum

[krl]

Mam wrażenie, ze w tym wątku zapanował chaos.
Zaczęło się od zadania (*): udowodnić, że warunki IND, MIN i MAX są równoważne.
Z dalszych wyjaśnień można odnieść wrażenie, że autor zadania (tzn. autor podręcznika z zadaniem) traktował je w sposób naiwny. Doprowadziło to do chaosu i konfuzji. Spróbuje pomóc.

Nie jest jasne, jak należy rozumieć zadanie (*). Czy chodzi tu o
(a) pokazanie prawdziwości równoważności zdań IND, MIN, MAX jako zdań mówiących o konkretnej rzeczywistości (tj. liczbach naturalnych \(\displaystyle{ \{0,1,2,3,\dots\}}\)), czy też o
(b) udowodnienie równoważności tych zdań w ramach jakiejś teorii \(\displaystyle{ T}\).

W przypadku (a) sprawa jest prosta: zdania IND, MAX, MIN są prawdziwe, a zatem ich równoważność też jest prawdziwa (bo jeśli \(\displaystyle{ p}\) i \(\displaystyle{ q}\) są zdaniami prawdziwymi, to zdanie \(\displaystyle{ p\Leftrightarrow q}\) też jest prawdziwe). W taki to złośliwy sposób można by rozwiązać zadanie. Przypuszczalnie autorowi nie o takie rozwiązanie chodziło. No, ale wtedy powinien się wyrażać ściślej.

W przypadku (b) pojawiają się dalsze problemy, głównie: o jaką teorię może tu chodzić? Np. tak ogólnie jeśli mówimy o logicznej równoważności zdań (formuł) \(\displaystyle{ p}\) i \(\displaystyle{ q}\), to mamy tu na myśli dowodliwość zdania \(\displaystyle{ p\Leftrightarrow q}\) bez żadnych pozalogicznych aksjomatów (innymi słowy, \(\displaystyle{ p\Leftrightarrow q}\) ma być tautologią).
W takim rozumieniu zadania jest ono błędne, warunki IND, MIN i MAX nie są logicznie równoważne.

Zazwyczaj jednak w przypadku (b) w naturalny sposób przyjmuje się, że teoria \(\displaystyle{ T}\) "w tle" to teoria mnogości \(\displaystyle{ ZFC}\). Wtedy jednak pojawia się podobny problem, co w przypadku (a): wszystkie trzy zdania IND, MAX i MIN są twierdzeniami tej teorii, a zatem ich równoważności też (w sposób trywialny). I tyle.

Przypuszczalnie autorowi mogło chodzić jednak o coś innego, a mianowicie o pokazanie jawnie dowodów równoważności warunków IND, MAX i MIN przy użyciu jedynie prostych własności zbiorów (z teorii \(\displaystyle{ ZFC}\)). Tak, jak zostało to częściowo wskazane w poprzednich wpisach.

Jeśli chce się to zrobić jednak ściślej, należy określić jak najprostszą teorię \(\displaystyle{ T}\) mówiącą o liczbach naturalnych, w ramach której
można następnie udowodnić równoważność trzech warunków. Osobiście nie odwoływałbym się tu do oryginalnych aksjomatów Peana, które są anachroniczne. Są tu znów dwa sposoby:

Sposób 1. \(\displaystyle{ T}\) jest teorią II rzędu, fragmentem teorii liczb naturalnych (II rzędu) bez aksjomatu indukcji. W tym przypadku jednak, z uwagi na użycie logiki II rzędu musimy trochę mówić o zbiorach (podzbiorach zbioru liczb naturalnych).
Sposób 2. \(\displaystyle{ T}\) jest teorią I rzędu, daną przez aksjomaty arytmetyki Peana (ale bez schematu indukcji). Ten przypadek jest czystszy metodologicznie, ale warunki IND, MAX i MIN trzeba tu przepisać bez odwoływania się do pojęcia zbioru, jako schematy formuł. To właśnie w arytmetyce Peana schemat indukcji jest aksjomatem (i mówi się w tym kontekście o aksjomacie indukcji).

Osobiście wolałbym sposób 2. Zaznaczę jednak, że w teorii mnogości \(\displaystyle{ ZFC}\) można pokazać, że zbiór liczb naturalnych (dany przez powszechnie akceptowaną formalizację) istnieje i jest jedyny, zdecydowanie różny od \(\displaystyle{ \omega+\omega}\), i składa się z liczb \(\displaystyle{ 0,1,2,3,\dots}\) (no, bo w \(\displaystyle{ ZFC}\) zachodzi twierdzenie o indukcji) .

[Dasio11]

Zaznaczę jednak, że w teorii mnogości \(\displaystyle{ ZFC}\) można pokazać, że zbiór liczb naturalnych (dany przez powszechnie akceptowaną formalizację) istnieje i jest jedyny, zdecydowanie różny od \(\displaystyle{ \omega+\omega}\), i składa się tylko z liczb \(\displaystyle{ 0,1,2,3,\dots}\) (no, bo w \(\displaystyle{ ZFC}\) zachodzi twierdzenie o indukcji) .

W teorii mnogości można pokazać, że zbiór liczb naturalnych jest różny od \(\displaystyle{ \omega + \omega}\) rozumianej w sensie ZFC. Ale raczej nie można pokazać, że składa się z liczb \(\displaystyle{ 0, 1, 2, 3, \ldots}\), a dokładniej: ze wszystkich iterowanych następników zera i tylko z nich. Jeśli bowiem istnieje jakikolwiek model ZFC, to istnieje też taki, w którym zbiór liczb naturalnych nie jest nawet dobrze uporządkowany, co widać oczywiście tylko z zewnątrz.

[krl]

Zaznaczę jednak, że w teorii mnogości \(\displaystyle{ ZFC}\) można pokazać, że zbiór liczb naturalnych (dany przez powszechnie akceptowaną formalizację) istnieje i jest jedyny, zdecydowanie różny od \(\displaystyle{ \omega+\omega}\), i składa się tylko z liczb \(\displaystyle{ 0,1,2,3,\dots}\) (no, bo w \(\displaystyle{ ZFC}\) zachodzi twierdzenie o indukcji) .

W teorii mnogości można pokazać, że zbiór liczb naturalnych jest różny od \(\displaystyle{ \omega + \omega}\) rozumianej w sensie ZFC. Ale raczej nie można pokazać, że składa się z liczb \(\displaystyle{ 0, 1, 2, 3, \ldots}\), a dokładniej: ze wszystkich iterowanych następników zera i tylko z nich. Jeśli bowiem istnieje jakikolwiek model ZFC, to istnieje też taki, w którym zbiór liczb naturalnych nie jest nawet dobrze uporządkowany, co widać oczywiście tylko z zewnątrz.

Teoria mnogości mówi o zbiorach, w tym o zbiorach skończonych i zbiorze liczb naturalnych. Tym prawdziwym. I o tym zbiorze liczb naturalnych \(\displaystyle{ \mathbb{N}}\) teoria mnogogości \(\displaystyle{ ZFC}\) dowodzi, że każdy jego podzbiór \(\displaystyle{ X}\), do którego należą kolejno liczby \(\displaystyle{ 0,1,2,3,\dots}\), jest równy \(\displaystyle{ \mathbb{N}}\). To miałem na myśli (i jest to zresztą twierdzenie o indukcji), w języku teorii mnogości nie da się inaczej (lepiej) wyrazić faktu, że \(\displaystyle{ \mathbb{N}=\{0,1,2,3,\dots\}}\). W dowodach często z tego ostatniego faktu korzystamy. Ściśle rzecz biorąc mamy wtedy na myśli twierdzenie o indukcji.
Oczywiście, zgadzam się z Twoim ostatnim zdaniem.
Rozważania metamatematyczne mogą prowadzić do zwątpienia w tożsamość podstawowych obiektów matematycznych. Dlatego uznałem za stosowne podkreślić, że zbiór liczb naturalnych jest tylko jeden (w teorii mnogości, ale w praktyce też i poza nią, z dokładnością do izomorfizmu). Rozważanie, czy \(\displaystyle{ \omega +\omega}\) może być zbiorem liczb naturalnych nie ma sensu.

[Dasio11]

Rozważanie, czy \(\displaystyle{ \omega +\omega}\) może być zbiorem liczb naturalnych nie ma sensu.

Owszem, w tym wątku takie rozważanie ma sens - uzasadnia ono bowiem potrzebę przytoczenia z książki większej ilości założeń o liczbach naturalnych, tak by nie spełniała ich opisana wcześniej struktura \(\displaystyle{ \omega + \omega}\), bo dopóki takich założeń nie będzie, dopóty zadanie pozostanie bezsensowne.