Czy dane twierdzenie jest prawdziwe?

[zdl]

Niech `\phi(x) ` będzie funkcją zdaniową o zakresie zmniennej ` x \in \NN `. Czy prawdziwe jest zdanie
"Jeśli ` (\forall n \in \NN)((\forall k \le n) \phi(k) \Rightarrow \phi(n))`, to `(\forall n \in \NN) \phi(n)`"?

No oko wydaje mi się to twierdzenie poprawne, ale dowodu jeszcze nie mam. Mam rację?

[Janusz Tracz]

Skoro pierwsze zdanie jest prawdziwe to w szczególności prawdą jest, że \(\displaystyle{ \phi(0) \Rightarrow \phi(1) }\) ale jeśli \(\displaystyle{ \phi(0)}\) oraz \(\displaystyle{ \phi(1)}\) były by fałszem to nieprawdą jest wtedy, że \(\displaystyle{ (\forall n \in \NN) \phi(n)}\), zaświadcza o tym \(\displaystyle{ n=0}\) oraz \(\displaystyle{ n=1}\) (wystarcza nam i tak jeden świadek).

[Dasio11]

Czy prawdziwe jest zdanie
"Jeśli ` (\forall n \in \NN)((\forall k \le n) \phi(k) \Rightarrow \phi(n))`, to `(\forall n \in \NN) \phi(n)`"?

Wynikanie nie zachodzi z raczej trywialnej przyczyny, że założenie jest zawsze spełnione, a teza niekoniecznie. Ale po drobnej zmianie w treści:

"Jeśli \(\displaystyle{ (\forall n \in \NN)((\forall k < n) \, \phi(k) \Rightarrow \phi(n))}\), to \(\displaystyle{ (\forall n \in \NN) \, \phi(n)}\)"

wynikanie staje się prawdziwe, i nosi nazwę indukcji porządkowej.

[zdl]

@Dasio: OK, ale potrzebuję jeszcze kontrprzykładu.

@Janusz Tracz: Rozumiem, że proponujesz `phi(x) = (x=0)`. Więc rozpatrze poprzednik implakacji dla `n=1`.

`( \forall k \le 1)(k = 0 \Rightarrow 1=0)`. I teraz zostaje podstawić za `k`, `0` oraz `1`.

Dla `0`: `0=0 \Rightarrow 1 = 0`, a więc zdanie jest fałszywe. Zatem zdanie ` (\forall k \le 1)(k = 0 \Rightarrow 1=0)` jest fałszywe, a co za tym idzie cały poprzednik implikacji jest również fałszywy. Więc ten kontrprzykład mi nie pomógł?

Gdzie jest mój błąd?

[Dasio11]

@Dasio: OK, ale potrzebuję jeszcze kontrprzykładu.

Przecież z mojej odpowiedzi natychmiast wynika, że kontrprzykładem jest każda formuła \(\displaystyle{ \phi(x)}\) o zakresie \(\displaystyle{ x \in \NN}\), dla której nie zachodzi zdanie \(\displaystyle{ (\forall n \in \NN) \, \phi(n)}\). Chyba potrafisz taką znaleźć?

Gdzie jest mój błąd?

Błąd polega na tym, że \(\displaystyle{ (\forall k \le n) \, \phi(k) \Rightarrow \phi(n)}\) znaczy to samo co \(\displaystyle{ \big[ (\forall k \le n) \, \phi(k) \big] \Rightarrow \phi(n)}\), ale co innego niż \(\displaystyle{ (\forall k \le n) \big[ \phi(k) \Rightarrow \phi(n) \big]}\).

[zdl]

Racja, dziękuję. Teraz wszystko działa.

Teraz pozostaje jeszcze pytanie, ale już bezpośrednio do pana J. Kraszewskiego z racji tego, że nie chcę mi się przepisywać całego przykładu. W pana książce w przykładzie 4.6 stosuje pan dowód za pomocą indukcji porządkowej czyli za pomocą twierdzenia 4.3(c). Jednocześnie w kroku indukcyjnym piszę pan "Przypuśćmy, że dla `m \le n` zachodzi `\phi(m)`. Według mnie powinno być tam `m < n`. Więc albo jeszcze nie do końca rozumiem ten dowód albo w tym przykładzie jest błąd.

P.S. Czy to celowa sztuczka po to, żeby działać na zbiorze `a_{n+1}`?

P.S.2 Ale jeżeli to celowa sztuczka to czy nie stosuje pan uproszczenia? Mamy tu w rzeczywistości do czynienia z twierdzeniem
"Jeśli `\phi(0) \wedge (\forall n \in \NN)((\forall k \le n)\phi(k) => \phi(n+1))`, to `(\forall n \in N) \phi(n)`"?

[Janusz Tracz]

@Janusz Tracz: Rozumiem, że proponujesz `phi(x) = (x=0)`. Więc rozpatrze poprzednik implakacji dla `n=1`.

`( \forall k \le 1)(k = 0 \Rightarrow 1=0)`. I teraz zostaje podstawić za `k`, `0` oraz `1`.

Dla `0`: `0=0 \Rightarrow 1 = 0`, a więc zdanie jest fałszywe. Zatem zdanie ` (\forall k \le 1)(k = 0 \Rightarrow 1=0)` jest fałszywe, a co za tym idzie cały poprzednik implikacji jest również fałszywy. Więc ten kontrprzykład mi nie pomógł?

Gdzie jest mój błąd?

Nie do końca rozumiem co masz na myśli z tym \(\displaystyle{ 1=0}\) itd. ale fragment

Błąd polega na tym, że \(\displaystyle{ (\forall k \le n) \, \phi(k) \Rightarrow \phi(n)}\) znaczy to samo co \(\displaystyle{ \big[ (\forall k \le n) \, \phi(k) \big] \Rightarrow \phi(n)}\), ale co innego niż \(\displaystyle{ (\forall k \le n) \big[ \phi(k) \Rightarrow \phi(n) \big]}\).

chyba wyjaśnił Ci wątpliwości.

[Dasio11]

P.S.2 Ale jeżeli to celowa sztuczka to czy nie stosuje pan uproszczenia? Mamy tu w rzeczywistości do czynienia z twierdzeniem
"Jeśli `\phi(0) \wedge (\forall n \in \NN)((\forall k \le n)\phi(k) => \phi(n+1))`, to `(\forall n \in N) \phi(n)`"?

Nie mam tej książki, ale powyższe wynikanie jest zawsze prawdziwe i jest wariantem indukcji porządkowej.

[Jan Kraszewski]

Teraz pozostaje jeszcze pytanie, ale już bezpośrednio do pana J. Kraszewskiego z racji tego, że nie chcę mi się przepisywać całego przykładu. W pana książce w przykładzie 4.6 stosuje pan dowód za pomocą indukcji porządkowej czyli za pomocą twierdzenia 4.3(c). Jednocześnie w kroku indukcyjnym piszę pan "Przypuśćmy, że dla `m \le n` zachodzi `\phi(m)`. Według mnie powinno być tam `m < n`. Więc albo jeszcze nie do końca rozumiem ten dowód albo w tym przykładzie jest błąd.

Nie ma błędu. Zakładam, że teza zachodzi dla \(\displaystyle{ m<n+1}\) i pokazuję, że wtedy zachodzi także dla \(\displaystyle{ n+1}\).

P.S. Czy to celowa sztuczka po to, żeby działać na zbiorze `a_{n+1}`?

To jest dopasowanie dowodu do konstrukcji z Przykładu 4.4(4).

P.S.2 Ale jeżeli to celowa sztuczka to czy nie stosuje pan uproszczenia? Mamy tu w rzeczywistości do czynienia z twierdzeniem "Jeśli `\phi(0) \wedge (\forall n \in \NN)((\forall k \le n)\phi(k) => \phi(n+1))`, to `(\forall n \in N) \phi(n)`"?

Mamy do czynienia z twierdzeniem, które sformułowałeś, ale to jest dokładnie to samo twierdzenie, co w tw. 4.3(c), tylko inaczej sformułowane. Zauważ, że w wersji z tw. 4.3(c) przypadek \(\displaystyle{ \phi(0)}\) został "schowany" w warunku \(\displaystyle{ (\forall n \in \NN)((\forall k < n)\phi(k) \Rightarrow \phi(n))}\), który można inaczej zapisać jako \(\displaystyle{ \phi(0)\land(\forall n\ge 1)((\forall k < n)\phi(k) \Rightarrow \phi(n))}\). Teraz stosując podstawienie \(\displaystyle{ n:=n+1}\) dostajemy twierdzenie, które sformułowałeś powyżej.

JK