Twierdzenie o indukcji

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1386
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 58 razy
Pomógł: 83 razy

Twierdzenie o indukcji

Post autor: Jakub Gurak »

Mamy twierdzenie o indukcji, dla dobrych porządków:

Niech \(\displaystyle{ (X, \le )}\) będzie niepustym zbiorem dobrze uporządkowanym.
Wtedy, w zbiorze \(\displaystyle{ X,}\) obowiązuje zasada indukcji, tzn.:

Dla dowolnego zbioru \(\displaystyle{ Z \subset X}\) (który to zbiór \(\displaystyle{ Z}\) reprezentuje wszelkiego typu własności twierdzeń odnośnie elementów zbioru \(\displaystyle{ X}\), i zbiór wszystkich elementów zbioru \(\displaystyle{ X}\), które spełniają daną własność jest ów podzbiorem zbioru \(\displaystyle{ X}\)), dla zbioru \(\displaystyle{ Z \subset X,}\) takiego, że:

(1): element najmniejszy zbioru \(\displaystyle{ X}\) należy do \(\displaystyle{ Z}\),
(2): dla dowolnego \(\displaystyle{ {\displaystyle \displaystyle x\in X}}\), jeśli \(\displaystyle{ {\displaystyle \displaystyle \{y\in X:y<x\}\subset Z}}\), to \(\displaystyle{ {\displaystyle \displaystyle x\in Z},}\)

zachodzi \(\displaystyle{ {\displaystyle \displaystyle Z=X}.}\)

Czyli wtedy, dane twierdzenie, jest prawdziwe w całym zbiorze dobrze uporządkowanym.

Przedstawię dwa przykłady zastosowania tego twierdzenia, czyli podam dwa przykłady dowodów indukcyjnych dla dobrych porządków ( nie dla liczb naturalnych, dowody ogólne, dla dowolnego zbioru dobrze uporządkowanego)- jeden prostszy, drugi trudniejszy.


Niech \(\displaystyle{ \mathbb{X}}\) będzie niepustą liczbą porządkową.

Wtedy każdy zbiór \(\displaystyle{ A \in \mathbb{X}}\) jest podzbiorem \(\displaystyle{ \mathbb{X}}\).
A zatem poniższe pytanie ma sens:
Jakie funkcje \(\displaystyle{ f:\mathbb{X} \rightarrow \mathbb{X}}\) spełniają:

\(\displaystyle{ \stackrel{ \rightarrow }{f} \left( A\right) = f(A)}\) , dla każdego zbioru \(\displaystyle{ A \in \mathbb{X}}\) :o

Rozwiązanie:

Identyczność \(\displaystyle{ I:\mathbb{X} \rightarrow \mathbb{X},}\) niewątpliwie spełnia to zadanie, bo dla \(\displaystyle{ A \in \mathbb{X}}\) mamy oczywiście: \(\displaystyle{ I(A)=A.}\)

Oraz \(\displaystyle{ \stackrel{ \rightarrow }{I} (A)= A,}\)

gdyż jest to identyczność, a więc obrazem danego zbioru jest on sam.

A więc identyczność spełnia to zadanie.

Wykażemy, że nie ma innych takich funkcji.

W tym celu wykażemy, że dowolna funkcja \(\displaystyle{ f:\mathbb{X} \rightarrow \mathbb{X}}\) spełniająca nasze zadanie, czyli taka, że:

\(\displaystyle{ \stackrel{ \rightarrow }{f} \left( A\right) = f(A)}\), dla każdego \(\displaystyle{ A \in \mathbb{X},}\)

jest równa identyczności: \(\displaystyle{ f= I _{\mathbb{X}}.}\)

Niech \(\displaystyle{ f}\) będzie dowolną taką funkcją.

Aby wykazać, że \(\displaystyle{ f=I _{\mathbb{X}}}\), wykażemy, że \(\displaystyle{ f(A)= I _{\mathbb{X}} (A)}\), dla każdego zbioru \(\displaystyle{ A \in \mathbb{X}.}\)

Wykażemy to indukcyjnie:

Niech \(\displaystyle{ A \in \mathbb{X}}\), i przypuśćmy, że dla każdej liczby porządkowej \(\displaystyle{ B<A}\) (równoważnie dla \(\displaystyle{ B \in A}\) ) mamy \(\displaystyle{ f(B)= I_X\left( B\right)=B }\). Pokażemy, że \(\displaystyle{ f(A) = I _{\mathbb{X}} ( A)= A.}\)

Mamy, na mocy założenia:

\(\displaystyle{ f(A)= \stackrel{ \rightarrow }{f} \left( A\right) = \left\{ f(x): \ x \in A\right\} = \left\{ f(B): \ B \in A\right\} = \left\{ B: \ B \in A\right\} =A.\square }\)(Wystarczy dowód pozbierać aby go zakończyć).


Drugim przykładem dowodu indukcyjnego będzie fragment dowodu twierdzenia o definiowaniu przez indukcję pozaskończoną.

Dla zbiorów \(\displaystyle{ A,B}\) przez \(\displaystyle{ PF\left( A,B\right) }\) oznaczamy zbiór wszystkich funkcji częściowych z \(\displaystyle{ A}\) do \(\displaystyle{ B}\), czyli zbiór funkcji na dowolnych podzbiorach zbioru \(\displaystyle{ A}\) i o wartościach w zbiorze \(\displaystyle{ B}\), czyli chodzi o zbiór:

\(\displaystyle{ PF\left( A,B\right)= \left\{ f \subset A \times B\Bigl| \ \left( a,b_1\right) \in f \wedge \left( a, b_2\right) \in f \Longrightarrow b_1= b_2 \right\}. }\)

Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem dobrze uporządkowanym, niech \(\displaystyle{ B}\) będzie dowolnym zbiorem, \(\displaystyle{ C}\) niech będzie niepustym zbiorem.

Twierdzenie o definiowaniu przez indukcję pozaskończoną mówi, że dla każdej funkcji \(\displaystyle{ g:PF\left( X \times B, C\right) \times \left( X \times B\right) \rightarrow C}\) istnieje dokładnie jedna funkcja \(\displaystyle{ h:X \times B \rightarrow C,}\) spełniająca:

\(\displaystyle{ h\left( x,b\right) = g\left( \ h \cap \left( O(x) \times B \right) \times C, \left( x,b\right) \ \right),}\)

gdzie, dla \(\displaystyle{ x \in X,}\) przez \(\displaystyle{ O\left( x\right)}\) oznaczamy zbiór wszystkich elementów silnie mniejszych od \(\displaystyle{ x}\), tzn.:

\(\displaystyle{ O(x)= \left\{ y \in X: \ y<x\right\}, }\) a
\(\displaystyle{ \overline{O(x)} =\left\{ y \in X: \ y \le x\right\}. }\):mrgreen:

FRAGMENT DOWODU TEGO FAKTU:

Niech \(\displaystyle{ g:PF\left( X \times B, C\right) \times \left( X \times B\right) \rightarrow C}\).

Rozważmy zbiór \(\displaystyle{ H}\), dany jako:

\(\displaystyle{ H=\left\{ f \in PF\left( X \times B, C\right): \ \ \bigvee\limits_{a \in X} \left( f: \overline{O(a)} \times B \rightarrow C \wedge \textbf{*} f\left( x,b\right)= g\left( \ f \cap \left( O(x) \times B \right) \times C, \left( x,b\right) \ \right) \right) \right\}.}\)

Innymi słowy, zbiór \(\displaystyle{ H,}\) to zbiór krótszych funkcji dla których twierdzenie zachodzi; dokładniej zbiór \(\displaystyle{ H}\) jest zbiorem wszystkich funkcji częściowych z \(\displaystyle{ X \times B}\) w \(\displaystyle{ C,}\) określonych na zbiorach postaci \(\displaystyle{ \overline{O(a)} \times B }\), gdzie \(\displaystyle{ a \in X,}\) spełniających równość z tezy twierdzenia- czyli jest to zbiór krótszych funkcji, dla których nasze twierdzenie zachodzi. Funkcja, której szukamy, powinna być określona na całym zbiorze \(\displaystyle{ X \times B}\).

Pokazujemy, że dla dowolnych dwóch funkcji z \(\displaystyle{ H}\) jedna jest rozszerzeniem drugiej.

Pokażemy teraz, że dla każdego \(\displaystyle{ a \in X}\) istnieje w \(\displaystyle{ H}\) funkcja określona na zbiorze \(\displaystyle{ \overline{O(a)} \times B}\), lub, równoważnie (na mocy definicji zbioru \(\displaystyle{ H}\)), dla każdego \(\displaystyle{ a \in X}\) istnieje funkcja określona na zbiorze \(\displaystyle{ \overline{O(a)} \times B,}\) spełniająca równość \(\displaystyle{ \textbf{*}}\).

Dowód jest indukcyjny:

Niech \(\displaystyle{ z \in X}\), i przypuśćmy, że dla każdego \(\displaystyle{ x \in X, x<z}\) istnieje funkcja określona na zbiorze \(\displaystyle{ \overline{O(x)} \times B,}\) spełniająca równość \(\displaystyle{ \textbf{*}}\). Pokażemy, że istnieje funkcja określona na zbiorze \(\displaystyle{ \overline{O(z)} \times B,}\) spełniająca równość \(\displaystyle{ \textbf{*}}\).

Niech \(\displaystyle{ H_z}\) będzie zbiorem wszystkich funkcji częściowych z \(\displaystyle{ H}\) określonych na zbiorach postaci \(\displaystyle{ \overline{O(x)} \times B}\), gdzie \(\displaystyle{ x<z.}\)

Określmy funkcję \(\displaystyle{ h_z}\), jako:

\(\displaystyle{ h_z= \bigcup H_z \cup \bigcup_{b \in B} \left\{ \ \left( \left( z,b\right) ; g\left( \bigcup H_z; \left( z,b\right) \right)\right) \ \right\} .}\)

(Zauważmy, że jak zsumujemy funkcje z rodziny \(\displaystyle{ H_z}\), czyli funkcje określone na zbiorach postaci \(\displaystyle{ \overline{O(x)} \times B}\), gdzie \(\displaystyle{ x<z}\) (na mocy założenia indukcyjnego na każdym takim zbiorze jest określona pewna funkcja spełniająca równość \(\displaystyle{ \textbf{*}}\)), to (bez względu na to czy element \(\displaystyle{ z}\) będzie elementem granicznym, czy też nie), to zabraknie nam określenia funkcji na ostatnim elemencie \(\displaystyle{ z}\) (po dowolnym \(\displaystyle{ b \in B}\)). Dodajemy zatem taki prosty zbiór punktów (to nie są straszne sumacje), bo to \(\displaystyle{ g\left( \bigcup H_z; \left( z,b\right) \right)}\)- to już nie są żadne sumacje- tu funkcja \(\displaystyle{ g}\) wybiera jeden element (bo każda funkcja wybiera jeden element) na podstawie ostatnio rozpatrywanej funkcji \(\displaystyle{ \bigcup H_z}\) (przekonaliśmy się już, że ta właśnie funkcja była 'ciut' za krótka), i funkcja \(\displaystyle{ g}\) wybiera na jej podstawie jeden element (i na argumentach \(\displaystyle{ z,b}\) tak działa ta definiowana funkcja \(\displaystyle{ h_z}\), tak jak działa funkcja \(\displaystyle{ g}\) na podstawie \(\displaystyle{ z,b}\))- funkcja \(\displaystyle{ g}\) wybiera tu jeden element; tu wprawdzie występuje jeszcze takie proste sumowanie- zamiast dodać jeden punkt, dodajemy takie punkty po zbiorze, czyli po \(\displaystyle{ b \in B}\)- ale, te sumacje, nie są aż takie straszne na jakie wyglądają).

Ponieważ dla dowolnych dwóch funkcji w \(\displaystyle{ H}\) jedna jest rozszerzeniem drugiej, więc również dla dowolnych dwóch funkcji w \(\displaystyle{ H_z}\) jedna jest rozszerzeniem drugiej (bo \(\displaystyle{ H_z \subset H}\)), a więc zbiór \(\displaystyle{ \bigcup H_z}\) jest funkcją częściową.

Na mocy naszej uwagi te dwa składniki sumy są funkcjami określonymi na zbiorach rozłącznych, a więc również \(\displaystyle{ h_z: \overline{O(z)} \times B \rightarrow C. }\)

Aby pokazać, że ta funkcja spełnia równość \(\displaystyle{ \textbf{*}}\), to weźmy dowolne elementy \(\displaystyle{ x \in \overline{O(z)}}\) i \(\displaystyle{ b \in B}\). Wtedy \(\displaystyle{ x \le z.}\)

Rozważmy dwa przypadki:

\(\displaystyle{ 1 ^{\circ}: x=z}\), wtedy \(\displaystyle{ h_z\left( z,b\right)= g\left( \bigcup H_z, \left( z,b\right) \right),}\) i ponieważ, jak łatwo można się przekonać:

\(\displaystyle{ {\displaystyle \displaystyle h_{z}\cap \left( (O(z)\times B\right) \times C)=\bigcup H_{z}}}\), to:

\(\displaystyle{ {\displaystyle \displaystyle h_{z}(z,b)=g( \ h_{z}\cap \left( (O(z)\times B\right) \times C),\left( z,b\right) \ ),}}\)

gdyż funkcja \(\displaystyle{ g}\) wybiera tylko jeden element.

\(\displaystyle{ 2 ^{\circ}:}\) W pozostałym przypadku \(\displaystyle{ x<z}\).

Wtedy \(\displaystyle{ {\displaystyle \displaystyle (\left( x,b\right) ,h_{z}(x,b))\in \bigcup H_{z}}}\), a więc taka para musi należeć do pewnej funkcji z \(\displaystyle{ H_z}\), nazwijmy tą funkcję jako \(\displaystyle{ h_x}\).

Ponieważ \(\displaystyle{ H_z \subset H}\), to \(\displaystyle{ h_x \in H}\), a więc funkcja \(\displaystyle{ h_x}\) spełnia równość \(\displaystyle{ \textbf{*}}\), a zatem:

\(\displaystyle{ {\displaystyle \displaystyle h_{z}(x,b)=h_{x}(x,b)=g( \ h_{x}\cap (\left( O(x)\times B\right) \times C),\left( x,b\right) \ ).} }\)

Skoro \(\displaystyle{ {\displaystyle \displaystyle h_{x}\in H_{z}}}\), to, z własności sumy: \(\displaystyle{ {\displaystyle \displaystyle h_{x}\subset \bigcup H_{z}}}\), a więc (z definicji funkcji \(\displaystyle{ h_z}\) ) otrzymujemy: \(\displaystyle{ {\displaystyle \displaystyle h_{x}\subset \bigcup H_{z} \subset h_{z}}}\), a więc \(\displaystyle{ h_x \subset h_z}\), a więc funkcja \(\displaystyle{ h_z}\) rozszerza funkcję \(\displaystyle{ h_x}\). Ponieważ \(\displaystyle{ h_x \in H}\), to funkcja \(\displaystyle{ h_x}\) musi być określona na zbiorze postaci \(\displaystyle{ \overline{ O(a)} \times B}\), gdzie \(\displaystyle{ a \in X}\), a ta funkcja jest już określona na parze \(\displaystyle{ \left( x,b\right)}\) , więc łatwo jest przekonać się, że ta funkcja będzie określona na całym zbiorze \(\displaystyle{ O(x) \times B}\), a więc jej rozszerzenie \(\displaystyle{ h_z}\) też będzie określone na tym zbiorze, i ta funkcja \(\displaystyle{ h_z}\) będzie przyjmować te same wartości, wobec czego:

\(\displaystyle{ h_z \cap \left( O(x) \times B \right) \times C = h_x \cap \left( O(x) \times B \right) \times C,}\)

a zatem:

\(\displaystyle{ {\displaystyle \displaystyle h_{z}(x,b)=g( \ h_{x}\cap (\left( O(x)\times B\right) \times C),\left( x,b\right) \ )=g( \ h_{z}\cap (\left( O(x)\times B\right) \times C),\left( x,b\right) \ ),}}\)

co należało pokazać.

Na mocy zasady indukcji dla dobrych porządków: dla każdego \(\displaystyle{ a \in X}\) istnieje funkcja określona na zbiorze \(\displaystyle{ \overline{O(a)} \times B,}\) spełniająca równość \(\displaystyle{ \textbf{*}. \square }\)


W ostatnią sobotę, na dobranoc, udowodniłem pewien fakt:

Rozważmy przedział \(\displaystyle{ A \subset \NN}\) w zbiorze liczb naturalnych, przedział co najmniej dwuelementowy, ograniczony z góry.
Wtedy ten zbiór \(\displaystyle{ A}\) ma liczbę najmniejszą \(\displaystyle{ a}\), a ponieważ jest ograniczony z góry, to \(\displaystyle{ A}\) ma liczbę największą \(\displaystyle{ M}\).

Wykażemy tzw. zasadę indukcji skończonej dla liczb z tego przedziału, tzn. wykażemy, że:

Dla dowolnego zbioru \(\displaystyle{ B \subset A}\), jeśli:

\(\displaystyle{ 1 ^{\circ}: M \in B}\), i
\(\displaystyle{ 2 ^{\circ}: \hbox{ dla } n>a: \hbox{ jeśli } n \in B, \hbox{ to } \left( n-1 \right) \in B}\),

to \(\displaystyle{ B=A.}\)

Intuicyjnie jest to oczywiste: podzbiory przedziału \(\displaystyle{ A}\) reprezentują wszelakie własności odnośnie liczb z tego przedziału, a poniższe twierdzenie służy dowodom faktów, które będą prawdziwe dla każdej liczby z tego przedziału (gdy są to długie przedziały). W tym celu sprawdzamy czy twierdzenie jest prawdziwe na elemencie największym, i czy jeśli jest prawdziwe na numerze silnie większym od elementu najmniejszego, to czy jest prawdziwe na numerze o jeden mniejszym. Dzięki temu twierdzenie będzie prawdziwe na \(\displaystyle{ (M-1), (M-2),\ldots, a+1,}\) i dalej \(\displaystyle{ a+1 >a}\), więc również to zachodzi na \(\displaystyle{ (a+1-1)=a}\), czyli fakt zachodzi dla każdej liczby z tego przedziału, a więc zbiór liczb z tego przedziału, spełniających daną własność, będzie równy całemu przedziałowi \(\displaystyle{ A}\). Jest to indukcja skończona, ale działa to też dla dowolnie dużych, skończonych przedziałów. Przedstawię teraz dowód tego faktu:

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ B}\) będzie zbiorem spełniającym nasze warunki.

Rozważmy zbiór \(\displaystyle{ C}\) dany jako:

\(\displaystyle{ C= \left\{ n \in \NN: \ n \in A \Longrightarrow n \in B \right\}.}\)

Wykażemy, że \(\displaystyle{ C= \NN.}\)

Oczywiście \(\displaystyle{ C \subset \NN}\).

Aby pokazać inkluzję w drugą stronę, to niech:\(\displaystyle{ n \in \NN}\).

Jeśli \(\displaystyle{ n\not \in A}\), to implikacja zachodzi, i \(\displaystyle{ n \in C}\).

Jeśli \(\displaystyle{ n \in A}\), to ponieważ liczba \(\displaystyle{ M}\) jest największa w \(\displaystyle{ A}\), to \(\displaystyle{ n \le M}\), a ponieważ \(\displaystyle{ a}\) jest najmniejsze w \(\displaystyle{ A}\), to \(\displaystyle{ a \le n.}\)

Jeśli \(\displaystyle{ n=M \in B}\), to implikacja zachodzi.

Jeśli \(\displaystyle{ n \neq M}\), to \(\displaystyle{ n<M.}\)

Przypuśćmy nie wprost, że \(\displaystyle{ n\not \in B.}\)

Ponieważ zbiory \(\displaystyle{ B \subset A}\) i \(\displaystyle{ A}\) są ograniczone z góry, to niech \(\displaystyle{ n_0}\) będzie największą liczbą naturalną \(\displaystyle{ n \in A}\), taką, że \(\displaystyle{ n\not \in B.}\)

Ponieważ \(\displaystyle{ M \in B}\), więc \(\displaystyle{ n_0 \neq M}\).

Ponieważ \(\displaystyle{ n_0 \in A}\), a \(\displaystyle{ M}\) jest największe w \(\displaystyle{ A}\), więc \(\displaystyle{ n_0 \le M}\) i \(\displaystyle{ n_0<M}\)( \(\displaystyle{ n_0 \neq M}\)). A zatem \(\displaystyle{ n_0+1 \le M}\).

Ponieważ \(\displaystyle{ A}\) jest przedziałem w \(\displaystyle{ \left( \NN, \le\right) }\) , a

\(\displaystyle{ A\ni n_0< n_0+1 \le M\in A}\),

więc wnioskujemy, że \(\displaystyle{ \left( n_0+1\right) \in A}\), a ponieważ \(\displaystyle{ n_0+1>n_0}\), to \(\displaystyle{ \left( n_0+1\right) \in B.}\)

( Gdyby byłoby \(\displaystyle{ \left( n_0+1\right) \not\in B}\), to \(\displaystyle{ \left( n_0+1\right) \in A \setminus B}\), a \(\displaystyle{ n_0}\) jest największe w \(\displaystyle{ A \setminus B}\), a zatem moglibyśmy wnioskować, że \(\displaystyle{ n_0 \ge n_0+1}\)- sprzeczność).

Wobec czego \(\displaystyle{ \left( n_0+1\right) \in B}\); ale \(\displaystyle{ n_0 \in A}\), a \(\displaystyle{ a}\) jest najmniejsze w \(\displaystyle{ A}\), więc \(\displaystyle{ a \le n_0}\), a zatem \(\displaystyle{ n_0+1>a}\), a ponieważ \(\displaystyle{ \left( n_0+1 \right) \in B}\), to na mocy naszych założeń \(\displaystyle{ n_0= \left( n_0+1\right) -1 \in B}\)- sprzeczność.

Wobec czego \(\displaystyle{ n \in B}\), i implikacja zachodzi; a zatem \(\displaystyle{ n \in C}\), i \(\displaystyle{ \NN= C.}\)

Łatwo zatem będzie pokazać, że \(\displaystyle{ A \subset B. }\)

Niech \(\displaystyle{ a \in A \subset \NN}\).

Wtedy \(\displaystyle{ a \in \NN=\CC}\), a zatem, z definicji zbioru \(\displaystyle{ C}\) wnioskujemy, że zachodzi implikacja \(\displaystyle{ a \in A \rightarrow a \in B}\).

Ponieważ \(\displaystyle{ a \in A}\), to \(\displaystyle{ a \in B}\), i \(\displaystyle{ A \subset B}\).

Mamy z założenia inkluzję w drugą stronę, wobec czego \(\displaystyle{ A=B.\square}\) :lol:

Dodano po 29 dniach 23 godzinach 32 minutach 3 sekundach:
Można uogólnić powyższy fakt na skończone podzbiory zbiorów liniowo uporządkowanych, tzn.:

Jeśli \(\displaystyle{ \left( X, \le \right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ A \subset X}\) jest skończonym podzbiorem, co najmniej dwuelementowym, wtedy zbiór \(\displaystyle{ A}\) z porządkiem \(\displaystyle{ \le}\) zawężonym do elementów tego zbioru jest, jako podzbiór zbioru liniowo uporządkowanego, jest liniowo uporządkowany; i jest to, z założenia, zbiór niepusty i skończony, a zatem zbiór \(\displaystyle{ A}\) ma element największy \(\displaystyle{ M}\) i ma element najmniejszy \(\displaystyle{ m}\).
Ponieważ jest to zbiór skończony, to \(\displaystyle{ A\sim \left\{ 1,2,3,\ldots,n\right\}}\), dla pewnego \(\displaystyle{ n \in \NN}\); możemy zatem ten zbiór ponumerować \(\displaystyle{ A= \left\{ f_1, f_2,\ldots, f_n\right\}. }\)
Zachodzi wówczas zasada indukcji dla elementów zbioru \(\displaystyle{ A}\):

Dla dowolnego zbioru \(\displaystyle{ B \subset A}\), jeśli:

\(\displaystyle{ 1 ^{\circ} \ M \in B,}\)
\(\displaystyle{ 2 ^{\circ} \ \hbox{ dla dowolnego } i>1, \hbox{ jeśli } f\left( i\right) \in B,\hbox{ to } f\left( i-1\right) \in B,}\)

zachodzi \(\displaystyle{ B=A}\).

Wykażemy powyższe twierdzenie, a następnie wykażemy zasadę indukcji skończonej 'od drugiej strony', z której (oraz z tej pierwszej zasady indukcji) będą wynikać dwie zasady indukcji skończonej w zbiorze liczb całkowitych, co jeszcze podkreślimy. Przedstawię teraz dowody tych ciekawych faktów.


DOWÓD PRZYTOCZONEGO TWIERDZENIA:

Mamy bijekcję, nie powiedziałem o tym jawnie, mamy bijekcję:

\(\displaystyle{ f:\left\{ 1,2,\ldots, n\right\} \rightarrow A,}\)

oraz mamy zbiór \(\displaystyle{ B \subset A,}\) spełniający powyższe warunki.

Rozważmy przeciwobraz \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left( B\right) \subset \left\{ 1,2,\ldots,n\right\}}\),

gdzie zauważmy, że zbiór \(\displaystyle{ \left\{ 1,2,\ldots, n\right\}}\) jest przedziałem w zbiorze liczb naturalnych, i ponieważ zbiór \(\displaystyle{ A}\) jest co najmniej dwuelementowy, to zbiór z nim równoliczny \(\displaystyle{ \left\{ 1,2,\ldots, n\right\}}\) również ma co najmniej dwa elementy, i jest ograniczony z góry ( przez liczbę \(\displaystyle{ n}\) ).

Stosujemy do niego oraz do zbioru \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left( B\right) \subset \left\{ 1,2,\ldots,n\right\}}\), stosujemy do nich zasadę indukcji skończonej dla zbioru liczb naturalnych, którą wykazałem w poście powyżej:

\(\displaystyle{ 1 ^{\circ} \ }\) Baza indukcji: Ponieważ \(\displaystyle{ M \in B}\), a \(\displaystyle{ f(n)=M}\), więc \(\displaystyle{ n \in\stackrel{ \rightarrow }{f ^{-1} } \left( B\right)}\), a zatem spełniona jest podstawa indukcji.
\(\displaystyle{ 2 ^{\circ} \ }\) Krok indukcyjny: Dla \(\displaystyle{ i>1}\), jeśli \(\displaystyle{ i \in \stackrel{ \rightarrow }{f ^{-1} } \left( B\right)}\), to \(\displaystyle{ \left( i-1\right) \in \stackrel{ \rightarrow }{f ^{-1} } \left( B\right)}\).
Aby to pokazać, to jeśli \(\displaystyle{ i \in \stackrel{ \rightarrow }{f ^{-1} } \left( B\right)}\), to z definicji przeciwobrazu: \(\displaystyle{ f(i) \in B}\), a zatem, na mocy założenia \(\displaystyle{ 2 ^{\circ }}\) odnośnie zbioru \(\displaystyle{ B}\), otrzymujemy: \(\displaystyle{ f\left( i-1\right) \in B}\), co oznacza, że \(\displaystyle{ \left( i-1\right) \in \stackrel{ \rightarrow }{f ^{-1} } \left( B\right)}\), co dowodzi kroku indukcyjnego.

Na mocy zasady indukcji dla przedziałów w zbiorze liczb naturalnych, udowodnionej w poście powyżej, otrzymujemy: \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left( B\right)= \left\{ 1,2,\ldots, n\right\}.
}\)


Ponieważ funkcja \(\displaystyle{ f}\) jest bijekcją, więc:

\(\displaystyle{ \stackrel{ \rightarrow }{f} \left( \stackrel{ \rightarrow }{f ^{-1} } \left( B\right) \right) = B= \stackrel{ \rightarrow }{f} \left( \left\{ 1,2,\ldots, n\right\} \right)= \left\{ f_1, f_2, \ldots, f_n\right\} =A. \square}\) 8-)


Wykażemy zasadę indukcji , symetryczną do tej, zasadę indukcji skończonej w zbiorze liniowo uporządkowanym, tylko od drugiej strony, tzn.:

Niech \(\displaystyle{ \left( X, \le \right)}\) będzie zbiorem liniowo uporządkowanym, a \(\displaystyle{ A \subset X}\) niech będzie skończonym podzbiorem, co najmniej dwuelementowym.
Wtedy zbiór \(\displaystyle{ A}\) z porządkiem \(\displaystyle{ \le}\) zawężonym do zbioru \(\displaystyle{ A}\) jest zbiorem liniowo uporządkowanym. Ponieważ jest to zbiór skończony, to możemy go ponumerować: \(\displaystyle{ A= \left\{ f_1, f_2, \ldots, f_n\right\}}\).
Wykażemy, że:

Dla dowolnego zbioru \(\displaystyle{ B \subset A}\), jeśli:

\(\displaystyle{ 1 ^{\circ} \ f_1 \in B,}\) i
\(\displaystyle{ 2 ^{\circ} \ \hbox{ dla } i<n, \hbox{ jeśli } f\left( i\right) \in B, \hbox{ to } f\left( i+1\right) \in B,}\)

zachodzi \(\displaystyle{ B=A}\).
DOWÓD TEGO FAKTU::    
Z powyższego twierdzenia wynika zasada indukcji skończonej dla ograniczonych przedziałów w zbiorze liczb całkowitych, tzn.:

Rozważmy zbiór liczb całkowitych \(\displaystyle{ \left( \ZZ, \le \right)}\), oraz rozważmy ograniczony przedział \(\displaystyle{ A \subset \ZZ}\), co najmniej dwuelementowy. Wtedy zbiór \(\displaystyle{ A}\) jest zbiorem skończonym (ale może być to bardzo długi przedział), i aby pokazać, że dane twierdzenie, odnośnie liczb z tego przedziału, jest prawdziwe dla każdej liczby z tego przedz\(\displaystyle{ }\)iału, wystarczy pokazać dwa fakty:

\(\displaystyle{ 1 ^{\circ} }\) Twierdzenie jest prawdziwe na elemencie najmniejszym \(\displaystyle{ m}\) tego przedziału;
\(\displaystyle{ 2 ^{\circ } }\) Dla elementu największego \(\displaystyle{ M}\) tego przedziału, dla dowolnego \(\displaystyle{ i<M, i \in \ZZ}\), jeśli twierdzenie jest prawdziwe na \(\displaystyle{ i}\), to jest prawdziwe na \(\displaystyle{ i+1}\).

Wtedy dane twierdzenie jest prawdziwe dla każdej liczby z tego przedziału.

Ten sam wynik można uzyskać sprawdzając, czy:

\(\displaystyle{ 1 ^{\circ}}\) Czy dane twierdzenie jest prawdziwe na elemencie największym \(\displaystyle{ M}\) tego przedziału,
\(\displaystyle{ 2 ^{\circ}}\) I czy jeśli to dane twierdzenie jest prawdziwe dla \(\displaystyle{ i>m}\), to czy jest prawdziwe na \(\displaystyle{ \left( i-1\right).}\)

Wówczas to dane twierdzenie również jest prawdziwe dla każdej liczby z tego przedziału.


Na koniec dodam, że mamy również zasadę indukcji dla liczb całkowitych, tzn.:

Dla dowolnego zbioru \(\displaystyle{ A \subset \ZZ}\), jeśli:

\(\displaystyle{ 1 ^{\circ } \ 0 \in A,}\)
\(\displaystyle{ 2 ^{\circ} \hbox{ jeśli } n \in A, \hbox{ to } \left( n+1\right) \in A \hbox{ i } \left( n-1\right) \in A,}\)

to \(\displaystyle{ A=\ZZ.}\)

(Którą to zasadę indukcji udowodniłem ostatnio TUTAJ, NA SAMYM KOŃCU ). 8-)
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1386
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 58 razy
Pomógł: 83 razy

Re: Twierdzenie o indukcji

Post autor: Jakub Gurak »

Przypomnijmy, jeśli mamy prostokąt \(\displaystyle{ X \times Y}\), oraz mamy rodzinę \(\displaystyle{ \mathbb{B}}\) funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), określonych na rozłącznych podzbiorach zbioru \(\displaystyle{ X,}\) wtedy suma \(\displaystyle{ \bigcup\mathbb{B}}\) jest funkcją częściową z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), i jest to funkcja ze zbioru \(\displaystyle{ \bigcup_{f \in \mathbb{B}} f_L}\) w zbiór \(\displaystyle{ Y}\)- jest to dość prosty fakt, będziemy z niego korzystać.

Niech \(\displaystyle{ X}\) będzie zbiorem (co najmniej przeliczalnym, ale będzie to własność ogólna, więc nawet gdyby nie było możliwości zastosowania tego faktu, to formalnie fakt zachodziłby- warunek byłby pusto spełniony, a więc formalnie byłby spełniony), a \(\displaystyle{ \mathbb{B}}\) niech będzie przeliczalną (równoliczną ze zbiorem \(\displaystyle{ \NN}\) ) rodziną podzbiorów zbioru \(\displaystyle{ X}\), rodziną zbiorów rozłącznych \(\displaystyle{ \left( X_n\right) _{n \in \NN}}\). Niech \(\displaystyle{ Y}\) będzie niepust\(\displaystyle{ }\)ym zbiorem.

Wtedy funkcję \(\displaystyle{ f: \bigcup_{n \in \NN} X_n \rightarrow Y}\) można zdefiniować w sposób indukcyjny:

W tym celu:

Definiujemy najpierw funkcje \(\displaystyle{ f_0:X_0 \rightarrow Y}\) w pewien sposób.

Załóżmy, że zdefiniowaliśmy już funkcję \(\displaystyle{ f_0: X_0 \rightarrow Y, f_1: X_1 \rightarrow Y, \ldots, f_n: X_n \rightarrow Y.}\)
Wtedy określamy funkcję \(\displaystyle{ f _{n+1}: X_ {n+1} \rightarrow Y}\), czyli dla dowolnego ustalonego \(\displaystyle{ x \in X _{n+1}}\) określamy jeden element \(\displaystyle{ f _{n+1} \left( x\right).}\)

Z twierdzenia o definiowaniu przez indukcję (te funkcję są podzbiorami ustalonego zbioru \(\displaystyle{ X \times Y}\), a więc są elementami jego zbioru potęgowego) otrzymujemy ciąg funkcji \(\displaystyle{ \left( f_n\right) _{n \in \NN}}\) zgodny z naszym konstruowaniem, tzn. dla dowolnego ustalonego \(\displaystyle{ n \in \NN}\), mamy funkcję \(\displaystyle{ f_n: X_n \rightarrow Y,}\) zgodną z naszym konstruowaniem.

Wtedy \(\displaystyle{ f_n}\) jest funkcją częściową z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), i dla liczb naturalnych \(\displaystyle{ n \neq m}\) zbiory \(\displaystyle{ \left( f_n\right) _L= X_n}\) oraz \(\displaystyle{ \left( f_m\right) _L=X_m}\) są rozłączne (z założenia), stosując zatem przytoczony fakt otrzymujemy, że suma: \(\displaystyle{ \bigcup_{n \in \NN} f_n}\) jest funkcją ze zbioru \(\displaystyle{ \bigcup_{n \in \NN} \left( f_n\right) _L= \bigcup_{n \in \NN} X_n}\) w zbiór \(\displaystyle{ Y.}\)
I dla \(\displaystyle{ n \in \NN}\), oraz dla funkcji \(\displaystyle{ f_n: X_n \rightarrow Y}\), i dla dowolnego ustalonego \(\displaystyle{ x \in X_n}\), mamy:

\(\displaystyle{ \left( \bigcup_{n \in \NN} f_n\right) \left( x\right) = f _{n} \left( x\right) =\\}\)

\(\displaystyle{ = \begin{cases} f_0\left( x\right), \hbox{ dla } n=0; \\ f_n\left( \left( f_0, f_1, \ldots, f _{n-1} \right);x \right) ; \hbox{ dla } n \neq 0. \end{cases}\square }\)

Zamierzam to wykorzystać definiując pewną funkcję na sumie przedziałów w zbiorze liczb rzeczywistych, aby zbadać moc wszystkich funkcji \(\displaystyle{ f:\RR \rightarrow \RR}\), funkcji słabo rosnących. 8-)
ODPOWIEDZ