Udowodnić prawdziwość twierdzenia

[zdl]

Mam twierdzenie, które według mnie potrafię udowdnić, ale intuicyjnie coś mi nie gra i chciałem zapytać o poprawność.

Zadanie:
Niech `\phi(x,y)` będzie funkcją zdaniową o zakresie zmiennych `x,y \in \NN`. Wykazać, że jeśli `\phi(0,0)` oraz dla dowolnych `m,n \in \NN` z prawdziwości zdania `\phi(m,m)` wynika prawdziwość zdań `\phi(m+1, n)` i `\phi(m, n+1)`, to zdanie `\phi(m,n)` jest prawdziwe dla wszystkich `m,n \in \NN`.

Rozwiązanie:
Zakładam nie wprost, że istnieją `m,n \in \NN` dla których `\phi(x,y)` jest fałszywe. `A := \{m \in \NN: (\exists n \in \N) \neg \phi(m,n)\}` i analogiczny zbiór `B`. Skoro mam `\neg phi(x,y)` to wiem, że zbiory `A,B` są niepuste i mają elementy najmniejsze, kolejno `a,b`. Od razu możemy przyjąć z założenia `\phi(0,0)`, że `a,b \ne 0`. Skoro `a>0` to mogę ustalić `a-1 \in NN`. A więc `\phi(a-1,b)` jest prawdziwe, bo inaczej `a-1` byłoby elementem `A` i to elementem najmniejszym. Następnie z założenia otrzymuję `\phi(a,b)` co prowadzi do sprzeczności z `\neg \phi(a,b)`.

Intuicyjnie czułem jeszcze przed chwilą, że gdzieś mam tutaj błąd, bo przecież skorzystałem jedynie z prawdziwości `\phi(m+1, n)`, a drugi warunek zupełnie pominąłem. Po chwili doszedłem do wniosku, że przecież założenie `a,b \ne 0` jest błędne. Bo warunek `phi(0,0)` nie zabrania `a=1, b = 0` i odwrotnie. Dlatego muszę rozważyć dwa warianty na wypadek, gdyby `a` lub `b` (ale nie oba) faktycznie było równe `0` i wtedy wszystko gra. Prawda?

[Jan Kraszewski]

Po chwili doszedłem do wniosku, że przecież założenie `a,b \ne 0` jest błędne.

To akurat nie było założenie, ale Twój wniosek z założenia, ale tak, był to wniosek błędny.

JK

[Thingoln]

Ukryta treść:    

Czy można to udowodnić indukcyjnie?

[Jan Kraszewski]

Czy można to udowodnić indukcyjnie?

Oczywiście. Mamy pokazać, że

\(\displaystyle{ (\forall m\in\NN)(\forall n\in\NN)\phi(m,n).}\)

Oznaczmy \(\displaystyle{ \psi(m)=(\forall n\in\NN)\phi(m,n)}\) i pokazujemy indukcją po \(\displaystyle{ m}\), że \(\displaystyle{ (\forall m\in\NN)\psi(m).}\) W tym celu wykonujemy krok bazowy i krok indukcyjny i w każdym z nich przeprowadzamy niezależny dowód indukcyjny ("zagnieżdżony" w tym podstawowym) po \(\displaystyle{ n}\).

JK

[a4karo]

Chyba najłatwiej indukcją po `n+m`

[Jan Kraszewski]

Ale wtedy musisz sprecyzować, na czym polega ta indukcja, co samo w sobie może być trudniejsze niż wspomniany przeze mnie dowód.

JK

[Dasio11]

co prowadzi do sprzeczności z `\neg \phi(a,b)`.

Tu jest drugi błąd - skąd wiesz, że zachodzi \(\displaystyle{ \neg \phi(a, b)}\)?

[zdl]

Ukryta treść:    

Czy można to udowodnić indukcyjnie?

Taką drogę zaproponował pan J.K. w rozwiązaniu.

Tu jest drugi błąd - skąd wiesz, że zachodzi \(\displaystyle{ \neg \phi(a, b)}\)?

Nie widzę tu błędu. Tzn. być może zbyt skrótowo napisałem i zabrakło wyjasnienia. Wiem, że `a,b` są kolejno najmniejszymi elementami `A, B`. To oznacza, że istnieje `c` taki, że `\not \phi(a,c)` oraz istnieje `d` taki, że `\not \phi(d,b)`. Weżmy zbiór `C_a := \{x \in \NN: \not \phi(a,x)\}`, jest oczywiście niepusty, bo należy do niego `c` oraz jego najmniejszym elemenem jest `b` (czyli `\not \phi(a,b)`, a więc to czego nam brakowało). Dlaczego `b` jest jego najmniejszym elementem? Gdyby nie był to mielibyśmy element najmniejszy `f<b`, gdzie `\not \phi(a,f)`. To by oznaczało, że `f` jest elementem `B` oraz jest mniejszy od `b`, a to stoi w sprzeczności z tym, że `b` jest elementem najmniejszym `B`.

Teraz dobrze?

[Dasio11]

Dlaczego `b` jest jego najmniejszym elementem? Gdyby nie był to mielibyśmy element najmniejszy `f<b`

W ten sposób można tylko uzasadnić, że w \(\displaystyle{ C_a}\) nie ma elementu mniejszego niż \(\displaystyle{ b}\). Ale nie da się tak uzasadnić, że \(\displaystyle{ b}\) jest elementm \(\displaystyle{ C_a}\), a przecież właśnie to potrzebujesz udowodnić.

[zdl]

W ten sposób można tylko uzasadnić, że w \(\displaystyle{ C_a}\) nie ma elementu mniejszego niż \(\displaystyle{ b}\). Ale nie da się tak uzasadnić, że \(\displaystyle{ b}\) jest elementm \(\displaystyle{ C_a}\), a przecież właśnie to potrzebujesz udowodnić.

OK, chyba rozumiem zarzut. Problem w tym, że założyłem niejawnie, że prawdziwe zdanie `\not \phi(a,b)` będzie miało najmniejszą możliwą parę `(a,b)`, to jest `a` będzie możliwie najmniejszym elementem oraz `b` będzie możliwie najmniejszym elementem. A to nie jest mądre założenie bo teoretycznie mógłbym mieć `\not \phi(5,4)` oraz `\not \phi(3,5)`, ale już niekoniecznie `\not \phi(3,4)`.

Pytanie czy mogę z tego jeszcze jakość wybrnąć czy pozostaje mi tylko indukcjia? Właśnie nad tym teraz myślę.

Dodano po 13 minutach 10 sekundach:
To jeszcze raz dowód, ale ze skrótami, żeby nie przepisywać wszystkiego.

`a,b` są najmniejszymi elementami kolejno `A, B`. Weżmy najmniejszy element `c \in C_a`. Więc mamy `\not \phi(a,c)`. Wiemy, że prawdziwe jest `\phi(a-1, c)`. Z założenia otrzymujemy `\phi(a,c)` co prowadzi do sprzeczności z `\not \phi(a,c)`. Analogicznie pozostaje drugi wariant dla `b-1`.

Teraz jest dobrze? Czy znowu coś pomieszałem?

[Dasio11]

`a,b` są najmniejszymi elementami kolejno `A, B`. Weżmy najmniejszy element `c \in C_a`. Więc mamy `\not \phi(a,c)`. Wiemy, że prawdziwe jest `\phi(a-1, c)`. Z założenia otrzymujemy `\phi(a,c)` co prowadzi do sprzeczności z `\not \phi(a,c)`. Analogicznie pozostaje drugi wariant dla `b-1`.

To zdecydowanie lepszy kierunek, ale nadal nie jest dobrze. Po stwierdzeniu że \(\displaystyle{ \neg \phi(a, c)}\) powinieneś rozważyć trzy przypadki: \(\displaystyle{ a > 0, c > 0}\) i \(\displaystyle{ (a, c) = (0, 0)}\), i w każdym dojść do sprzeczności.

[zdl]

No to jeszcze raz cały, kompletny dowód. Proszę o sprawdzenie.

Załóżmy nie wprost, że zdanie "`\phi(m,n)` jest prawdziwe dla wszystkich `m,n`" nie jest prawdziwe. To oznacza, że zdanie `\phi(m,n)` nie jest prawdziwe dla pewnych `m,n`, a to z kolei znaczy, że prawdziwe jest zdanie `\not phi(m,n)` dla pewnych `m,n`. Ustalmy `A := \{m \in \NN: (\exists n \in \NN) \not \phi(m,n)\}`. Skoro `\not \phi(m,n)` jest prawdziwe dla pewnych `m,n` to zbiór `A` ma przynajmniej jeden element. Z zasady minimum, wiemy, że zbiór `A` ma element najmniejszy i nazwijmy go `a`. Skoro `a \in A` to istnieje element `b` taki, że `\not \phi(a,b)`. Rozpatrzmy zbiór `C_a:=\{x \in \NN: \not \phi(a,x)\}`. Skoro `\not \phi(a,b)` to `b \in C_a` czyli zbiór `C_a` jest niepusty, a to z zasady minumum oznacza, że ma element najmniejszy `c` czyli prawdziwe jest `\not \phi(a,c)`. Z założenia wiemy, że `\phi(0,0)` jest prawdziwe czyli `a,c \in \NN` nie mogą być oba jednocześńie równe `0`. Załózmy, że `a>0`, a więc istnieje `a-1 \in \NN` i rozpatrzmy zdanie `\phi(a-1, c)`. Zdanie musi być prawdziwe, bo inaczej `a-1` byłoby elementem najmniejszmy zbioru `A`, co stoi w sprzeczności z tym, że `a` jest elementem najmniejszy zbioru `A`. Z założenia, które mówi, że z prawdziwości `\phi(m,n)` wynika `\phi(m+1,n)` otrzymujemy prawdziwość zdania `\phi(a-1+1, c)` czylli prawdziwość `\phi(a,c)` co stoi w sprzeczności z `\not phi(a,c)`. A więc `a` nie może być większe od zera. Zatem `c` musi być większe od `0` i rozpatrzmy wariant `c > 0`. Skoro `c > 0` to `c-1 \in \NN`. Zdanie `\phi(a,c-1)` jest prawdzie, bo gdyby nie było to `c-1` byłoby elementem najmniejszym `C_a` co stoi w sprzeczności z tym, że `c` jest elementem najmniejszym `C_a`. Z założenia, które mówi, że z prawdziwości `\phi(m, n)` wynika `\phi(m, n+1)` otrzymujemy prawdziwość `\phi(a, c-1+1)` czyli `\phi(a, c)`, a więc w każdym możliwym wariancie otrzymujemy `\phi(a,c)` co stoi w sprzeczności z `\not \phi(a,c)`, a co za tym idzie nasze założenie, że istnieją `m,n` dla których fałszywe jest `\phi(m,n)` było błędne czyli dla wszystkich `m,n \in \NN` mamy `\phi(m,n)` co kończy dowód.

[Dasio11]

Teraz powiedziałbym, że jest aż zbyt dokładnie, ale ważniejsze, że poprawnie.

[zdl]

Dziękuję.