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 $\displaystyle (A,\sqsubseteq )$ jest łańcuchowo zupełny, jeśli każdy łańcuch posiada supremum.

Definicja 3.2.

Dla posetu $\displaystyle (A,\sqsubseteq )$ funkcję $\displaystyle f$ przeprowadzającą $\displaystyle A$ w $\displaystyle A$ i taką, że $\displaystyle x\sqsubseteq f(x)$ dla dowolnego $\displaystyle x\in A$ 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 $\displaystyle (A,\sqsubseteq )$ i progresję $\displaystyle f$ operującą na nim. W dowodzie niezbędna jest koncepcja zbiorów, które nazwiemy "miłymi". Ustalmy dowolny element $\displaystyle a\in A$. Zbiór $\displaystyle B\subseteq A$ jest miły, jeśli spełnia wszystkie poniższe warunki:

• $\displaystyle a\in B$,
• jeśli $\displaystyle x\in B$ to również $\displaystyle f(x)\in B$ i
• jeśli $\displaystyle C\subseteq B$ jest łańcuchem w $\displaystyle (A,\sqsubseteq )$, to $\displaystyle \bigvee C\in B$.

Bardzo łatwo zauważyć, że przecięcie dowolnej rodziny miłych pozdbiorów jest miłe. Zdefiniujmy "najmilszy" podzbiór $\displaystyle B_{0}$ jako:

$\displaystyle B_{0}=\bigcap \{B\subseteq A\,|\,{\text{B jest miły}}\},$

wtedy $\displaystyle B_{0}$ jest oczywiście miły. Równocześnie $\displaystyle B_{0}$ jest podzbiorem każdego miłego zbioru. Wykażmy parę własności elementów zbioru $\displaystyle B_{0}$. Po pierwsze, żaden element istotnie mniejszy niż $\displaystyle a$ nie jest elementem $\displaystyle B_{0}$ - jest to oczywistą konsekwencją faktu, że zbiór $\displaystyle \{x\in A\,|\,x\geq a\}$ jest miły, więc jest nadzbiorem $\displaystyle B_{0}$.

Zdefiniujmy jeszcze mniejszy zbiór:

$\displaystyle B_{0}'=\{x\in B_{0}\,|\,\forall y\in B_{0}\;y\sqsubset x\implies f(y)\sqsubseteq x\}\subseteq B_{0}$

i wykażmy kilka faktów o elementach $\displaystyle B_{0}'$.

Lemat 3.1.

Jeśli $\displaystyle x\in B_{0}'$, to dla każdego $\displaystyle y\in B_{0}$ mamy $\displaystyle y\sqsubseteq x\lor f(x)\sqsubseteq y$.

Dowód

Ustalmy dowolny $\displaystyle x\in B_{0}'$ i zdefiniujmy zbiór:

$\displaystyle B_{x}=\{y\in B_{0}\,|\,y\sqsubseteq x\lor f(x)\sqsubseteq y\}.$

Wykażemy, że zbiór $\displaystyle B_{x}$ jest miły i, co za tym idzie, że $\displaystyle B_{x}=B_{0}$:

• $\displaystyle a\in B_{x}$, ponieważ wiemy, że $\displaystyle a\sqsubseteq x$ dla dowolnego $\displaystyle x\in B_{0}$,
• Załóżmy teraz, że $\displaystyle y\in B_{x}$ i wykażmy $\displaystyle f(y)\in B_{x}$. Jeśli $\displaystyle y\in B_{x}$ na mocy $\displaystyle f(x)\sqsubseteq y$, to niewątpliwie $\displaystyle f(x)\sqsubseteq f(y)$, co kończy ten przypadek. Jeśli natomiast $\displaystyle y\sqsubseteq x$, to albo $\displaystyle y=x$ i wtedy $\displaystyle f(x)\sqsubseteq f(y)$, albo $\displaystyle y\sqsubset x$ i wtedy, na mocy definicji $\displaystyle B_{0}'$, mamy $\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 $\displaystyle C\subseteq B_{x}$ jest łańcuchem i dla wszystkich $\displaystyle y\in C$ zachodzi $\displaystyle y\sqsubseteq x$, to również $\displaystyle \bigvee C\sqsubseteq x$ i $\displaystyle \bigvee C\in B_{x}$. Jeśli dla pewnego $\displaystyle y\in C$ mamy $\displaystyle f(x)\sqsubseteq y$, to również $\displaystyle f(x)\sqsubseteq \bigvee C$, co należało dowieść.

W kolejnym lemacie dowodzimy, że zbiory $\displaystyle B_{0}'$ i $\displaystyle B_{0}$ są równe:

Lemat 3.2.

Zbiór $\displaystyle B_{0}'$ jest miły.

Dowód

Wykażemy, że zbiór $\displaystyle B_{0}'$ jest miły, a więc:

• $\displaystyle a\in B_{0}'$, ponieważ wykazaliśmy wcześniej, że $\displaystyle y\sqsubset a$ nie zachodzi dla żadnego $\displaystyle y\in B_{0}$.
• Ustalmy $\displaystyle x\in B_{0}'$, żeby wykazać $\displaystyle f(x)\in B_{0}'$. Ustalmy $\displaystyle y\in B_{0}$ takie, że $\displaystyle y\sqsubset f(x)$. Na mocy Lematu 3.1 (patrz lemat 3.1.) dostajemy $\displaystyle y\sqsubseteq x\lor f(x)\sqsubseteq y$. Druga część alternatywy stoi w sprzeczności z założeniem, więc $\displaystyle y\sqsubseteq x$ i albo $\displaystyle y=x$, więc $\displaystyle f(y)\sqsubseteq f(x)$, albo $\displaystyle y\sqsubset x$ i na mocy założenia $\displaystyle f(y)\sqsubseteq x\sqsubseteq f(x)$, co należało pokazać.
• Ustalmy dowolny $\displaystyle C\subseteq B_{0}'$ łańcuch w $\displaystyle (A,\sqsubseteq )$. Załóżmy, że $\displaystyle y\sqsubset \bigvee C$. Jeśli dla jakiegoś $\displaystyle x\in C$ mamy $\displaystyle y\sqsubset x$, wtedy $\displaystyle f(y)\sqsubseteq x\sqsubseteq \bigvee C$, 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 $\displaystyle x\in C$ prawdziwe $\displaystyle x=y$ lub $\displaystyle x\sqsubseteq f(x)\sqsubseteq y$, co jest sprzeczne z założeniem mówiącym, że $\displaystyle y\sqsubset \bigvee C$.

Tak więc $\displaystyle B_{0}'=B_{0}$, czyli dla dowolnych $\displaystyle x$ i $\displaystyle y$ w $\displaystyle B_{0}$ mamy, na podstawie Lematu 3.1 (patrz lemat 3.1.), $\displaystyle y\sqsubseteq x$ lub $\displaystyle x\sqsubseteq f(x)\sqsubseteq y$. Wnioskujemy, że $\displaystyle B_{0}$ jest uporządkowany liniowo, czyli jest łańcuchem. Niewątpliwie $\displaystyle \bigvee B_{0}\in B_{0}$ (na podstawie definicji zbiorów miłych) i $\displaystyle f(\bigvee B_{0})\in B_{0}$ (na podstawie tej samej definicji), więc $\displaystyle f(\bigvee B_{0})=\bigvee B_{0}$, co dowodzi istnienia punktu stałego odwzorowania $\displaystyle f$.