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}}\)
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\}. }\)
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}\)
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}\)
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::
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 ).