Dowód indukcyjny dla liczb naturalnych.

[arek0092]

Dzień dobry,

zmagam się ze zrozumieniem koncepcji dowodu za pomocą indukcji, która pomimo swojej prostej definicji sprawia mi całkiem sporo kłopotu. Co utworzenie zbioru jest całkiem proste i schematyczne, wykazanie że zbiór pusty należy do niego też (mam nadzieję) mi wychodzi to ostatni krok jest małą zagadką. Może przedstawienie tego na przykładzie pozwoli to trochę zobrazować.

A więc mam taki przykład do udowodnienia.

\(\displaystyle{ n \subset m' \Rightarrow n \subset m \vee m \in n}\)

Więc zaczynam od zdefiniowania zbioru który spełnia to założenie:
\(\displaystyle{ M = \left\{ n \in \NN : \forall m \in \NN : n \subset m' \Rightarrow n \subset m \vee m \in n \right\} \subset
\NN }\)
gdzie \(\displaystyle{ \NN}\) to zbiór liczb naturalnych

Teraz 1 krok, czy że \(\displaystyle{ 0 \in M}\):
I to jest prawda ponieważ \(\displaystyle{ 0 \in \NN}\) więc możemy brać je pod uwagę oraz lewa strona implikacji dla 0 jest prawdziwa dla każdego m ponieważ każdy następnik zawiera w sobie zbiór pusty.
Ma sens to rozumowanie?

I tutaj w drugim kroku mam najwięcej wątpliwości, nie wiem do końca z czego skorzystać. Skoro muszę udowodnić że dla każdego n' jest to spełnione to czy mogę po prostu wyjść z lewej strony implikacji? W sensie \(\displaystyle{ n' \subset m'}\) ?
Ale znowu korzystając z def. następnika dojdę do \(\displaystyle{ n' \subset m \cup \left\{ m\right\} }\) i nie bardzo mógłbym to rozdzielić. Nie wiem jak mógłym wyjść na \(\displaystyle{ n' \subset m \vee m \in n' }\), bo chyba do tego mam dążyć, tak?

Mógłbym prosić o pokierowanie w jaki dokładnie sposób się za takie przykłady zabierać? Rozpisany ciąg myślowy kogoś doświadczonego mógłby zdecydowanie pomóc.

[Jan Kraszewski]

A co to jest \(\displaystyle{ m'}\) ?

Poza tym w Twoim "przykładzie do udowodnienia" brakuje kwantyfikatorów, wypadałoby też wspomnieć, jak definiujesz liczby naturalne.

JK

[arek0092]

Naturalnie, już tłumaczę.

\(\displaystyle{ m' }\) jest to następnik liczby \(\displaystyle{ m}\), a samo \(\displaystyle{ m }\) jako dowolna liczba spełniająca tamto założenie. \(\displaystyle{ ' }\) zostało przyjęte jako oznaczenie następnika.

A w samym przykładzie zapomniałem o dopisaniu że chodzi o dowolne \(\displaystyle{ m,n \in \mathbb{N} }\)

Zbiór liczb naturalnych zdefiniowany jest jako najmniejszy zbiór induktywny, gdzie każda liczba jest albo 0 albo następnikiem.
Np. :
0 = \(\displaystyle{ \emptyset}\)
1 = \(\displaystyle{ \left\{ \emptyset\right\} }\)
2 = \(\displaystyle{ \left\{\emptyset , \left\{ \emptyset\right\} \right\} }\)
...

Mam nadzieję że teraz mój problem jest bardziej zrozumiały, jeśli nie to proszę o następne uwagi.
Dziękuję za odpowiedź.

[matmatmm]

Twoją tezę można znacznie wzmocnić. Mianowicie założenie \(\displaystyle{ n\subset m'}\) jest niepotrzebne, bo dla dowolnych liczb naturalnych \(\displaystyle{ n,m}\) zachodzi

\(\displaystyle{ n\subset m \vee m\in n}\)

Własność ta to nic innego jak spójność relacji porządku, bowiem według standardowych definicji

\(\displaystyle{ n\subset m \iff n\le m}\)
\(\displaystyle{ m\in n \iff m<n}\)

Dodano po 7 minutach 38 sekundach:

Teraz 1 krok, czy że \(\displaystyle{ 0 \in M}\):
I to jest prawda ponieważ \(\displaystyle{ 0 \in \NN}\) więc możemy brać je pod uwagę oraz lewa strona implikacji dla 0 jest prawdziwa dla każdego m ponieważ każdy następnik zawiera w sobie zbiór pusty.
Ma sens to rozumowanie?

Dodam, że ta próba dowodu bazy indukcji (dla tezy w Twojej wersji) jest niepoprawna. Z prawdziwości poprzednika nie wynika prawdziwość implikacji.

[Jakub Gurak]

Więc zaczynam od zdefiniowania zbioru który spełnia to założenie:
\(\displaystyle{ M = \left\{ n \in \NN : \forall m \in \NN : n \subset m' \Rightarrow n \subset m \vee m \in n \right\} \subset
\NN }\)
gdzie \(\displaystyle{ \NN}\) to zbiór liczb naturalnych

Teraz 1 krok, czy że \(\displaystyle{ 0 \in M}\):
I to jest prawda ponieważ \(\displaystyle{ 0 \in \NN}\) więc możemy brać je pod uwagę oraz lewa strona implikacji dla 0 jest prawdziwa dla każdego m ponieważ każdy następnik zawiera w sobie zbiór pusty.
Ma sens to rozumowanie?

Za mało. Dla każdego \(\displaystyle{ m}\) naturalnego \(\displaystyle{ \emptyset\subset m'}\) i \(\displaystyle{ \emptyset \subset m}\), a stąd łatwo wynika, że dla każdego \(\displaystyle{ m}\) naturalnego zachodzi cała implikacje ( sprawdź), a więc \(\displaystyle{ 0=\emptyset\in M.}\)

Warto widzieć jaką treść niosą te formalne znaczki. Mamy tak naprawdę pokazać, że jeśli \(\displaystyle{ n \subset m'}\), czyli \(\displaystyle{ n \le m'}\), to \(\displaystyle{ n \le m}\) lub \(\displaystyle{ m<n}\) (bo \(\displaystyle{ m<n}\), oznacza, że \(\displaystyle{ m\in n}\)), co jest intuicyjnie prawdą. Nie zastępuje to formalnego dowodu, ale warto o tym pamiętać.

Dowód kroku indukcyjnego:
Weźmy \(\displaystyle{ n\in M}\), i pokażmy, że \(\displaystyle{ n'\in M.}\)
W tym celu ustalamy dowolną liczbę naturalną m, taką, że \(\displaystyle{ n' \subset m'}\), i pokażmy że \(\displaystyle{ n' \subset m}\) lub \(\displaystyle{ m\in n'.}\) Jeśli \(\displaystyle{ n'=m',}\) to również \(\displaystyle{ n= m}\), i wtedy \(\displaystyle{ m \in n'=m'=m\cup\left\{ m\right\}}\), co należało pokazać.
Jeśli \(\displaystyle{ n' \neq m'}\), to \(\displaystyle{ n' \subsetneq m'}\), a zatem (\(\displaystyle{ n'<m'}\)), \(\displaystyle{ n' \in m'=m \cup\left\{ m\right\}.}\) Jeśli \(\displaystyle{ n' \in m}\), to \(\displaystyle{ n' \subset m}\), co należało pokazać.
Jeśli \(\displaystyle{ n'\notin m}\), to pozostaje możliwość \(\displaystyle{ n' \in \left\{ m\right\} }\), a stąd oczywiście \(\displaystyle{ n'=m,}\) więc w szczególności \(\displaystyle{ n' \subset m.\square}\)

Mam nadzieję, że znasz fakt, że dla dowolnych dwóch liczb naturalnych \(\displaystyle{ n,m}\) mamy: \(\displaystyle{ n\in m \Leftrightarrow n\subsetneq m.}\)

[arek0092]

Twoją tezę można znacznie wzmocnić. Mianowicie założenie \(\displaystyle{ n\subset m'}\) jest niepotrzebne, bo dla dowolnych liczb naturalnych \(\displaystyle{ n,m}\) zachodzi

\(\displaystyle{ n\subset m \vee m\in n}\)

Własność ta to nic innego jak spójność relacji porządku, bowiem według standardowych definicji

\(\displaystyle{ n\subset m \iff n\le m}\)
\(\displaystyle{ m\in n \iff m<n}\)

Tak, też udało mi się to zauważyć jednak bardzo mi zależy na zrozumieniu całego sensu dowodu indukcyjnego. Może w tym przykładzie nie jest konieczny, nie mniej jednak myślę że to dobry przykład właśnie do zobrazowania całej procedury.

Dodam, że ta próba dowodu bazy indukcji (dla tezy w Twojej wersji) jest niepoprawna. Z prawdziwości poprzednika nie wynika prawdziwość implikacji.

Faktycznie, mój błąd, pospieszyłem się za bardzo z wnioskami.
Czyli raczej powinno być:

\(\displaystyle{ 0 \in M }\) ponieważ \(\displaystyle{ 0 \in \mathbb{N}}\) więc możemy brać je pod uwagę oraz lewa strona implikacji dla 0 jest prawdziwa dla każdego m ponieważ, lewa jest prawdziwa (każdy zbiór zawiera w sobie \(\displaystyle{ \emptyset}\)) i prawa również (\(\displaystyle{ \emptyset}\) zawiera się w każdym zbiorze).
Mam jeszcze małą wątpliwość, czy \(\displaystyle{ \emptyset \subset \emptyset}\), ale wydaje mi się że to prawda z racji że każdy zbiór sam w sobie się zawiera co wynika ze zwrotności.

Czy teraz ten krok jest poprawny?

A co do drugiego kroku to już myślę że jestem bliżej jak dalej po całym dniu analizowania tematu jednak ta implikacja nadal sprawia mi kłopot.

Dziękuję za uwagi.

Dodano po 27 minutach 47 sekundach:

Za mało. Dla każdego \(\displaystyle{ m}\) naturalnego \(\displaystyle{ \emptyset\subset m'}\) i \(\displaystyle{ \emptyset \subset m}\), a stąd łatwo wynika, że dla każdego \(\displaystyle{ m}\) naturalnego zachodzi cała implikacje ( sprawdź), a więc \(\displaystyle{ 0=\emptyset\in M.}\)

Tak, wydaje mi się że w poście wyżej trochę dłuższym zapisem osiągnąłem ten sam dowód.

Dowód kroku indukcyjnego:
Weźmy \(\displaystyle{ n\in M}\), i pokażmy, że \(\displaystyle{ n'\in M.}\)
W tym celu ustalamy dowolną liczbę naturalną m, taką, że \(\displaystyle{ n' \subset m'}\), i pokażmy że \(\displaystyle{ n' \subset m}\) lub \(\displaystyle{ m\in n'.}\) Jeśli \(\displaystyle{ n'=m',}\) to również \(\displaystyle{ n= m}\), i wtedy \(\displaystyle{ m \in n'=m'=m\cup\left\{ m\right\}}\), co należało pokazać.
Jeśli \(\displaystyle{ n' \neq m'}\), to \(\displaystyle{ n' \subsetneq m'}\), a zatem (\(\displaystyle{ n'<m'}\)), \(\displaystyle{ n' \in m'=m \cup\left\{ m\right\}.}\) Jeśli \(\displaystyle{ n' \in m}\), to \(\displaystyle{ n' \subset m}\), co należało pokazać.
Jeśli \(\displaystyle{ n'\notin m}\), to pozostaje możliwość \(\displaystyle{ n' \in \left\{ m\right\} }\), a stąd oczywiście \(\displaystyle{ n'=m,}\) więc w szczególności \(\displaystyle{ n' \subset m.\square}\)

Mam nadzieję, że znasz fakt, że dla dowolnych dwóch liczb naturalnych \(\displaystyle{ n,m}\) mamy: \(\displaystyle{ n\in m \Leftrightarrow n\subsetneq m.}\)

Bardzo dziękuję za ten dowód. Przyznam że na zajęciach posługujemy się raczej "znaczkowym" zapisem, ale myślę że jest tak czytelny że uda mi się bez trudu go odtworzyć. Oczywiście przede wszystkim zależało mi na tak przekazanym toku myślowym, będę mógł się na nim wzorować przy kolejnych przykładach.
Jeszcze raz bardzo dziękuję.