Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
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

Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję

Post 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??
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

Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję

Post 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
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: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję

Post 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??
Jan Kraszewski pisze: 15 sty 2022, o 19:43 :?:
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. :lol:
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??

:lol:
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

Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję

Post 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
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: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję

Post 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::    
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::    
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.

Jako kontrprzykład wystarczy wziąć:

\(\displaystyle{ X=\NN}\), \(\displaystyle{ R= \le _\NN, S= \left( \le _{\NN} \right) ^{-1}.}\)

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. :roll:

:lol:
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

Re: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję

Post 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
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: Podzbiór zbioru liniowo uporządkowanego- pytanie o definicję

Post 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... :?
ODPOWIEDZ