Zasada indukcji dla dobrych porządków

[Jakub Gurak]

Napiszę tu trochę na ten temat.

Niech \(\displaystyle{ (X, \le )}\) będzie zbiorem liniowo uporządkowanym. W \(\displaystyle{ (X, \le )}\) obowiązuje zasada indukcji, jeśli przede wszystkim istnieje element najmniejszy \(\displaystyle{ a\in X}\), oraz dla dowolnego zbioru \(\displaystyle{ Z\subset X}\), takiego, że

1. \(\displaystyle{ a\in Z}\).
2.dla dowolnego \(\displaystyle{ x\in X}\): jeśli \(\displaystyle{ O(x)\subset Z}\) (czyli \(\displaystyle{ \left\{ y\in X: \ \ y<x\right\}\subset Z}\)) to \(\displaystyle{ x\in Z,
}\)

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

Jest to uogólnienie zasady indukcji porządkowej na zbiorze liczb naturalnych. Jeśli chcemy pokazać, że pewna własność \(\displaystyle{ \alpha (x)}\) jest spełniona dla wszystkich elementów zbioru \(\displaystyle{ X }\)(w którym obowiązuje zasada indukcji), to sprawdzamy czy ta własność jest spełniona na elemencie najmniejszym \(\displaystyle{ a}\), oraz czy dla dowolnego \(\displaystyle{ x\in X, }\) jeśli dla wszystkich \(\displaystyle{ y<x}\) własność \(\displaystyle{ \alpha}\) jest spełniona, to czy jest spełniona również na \(\displaystyle{ x}\). Gdy są spełnione te wszystkie wymagania to zasada indukcji głosi, że własność \(\displaystyle{ \alpha (x)}\) jest spełniona dla każdego \(\displaystyle{ x\in X}\). Formalnie, dla dowolnej rozważanej własności \(\displaystyle{ \alpha (x),}\) definiujemy zbiór \(\displaystyle{ Z=\left\{ x\in X: \alpha (x)\right\}}\), tych elementów \(\displaystyle{ X}\) które ją spełniają, jeśli zbiór \(\displaystyle{ Z}\) spełnia odpowiednie powyższym własności, to \(\displaystyle{ Z=X}\), czyli własność \(\displaystyle{ \alpha (x)}\) jest spełniona dla każdego \(\displaystyle{ x\in X}\). Zwróćmy uwagę jeszcze, że zasada indukcji w zbiorze \(\displaystyle{ X}\), podobnie jak w zbiorze liczb naturalnych, w danym zbiorze \(\displaystyle{ X}\), można rozpatrywać różne własności- jeśli tylko są spełnione te dwa warunki, to zasada indukcji pozwala wywnioskować, że zawsze właśność \(\displaystyle{ \alpha (x)}\) jest spełniona dla każdego \(\displaystyle{ x\in X}\), stąd to wymaganie by to zachodziło dla dowolnego zbioru \(\displaystyle{ Z\subset X}\), które to podzbiory zbioru \(\displaystyle{ X}\) przedstawiają wszystkie własności \(\displaystyle{ \alpha (x)}\), gdzie \(\displaystyle{ x\in X.}\)

Przypomnę, że zbiór liniowo uporządkowany \(\displaystyle{ (X, \le )}\) nazywamy zbiorem dobrze uporządkowanym, gdy każdy niepusty podzbiór \(\displaystyle{ X}\) ma element najmniejszy.

Wykażemy teraz, że jeśli \(\displaystyle{ \left( X, \le \right) }\) jest zbiorem liniowo uporządkowanym, w którym istnieje element najmniejszy, to w \(\displaystyle{ X}\) obowiązuje zasada indukcji, wtedy i tylko wtedy, gdy porządek na \(\displaystyle{ X}\) jest dobry.

Czyli zasada indukcji obowiązuje dokładnie w zbiorach dobrze uporządkowanych.

W szczególności to oznacza, że w każdym niepustym zbiorze dobrze uporządkowanym obowiązuje zasada indukcji( zbiór dobrze uporządkowany jest liniowo uporządkowany, i ponieważ cały zbiór jest niepusty, więc istnieje w nim element najmniejszy, to ponieważ jest dobrze uporządkowany, więc na mocy implikacji \(\displaystyle{ \Leftarrow}\) obowiązuje w nim zasada indukcji).

Dowód:

Niech \(\displaystyle{ \left( X, \le \right)}\) będzie zbiorem liniowo uporządkowanym w którym istnieje element najmniejszy \(\displaystyle{ z\in X.}\)

\(\displaystyle{ \Longleftarrow}\) Przypuśćmy, ze porządek jest dobry. Aby pokazać, że zachodzi w nim zasada indukcji, to niech \(\displaystyle{ Z}\) będzie dowolnym zbiorem \(\displaystyle{ Z\subset X}\), takim, że

1. \(\displaystyle{ z\in Z.}\)
2.dla dowolnego \(\displaystyle{ x\in X}\), jeśli \(\displaystyle{ O(x)\subset Z}\), to \(\displaystyle{ x\in Z}\).

Pokażemy, że \(\displaystyle{ Z=X.}\)
Dla dowodu niewprost, przypuśćmy, że \(\displaystyle{ Z\subsetneq X}\). Niech \(\displaystyle{ A=X \setminus Z}\). Wtedy \(\displaystyle{ A}\) jest zbiorem niepustym i jest podzbiorem \(\displaystyle{ X}\), więc z definicji zbioru dobrze uporządkowanego ma element najmniejszy \(\displaystyle{ a\in A}\). Skoro \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ A}\), to każdy element \(\displaystyle{ b\in X}\), dla którego \(\displaystyle{ b<a}\) nie należy do \(\displaystyle{ A=X \setminus Z}\), więc należy do \(\displaystyle{ Z}\), wtedy \(\displaystyle{ O(a)=\left\{ b\in X: b<a\right\} \subset Z}\), a więc z drugiej własności otrzymujemy, że \(\displaystyle{ a\in Z}\), i \(\displaystyle{ a \in A=X \setminus Z}\), zatem \(\displaystyle{ a\not\in Z}\)- sprzeczność. \(\displaystyle{ \square}\)

\(\displaystyle{ \Longrightarrow}\) Przypuśćmy, że w \(\displaystyle{ X}\) zachodzi zasada indukcji. Aby pokazać, że \(\displaystyle{ X}\) jest dobrze uporządkowany, ustalmy dowolny niepusty podzbiór \(\displaystyle{ A\subset X.}\) Przypuśćmy dla dowodu nie wprost, że nie ma on elementu najmniejszego. Zdefiniujmy zbiór \(\displaystyle{ Z}\) jako zbiór tych elementów \(\displaystyle{ X}\) ,które są silnie mniejsze od wszystkich elementów z \(\displaystyle{ A}\), czyli

\(\displaystyle{ Z= \left\{ b\in X\Bigl| \ \ \bigwedge\limits_{a\in A} b<a \right\} .}\)

Ponieważ \(\displaystyle{ A \neq \left\{ \right\}}\), to \(\displaystyle{ Z \neq X.}\) Wtedy element najmniejszy \(\displaystyle{ z\in X}\), należy również do \(\displaystyle{ Z}\)( bo jest najmniejszy w całym \(\displaystyle{ X}\)). Pokażemy, że dla dowolnego \(\displaystyle{ x\in X}\), jeśli \(\displaystyle{ \left\{ y\in X: \ \ y<x\right\} \subset Z}\), to \(\displaystyle{ x\in Z}\). Niech \(\displaystyle{ x\in X}\). Przypuśćmy (dla dowodu nie wprost), że \(\displaystyle{ \left\{ y\in X: \ \ y<x\right\} \subset Z}\), oraz \(\displaystyle{ x\not\in Z}\). Ponieważ \(\displaystyle{ x\not\in Z}\), to nie jest prawdą aby \(\displaystyle{ x}\) był silnie mniejszy od każdego elementu zbioru \(\displaystyle{ A}\), a więc istnieje element \(\displaystyle{ a\in A}\) ,taki, że \(\displaystyle{ x\not< a}\), ponieważ porządek jest liniowy, więc wtedy \(\displaystyle{ a\le x}\), wtedy każdy element silnie mniejszy od \(\displaystyle{ x}\) należy do \(\displaystyle{ Z}\), a zatem z definicji tego zbioru jest silnie mniejszy od każdego elementu \(\displaystyle{ A}\), zatem nie może należeć do \(\displaystyle{ A}\). Zatem żaden element silnie mniejszy od \(\displaystyle{ x}\) nie należy do \(\displaystyle{ A}\), więc ponieważ \(\displaystyle{ a\le x}\), oraz \(\displaystyle{ a\in A}\), więc pozostaje możliwość \(\displaystyle{ a=x}\), a więc \(\displaystyle{ x\in A}\). Z tego samego powodu, w wersji takiej: że każdy element \(\displaystyle{ A}\) nie może być silnie mniejszy od \(\displaystyle{ x}\), i z faktu, że porządek jest liniowy, więc te elementy muszą być większe od \(\displaystyle{ x}\), więc otrzymujemy, że element \(\displaystyle{ x}\) jest elementem najmniejszym w \(\displaystyle{ A}\), co jest sprzeczne z założeniem, że w \(\displaystyle{ A}\) nie ma elementu najmniejszego. Wobec tego konieczne jest aby \(\displaystyle{ x\in Z.}\)

Pokazaliśmy, że zbiór \(\displaystyle{ Z}\) spełnia założenia zasady indukcji. Ponieważ zasada ta obowiązuje w \(\displaystyle{ X}\), to otrzymujemy \(\displaystyle{ Z=X}\)- sprzeczność.\(\displaystyle{ \square}\)

[Dasio11]

Niech \(\displaystyle{ (X, \le )}\) będzie zbiorem liniowo uporządkowanym. W \(\displaystyle{ (X, \le )}\) obowiązuje zasada indukcji, jeśli przede wszystkim istnieje element najmniejszy \(\displaystyle{ a\in X}\), oraz dla dowolnego zbioru \(\displaystyle{ Z\subset X}\), takiego, że

1. \(\displaystyle{ a\in Z}\).
2.dla dowolnego \(\displaystyle{ x\in X}\): jeśli \(\displaystyle{ O(x)\subset Z}\) (czyli \(\displaystyle{ \left\{ y\in X: \ \ y<x\right\}\subset Z}\)) to \(\displaystyle{ x\in Z,
}\)

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

Zazwyczaj zasadę indukcji formułuje się prościej:

Dla dowolnego zbioru \(\displaystyle{ Z \subseteq X}\) takiego, że

0. dla dowolnego \(\displaystyle{ x \in X}\), jeśli \(\displaystyle{ O(x) \subseteq Z}\), to \(\displaystyle{ x \in Z}\)

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

Nietrudno wykazać, że jest to sformułowanie równoważne.

\(\displaystyle{ \Longrightarrow}\) Przypuśćmy, że w \(\displaystyle{ X}\) zachodzi zasada indukcji. Aby pokazać, że \(\displaystyle{ X}\) jest dobrze uporządkowany, ustalmy dowolny niepusty podzbiór \(\displaystyle{ A\subset X.}\) Przypuśćmy dla dowodu nie wprost, że nie ma on elementu najmniejszego. Zdefiniujmy zbiór \(\displaystyle{ Z}\) jako zbiór tych elementów \(\displaystyle{ X}\) ,które są silnie mniejsze od wszystkich elementów z \(\displaystyle{ A}\), czyli

\(\displaystyle{ Z= \left\{ b\in X\Bigl| \ \ \bigwedge\limits_{a\in A} b<a \right\} .}\)

Ponieważ \(\displaystyle{ A \neq \left\{ \right\}}\), to \(\displaystyle{ Z \neq X.}\) Wtedy element najmniejszy \(\displaystyle{ z\in X}\), należy również do \(\displaystyle{ Z}\)( bo jest najmniejszy w całym \(\displaystyle{ X}\)). Pokażemy, że dla dowolnego \(\displaystyle{ x\in X}\), jeśli \(\displaystyle{ \left\{ y\in X: \ \ y<x\right\} \subset Z}\), to \(\displaystyle{ x\in Z}\). Niech \(\displaystyle{ x\in X}\). Przypuśćmy (dla dowodu nie wprost), że \(\displaystyle{ \left\{ y\in X: \ \ y<x\right\} \subset Z}\), oraz \(\displaystyle{ x\not\in Z}\). Ponieważ \(\displaystyle{ x\not\in Z}\), to nie jest prawdą aby \(\displaystyle{ x}\) był silnie mniejszy od każdego elementu zbioru \(\displaystyle{ A}\), a więc istnieje element \(\displaystyle{ a\in A}\) ,taki, że \(\displaystyle{ x\not< a}\), ponieważ porządek jest liniowy, więc wtedy \(\displaystyle{ a\le x}\), wtedy każdy element silnie mniejszy od \(\displaystyle{ x}\) należy do \(\displaystyle{ Z}\), a zatem z definicji tego zbioru jest silnie mniejszy od każdego elementu \(\displaystyle{ A}\), zatem nie może należeć do \(\displaystyle{ A}\). Zatem żaden element silnie mniejszy od \(\displaystyle{ x}\) nie należy do \(\displaystyle{ A}\), więc ponieważ \(\displaystyle{ a\le x}\), oraz \(\displaystyle{ a\in A}\), więc pozostaje możliwość \(\displaystyle{ a=x}\), a więc \(\displaystyle{ x\in A}\). Z tego samego powodu, w wersji takiej: że każdy element \(\displaystyle{ A}\) nie może być silnie mniejszy od \(\displaystyle{ x}\), i z faktu, że porządek jest liniowy, więc te elementy muszą być większe od \(\displaystyle{ x}\), więc otrzymujemy, że element \(\displaystyle{ x}\) jest elementem najmniejszym w \(\displaystyle{ A}\), co jest sprzeczne z założeniem, że w \(\displaystyle{ A}\) nie ma elementu najmniejszego. Wobec tego konieczne jest aby \(\displaystyle{ x\in Z.}\)

Pokazaliśmy, że zbiór \(\displaystyle{ Z}\) spełnia założenia zasady indukcji. Ponieważ zasada ta obowiązuje w \(\displaystyle{ X}\), to otrzymujemy \(\displaystyle{ Z=X}\)- sprzeczność.\(\displaystyle{ \square}\)

O wiele krócej: weźmy dowolny niepusty podzbiór \(\displaystyle{ A \subseteq X}\). Wtedy \(\displaystyle{ Z := X \setminus A \neq X}\), więc z zasady indukcji istnieje \(\displaystyle{ x \in X}\), taki że \(\displaystyle{ O(x) \subseteq Z}\) lecz \(\displaystyle{ x \notin Z}\). Znaczy to dokładnie tyle, że \(\displaystyle{ x \in A}\) i dla każdego \(\displaystyle{ y < x}\) jest \(\displaystyle{ y \notin A}\). Czyli: \(\displaystyle{ x}\) jest elementem najmniejszym w \(\displaystyle{ A}\).


Całą równoważność można łatwo zrozumieć, jeśli przeformułuje się zasadę indukcji podstawiając \(\displaystyle{ A := X \setminus Z}\):

Dla dowolnego zbioru \(\displaystyle{ A \subseteq X}\) takiego, że

0. dla każdego \(\displaystyle{ x \in X}\) jeśli \(\displaystyle{ x \in A}\), to \(\displaystyle{ O(x) \cap A \neq \varnothing}\)

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

To zaś w oczywisty sposób jest równoważne stwierdzeniu, że każdy niepusty podzbiór \(\displaystyle{ X}\) ma element najmniejszy.

[Jakub Gurak]

Podam teraz prosty przykład (ale chyba nie oczywisty) dowodu indukcyjnego względem dobrego porządku( nie na zbiorze liczb naturalnych, tylko ogólnie dla liczby porządkowej \(\displaystyle{ X}\)).

Niech \(\displaystyle{ \mathbb{X}}\) będzie niepustą liczbą porządkową von Neumanna. Zadajmy, ciekawe pytanie:

Jakie funkcję \(\displaystyle{ f:\mathbb{X} \rightarrow \mathbb{X}}\) spełniają

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

Polecenie ma sens, bo ponieważ \(\displaystyle{ \mathbb{X}}\) jest liczbą porządkową, więc każdy element zbioru \(\displaystyle{ \mathbb{X}}\) jest podzbiorem zbioru \(\displaystyle{ \mathbb{X},}\) więc możemy również liczyć obraz zbioru \(\displaystyle{ A\in\mathbb{X}}\) (wtedy \(\displaystyle{ A\subset\mathbb{X}}\))

Identyczność \(\displaystyle{ I_{\mathbb{X}}}\) to spełnia, aby to uzasadnić to zauważmy, że jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ I_{X} }\) funkcją identyczności na zbiorze \(\displaystyle{ X}\), to obrazem każdego zbioru \(\displaystyle{ A\subset X}\) jest ten sam zbiór. Jest to prosty fakt.

Jeśli więc, \(\displaystyle{ \mathbb{X}}\) jest niepustą liczbą porządkową von Neumanna:

\(\displaystyle{ I _{\mathbb{X}}:\mathbb{X} \rightarrow \mathbb{X}}\) , to jeśli \(\displaystyle{ A\in\mathbb{X}}\), to

\(\displaystyle{ I(A)=A}\) oczywiście, oraz
\(\displaystyle{ \stackrel{ \rightarrow }{I}\left( A\right) =A}\), gdyż to identyczność- na mocy przytoczonego faktu.

Zatem identyczność to spełnia. Pokażemy, że tylko identyczność to spełnia( niestety, ale za to podam prosty, choć ogólny, dowód indukcyjny, i , i to nie na zbiorze liczb naturalnych, ogólnie).

Zauważmy, że \(\displaystyle{ \mathbb{X}}\) jest dobrze uporządkowana przez inkluzję. I jest niepusta, więc zachodzi w niej zasada indukcji. Wtedy rzeczywiście możemy pominąć sprawdzanie czy warunek zachodzi dla elementu najmniejszego.

Aby wykazać, że tylko identyczność to spełnia, wykażemy, że dowolna funkcja \(\displaystyle{ f:\mathbb{X} \rightarrow \mathbb{X}}\), taka, że

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

jest równa \(\displaystyle{ f=I_{X}.}\)

Niech \(\displaystyle{ f:\mathbb{X} \rightarrow \mathbb{X} }\) będzie funkcją spełniająca równość (*).

Aby wykazać, że \(\displaystyle{ f=I_{X}}\), wykażemy, że dla każdego \(\displaystyle{ A\in\mathbb{X}}\) mamy \(\displaystyle{ f(A)=I(A)=A}\). W tym celu wykażemy, ze zbiór \(\displaystyle{ Y=\left\{ A\in\mathbb{X}: \ \ f(A)=I(A)\right\}}\) jest równy całemu zbiorowi \(\displaystyle{ \mathbb{X}}\). Wykażemy to indukcyjnie.

Niech \(\displaystyle{ A\in\mathbb{X}.}\) Przypuśćmy, że dla każdego \(\displaystyle{ B<A}\) (\(\displaystyle{ B\in A}\)) mamy \(\displaystyle{ f(B)=I(B)=B}\). Pokażemy, że \(\displaystyle{ f(A)=I(A)=A}\), czyli, że \(\displaystyle{ f(A)=A.}\)

Ponieważ \(\displaystyle{ f}\) spełnia równość (*), więc:

\(\displaystyle{ f(A)=\stackrel{ \rightarrow }{f}\left( A\right)=\left\{ f(x)\Bigl| \ \ x\in A\right\} =\left\{ f(B)=I(B)=B\Bigl| \ \ B\in A\right\} =A.}\)

Gdzie przedostatnia równość wynika z założenia indukcyjnego. A zatem \(\displaystyle{ f(A)=A.}\) \(\displaystyle{ \square }\)