Aksjomat indukcji a zasada minimum i maksimum

[Bran]

Udowodnij, że aksjomat indukcji, zasada minimum i zasada maksimum są równoważne.

Aksjomat indukcji:
Jeśli \(\displaystyle{ S}\) jest dowolnym zbiorem takim, że:
(1) \(\displaystyle{ 1 \in S}\),
(2) dla dowolnego \(\displaystyle{ n}\), jeśli \(\displaystyle{ n \in S}\), to \(\displaystyle{ n+1 \in S}\),
to \(\displaystyle{ \NN \subset S}\).

Zasada minimum
W każdym niepustym podzbiorze zbioru liczb naturalnych istnieje element najmniejszy.

Zasada maksimum
W każdym niepustym ograniczonym podzbiorze zbioru liczb naturalnych istnieje element największy.

Treść aksjomatu i twierdzeń pochodzi z książki, z której mam zadanie.

Bardzo proszę o podpowiedź/nakierowanie.

[Janusz Tracz]

\(\displaystyle{ \text{ZIM} \Rightarrow \text{ZM} }\)
Niech \(\displaystyle{ S}\) będzie zbiorem takim, że spełnione są warunki \(\displaystyle{ (1)}\) i \(\displaystyle{ (2)}\) ale (nie wprost) nie jest to nadzbiór \(\displaystyle{ \NN}\). Rozważmy zatem niepusty zbiór \(\displaystyle{ \NN \setminus S}\) który ma element najmniejszy \(\displaystyle{ n_0\in \NN \setminus S}\) czyli \(\displaystyle{ n_0-1\in S}\) ale z definicji \(\displaystyle{ S}\) wynika, że jednak \(\displaystyle{ n_0\in S}\). Sprzeczność.

PS polecam rysunek.

[Bran]

Skąd my wiemy, że zbiór \(\displaystyle{ \NN \setminus S}\) miałby element najmniejszy?

Ponadto nie widzę idei dowodu Zakładasz nie wprost zaprzeczenie wniosku aksjomatu indukcji i dochodzisz do sprzeczności (co by oznaczało, że własnie dowiodłeś aksjomatu )
Jestem zupełnie pogubiony, mógłbyś wyjaśnić troszkę szerzej?

[Gosda]

Kod: Zaznacz cały

https://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skrypt/node14.html

Twierdzenie 13.2 (Zasada minimum) Każdy niepusty podzbiór zbioru liczb naturalnych zawiera element najmniejszy.

Dowód. Niech \(X\) będzie niepustym podzbiorem \(\bf N\) i niech

\(\displaystyle{ Z=\{n\in{\mathbb{N}}: \{0,\dots,n\}\cap X=\emptyset\}.}\)

Przypuśćmy nie wprost, że \(X\) nie ma elementu najmniejszego. W szczególności \(0\not\in X\) (bo \(0\) jest najmniejszą liczbą naturalną), więc \(0\in Z\). Przypuśćmy teraz, że \(n\in Z\). Znaczy to, że \(\{0,\dots,n\}\) jest rozłączny z \(X\). Jeśli teraz \(n+1\in X\), to \(n+1\) byłaby najmniejszą liczbą w \(X\), sprzeczność. Dostajemy więc \(n+1\not\in X\), czyli również \(\{0,\dots,n+1\}\cap X=\emptyset\) i \(n+1\in Z\).

W ten sposób widzimy, że zbiór \(Z\) spełnia założenia twierdzenia 13.1. Dlatego wnioskujemy, że \(Z=\mathbb{N}\). Znaczy to jednak, że \(X=\emptyset\), sprzeczność. \(\Box\)

[Janusz Tracz]

Zakładasz nie wprost zaprzeczenie wniosku aksjomatu indukcji i dochodzisz do sprzeczności

Przepraszam kierunek implikacji powinien być odwrotnie Chciałem zacząć właśnie od \(\displaystyle{ \text{ZIM} \Rightarrow \text{ZM}}\) ale już późno było i się rozmyśliłem bo to dłuższy dowód od tego (a kierunku implikacji nie zmieniłem). Dowód z mojego ostatniego postu pokazuje, że \(\displaystyle{ \text{ZM} \Rightarrow \text{ZIM}}\) przy czym jest nie wprost czyli zakładam \(\displaystyle{ \text{ZM} \wedge \neg \text{ZIM}}\) pokazując sprzeczność. Założenie \(\displaystyle{ \text{ZM} }\) pozwala mi wybierać z podzbiorów element najmniejszy \(\displaystyle{ n_0}\) a \(\displaystyle{ \neg \text{ZIM}}\) polega na założeniu \(\displaystyle{ (1)}\) i \(\displaystyle{ (2)}\) oraz zanegowaniu tezy czyli \(\displaystyle{ \NN \subset S}\). Okazuje się bowiem, że jeśli \(\displaystyle{ S}\) jest podzbiorem właściwym \(\displaystyle{ \NN}\) to \(\displaystyle{ \NN \setminus S}\) jest niepusty z \(\displaystyle{ \text{ZM}}\) można powiedzieć, że \(\displaystyle{ n_0}\) jest najmniejszy w \(\displaystyle{ \NN \setminus S}\) czyli \(\displaystyle{ \red{n_0-1}\in S}\) ale z \(\displaystyle{ (2)}\) wynika, że \(\displaystyle{ \red{n_0-1}+1\in S}\) czyli \(\displaystyle{ n_0\in S}\) ale to jest sprzeczność bo nie można zajść to jednocześnie z \(\displaystyle{ n_0\in \NN \setminus S}\). Formalnie trzeba jeszcze zauważyć, że \(\displaystyle{ 1\in S}\) dlatego \(\displaystyle{ n_0>1}\) tak więc \(\displaystyle{ n_0-1\in\NN}\). To jeśli chodzi o konstrukcję i idee dowodu.

co by oznaczało, że własnie dowiodłeś aksjomatu

Aksjomat indukcji jest tu aksjomatem tylko z nazwy. My traktujemy \(\displaystyle{ \text{ZIM}}\) jako twierdzenie.

W wielu źródłach można zamiast „aksjomatu indukcji” spotkać nazwę „twierdzenie o indukcji”; odpowiedź na pytanie tytułowe zależy od kontekstu, w którym jest ono stawiane.

W zastosowaniach matematyki, matematyce elementarnej, czy matematyce dyskretnej dominuje tendencja do mówienia o „twierdzeniu o indukcji matematycznej”, również dlatego, by uniknąć przesadnej formalizacji. Wprowadzając indukcję matematyczną podaje się często dowód twierdzenia o indukcji korzystając z dość intuicyjnej zasady dobrego uporządkowania liczb naturalnych, tzn. założenia, że każdy niepusty zbiór liczb naturalnych zawiera element najmniejszy.

Natomiast w logice, szczególnie gdy liczby naturalne wprowadzane są za pomocą aksjomatów Peana, indukcja traktowana jest jako aksjomat. Z powodu kwantyfikowania po zbiorach w gruncie rzeczy jest to aksjomat logiki drugiego rzędu; w przypadku, gdy rozwijana teoria jest formalizowana w logice pierwszego rzędu, słowo „aksjomat” w wyrażeniu „aksjomat indukcji” należy rozumieć w istocie jako schemat aksjomatu: nieskończoną listę aksjomatów, osobnych dla każdej formuły.

Gosda natomiast pokazał to co ja chciałem na początku czyli \(\displaystyle{ \text{ZIM} \Rightarrow \text{ZM}}\) co robi się również nie wprost zakładając \(\displaystyle{ \neg \text{ZM} \wedge \text{ZIM} }\) i wnioskując sprzeczność. Tą konstrukcję widać to szczególnie w zdaniu: Przypuśćmy nie wprost, że \(\displaystyle{ X}\) nie ma elementu najmniejszego (co jest zaprzeczeniem zasady minimum). Tym samym pokazana została implikacja w dwie strony pomiędzy \(\displaystyle{ \text{ZM}}\) a \(\displaystyle{ \text{ZIM}}\) czyli są to równoważne twierdzenia.

PS polecam zerknąć jeszcze tu

[Dasio11]

Treść aksjomatu i twierdzeń pochodzi z książki, z której mam zadanie.

Brakuje jeszcze dość istotnych informacji, mianowicie: jak są zdefiniowane operacja następnika (\(\displaystyle{ n \mapsto n+1}\)) i porządek? Lub - jeśli wprowadzone są aksjomatycznie - jakie to aksjomaty?

[Bran]

Treść aksjomatu i twierdzeń pochodzi z książki, z której mam zadanie.

Brakuje jeszcze dość istotnych informacji, mianowicie: jak są zdefiniowane operacja następnika (\(\displaystyle{ n \mapsto n+1}\)) i porządek? Lub - jeśli wprowadzone są aksjomatycznie - jakie to aksjomaty?

Niestety autor nie podał takich informacji, ale domyślam się, że używa nazwy aksjomat indukcji, to używa aksjomatyki Peano, gdzie następnik jest pojęciem pierwotnym, a fakt \(\displaystyle{ n^* = n+1}\) jest twierdzeniem wynikającym z indukcji i przyjęcia systemu liczbowego. Z tym, że oczywiście to są tylko moje domysły.

[Dasio11]

To może z innej strony: czy jakikolwiek aksjomat powoduje, że liczby naturalne nie mogą wyglądać jak \(\displaystyle{ \omega + \omega}\) ? Bo jeśli nie, to z samej Zasady minimum nie wynika Zasada indukcji matematycznej.

W razie gdybyś nie znał liczb porządkowych: \(\displaystyle{ \omega + \omega}\) to zbiór \(\displaystyle{ \{ 0, 1, 2, 3, \ldots \} \cup \{ \omega, \omega+1, \omega+2, \omega+3, \ldots \}}\) z porządkiem

\(\displaystyle{ 0 < 1 < 2 < 3 < \ldots < \omega < \omega+1 < \omega+2 < \omega+3 < \ldots}\)

i operacją następnika zdefiniowaną jako "przejście o jeden w prawo" w tym porządku.

[Bran]

Co masz na myśli mówiąc, że liczba naturalna (nie)może wyglądać jak \(\displaystyle{ \omega + \omega}\). Co to jest \(\displaystyle{ \omega}\)? Domyślam się, ze jakaś liczba naturalna. W takim razie wydaje mi się, że jeżeli definiujemy dodawanie tak jak zwykle się definiuje w zbiorze liczb naturalnych, to \(\displaystyle{ \omega + \omega}\) jest liczbą parzystą. Więc nie każda liczba naturalna może tak wyglądać, ale podejrzewam, że nie o to chodziło.

[Dasio11]

Co to jest \(\displaystyle{ \omega}\)?

To nieistotne. W ostatnim poście opisałem, czym jest zbiór \(\displaystyle{ \omega + \omega}\), i do zrozumienia opisu nie potrzeba wiedzieć, czym jest \(\displaystyle{ \omega}\) - możesz potraktować to jako nic nieznaczący symbol. I pytam: dlaczego zbiór liczb naturalnych, o którym jest mowa w Twojej książce, nie może wyglądać tak jak ten opisany zbiór (włącznie z porządkiem i operacją następnika)?

Bo oczywiście w sytuacji aksjomatycznej zbiór liczb naturalnych to już nie jest "zero, jeden, dwa i wszystkie kolejne liczby", tylko dowolna struktura spełniająca jawnie wypisane aksjomaty. Jeśli więc żaden podany w książce aksjomat nie jest fałszywy w strukturze \(\displaystyle{ \omega + \omega}\), to nie ma powodu, żeby tej struktury nie nazwać zbiorem liczb naturalnych.

[Jakub Gurak]

W razie gdybyś nie znał liczb porządkowych: \(\displaystyle{ \omega + \omega}\) to zbiór \(\displaystyle{ \{ 0, 1, 2, 3, \ldots \} \cup \{ \omega, \omega+1, \omega+2, \omega+3, \ldots \}}\) z porządkiem

\(\displaystyle{ 0 < 1 < 2 < 3 < \ldots < \omega < \omega+1 < \omega+2 < \omega+3 < \ldots}\)

i operacją następnika zdefiniowaną jako "przejście o jeden w prawo" w tym porządku.

Brakuje, myślę, że kluczowej informacji, czy \(\displaystyle{ \omega\in\left\{ 0,1,2,\ldots \right\}.}\) Bo jeśli nie należy, to zdziwiłbym się gdyby było \(\displaystyle{ \NN:=\omega+\omega.}\)

[Jan Kraszewski]

Brakuje, myślę, że kluczowej informacji, czy \(\displaystyle{ \omega\in\left\{ 0,1,2,\ldots \right\}.}\) Bo jeśli nie należy, to zdziwiłbym się gdyby było \(\displaystyle{ \NN:=\omega+\omega.}\)

Chyba nie zrozumiałeś tego, co napisał Dasio11. Oczywiście nie należy, więc możesz się zdziwić...

JK

[Jakub Gurak]

Ale czy w takiej sytuacji może być przyjęte za zbiór liczb naturalnych \(\displaystyle{ \omega+\omega}\) - chyba zasada indukcji matematycznej to wyklucza.

[Janusz Tracz]

To może z innej strony: czy jakikolwiek aksjomat powoduje, że liczby naturalne nie mogą wyglądać jak \(\displaystyle{ \omega + \omega}\) ?

Ja chyba zakumkałem. W sumie \(\displaystyle{ \omega}\) i to czym jest faktycznie, nie ma tu żadnego znaczenia. Pytanie o tu, czy jest jakiś aksjomat który zabraniał by definiowanemu zbiorowi liczb naturalnych wyglądać tak:

\(\displaystyle{ \NN_{\text{w niestandardowym kontekście}}= \left\{ 0,1,2,3,...,\red{\otimes} , \green{\odot} , \green{\ominus} , \green{\oslash} , \green{\oplus}, ... \right\} }\)

z porządkiem danym przez

\(\displaystyle{ 0<1<2<3<...<\red{\otimes}<\green{ \odot} <\green{\ominus} < \green{\oslash }< \green{\oplus} <... }\)

jeśli w aksjomatyce podczas tworzenia \(\displaystyle{ \NN_{\text{ jeszcze bez kontekstu}}}\) masz powiedziane, że nie wolno takich konstrukcji roić to wtedy \(\displaystyle{ \text{ZM} \Rightarrow \text{ZIM}}\) jeśli jednak wolno robić takie rzeczy wtedy implikacja nie jest prawdziwa. Żeby uchronić się przed takimi sytuacjami można by zażądać aby każdy element z wyjątkiem \(\displaystyle{ 0}\) miał poprzednik? Ale, żeby nie wymyślać to posłużę się aksjomatyką \(\displaystyle{ \NN}\)

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Aksjomaty_i_konstrukcje_liczb#Aksjomatyka_Peana

. Jest tam napisane:

1. \(\displaystyle{ J}\) jest liczbą naturalną.
2. Dla każdej liczby naturalnej istnieje dokładnie jedna liczba naturalna, zwana jej następnikiem.
3. \(\displaystyle{ J}\) nie jest następnikiem żadnej liczby naturalnej.
4. Jeśli dwie liczby naturalne mają równe następniki, to są sobie równe.
5. Aksjomat indukcji:
Niech dany będzie zbiór, którego elementami są liczby naturalne o następujących własnościach:
a. \(\displaystyle{ J}\) jest elementem tego zbioru
b. Wraz z każdą liczbą naturalną należącą do tego zbioru należy do niego także jej następnik.
Wówczas zbiór ten zawiera wszystkie liczby naturalne.

Wydaje mi się, że aksjomat \(\displaystyle{ 3}\) nie dopuszcza do sytuacji w której mogą powstać takie dziwne konstrukcji. Jeśli patrzył bym na \(\displaystyle{ \NN_{\text{w niestandardowym kontekście}}}\) przez pryzmat \(\displaystyle{ 3}\) doszedł bym do konieczności założenia, że \(\displaystyle{ 0=\red{\otimes}}\). Ogólnie aksjomat \(\displaystyle{ 3}\) chroni przed takim rozszczepieniem się definiowanego zbioru bo nic nie stało by na przeszkodzie by iść dalej i tworzyć

\(\displaystyle{ \NN=\left\{ 0,1,2,3,...,\otimes , \odot , \ominus , \oslash , \oplus , ... , \Diamond , \triangle ,\nabla ,... \right\} }\)

z porządkiem analogicznie jak wyżej. Aksjomat \(\displaystyle{ 3}\) ucina to do \(\displaystyle{ 0=\otimes = \Diamond=...}\) tym samym czyniąc:

\(\displaystyle{ \NN=\left\{ 0,1,2,3,...,\otimes , \odot , \ominus , \oslash , \oplus , ... , \Diamond , \triangle ,\nabla ,... \right\} = \left\{ 0,1,2,3,...\right\} }\)

[Dasio11]

Ale czy w takiej sytuacji może być przyjęte za zbiór liczb naturalnych \(\displaystyle{ \omega+\omega}\) - chyba zasada indukcji matematycznej to wyklucza.

Jeśli uważnie przeczytasz treść zadania, to zauważysz, że Zasada indukcji jest jednym z trzech warunków, których wzajemną równoważność trzeba udowodnić, nie może więc jednocześnie być globalnie obowiązującym aksjomatem.

Żeby uchronić się przed takimi sytuacjami można by zażądać aby każdy element z wyjątkiem \(\displaystyle{ 0}\) miał poprzednik?

Taki aksjomat rzeczywiście by wystarczył...

3. \(\displaystyle{ J}\) nie jest następnikiem żadnej liczby naturalnej.

Wydaje mi się, że aksjomat \(\displaystyle{ 3}\) nie dopuszcza do sytuacji w której mogą powstać takie dziwne konstrukcji.

...ale ten już nie, bo przecież \(\displaystyle{ 0}\) nie jest następnikiem w \(\displaystyle{ \omega + \omega}\).

W rzeczywistości \(\displaystyle{ \omega + \omega}\) spełnia cztery pierwsze z zacytowanych aksjomatów i dopiero piąty, czyli Zasada indukcji, w pewnym sensie wyklucza, by ta struktura mogła być zbiorem liczb naturalnych (

Kod: Zaznacz cały

https://mathoverflow.net/questions/40821/existence-of-an-omega-nonstandard-model-of-zfc-from-compactness

).