Logika i teoria mnogości/Wykład 10.2
Twierdzenie Bourbakiego- Witta
Rozdział ten jest poświęcony twierdzeniu, z którego będziemy korzystali w Wykładzie 11, dotyczącym dyskusji nad aksjomatem wyboru.
Wprowadzamy podstawowe definicje:
Definicja 3.1.
Mówimy, że poset jest łańcuchowo zupełny, jeśli każdy łańcuch posiada supremum.
Definicja 3.2.
Dla posetu funkcję przeprowadzającą w i taką, że dla dowolnego nazywamy progresją.
Twierdzenie 3.3. [Bourbaki-Witt]
Każda progresja na łańcuchowo zupełnym posecie posiada punkt stały.
Dowód:
W czasie tego dowodu zostaną pokazane dodatkowo dwa Lematy 3.1 i 3.2 (patrz lemat 3.1. i lemat 3.2.). Są one częścią całego dowodu. Ustalmy łańcuchowo zupełny poset i progresję operującą na nim. W dowodzie niezbędna jest koncepcja zbiorów, które nazwiemy "miłymi". Ustalmy dowolny element . Zbiór jest miły, jeśli spełnia wszystkie poniższe warunki:
- ,
- jeśli to również i
- jeśli jest łańcuchem w , to .
Bardzo łatwo zauważyć, że przecięcie dowolnej rodziny miłych pozdbiorów jest miłe. Zdefiniujmy "najmilszy" podzbiór jako:
wtedy jest oczywiście miły. Równocześnie jest podzbiorem każdego miłego zbioru. Wykażmy parę własności elementów zbioru . Po pierwsze, żaden element istotnie mniejszy niż nie jest elementem - jest to oczywistą konsekwencją faktu, że zbiór jest miły, więc jest nadzbiorem .
Zdefiniujmy jeszcze mniejszy zbiór:
i wykażmy kilka faktów o elementach .
Lemat 3.1.
Jeśli , to dla każdego mamy .
Dowód
Ustalmy dowolny i zdefiniujmy zbiór:
Wykażemy, że zbiór jest miły i, co za tym idzie, że :
- , ponieważ wiemy, że dla dowolnego ,
- Załóżmy teraz, że i wykażmy . Jeśli na mocy , to niewątpliwie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle f(x)\sqsubseteq f(y)} , co kończy ten przypadek. Jeśli natomiast Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle y\sqsubseteq x} , to albo Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle y=x} i wtedy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle f(x)\sqsubseteq f(y)} , albo Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle y\sqsubset x} i wtedy, na mocy definicji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle B_0'} , mamy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle f(y)\sqsubseteq x} , co dowodzi, że również w tym przypadku Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle f(y)\in B_x} .
- Jeśli jest łańcuchem i dla wszystkich zachodzi , to również i . Jeśli dla pewnego mamy , to również , co należało dowieść.

W kolejnym lemacie dowodzimy, że zbiory i są równe:
Lemat 3.2.
Zbiór jest miły.
Dowód
Wykażemy, że zbiór jest miły, a więc:
- , ponieważ wykazaliśmy wcześniej, że nie zachodzi dla żadnego .
- Ustalmy , żeby wykazać . Ustalmy takie, że . Na mocy Lematu 3.1 (patrz lemat 3.1.) dostajemy . Druga część alternatywy stoi w sprzeczności z założeniem, więc i albo , więc , albo i na mocy założenia , co należało pokazać.
- Ustalmy dowolny łańcuch w . Załóżmy, że . Jeśli dla jakiegoś mamy , wtedy , co należało pokazać. Przeciwny przypadek jest niemożliwy na podstawie Lematu 3.1. (patrz lemat 3.1.). Mielibyśmy wtedy dla każdego prawdziwe lub , co jest sprzeczne z założeniem mówiącym, że .

Tak więc , czyli dla dowolnych i w mamy, na podstawie Lematu 3.1 (patrz lemat 3.1.), lub . Wnioskujemy, że jest uporządkowany liniowo, czyli jest łańcuchem. Niewątpliwie (na podstawie definicji zbiorów miłych) i (na podstawie tej samej definicji), więc , co dowodzi istnienia punktu stałego odwzorowania .