Logika i teoria mnogości/Wykład 10.2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
Linia 1: Linia 1:
==Twierdzenie Bourbaki- Witt==
+
==Twierdzenie Bourbakiego- Witta==
  
Rozdział ten jest poświęcony twierdzeniu z którego będziemy korzystali w wykładzie 11
+
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 taka, że <math>\displaystyle x\sqsubseteq
+
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 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.
+
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 parę faktów o elementach <math>\displaystyle B_0'</math>.
+
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, dla każdego <math>\displaystyle y\in B_0</math> mamy <math>\displaystyle y\sqsubseteq x\lor f(x)\sqsubseteq y</math>.
+
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 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 <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. Niewątplwie <math>\displaystyle \bigvee B_0 \in B_0</math>&nbsp;(na
+
uporządkowany liniowo, czyli jest łańcuchem. Niewątpliwie <math>\displaystyle \bigvee B_0 \in B_0</math>&nbsp;(na
 
podstawie definicji zbiorów miłych) i <math>\displaystyle f(\bigvee B_0)\in B_0</math>&nbsp;(na podstawie tej samej
 
podstawie definicji zbiorów miłych) i <math>\displaystyle f(\bigvee B_0)\in B_0</math>&nbsp;(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ść.
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 .