Logika i teoria mnogości/Wykład 10.2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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ść.
End of proof.gif

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 .
End of proof.gif

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 .