porządki liniowe gęste

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

porządki liniowe gęste

Post autor: Zordon »

Zapraszam wszystkich ambitnych do zmierzenia się z takim zadaniem :
Pokazać, że dowolne dwa zbiory przeliczalne uporządkowane gęstymi relacjami porządku bez końców są izomorficzne.
Porządek gęsty: \(\displaystyle{ \forall_{x,y}(x<y \Rightarrow (\exists_z x<z<y))}\)
bez końców: \(\displaystyle{ \forall_{x}(\exists_{y,z} y<x<z)}\)
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

porządki liniowe gęste

Post autor: Jan Kraszewski »

I bez zaglądania do podręczników (bo to fakt klasyczny...)

JK
Tomasz Tkaczyk
Użytkownik
Użytkownik
Posty: 476
Rejestracja: 20 cze 2008, o 21:34
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 8 razy
Pomógł: 93 razy

porządki liniowe gęste

Post autor: Tomasz Tkaczyk »

Niech \(\displaystyle{ A, B}\) będą przeliczalnymi liniowymi gęstymi porządkami bez końców.

Niech \(\displaystyle{ A = \lbrace a_{n}: n< \omega \rbrace}\),

Niech \(\displaystyle{ B = \lbrace b_{n}: n < \omega \rbrace}\).

Niech \(\displaystyle{ A_{n} = \lbrace a_{i}: i \le n \rbrace}\).

Niech \(\displaystyle{ B_{n} = \lbrace b_{i}: i \le n \rbrace}\).

Załóżmy ponadto, że \(\displaystyle{ a_{0} < a_{1}}\), \(\displaystyle{ b_{0} < b_{1}}\).

Stworzymy indukcyjnie rosnący ciąg funkcji \(\displaystyle{ f_{n}: A_{n} \rightarrow B_{n}}\).

Niech \(\displaystyle{ f_{0}(a_{0}) = b_{0}}\) i \(\displaystyle{ f_{1}(a_{1}) = b_{1}}\), oraz

\(\displaystyle{ f_{0} \subset f_{1}}\).

Krok indukcyjny.

Załóżmy, że mamy zdefiniowane funkcje \(\displaystyle{ f_{0}, f_{1}, ..., f_{2n}, f_{2n + 1}}\) tak, że

\(\displaystyle{ f_{i-1} \subset f_{i}, f_{i}: A_{i} \rightarrow B_{i}}\) dla \(\displaystyle{ i \le 2n+1}\).

Zdefiniujemy funkcje \(\displaystyle{ f_{2n+2}, f_{2n+3}}\).

Niech \(\displaystyle{ f_{2n+1} \subset f_{2n+2}}\), oraz określmy

\(\displaystyle{ f_{2n+2}(a_{t}) = b_{k}}\), gdzie \(\displaystyle{ t}\) jest najmniejsze takie, że \(\displaystyle{ a_{t}}\) nie jest w dziedzinie funkcji \(\displaystyle{ f_{2n+1}}\) i \(\displaystyle{ k}\) jest takie, aby \(\displaystyle{ f_{2n+2}}\) była rosnąca. Można takie \(\displaystyle{ k}\) znaleźć, bo porządek \(\displaystyle{ B}\) jest gęsty.

Niech \(\displaystyle{ m}\) będzie najmniejsze takie, że nie istnieje \(\displaystyle{ l \le 2n+2}\) takie, że \(\displaystyle{ b_{m} \in f_{l}(A_{l})}\).

Niech \(\displaystyle{ f_{2n+2} \subset f_{2n+3}}\).
Określmy \(\displaystyle{ f_{2n+3}(a_{j}) = b_{m}}\), gdzie \(\displaystyle{ j}\) jest takie, aby \(\displaystyle{ f_{2n+3}}\) była rosnąca. Można takie \(\displaystyle{ j}\) znaleźć, bo porządek \(\displaystyle{ A}\) jest gęsty.

Tak zdefiniowany jest rosnący ciąg funkcji \(\displaystyle{ (f_{n})_{n < \omega}}\).

Niech \(\displaystyle{ f = \bigcup_{n < \omega} f_{n}}\).

\(\displaystyle{ f: A \rightarrow B}\) i jest "na", bo konstrukcja była przeprowadzona tak, aby nie ominąć żadnego \(\displaystyle{ b_{n}}\).

Dla każdego \(\displaystyle{ n < \omega}\), \(\displaystyle{ f_{n}}\) jest rosnąca.

Zatem \(\displaystyle{ f}\) jest rosnąca. Jest też różnowartościowa, bo w krokach nieparzystych dobieraliśmy takie \(\displaystyle{ b_{m}}\), które nigdy wcześniej nie wystąpiło.

Zatem \(\displaystyle{ f}\) jest izomorfizmem porządków \(\displaystyle{ A, B}\).
krl
Użytkownik
Użytkownik
Posty: 609
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 135 razy

porządki liniowe gęste

Post autor: krl »

To może ja zaproponuję trochę trudniejszy wariant tego zadania. Mówimy, że porządek liniowy jest \(\displaystyle{ \omega_1}\)-like, gdy jest nieprzeliczalny i każdy jego właściwy odcinek początkowy jest przeliczalny. Widać więc, że każdy porządek liniowy, który jest \(\displaystyle{ \omega_1}\)-like, jest mocy \(\displaystyle{ \aleph_1}\) i w ogóle jest dość podobny do \(\displaystyle{ \omega_1}\) (stąd nazwa).
Zadanie:
Skonstruować dwa nieizomorficzne gęste porządki porządki liniowe bez końców, które są \(\displaystyle{ \omega_1}\)-like.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

porządki liniowe gęste

Post autor: Dasio11 »

Rozwiązanie:    
Fajne zadanie.
krl
Użytkownik
Użytkownik
Posty: 609
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 135 razy

porządki liniowe gęste

Post autor: krl »

Nieskończoność pobudza wyobraźnię ludzi. Ale dopiero w matematyce można odkrywać jej zdumiewające aspekty. Powyższe zadanie dotyczy jednego z takich aspektów, który związany jest ze specyficzną strukturą liczb porządkowych.

Wersja hardkorowa: zbudować \(\displaystyle{ 2^{\aleph_1}}\) takich nieizomorficznych porządków.

Wskazówka:
Ukryta treść:    
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

porządki liniowe gęste

Post autor: Dasio11 »

Rozwiązanie:    
W zasadzie to samo plus parę sztuczek na zbiorach stacjonarnych. :p
krl
Użytkownik
Użytkownik
Posty: 609
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 135 razy

porządki liniowe gęste

Post autor: krl »

Tak, w zasadzie to samo. Ale w zadaniu chodzi o to, że te sztuczki prowadzą właśnie do pojęcia zbioru stacjonarnego. Inaczej: pokazują, jak to pojęcie wyraża określoną własność nieskonczoności. Dalsze uogólnienie: każda teoria niestabilna ma \(\displaystyle{ 2^{\aleph_1}}\) modeli mocy \(\displaystyle{ \aleph_1}\).
(Wskazówka: To już jest teoria modeli. Teoria niestabilna ma formułę z własnością porządkową. W pewnym sensie w jej modelach można zakodować w rozmyty sposób nieizomorficzne porządki.)
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

porządki liniowe gęste

Post autor: Dasio11 »

No, Panie Profesorze, to mi Pan zabił klina. Muszę się chwilę zastanowić.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

porządki liniowe gęste

Post autor: Jakub Gurak »

Zordon pisze:Zapraszam wszystkich ambitnych do zmierzenia się z takim zadaniem :
Pokazać, że dowolne dwa zbiory przeliczalne uporządkowane gęstymi relacjami porządku bez końców są izomorficzne.
Nie jestem zainteresowany, gdyż to twierdzenie nie jest dla mnie zaskakujące- tu jest dużo założeń, więc to nie dziwne jak dla mnie (a jedno twierdzenie teorii mnogości mogę mieć bez dowodu). Równoważna postać tego twierdzenia, to że dowolny zbiór liniowo uporządkowany, nieskończony, przeliczalny, gęsty, bez końców (bez elementu najmniejszego i największego) jest podobny (izomorficzny- nie lubię tego słowa ) do zbioru liczb wymiernych z naturalnym porządkiem ( \(\displaystyle{ \Longrightarrow}\) zbiór liczb wymiernych spełnia te założenia.\(\displaystyle{ \Longleftarrow}\) na podobnej zasadzie + przechodniość podobieństwa ).

Natomiast chciałbym zastosować to twierdzenie, aby udowodnić ciekawy fakt odnośnie dowolnego zbioru liniowo uporządkowanego, co najwyżej przeliczalnego. Otóż ten fakt mówi, że taki dowolny ustalony zbiór liniowo uporządkowany jest podobny do pewnego podzbioru zbioru liczb wymiernych (z naturalnym porządkiem na tych liczbach wymiernych).

Dowód:

Niech \(\displaystyle{ \left( X, \le \right)}\) będzie dowolnym zbiorem liniowo uporządkowanym, co najwyżej przeliczalnym. Jeśli \(\displaystyle{ X}\) jest zbiorem skończonym, i ma \(\displaystyle{ n}\) elementów, to \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \left\{ 1,2,\ldots, n\right\}}\), i dowód jest zakończony. Pozostaje założyć, że zbiór \(\displaystyle{ X}\) jest nieskończony. Będziemy chcieli zastosować to twierdzenie (w równoważnej drugiej wersji ) do \(\displaystyle{ \left( X \times \QQ, \le _{l} \right),}\) gdzie \(\displaystyle{ \le _{l}}\) jest porządkiem leksykograficznym danego porządku \(\displaystyle{ \le}\) na \(\displaystyle{ X}\), i naturalnego porządku na zbiorze liczb wymiernych .

Ponieważ \(\displaystyle{ X}\) jest równoliczny z \(\displaystyle{ \NN,}\) I \(\displaystyle{ \QQ}\) jest równolicznym z \(\displaystyle{ \NN}\), to również ich iloczyn kartezjański \(\displaystyle{ X \times \QQ}\) jest równoliczny z \(\displaystyle{ \NN.}\) Ponieważ zbiór \(\displaystyle{ X}\) jest uporządkowany liniowo przez \(\displaystyle{ \le,}\) i zbiór liczb wymiernych jest uporządkowany liniowo przez naturalny porządek, więc ich porządek leksykograficzny jest liniowy. Pokażemy teraz, że ten porządek leksykograficzny jest gęsty. Weźmy dwie pary \(\displaystyle{ \left( x _{1}, a_{1} \right);\left( x_{2},a_{2} \right)}\) z \(\displaystyle{ X\times \QQ,}\), takie, że \(\displaystyle{ \left( x _{1},a _{1} \right) <_{l}\left( x _{2},a _{2} \right).}\) Rozważmy dwa przypadki:\(\displaystyle{ x _{1} \neq x _{2}.}\) W takim wypadku z definicji porządku leksykograficznego dostajemy \(\displaystyle{ x _{1}<x _{2}.}\) Ponieważ \(\displaystyle{ a _{1}+1 \in \QQ,}\) więc \(\displaystyle{ \left( x _{1},a_{1}\right) <_{l}\left( x_{1}, a_{1}+1 \right) <_{l} \left( x _{2},a _{2} \right)}\) (z definicji porządku leksykograficznego), co oznacza, że pomiędzy parami \(\displaystyle{ \left( x _{1},a _{1} \right);\left( x _{2},a _{2} \right)}\) jest para pośrednia. W pozostałym przypadku \(\displaystyle{ x _{1}=x _{2},}\) oznaczmy ten element jako \(\displaystyle{ x.}\) Wtedy z definicji porządku leksykograficznego \(\displaystyle{ a _{1}<_{Q} a _{2}.}\) Ponieważ \(\displaystyle{ \le _{Q}}\) jest porządkiem gęstym, więc istnieje \(\displaystyle{ a _{3} \in \QQ,}\) spełniające \(\displaystyle{ a _{1}<_{\QQ} a _{3}<_{\QQ} a _{2},}\) skąd \(\displaystyle{ \left( x,a_{1} \right) < _{l}\left( x,a _{3} \right)< _{l}\left( x,a _{2} \right),}\) czyli również pomiędzy parami \(\displaystyle{ \left( x _{1},a _{1} \right);\left( x_{2},a _{2} \right)}\) jest para pośrednia. A więc porządek \(\displaystyle{ \le _{l}}\) jest gęsty. Pozostało sprawdzić, że w \(\displaystyle{ \left( X\times \QQ, \le _{l} \right)}\) nie ma elementu najmniejszego ani największego. Aby pokazać ostatnie, ustalmy dowolną parę \(\displaystyle{ \left( x, n \right) \in X \times \QQ.}\) Nie może ona być elementem największym, bo możemy do niej dobrać parę \(\displaystyle{ \left( x, n+1\right) \in X \times \QQ,}\) gdzie \(\displaystyle{ \left( x,n\right)< _{l}\left( x,n+1\right).}\) Więc nie ma tu elementu największego, w sposób podobny można sprawdzić, że nie ma tu elementu najmniejszego.

Wobec czego spełnione są wszystkie założenia naszego twierdzenia, i w związku z czym \(\displaystyle{ \left( X \times Q, \le _{l} \right)}\) jest podobny do zbioru \(\displaystyle{ \left( Q, \le _{Q}\right)}\) . Oczywiście \(\displaystyle{ \left( X \times \left\{ 0\right\}, \le _{l}\right)}\) jest podobny do \(\displaystyle{ \left( X, \le \right).}\) Ponieważ \(\displaystyle{ \left( X \times \QQ, \le _{l}\right)}\) jest podobny do \(\displaystyle{ \left( \QQ, \le _{Q} \right),}\) więc jego podzbiór \(\displaystyle{ X \times \left\{ 0\right\}}\) jest podobny do obrazu tego zbioru przez podobieństwo( chyba tak, ale coś pewny nie jestem ), czyli do zbioru \(\displaystyle{ A \subset \QQ}\), z naturalnym porządkiem \(\displaystyle{ \le _{A}}\) na liczbach wymiernych, z przechodniości podobieństwa \(\displaystyle{ \left( X, \le \right)}\) jest podobny do \(\displaystyle{ \left( A, \le _{A} \right).\square}\) Dobrze

Można też łatwo udowodnić( też używając twierdzenia z tego tematu), że suma porządkowa dwóch zbiorów liniowo uporządkowanych podobnych do zbioru liczb wymiernych z naturalnym porządkiem jest dalej podobna do \(\displaystyle{ \QQ.}\)
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: porządki liniowe gęste

Post autor: Jakub Gurak »

Udowodniłem wczoraj, że każdy zbiór liniowo uporządkowany gęsty \(\displaystyle{ (X, \le )}\), który ma co najmniej dwa elementy jest nieskończony. Lubię udowadniać takie proste ogólne fakty. :lol:
Dowód:    
Spotkałem w książce takie nawet ciekawe zadanie, z którym mam problem:
Wykazać, że każdy zbiór liniowy uporządkowany gęsty (nieskończony) zawiera podzbiór podobny do zbioru liczb wymiernych z naturalnym porządkiem. Jak to udowodnić??
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: porządki liniowe gęste

Post autor: a4karo »

Skonstruować go
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: porządki liniowe gęste

Post autor: Jakub Gurak »

Tylko jak :?: , poproszę wskazówkę.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: porządki liniowe gęste

Post autor: a4karo »

Pewnie gdybyś czytał coś więcej niż Ważniaka, to poznałbyś tego typu konstrukcje

\(\displaystyle{ \QQ= \bigcup_{}^{} \frac1n \ZZ}\)
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: porządki liniowe gęste

Post autor: Dasio11 »

Ustaw liczby wymierne w ciąg \(\displaystyle{ \QQ = \{ q_n : n \in \NN \}}\), weź elementy \(\displaystyle{ a < b}\) z docelowego porządku i określaj rekurencyjnie włożenia \(\displaystyle{ f_n : \{ q_1, \ldots, q_n \} \to (a, b)}\).
ODPOWIEDZ