Logika i teoria mnogości/Wykład 10.2

From Studia Informatyczne

[Edytuj]

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 \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ść.
image:End_of_proof.gif

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.
image:End_of_proof.gif

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.

Źródło: "http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogo%C5%9Bci/Wyk%C5%82ad_10.2"