Logika i teoria mnogości/Wykład 10.2

Twierdzenie Bourbaki- Witt

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

Definicja 3.2.

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

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

Bardzo łatwo zauważyć, że przecięcie dowolnej rodziny miłych pozdbiorów jest miłe. Zdefiniujmy "najmilszy" podzbiór $B_0$ jako

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

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

Zdefiniujmy jeszcze mniejszy zbiór

${B_0}^{\prime }=\{x\in B_0|\mathrm{\forall }y\in B_{0}y⊏x⟹f(y)⊑x\}\subseteq B_0$

i wykażmy parę faktów o elementach ${B_0}^{\prime }$.

Lemat 3.1.

Jeśli $x\in {B_0}^{\prime }$ to, dla każdego $y\in B_0$ mamy $y⊑x\vee f(x)⊑y$.

Dowód

Ustalmy dowolny $x\in {B_0}^{\prime }$ i zdefiniujmy zbiór

$B_x=\{y\in B_0|y⊑x\vee f(x)⊑y\}.$

Wykażemy, że zbiór $B_x$ jest miły i, co za tym idzie, że $B_x=B_0$.

• $a\in B_x$, ponieważ wiemy, że $a⊑x$ dla dowolnego $x\in B_0$,
• Załóżmy teraz, że $y\in B_x$ i wykażmy $f(y)\in B_x$. Jeśli $y\in B_x$ na mocy $f(x)⊑y$, to niewątpliwie $f(x)⊑f(y)$ co kończy ten przypadek. Jeśli natomiast $y⊑x$, to albo $y=x$ i wtedy $f(x)⊑f(y)$, albo $y⊏x$ i wtedy, na mocy definicji ${B_0}^{\prime }$ mamy $f(y)⊑x$ co dowodzi, że również w tym przypadku $f(y)\in B_x$.
• Jeśli $C\subseteq B_x$ jest łańcuchem i dla wszystkich $y\in C$ zachodzi $y⊑x$, to również $\bigvee C⊑x$ i $\bigvee C\in B_x$. Jeśli dla pewnego $y\in C$ mamy $f(x)⊑y$ to również $f(x)⊑\bigvee C$ co należało dowieść.

W kolejnym lemacie dowodzimy, że zbiory ${B_0}^{\prime }$ i $B_0$ są równe

Lemat 3.2.

Zbiór ${B_0}^{\prime }$ jest miły.

Dowód

Wykażemy, że zbiór ${B_0}^{\prime }$ jest miły a więc

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

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