szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 maja 2018, o 20:03 
Użytkownik

Posty: 992
Dobry wieczór,

Czy ktoś jest w stanie podać prosty przykład zastosowania indukcji pozaskończonej. Znam indukcję pozaskończoną, ale wszystkie przykłady, na które się natykam są to raczej przykłady trudne, tzn. kawałki bardziej skomplikowanych dowodów. Chciałbym jakiś prosty przykład, w którym jasno widać zastosowanie indukcji pozaskończonej.

Ktoś taki przykład zna?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2018, o 20:42 
Administrator

Posty: 22627
Lokalizacja: Wrocław
No cóż, indukcja pozaskończona to metoda dowodowa, nic więc dziwnego, że spotykasz ją w dowodach. A jako że dotyczy liczb porządkowych, to nie jest zaskakujące, że są to niekoniecznie proste dowody.

Trudno ocenić, co dla Ciebie jest "prostym przykładem".

JK
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2018, o 20:49 
Korepetytor
Avatar użytkownika

Posty: 3983
Lokalizacja: Praga, Dąbrowa Górnicza, Lancaster
Spójrz proszę na konstrukcję zbiorów Bernsteina.
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2018, o 21:39 
Użytkownik

Posty: 992
Jan Kraszewski napisał(a):
Trudno ocenić, co dla Ciebie jest "prostym przykładem".


Przez prosty przykład rozumiem krótki przykład.
Góra
Mężczyzna Offline
PostNapisane: 13 maja 2018, o 23:08 
Administrator

Posty: 22627
Lokalizacja: Wrocław
Spektralny napisał(a):

To oczywiście kwestia dyskusji terminologicznych, ale dla mnie to rekursja pozaskończona, a nie indukcja pozaskończona.

Jeżeli squared ma na myśli rekursję, to oczywiście jest dużo ładnych konstrukcji.

JK
Góra
Mężczyzna Offline
PostNapisane: 14 maja 2018, o 19:36 
Użytkownik

Posty: 992
Nie wiem, czy to różnica, ale miałem na myśli indukcję pozaskończoną.
Góra
Mężczyzna Offline
PostNapisane: 14 maja 2018, o 19:59 
Administrator

Posty: 22627
Lokalizacja: Wrocław
squared napisał(a):
Nie wiem, czy to różnica, ale miałem na myśli indukcję pozaskończoną.

Czyli chodziło Ci o przykłady dowodów, a nie przykłady konstrukcji, tak?

JK
Góra
Mężczyzna Offline
PostNapisane: 15 maja 2018, o 02:43 
Użytkownik

Posty: 372
Lokalizacja: Rzeszów
No tak, pisząc pracę licencjacką o dobrych porządkach, miałem problem ze znalezieniem przykładów dowodów indukcyjnych (dla dobrych porządków). Teraz mogę znaleźć jeden prosty przykład.

Przykład będzie uogólnieniem zadania:

Ile jest funkcji (jakie to są) f:\NN \rightarrow \NN takich, że f\left( n\right) =\stackrel{ \rightarrow }{f}\left( n\right), dla każdego n\in\NN :?:

Tu przez liczby naturalne, rozumiemy liczby naturalne w sensie von Neumanna, gdzie liczba naturalna jest zbiorem liczb naturalnych od niej mniejszych, więc polecenie ma sens.

Niewątpliwie identyczność na \NN spełnia zadanie- f=I _{\NN}. Niech n\in \NN. Wtedy:

f\left( n\right) =n, oraz

\stackrel{ \rightarrow }{f}\left( n\right)=\stackrel{ \rightarrow }{f}\left\{ m\in\NN:  \  \ m<n\right\} =\left\{ m\in\NN:  \  \ m<n\right\} =n, co wobec dowolności n pokazuje, że identyczność spełnia zadanie. Co więcej, to jedyna funkcja, która spełnia zadanie.

Aby to pokazać, pokażemy, że dowolna funkcja g:\NN \rightarrow  \NN, taka, że g\left( n\right) =\stackrel{ \rightarrow }{g}\left( n\right), dla każdego n\in\NN , jest równa f=I_{\NN}, czyli dowolna funkcja spełniająca zadanie jest tą właśnie funkcją identyczności, a więc identyczność jest jedyną funkcją spełniającą zadanie.

Aby pokazać, że g=f=I_{\NN}, wykażemy indukcyjnie, że X=\left\{ n\in\NN: \  \ g\left( n\right)=f\left( n\right)\right\}=\NN.

Podstawa indukcji: f\left( 0\right)=0 - bo to identyczność, oraz

g\left( 0\right) =\stackrel{ \rightarrow }{g}\left( 0\right)=\stackrel{ \rightarrow }{g}\left( \emptyset \right)=\emptyset=0, a więc g\left( 0\right)=f\left( 0\right)\right\}, i 0\in X.

Krok indukcyjny: Załóżmy, że n\in X. Pokażemy, że n'=n \cup \left\{ n\right\} \in X. Niewątpliwie f\left( n'\right)= f\left( n+1\right)=n+1. Tymczasem

g\left( n'\right)=\stackrel{ \rightarrow }{g}\left( n'\right)=\stackrel{ \rightarrow }{g}\left( n \cup \left\{ n\right\}\right)=\stackrel{ \rightarrow }{g}\left( n\right) \cup \stackrel{ \rightarrow }{g}\left\{ n\right\} =g\left( n\right) \cup \left\{ g\left( n\right)\right\}=f\left( n\right) \cup \left\{ f\left( n\right)\right\} =n \cup \left\{ n\right\} =n+1.

Ostatnia równość pochodzi z faktu, że f jest identycznością, a poprzednia z założenia indukcyjnego, że g\left( n\right)=f\left( n\right)\right\}. Wcześniej dwukrotnie skorzystaliśmy z założeń o funkcji g. A więc g\left( n'\right)=f\left( n'\right), czyli n' \in X.

Z zasady indukcji dla liczb naturalnych, dla każdego n naturalnego g\left( n\right)=f\left( n\right), zatem g=f=I_{\NN}, i identyczność jest jedyną funkcją spełniającą zadanie. \square :lol:

Skoro mowa o indukcji pozaskończonej, to powyższe zadanie można uogólnić, następująco:

Niech X będzie liczbą porządkową von Neumanna. Ile jest funkcji (jakie to są) f:X \rightarrow X takich, że f\left( A\right) =\stackrel{ \rightarrow }{f}\left( A\right), dla każdego A\in X :?:

Polecenie ma sens, bo ponieważ X jest liczbą porządkową, więc każdy element X jest jego podzbiorem, więc możemy nie tylko mówić o wartości funkcji dla zbioru A, ale również o obrazie zbioru A poprzez funkcję f.

Wynik jest analogiczny- tylko identyczność na X to spełnia. Łatwo sprawdzić, że identyczność na X spełnia zadanie. Aby pokazać, że jest to jedyna funkcja spełniająca zadanie, należy pokazać, że dowolna funkcja g:X \rightarrow X taka, że g\left( A\right) =\stackrel{ \rightarrow }{g}\left( A\right), dla każdego A\in X, jest równa g=f=I_{X}.

Weźmy dowolną taką funkcję g spełniającą zadanie. Aby pokazać, że g=f=I_{X}, wykażemy indukcyjnie, że Y=\left\{ x\in X: \ \ g\left( x\right)=f\left( x\right)\right\}=X.

Wiemy, że liczba porządkowa X jest dobrze uporządkowana przez inkluzję. W tym zadaniu będziemy więc oznaczać:

A \le B \Longleftrightarrow A\subset B.
A<B \Longleftrightarrow A\in B.

Rozpoczynając dowód indukcyjny, to niech A\in X. Przypuśćmy, że dla każdego B<A zachodzi B\in Y. Pokażemy, że A\in Y. Niewątpliwie f\left( A\right)=A. Natomiast z założeń o funkcji g mamy: g\left( A\right) =\stackrel{ \rightarrow }{g}\left( A\right) Ponieważ jednak dla każdego B<A, czyli dla każdego B\in A, mamy B\in Y, a więc z definicji tego zbioru wartości f\left( B\right) i g\left( B\right) są sobie równe, to również obrazy zbioru A poprzez odpowiednio g i f są równe, czyli \stackrel{ \rightarrow }{g}\left( A\right)=\stackrel{ \rightarrow }{f}\left( A\right), czyli g\left( A\right) =\stackrel{ \rightarrow }{g}\left( A\right)=\stackrel{ \rightarrow }{f}\left( A\right)=A, bo f jest identycznością. Zatem A\in Y Z zasady indukcji dla dobrych porządków Y=\left\{ x\in X: \ \ g\left( x\right)=f\left( x\right)\right\}=X, a więc na wszystkich elementach zbioru X wartości odpowiednie funkcji f i g są równe, a więcg=f=I_{X}, i identyczność jest jedyną funkcją spełniającą zadanie.\square :lol: :D
Góra
Mężczyzna Offline
PostNapisane: 15 maja 2018, o 16:14 
Użytkownik

Posty: 992
Jan Kraszewski napisał(a):
Czyli chodziło Ci o przykłady dowodów, a nie przykłady konstrukcji, tak?
JK


Nie musi być dowód, może być konstrukcja. Chciałem mieć przykład zastosowania, w miarę krótki, by móc w parę zdań o nim opowiedzieć.
Góra
Mężczyzna Offline
PostNapisane: 15 maja 2018, o 17:04 
Administrator

Posty: 22627
Lokalizacja: Wrocław
squared napisał(a):
Nie musi być dowód, może być konstrukcja. Chciałem mieć przykład zastosowania, w miarę krótki, by móc w parę zdań o nim opowiedzieć.

No to Spektralny podał Ci przykład, takich przykładów jest dużo.

Warto mieć jednak świadomość, że stwierdzając, iż "Nie musi być dowód, może być konstrukcja" utożsamiasz rekursję pozaskończoną z indukcją pozaskończoną (co niekiedy jest robione, ale w innych miejscach te dwa pojęcia są wyraźnie rozróżniane).

JK
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Indukcja pozaskończona - zadanie 2  TPB  4
 indukcja pozaskończona  magda2530  1
 indukcja WB 492  kz  3
 Tw. o definiowaniu przez indukcję pozaskończoną  Jakub Gurak  6
 indukcja w teorii mnogości  duuj  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl