Logika i teoria mnogości/Wykład 10.2: Różnice pomiędzy wersjami
Linia 1: | Linia 1: | ||
− | ==Twierdzenie | + | ==Twierdzenie Bourbakiego- Witta== |
− | Rozdział ten jest poświęcony twierdzeniu z którego będziemy korzystali w | + | Rozdział ten jest poświęcony twierdzeniu, z którego będziemy korzystali w Wykładzie 11, |
dotyczącym dyskusji nad aksjomatem wyboru. | dotyczącym dyskusji nad aksjomatem wyboru. | ||
− | Wprowadzamy podstawowe definicje | + | Wprowadzamy podstawowe definicje: |
{{definicja|3.1.|| | {{definicja|3.1.|| | ||
− | Mówimy, że poset <math>\displaystyle (A,\sqsubseteq)</math> jest ''łańcuchowo zupełny'' jeśli każdy | + | Mówimy, że poset <math>\displaystyle (A,\sqsubseteq)</math> jest ''łańcuchowo zupełny'', jeśli każdy |
łańcuch posiada supremum. | łańcuch posiada supremum. | ||
}} | }} | ||
Linia 14: | Linia 14: | ||
{{definicja|3.2.|| | {{definicja|3.2.|| | ||
− | Dla posetu <math>\displaystyle (A,\sqsubseteq)</math> funkcję <math>\displaystyle f</math> przeprowadzającą <math>\displaystyle A</math> w <math>\displaystyle A</math> i | + | Dla posetu <math>\displaystyle (A,\sqsubseteq)</math> funkcję <math>\displaystyle f</math> przeprowadzającą <math>\displaystyle A</math> w <math>\displaystyle A</math> i taką, że <math>\displaystyle x\sqsubseteq |
f(x)</math> dla dowolnego <math>\displaystyle x\in A</math> nazywamy ''progresją''. | f(x)</math> dla dowolnego <math>\displaystyle x\in A</math> nazywamy ''progresją''. | ||
}} | }} | ||
Linia 25: | Linia 25: | ||
Dowód: | Dowód: | ||
− | W czasie tego dowodu zostaną pokazane dodatkowo dwa | + | W czasie tego dowodu zostaną pokazane dodatkowo dwa Lematy 3.1 i 3.2 (patrz [[#lemat_3_1|lemat 3.1.]] i [[#lemat_3_2|lemat 3.2.]]). Są one częścią całego dowodu. |
Ustalmy łańcuchowo zupełny poset | Ustalmy łańcuchowo zupełny poset | ||
<math>\displaystyle (A,\sqsubseteq)</math> i progresję <math>\displaystyle f</math> operującą na nim. W dowodzie niezbędna jest | <math>\displaystyle (A,\sqsubseteq)</math> i progresję <math>\displaystyle f</math> operującą na nim. W dowodzie niezbędna jest | ||
koncepcja zbiorów, które nazwiemy "miłymi". Ustalmy dowolny element <math>\displaystyle a\in A</math>. Zbiór | koncepcja zbiorów, które nazwiemy "miłymi". Ustalmy dowolny element <math>\displaystyle a\in A</math>. Zbiór | ||
− | <math>\displaystyle B\subseteq A</math> jest miły jeśli spełnia wszystkie poniższe warunki: | + | <math>\displaystyle B\subseteq A</math> jest miły, jeśli spełnia wszystkie poniższe warunki: |
* <math>\displaystyle a\in B</math>, | * <math>\displaystyle a\in B</math>, | ||
* jeśli <math>\displaystyle x\in B</math> to również <math>\displaystyle f(x)\in B</math> i | * jeśli <math>\displaystyle x\in B</math> to również <math>\displaystyle f(x)\in B</math> i | ||
Linia 35: | Linia 35: | ||
Bardzo łatwo zauważyć, że przecięcie dowolnej rodziny miłych pozdbiorów jest miłe. | Bardzo łatwo zauważyć, że przecięcie dowolnej rodziny miłych pozdbiorów jest miłe. | ||
− | Zdefiniujmy "najmilszy" podzbiór <math>\displaystyle B_0</math> jako | + | Zdefiniujmy "najmilszy" podzbiór <math>\displaystyle B_0</math> jako: |
<center><math>\displaystyle B_0 = \bigcap\{B\subseteq A\,|\, \text{B jest miły}\}, | <center><math>\displaystyle B_0 = \bigcap\{B\subseteq A\,|\, \text{B jest miły}\}, | ||
Linia 41: | Linia 41: | ||
wtedy <math>\displaystyle B_0</math> jest oczywiście miły. Równocześnie <math>\displaystyle B_0</math> jest podzbiorem każdego miłego | wtedy <math>\displaystyle B_0</math> jest oczywiście miły. Równocześnie <math>\displaystyle B_0</math> jest podzbiorem każdego miłego | ||
− | zbioru. Wykażmy parę własności elementów zbioru <math>\displaystyle B_0</math>. Po pierwsze żaden element | + | zbioru. Wykażmy parę własności elementów zbioru <math>\displaystyle B_0</math>. Po pierwsze, żaden element |
istotnie mniejszy niż <math>\displaystyle a</math> nie jest elementem <math>\displaystyle B_0</math> - jest to oczywistą konsekwencją | istotnie mniejszy niż <math>\displaystyle a</math> nie jest elementem <math>\displaystyle B_0</math> - jest to oczywistą konsekwencją | ||
faktu, że zbiór <math>\displaystyle \{x\in A\,|\, x\geq a\}</math> jest miły, więc jest nadzbiorem <math>\displaystyle B_0</math>. | faktu, że zbiór <math>\displaystyle \{x\in A\,|\, x\geq a\}</math> jest miły, więc jest nadzbiorem <math>\displaystyle B_0</math>. | ||
− | Zdefiniujmy jeszcze mniejszy zbiór | + | Zdefiniujmy jeszcze mniejszy zbiór: |
<center><math>\displaystyle B_0' = \{x\in B_0\,|\, \forall y\in B_0\; y\sqsubset x \implies f(y)\sqsubseteq x\}\subseteq | <center><math>\displaystyle B_0' = \{x\in B_0\,|\, \forall y\in B_0\; y\sqsubset x \implies f(y)\sqsubseteq x\}\subseteq | ||
Linia 51: | Linia 51: | ||
</math></center> | </math></center> | ||
− | i wykażmy | + | i wykażmy kilka faktów o elementach <math>\displaystyle B_0'</math>. |
<span id="lemat_3_1">{{lemat|3.1.|| | <span id="lemat_3_1">{{lemat|3.1.|| | ||
− | Jeśli <math>\displaystyle x\in B_0'</math> to | + | Jeśli <math>\displaystyle x\in B_0'</math>, to dla każdego <math>\displaystyle y\in B_0</math> mamy <math>\displaystyle y\sqsubseteq x\lor f(x)\sqsubseteq y</math>. |
}}</span> | }}</span> | ||
{{dowod||| | {{dowod||| | ||
− | Ustalmy dowolny <math>\displaystyle x\in B_0'</math> i zdefiniujmy zbiór | + | Ustalmy dowolny <math>\displaystyle x\in B_0'</math> i zdefiniujmy zbiór: |
<center><math>\displaystyle B_x = \{y\in B_0\,|\, y\sqsubseteq x\lor f(x)\sqsubseteq y \}. | <center><math>\displaystyle B_x = \{y\in B_0\,|\, y\sqsubseteq x\lor f(x)\sqsubseteq y \}. | ||
</math></center> | </math></center> | ||
− | Wykażemy, że zbiór <math>\displaystyle B_x</math> jest miły i, co za tym idzie, że <math>\displaystyle B_x = B_0</math> | + | Wykażemy, że zbiór <math>\displaystyle B_x</math> jest miły i, co za tym idzie, że <math>\displaystyle B_x = B_0</math>: |
* <math>\displaystyle a\in B_x</math>, ponieważ wiemy, że <math>\displaystyle a\sqsubseteq x</math> dla dowolnego <math>\displaystyle x\in B_0</math>, | * <math>\displaystyle a\in B_x</math>, ponieważ wiemy, że <math>\displaystyle a\sqsubseteq x</math> dla dowolnego <math>\displaystyle x\in B_0</math>, | ||
− | * Załóżmy teraz, że <math>\displaystyle y\in B_x</math> i wykażmy <math>\displaystyle f(y)\in B_x</math>. Jeśli <math>\displaystyle y\in B_x</math> na mocy <math>\displaystyle f(x)\sqsubseteq y</math>, to niewątpliwie <math>\displaystyle f(x)\sqsubseteq f(y)</math> co kończy ten przypadek. Jeśli natomiast <math>\displaystyle y\sqsubseteq x</math>, to albo <math>\displaystyle y=x</math> i wtedy <math>\displaystyle f(x)\sqsubseteq f(y)</math>, albo <math>\displaystyle y\sqsubset x</math> i wtedy, na mocy definicji <math>\displaystyle B_0'</math> mamy <math>\displaystyle f(y)\sqsubseteq x</math> co dowodzi, że również w tym przypadku <math>\displaystyle f(y)\in B_x</math>. | + | * Załóżmy teraz, że <math>\displaystyle y\in B_x</math> i wykażmy <math>\displaystyle f(y)\in B_x</math>. Jeśli <math>\displaystyle y\in B_x</math> na mocy <math>\displaystyle f(x)\sqsubseteq y</math>, to niewątpliwie <math>\displaystyle f(x)\sqsubseteq f(y)</math>, co kończy ten przypadek. Jeśli natomiast <math>\displaystyle y\sqsubseteq x</math>, to albo <math>\displaystyle y=x</math> i wtedy <math>\displaystyle f(x)\sqsubseteq f(y)</math>, albo <math>\displaystyle y\sqsubset x</math> i wtedy, na mocy definicji <math>\displaystyle B_0'</math>, mamy <math>\displaystyle f(y)\sqsubseteq x</math>, co dowodzi, że również w tym przypadku <math>\displaystyle f(y)\in B_x</math>. |
− | * Jeśli <math>\displaystyle C\subseteq B_x</math> jest łańcuchem i dla wszystkich <math>\displaystyle y\in C</math> zachodzi <math>\displaystyle y\sqsubseteq x</math>, to również <math>\displaystyle \bigvee C\sqsubseteq x</math> i <math>\displaystyle \bigvee C\in B_x</math>. Jeśli dla pewnego <math>\displaystyle y\in C</math> mamy <math>\displaystyle f(x)\sqsubseteq y</math> to również <math>\displaystyle f(x)\sqsubseteq\bigvee C</math> co należało dowieść. | + | * Jeśli <math>\displaystyle C\subseteq B_x</math> jest łańcuchem i dla wszystkich <math>\displaystyle y\in C</math> zachodzi <math>\displaystyle y\sqsubseteq x</math>, to również <math>\displaystyle \bigvee C\sqsubseteq x</math> i <math>\displaystyle \bigvee C\in B_x</math>. Jeśli dla pewnego <math>\displaystyle y\in C</math> mamy <math>\displaystyle f(x)\sqsubseteq y</math>, to również <math>\displaystyle f(x)\sqsubseteq\bigvee C</math>, co należało dowieść. |
}} | }} | ||
− | W kolejnym lemacie dowodzimy, że zbiory <math>\displaystyle B_0'</math> i <math>\displaystyle B_0</math> są równe | + | W kolejnym lemacie dowodzimy, że zbiory <math>\displaystyle B_0'</math> i <math>\displaystyle B_0</math> są równe: |
<span id="lemat_3_2">{{lemat|3.2.|| | <span id="lemat_3_2">{{lemat|3.2.|| | ||
Linia 81: | Linia 81: | ||
{{dowod||| | {{dowod||| | ||
− | Wykażemy, że zbiór <math>\displaystyle B_0'</math> jest miły a więc | + | Wykażemy, że zbiór <math>\displaystyle B_0'</math> jest miły, a więc: |
* <math>\displaystyle a\in B_0'</math>, ponieważ wykazaliśmy wcześniej, że <math>\displaystyle y\sqsubset a</math> nie zachodzi dla żadnego <math>\displaystyle y\in B_0</math>. | * <math>\displaystyle a\in B_0'</math>, ponieważ wykazaliśmy wcześniej, że <math>\displaystyle y\sqsubset a</math> nie zachodzi dla żadnego <math>\displaystyle y\in B_0</math>. | ||
− | * Ustalmy <math>\displaystyle x\in B_0'</math>, żeby wykazać <math>\displaystyle f(x)\in B_0'</math> | + | * Ustalmy <math>\displaystyle x\in B_0'</math>, żeby wykazać <math>\displaystyle f(x)\in B_0'</math>. Ustalmy <math>\displaystyle y\in B_0</math> takie, że <math>\displaystyle y\sqsubset f(x)</math>. Na mocy Lematu 3.1 (patrz [[#lemat_3_1|lemat 3.1.]]) dostajemy <math>\displaystyle y\sqsubseteq x\lor f(x)\sqsubseteq y</math>. Druga część alternatywy stoi w sprzeczności z założeniem, więc <math>\displaystyle y\sqsubseteq x</math> i albo <math>\displaystyle y=x</math>, więc <math>\displaystyle f(y)\sqsubseteq f(x)</math>, albo <math>\displaystyle y\sqsubset x</math> i na mocy założenia <math>\displaystyle f(y)\sqsubseteq x\sqsubseteq f(x)</math>, co należało pokazać. |
− | * Ustalmy dowolny <math>\displaystyle C\subseteq B_0'</math> łańcuch w <math>\displaystyle (A,\sqsubseteq)</math>. Załóżmy, że <math>\displaystyle y\sqsubset \bigvee C</math>. Jeśli dla jakiegoś <math>\displaystyle x\in C</math> mamy <math>\displaystyle y\sqsubset x</math> wtedy <math>\displaystyle f(y)\sqsubseteq x\sqsubseteq \bigvee C</math>, co należało pokazać. Przeciwny przypadek jest niemożliwy na podstawie Lematu 3.1. (patrz [[#lemat_3_1|lemat 3.1.]]). Mielibyśmy wtedy dla każdego <math>\displaystyle x\in C</math> prawdziwe <math>\displaystyle x=y</math> lub <math>\displaystyle x\sqsubseteq f(x)\sqsubseteq y</math> co jest sprzeczne z założeniem mówiącym, że <math>\displaystyle y\sqsubset \bigvee C</math>. | + | * Ustalmy dowolny <math>\displaystyle C\subseteq B_0'</math> łańcuch w <math>\displaystyle (A,\sqsubseteq)</math>. Załóżmy, że <math>\displaystyle y\sqsubset \bigvee C</math>. Jeśli dla jakiegoś <math>\displaystyle x\in C</math> mamy <math>\displaystyle y\sqsubset x</math>, wtedy <math>\displaystyle f(y)\sqsubseteq x\sqsubseteq \bigvee C</math>, co należało pokazać. Przeciwny przypadek jest niemożliwy na podstawie Lematu 3.1. (patrz [[#lemat_3_1|lemat 3.1.]]). Mielibyśmy wtedy dla każdego <math>\displaystyle x\in C</math> prawdziwe <math>\displaystyle x=y</math> lub <math>\displaystyle x\sqsubseteq f(x)\sqsubseteq y</math>, co jest sprzeczne z założeniem mówiącym, że <math>\displaystyle y\sqsubset \bigvee C</math>. |
}} | }} | ||
Tak więc <math>\displaystyle B_0' = B_0</math>, czyli dla dowolnych <math>\displaystyle x</math> i <math>\displaystyle y</math> w <math>\displaystyle B_0</math> mamy, na podstawie | Tak więc <math>\displaystyle B_0' = B_0</math>, czyli dla dowolnych <math>\displaystyle x</math> i <math>\displaystyle y</math> w <math>\displaystyle B_0</math> mamy, na podstawie | ||
Lematu 3.1 (patrz [[#lemat_3_1|lemat 3.1.]]), <math>\displaystyle y\sqsubseteq x</math> lub <math>\displaystyle x\sqsubseteq f(x)\sqsubseteq y</math>. Wnioskujemy, że <math>\displaystyle B_0</math> jest | Lematu 3.1 (patrz [[#lemat_3_1|lemat 3.1.]]), <math>\displaystyle y\sqsubseteq x</math> lub <math>\displaystyle x\sqsubseteq f(x)\sqsubseteq y</math>. Wnioskujemy, że <math>\displaystyle B_0</math> jest | ||
− | uporządkowany liniowo, czyli jest łańcuchem. | + | uporządkowany liniowo, czyli jest łańcuchem. Niewątpliwie <math>\displaystyle \bigvee B_0 \in B_0</math> (na |
podstawie definicji zbiorów miłych) i <math>\displaystyle f(\bigvee B_0)\in B_0</math> (na podstawie tej samej | podstawie definicji zbiorów miłych) i <math>\displaystyle f(\bigvee B_0)\in B_0</math> (na podstawie tej samej | ||
− | definicji), więc <math>\displaystyle f(\bigvee B_0) = \bigvee B_0</math> co dowodzi istnienia punktu stałego | + | definicji), więc <math>\displaystyle f(\bigvee B_0) = \bigvee B_0</math>, co dowodzi istnienia punktu stałego |
odwzorowania <math>\displaystyle f</math>. | odwzorowania <math>\displaystyle f</math>. |
Aktualna wersja na dzień 19:56, 17 wrz 2006
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 , co kończy ten przypadek. Jeśli natomiast , to albo i wtedy , albo i wtedy, na mocy definicji , mamy , co dowodzi, że również w tym przypadku .
- 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 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ć. , żeby wykazać . Ustalmy takie, że . Na mocy Lematu 3.1 (patrz
- Ustalmy dowolny lemat 3.1.). Mielibyśmy wtedy dla każdego prawdziwe lub , co jest sprzeczne z założeniem mówiącym, że . ł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

Tak więc 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 .
, czyli dla dowolnych i w mamy, na podstawie Lematu 3.1 (patrz