Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://matematyka.pl/
Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję
Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję
: 15 sty 2022, o 19:21
autor: Jakub Gurak
Muszę o to w końcu spytać, bo w dowodach to się przydaje, a coś nie jestem pewien czy mogę w taki właśnie sposób z tego korzystać:
Mamy fakt, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ Y\subset X}\) podzbiorem, to zbiór \(\displaystyle{ Y}\) jest liniowo uporządkowany (przez porządek \(\displaystyle{ \le}\) zawężony do zbioru \(\displaystyle{ Y}\)).
No i mam pytanie, bo w dowodach z tego korzystam, a coś nie jestem pewien czy tak mi wolno. Pytanie, czy mamy równoważność, (zachowując oznaczenia, i porządek na zbiorze \(\displaystyle{ Y}\) oznaczając jako \(\displaystyle{ \le _{Y}}\)), to pytanie czy mamy równoważność zawsze prawdziwą:
\(\displaystyle{ x \le _{Y} y \Longleftrightarrow x \le y \wedge x,y \in Y}\)
Chciałbym się upewnić czy w ten sposób mogę z tego korzystać. W dowodach to się przydaje, a coś nie jestem pewny czy można tak. Jest dobrze
I jeszcze pytanie, bo mamy twierdzenie, że podzbiór zbioru uporządkowanego (niekoniecznie liniowo) jest uporządkowany.
Pytanie: jak zinterpretować to (ten porządek na podzbiorze ) na diagramie Hassego ? Czy to jest ten sam dany diagram na nadzbiorze tylko ograniczony do elementów tego podzbioru Jak to się interpretuje??
Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję
: 15 sty 2022, o 19:43
autor: Jan Kraszewski
Jakub Gurak pisze: ↑15 sty 2022, o 19:21
No i mam pytanie, bo w dowodach z tego korzystam, a coś nie jestem pewien czy tak mi wolno. Pytanie, czy mamy równoważność, (zachowując oznaczenia, i porządek na zbiorze \(\displaystyle{ Y}\) oznaczając jako \(\displaystyle{ \le _{Y}}\)), to pytanie czy mamy równoważność zawsze prawdziwą:
\(\displaystyle{ x \le _{Y} y \Longleftrightarrow x \le y \wedge x,y \in Y}\)
No skoro masz taką wątpliwość, to naturalnym byłoby spróbować dowieść prawdziwość tej równoważności. Próbowałeś?
Jakub Gurak pisze: ↑15 sty 2022, o 19:21Pytanie: jak zinterpretować to (ten porządek na podzbiorze ) na diagramie Hassego ? Czy to jest ten sam dany diagram na nadzbiorze tylko ograniczony do elementów tego podzbioru
Co to znaczy "ten sam dany diagram na nadzbiorze tylko ograniczony do elementów tego podzbioru"? Czy jeśli weźmiesz diagram zbioru uporządkowanego \(\displaystyle{ \left\langle \{1,2,3\},\le\right\rangle }\) i rozważasz ten sam porządek na podzbiorze \(\displaystyle{ \{1,3\}}\), to czy to jest "ten sam dany diagram na nadzbiorze tylko ograniczony do elementów tego podzbioru"?
Jakub Gurak pisze: ↑15 sty 2022, o 19:21Jak to się interpretuje??
JK
Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję
: 16 sty 2022, o 19:40
autor: Jakub Gurak
Jakub Gurak pisze: ↑15 sty 2022, o 19:21\(\displaystyle{ }\)
No i mam pytanie, bo w dowodach z tego korzystam, a coś nie jestem pewien czy tak mi wolno. Pytanie, czy mamy równoważność, (zachowując oznaczenia, i porządek na zbiorze \(\displaystyle{ Y}\) oznaczając jako \(\displaystyle{ \le _{Y}}\)), to pytanie czy mamy równoważność zawsze prawdziwą:
\(\displaystyle{ x \le _{Y} y \Longleftrightarrow x \le y \wedge x,y \in Y}\) ??
Jan Kraszewski pisze: ↑15 sty 2022, o 19:43
No skoro masz taką wątpliwość, to naturalnym byłoby spróbować dowieść prawdziwość tej równoważności. Próbowałeś?
Wczoraj się chwilę zastanowiłem, wychodzi na to, że ta równoważność będzie zachodzić, racja Proszę o odpowiedź.
jeszcze pytanie, bo mamy twierdzenie, że podzbiór zbioru uporządkowanego (niekoniecznie liniowo) jest uporządkowany.
Pytanie: jak zinterpretować to (ten porządek na podzbiorze ) na diagramie Hassego ? Jak to się interpretuje??
No bo skoro zbiory uporządkowane przedstawia się na diagramach Hassego, a każdy podzbiór zbioru uporządkowanego jest uporządkowany, to naturalnym wydaje się pytanie jak wygląda diagram Hassego na podzbiorze uporządkowanym. Myślałem, że jest związany z diagramem zbioru uporządkowanego danego na wejściu.
Jan Kraszewski pisze: ↑15 sty 2022, o 19:43
Czy jeśli weźmiesz diagram zbioru uporządkowanego \(\displaystyle{ \left\langle \{1,2,3\},\le\right\rangle }\) i rozważasz ten sam porządek na podzbiorze \(\displaystyle{ \{1,3\}}\), to czy to jest "ten sam dany diagram na nadzbiorze tylko ograniczony do elementów tego podzbioru "?
Tego nie przewidziałem, czyli trzeba by każdy odrzucony element zastąpić 'złączeniem dróg'- drogi z ostatniego nie wyrzuconego elementu do tego elementu i drogi od tego elementu do następnego nie wyrzuconego elementu ( w razie czego takich dróg może być więcej niż \(\displaystyle{ 2}\), powiedzmy, że będzie ich \(\displaystyle{ n}\) ). Czyli u nas wyrzuconym elementem był \(\displaystyle{ 2}\), więc tworzymy złączenie drogi od \(\displaystyle{ 1}\) do \(\displaystyle{ 2}\) i drogi od \(\displaystyle{ 2}\) do \(\displaystyle{ 3}\), I wtedy może otrzymamy diagram Hassego podzbioru uporządkowanego? I to w całej ogólności, tak??
Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję
: 16 sty 2022, o 20:03
autor: Jan Kraszewski
Jakub Gurak pisze: ↑16 sty 2022, o 19:40Wczoraj się chwilę zastanowiłem, wychodzi na to, że ta równoważność będzie zachodzić, racja Proszę o odpowiedź.
No cóż, równoważność \(\displaystyle{ x \le _{Y} y \Longleftrightarrow x \le y \wedge x,y \in Y}\) to po prostu definicja relacji \(\displaystyle{ \le_Y...}\)
Jakub Gurak pisze: ↑16 sty 2022, o 19:40No bo skoro zbiory uporządkowane przedstawia się na diagramach Hassego, a każdy podzbiór zbioru uporządkowanego jest uporządkowany, to naturalnym wydaje się pytanie jak wygląda diagram Hassego na podzbiorze uporządkowanym. Myślałem, że jest związany z diagramem zbioru uporządkowanego danego na wejściu.
No jakoś związany jest...
Jakub Gurak pisze: ↑16 sty 2022, o 19:40Tego nie przewidziałem, czyli trzeba by każdy odrzucony element zastąpić 'złączeniem dróg'- drogi z ostatniego nie wyrzuconego elementu do tego elementu i drogi od tego elementu do następnego nie wyrzuconego elementu ( w razie czego takich dróg może być więcej niż \(\displaystyle{ 2}\), powiedzmy, że będzie ich \(\displaystyle{ n}\) ). Czyli u nas wyrzuconym elementem był \(\displaystyle{ 2}\), więc tworzymy złączenie drogi od \(\displaystyle{ 1}\) do \(\displaystyle{ 2}\) i drogi od \(\displaystyle{ 2}\) do \(\displaystyle{ 3}\), I wtedy może otrzymamy diagram Hassego podzbioru uporządkowanego? I to w całej ogólności, tak??
Brzmi to dość zawikłanie. Musisz po prostu pamiętać, że diagram Hassego to nie jest zwykły graf relacji, więc w zasadzie jak chcesz mieć diagram Hassego podzbioru, to powinieneś wyjściowy diagram Hassego uzupełnić do grafu relacji (pętelki można sobie darować...), potem z tego grafu możesz usunąć elementy spoza podzbioru i strzałki do nich, a potem poprawić otrzymany graf tak, by stał się diagramem Hassego.
JK
Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję
: 24 sty 2022, o 23:29
autor: Jakub Gurak
Czyli chyba wychodzi na to samo, gdyż chodzi o przechodniość relacji...
Udowodniłem wczoraj, że jeśli mamy zbiór uporządkowany, oraz podzbiór uporządkowany, oraz antyłańcuch \(\displaystyle{ A }\) w tym nadzbiorze \(\displaystyle{ X}\), to przekrój antyłańcucha \(\displaystyle{ A}\) do podzbioru uporządkowanego jest antyłańcuchem w tym podzbiorze. Udowodniłem też wczoraj, taki bardzo ciekawy fakt, że jeśli mamy dwa zbiory uporządkowane \(\displaystyle{ (X,R)}\);\(\displaystyle{ (Y,S),}\) gdzie zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są rozłączne, i jeśli mamy antyłańcuch \(\displaystyle{ A\subset X}\) oraz antyłańcuch \(\displaystyle{ B\subset Y}\), to suma \(\displaystyle{ A \cup B}\) jest antyłańcuchem w \(\displaystyle{ \left( X \cup Y, R \cup S\right)}\)- czyli suma tych dwóch antyłańcuchów jest antyłańcuchem w sumie tych dwóch zbiorów uporządkowanych względem porządku, którym jest suma tych dwóch porządków- hm, bardzo ciekawe... Przedstawię teraz dowody tych ciekawych faktów.
Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem uporządkowanym, a \(\displaystyle{ Y\subset X}\) jego podzbiorem (z porządkiem \(\displaystyle{ \le _Y:= \le _{|Y}}\), czyli porządkiem \(\displaystyle{ \le}\) zawężonym do zbioru \(\displaystyle{ Y}\) ), a zbiór \(\displaystyle{ A\subset X}\) niech będzie antyłańcuchem. Wykażemy, że przekrój \(\displaystyle{ A \cap Y}\) jest antyłańcuchem w \(\displaystyle{ \left( Y, \le _Y\right) }\)- czyli, przekrój antyłańcucha z podzbiorem uporządkowanym, wtedy ten przekrój będzie antyłańcuchem w tym podzbiorze.
DOWÓD:
Mamy \(\displaystyle{ A \cap Y \subset Y}\), jak trzeba.
Aby wykazać, że ten zbiór jest antyłańcuchem w \(\displaystyle{ \left( Y, \le _Y\right) }\), to weźmy dwa różne elementy \(\displaystyle{ a,b \in A \cap Y.}\)
Przypuśćmy, że \(\displaystyle{ a \le _Y b}\). Ponieważ porządek \(\displaystyle{ \le}\) rozszerza porządek \(\displaystyle{ \le _Y}\), więc \(\displaystyle{ a \le b}\). Mamy \(\displaystyle{ a,b\in A}\), \(\displaystyle{ a \neq b}\), a \(\displaystyle{ A}\) jest antyłańcuchem w \(\displaystyle{ \left( X, \le\right) }\), więc elementy \(\displaystyle{ a,b}\) powinny być nieporównywalne względem \(\displaystyle{ \le}\) , a \(\displaystyle{ a \le b}\)- sprzeczność. Wobec czego \(\displaystyle{ a \not\le_Y b}\).
Przypuśćmy, że \(\displaystyle{ b \le _Y a}\). Wtedy analogicznie otrzymujemy sprzeczność.
Wobec czego \(\displaystyle{ a\not \le _Y b}\) i \(\displaystyle{ b \not \le _Y a}\), czyli elementy \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są nieporównywalne. Dowolność wyboru tych elementów oznacza, że zbiór \(\displaystyle{ A \cap Y}\) jest antyłańcuchem. \(\displaystyle{ \square }\)
(Będzie można sprawdzić analogiczny fakt dla łańcuchów- czyli czy zawężenie łańcucha do podzbioru uporządkowanego czy jest łańcuchem w tym podzbiorze- nie wiem, tego jeszcze nie badałem, będzie można zastanowić się).
Wykażemy teraz, taki bardzo ciekawy fakt, że jeśli \(\displaystyle{ \left( X,R\right) ; \left( Y,S\right)}\) są zbiorami uporządkowanymi, gdzie zbiory \(\displaystyle{ X,Y}\) są rozłączne( wtedy zbiór \(\displaystyle{ X \cup Y}\) jest uporządkowany przez \(\displaystyle{ R \cup S}\) ), i jeśli mamy antyłańcuch \(\displaystyle{ A\subset X}\) oraz antyłańcuch \(\displaystyle{ B\subset Y}\), to suma \(\displaystyle{ A \cup B}\) jest antyłańcuchem w \(\displaystyle{ \left( X \cup Y, R \cup S\right) }\)- czyli suma tych dwóch antyłańcuchów jest antyłańcuchem w zbiorze uporządkowanym, którym jest ta suma rozłączna. W ukrytej treści poniżej przedstawiam dowód tego ciekawego faktu.
DOWÓD TEGO FAKTU::
Mamy \(\displaystyle{ A\subset X}\) oraz \(\displaystyle{ B\subset Y}\), więc \(\displaystyle{ A \cup B\subset X \cup Y}\), jak trzeba.
Weźmy dowolne różne elementy \(\displaystyle{ a,b \in A \cup B.}\)
Przypuśćmy, że \(\displaystyle{ a \le _{X \cup Y} b}\). Wtedy \(\displaystyle{ a \le _X b}\) lub \(\displaystyle{ a \le _Y b}\). Rozważmy cztery przypadki.
Jeśli \(\displaystyle{ a,b\in A}\). Ponieważ zbiór \(\displaystyle{ A \subset X}\) jest antyłańcuchem, \(\displaystyle{ a,b\in A}\) i \(\displaystyle{ a \neq b}\), więc elementy \(\displaystyle{ a,b}\) muszą być nieporównywalne, więc nie może być \(\displaystyle{ a \le _X b}\). Wobec czego pozostaje jedynie możliwość gdy: \(\displaystyle{ a \le _Y b}\). Łatwo prowadzi ona do sprzeczności, gdyż wtedy \(\displaystyle{ a,b\in S_L=Y}\). Ale \(\displaystyle{ a,b\in A\subset X}\), więc \(\displaystyle{ a,b\in X \cap Y}\), a zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są rozłączne-sprzeczność.
Jeśli \(\displaystyle{ a,b\in B}\), to analogicznie otrzymujemy sprzeczność.
Jeśli \(\displaystyle{ a\in A}\), \(\displaystyle{ b\in B}\). Wtedy \(\displaystyle{ a\in X, b\in Y.}\) Jeśli \(\displaystyle{ a \le _X b}\), to \(\displaystyle{ b\in X}\). Mamy \(\displaystyle{ b\in Y,}\) wobec czego \(\displaystyle{ b\in X \cap Y}\), a zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są rozłączne- sprzeczność.
A jeśli \(\displaystyle{ a \le _Y b}\), to \(\displaystyle{ a\in Y}\). Mamy \(\displaystyle{ a\in X}\), wobec czego \(\displaystyle{ a\in X \cap Y}\)- sprzeczność.
Jeśli \(\displaystyle{ b\in A, a\in B}\), to analogicznie jak powyżej otrzymujemy sprzeczność.
Kończy to połowę dowodu. (Drugą połowę spróbuję zrobić lepiej, tzn. krócej- inne przypadki rozpatrzę, i będzie wtedy prościej).
Przypuśćmy, że \(\displaystyle{ b \le _{X \cup Y} a}\). Wtedy \(\displaystyle{ b \le _X a}\) lub \(\displaystyle{ b \le _Y a.}\)
Jeśli \(\displaystyle{ b \le _X a}\). Wtedy \(\displaystyle{ b,a\in X}\). Ponieważ \(\displaystyle{ B\subset Y}\), więc \(\displaystyle{ X \cap B\subset X \cap Y=}\) i ponieważ zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są rozłączne, to ten przekrój jest pusty. Ponieważ jedynym podzbiorem zbioru pustego jest on sam, więc również \(\displaystyle{ X \cap B=\emptyset}\). Zatem ponieważ \(\displaystyle{ b,a\in X}\), więc zarówno: \(\displaystyle{ b\not\in B,}\) jak i i \(\displaystyle{ a\not\in B}\). Ale \(\displaystyle{ b,a \in A\cup B}\), więc \(\displaystyle{ b,a\in A}\), i ponieważ zbiór \(\displaystyle{ A}\) jest antyłańcuchem, i \(\displaystyle{ a \neq b}\), więc elementy \(\displaystyle{ a}\) i \(\displaystyle{ b}\) powinny być nieporównywalne, a mamy \(\displaystyle{ b \le _X a}\)- sprzeczność.
Jeśli \(\displaystyle{ b \le _Y a}\)- to analogicznie jak powyżej otrzymujemy sprzeczność. Wobec czego \(\displaystyle{ b \not\le _{X \cup Y} a.}\)
Tak więc \(\displaystyle{ a \not\le _{X \cup Y} b}\) i \(\displaystyle{ b \not\le _{X \cup Y} a}\), czyli elementy \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są nieporównywalne. Z dowolności wyboru takich elementów otrzymujemy, że zbiór \(\displaystyle{ A \cup B}\) jest antyłańcuchem.\(\displaystyle{ \square}\)
Na koniec wykażemy jeszcze jeden prosty fakt. Przypomnę może najpierw prosty fakt, że jeśli mamy dwa zbiory uporządkowane \(\displaystyle{ \left( X,R\right) }\); \(\displaystyle{ \left( Y,S\right) }\), to zbiór \(\displaystyle{ X \cap Y}\) jest zbiorem uporządkowanym przez \(\displaystyle{ R \cap S}\). Ten porządek działa tak, że zawsze:
\(\displaystyle{ x \le _{X \cap Y} y \Longleftrightarrow x \le _X y \wedge x \le _Y y. }\)
Wykażemy na koniec (zachowując powyższe oznaczenia), że jeśli mamy antyłańcuch \(\displaystyle{ A\subset X}\) oraz antyłańcuch \(\displaystyle{ B\subset Y}\), to przekrój \(\displaystyle{ A \cap B}\) jest antyłańcuchem względem zbioru uporządkowanego \(\displaystyle{ \left( X \cap Y, R \cap S\right)}\).
PROSTY DOWÓD TEGO FAKTU::
Mamy \(\displaystyle{ A\subset X, B\subset Y,}\) więc \(\displaystyle{ A \cap B\subset X \cap Y}\), jak trzeba.
Aby wykazać, że ten zbiór jest antyłańcuchem, to weźmy dwa dowolne różne elementy \(\displaystyle{ x,y\in A \cap B.}\)
Przypuśćmy, że \(\displaystyle{ x\left( R \cap S\right)y}\). Wtedy \(\displaystyle{ x\left( R\right) y}\) i \(\displaystyle{ x \left( S\right)y}\). Ponieważ \(\displaystyle{ x,y\in A}\), \(\displaystyle{ x \neq y}\), a zbiór \(\displaystyle{ A}\) jest antyłańcuchem względem \(\displaystyle{ R}\), więc elementy \(\displaystyle{ x}\) i \(\displaystyle{ y}\) powinny być nieporównywalne względem \(\displaystyle{ R}\), a \(\displaystyle{ x\left( R\right)y}\)- sprzeczność.
Przypuśćmy teraz, że \(\displaystyle{ y\left( R \cap S\right) x}\). Wtedy \(\displaystyle{ y\left( R \right) x}\) i \(\displaystyle{ y\left( S\right)x}\). Ponieważ \(\displaystyle{ x,y\in A}\), i \(\displaystyle{ x \neq y}\), a zbiór \(\displaystyle{ A}\) jest antyłańcuchem, więc wnioskujemy, że elementy \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są nieporównywalne względem \(\displaystyle{ R}\), podczas gdy \(\displaystyle{ y\left( R\right) x}\)-sprzeczność.
Wystarczy dowód pozbierać aby go zakończyć.\(\displaystyle{ \square}\)
Niestety, analogiczny fakt dla łańcuchów nie zachodzi, tzn. jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ R,S}\) są relacjami porządku w \(\displaystyle{ X}\). Wtedy \(\displaystyle{ (X,R); (X,S)}\) są zbiorami uporządkowanymi. Jeśli mamy łańcuch \(\displaystyle{ A\subset X}\) (w zbiorze uporządkowanym \(\displaystyle{ \left( X,R\right)}\) ), oraz łańcuch \(\displaystyle{ B\subset X}\), względem porządku \(\displaystyle{ S}\), to przekrój \(\displaystyle{ A \cap B}\) może nie być łańcuchem względem \(\displaystyle{ R \cap S}\), niestety.
Są to wręcz liniowe porządki na zbiorze liczb naturalnych. Łatwo się przekonać, że wtedy przekrój \(\displaystyle{ R \cap S=I_{\NN}}\) jest jedynie porządkiem identycznościowym na zbiorze liczb naturalnych. Biorąc zatem na łańcuch \(\displaystyle{ A}\) , biorąc: \(\displaystyle{ A=\left\{ 2,3,4\right\}}\), i biorąc: \(\displaystyle{ B=\left\{ 3,4,5\right\}}\), otrzymamy, jako przekrój, zbiór \(\displaystyle{ \left\{ 3,4\right\}}\), który nie jest łańcuchem względem \(\displaystyle{ I_\NN}\) (gdyż tu są tylko łańcuchy co najwyżej jednoelementowe), niestety.
Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję
: 25 sty 2022, o 00:03
autor: Jan Kraszewski
Jakub Gurak pisze: ↑24 sty 2022, o 23:29
Wykażemy teraz, taki bardzo ciekawy fakt, że jeśli \(\displaystyle{ \left( X,R\right) ; \left( Y,S\right)}\) są zbiorami uporządkowanymi, gdzie zbiory \(\displaystyle{ X,Y}\) są rozłączne
(...)
Wykażemy na koniec (zachowując powyższe oznaczenia), że jeśli mamy antyłańcuch \(\displaystyle{ A\subset X}\) oraz antyłańcuch \(\displaystyle{ B\subset Y}\), to przekrój \(\displaystyle{ A \cap B}\) jest antyłańcuchem względem zbioru uporządkowanego \(\displaystyle{ \left( X \cap Y, R \cap S\right)}\).
To trochę bezsensowny fakt, bo przy "powyższych oznaczeniach" mamy \(\displaystyle{ X \cap Y=\emptyset...}\)
JK
Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję
: 25 sty 2022, o 13:11
autor: Jakub Gurak
Aj, nieporozumienie. Tuż wyżej piszę:
Jakub Gurak pisze: ↑24 sty 2022, o 23:29Przypomnę może najpierw prosty fakt, że jeśli mamy dwa zbiory uporządkowane \(\displaystyle{ \left( X,R\right) }\); \(\displaystyle{ \left( Y,S\right) }\), to zbiór \(\displaystyle{ X \cap Y}\) jest zbiorem uporządkowanym przez \(\displaystyle{ R \cap S}\).
I o tylko taką sytuację mi chodziło. Niepotrzebnie dodałem ten zwrot "zachowując powyższe oznaczenia"- lubię, pewnie za bardzo, stawiać sprawę jasno. Jak widać, przyniosło to odwrotny efekt...