Porządki częściowe — zadania z logiki na IS AGH, zestaw 4, cz. 2
Zadania od widzów⏱ 1 h 25 min
Druga część zestawu 4 z logiki na Informatyce Stosowanej AGH: porządki częściowe w praktyce. Relacja prefiksu na słowach, podzielność, porządki produktowe i leksykograficzne oraz elementy minimalne i maksymalne.
W tym nagraniu
Czy relacja „bycia prefiksem” jest porządkiem częściowym
Porządek podzielności na liczbach naturalnych
Porządek produktowy i leksykograficzny
Elementy minimalne, maksymalne, najmniejsze i największe
Druga część zestawu 4 z logiki na Informatyce Stosowanej AGH (zadania 10–15) dotyczy porządków częściowych, czyli relacji zwrotnych, antysymetrycznych i przechodnich. Pierwszy przykład to relacja „bycia prefiksem” na słowach: sprawdzanie kolejnych warunków pokazuje, że jest to porządek częściowy, ale nie liniowy.
Dalej porządek podzielności na liczbach naturalnych i dwa sposoby porządkowania par: porządek produktowy (para jest mniejsza lub równa, gdy obie współrzędne są mniejsze lub równe) i leksykograficzny (jak w słowniku — decyduje pierwsza różniąca się współrzędna). Porządek leksykograficzny na parach liczb jest liniowy, produktowy — nie.
Kolejne zadania ćwiczą rozróżnienie elementów minimalnych i maksymalnych od najmniejszych i największych — w porządku częściowym element minimalny nie musi być najmniejszy — a także łańcuchy (zbiory elementów parami porównywalnych) i antyłańcuchy (zbiory elementów parami nieporównywalnych) w porządku podzielności. Nagranie przyda się każdemu, kto przerabia porządki na kursie logiki lub matematyki dyskretnej.
Rozdziały
Kliknij czas, żeby przewinąć nagranie do wybranego fragmentu.
Zadanie 10
Zadanie 11, feat. opowieść o porządku leksykograficznym
Transkrypt został wygenerowany automatycznie na podstawie napisów YouTube, więc może zawierać błędy w zapisie wzorów, nazwisk i terminów. Kliknij znacznik czasu, aby przewinąć wideo do danego fragmentu. (6528 słów)
Wracamy po przerwie patrzymy na ciągi skończone o wyrazach Ze zbioru liczb naturalnych czyli tak na słowa w alfabecie tylko że jest nieskończony i relacja to to jest relacja bycia prefiksem no więc pytanie czy to jest porządek częściowy to jest pytanie z gatunku trywialnych No bo jeśli jak to chcemy napisać tak brutalnie w znaczkach No to x jest prefiksem y tylko wtedy gdy Co gdy y jest równy jakiemuś x jest równy jakiemuś takiemu ciągowi a y jest równy temu ciągowi z dopisanym czymś jakimś yn aż ym x długość y czy sprawy porządku sprawdzamy czy z faktu że nieostry porządek bo wszystko jest prefixem więc Patrzymy czy z tych dwóch
Rzeczy wynika że x jest równe y XO y i że długość y długoś x czyli długość x jest równa długości y czyli na tym obrazku który widzimy jest równe m czyli x jest równe coś y musi być tym samm nie miejsc na wicej jeś x jest prefiksem y i Y jest prefiksem z to co to x jest równe coś y jest równe coś X1 do X potem jakieś elementy y to jest y teraz mamy y ono jest prefiksem z czyli z musi być taki sam tu gdzieś po drodze ma XN potem ma coś potem ma ym a potem jeszcze ma jakieś
Swoje elementy No to to Reason że x jest prefiksem z to widać gołym okiem czy element największy no nie tak jak mam dowolny x 1 XN to on jest prefiksem ciągu X1 XN i to nasza ulubiona liczba na przykład je czy minimalny Czy istnieje taki ciąg ciąg którego nikt nie jest prefiksem to zależy od floru notacji której używa autor zadań No bo jedna wersja jest taka że pusty string jest jest ciągiem a druga jest jest że nie no więc jeśli ciąg długości zery cnie
Długości zer jest w te to w ogóle jest najmniejsze jeśli nie to każdy ciąg długości 1 jest jest minimalny każdy ciąg długości x składający się po prostu z jednej liczby jest minimalny Okej czyli w pewnym sensie to jest tak że my bierzemy liczbę bierzemy liczbę produkujemy z niej parę iamy do tej pary porządek graficzny Pamiętam że było takie coś co się nazywało porządek graficzny jak ja miałem jeden zbiór uporządkowany i drugi to ja mówiłem że xy jest mniejsze równe w porządku leksykograficznym niż x prim y prim wtedy tylko wtedy
Gdy Co gdy x jest mniejsze równe po xu od x tu mniejsze lub to jest równe oraz Y jest mniejsze równe po Yu od y w szczególności jeśli oba porządki ten xy i yow są liniowe to leksyk graficzne też jest liniowy tak porównujemy pierwsze współrzędne jak są równe to porównujemy drugie tutaj mamy taką sytuację że ja biorę n ja go wrzucam w liczbę dzielników różnych dzielników i n to jest przekształcenie zwróconym zerem w n n plus r n tak będziemy pisać różnych dzielników zawsze jest przynajmniej je też może być plus to nie ma znaczenia ja twierdzę że to co jest w tym zadaniu tak tutaj mam
Zanurzenie tu po tej stronie mam ten porządek który jest który jest w zadaniu a po tej stronie mammal Natural i to wynika bezpośrednio z definicji to znaczy to znaczy n jest mniejsze równe niż m w tym sensie to jest równoważne z tym że para Alfa NN jest mniejsza równa Pole graficznemu niż para Alfa od m No to w szczególności udowodniliśmy udowodniliśmy że to jest to się zanurza zanurza się monotonicznie w częściowy porządek to jest ten nawet jest liniowy jak wyjmę podzbiór z liniowego porządku to to jest częściowy porządek czy jest liniowym porządkiem ale jak to udowodnimy wystarczy znale
Liczby które są nieporównywalne Nie zaraz z Zaz ź mówię prostu jak wyciągnę zego porządku wciągnę Oczywiście że to jest że to jest porządek liniowy więc to to jest to jest zanurzenie czyli izomorfizm na swój obraz to jest io z podzbiorem r z porządkiem le graficznym jest liniowy więc ten zadaniu też jest liniowy natomiast ten dobry porządek to ma ma konkretn definicję mówiliśmy że porządek jest dobry Gdy nie ma nieskończonych schodzących łańcuchów jedna wersja jest taka gdy nie istnieje ciąg x1 x2 i tak
Dalej taki że X1 jest większe niż x2 większe niż X3 większe niż x4 i tak dalej No i jak jest u nas u nas jest to jest jen warunek drugi warunek jest taki że każdy niepusty podzbiór ma element najmniejszy w szczególności n plus takie jest Plus jest dobry z jest zły sylab a nie jest dobry ma jak powiedział święty Kevin Office nasz porządek jak nasz porządek
Tak naprawdę on działa w ten sposób że jaam wyciągnięcie czegoś co jest funkcją z to jest funkcja y x to jest także na poziomie każdego ja mam kropkę na na poziomie alfa i temu patrzymy le graficznie najpier pierze współrzędne A jak one nie dadzą nie dadzą porównania to porównujemy drugie no to generalnie Ja myślę że ja myślę że on nie ma jak być zły no bo o ile ten porządek tutaj A nie zaraz sekundę ten porządek też jest dobry tak tak ten porządek też jest dobry No bo Spójrzcie ten n plus raz n plus z porządkiem leksykograficznym to jak wygląda wą że biorę sobie i tak dalej potem to jest z normalnym porządkiem na na enie potem mówię że każdy stąd jest mniejszy niż następna
Kopia i tak dalej wy porządku To się nazywa po prostu konkatenacja albo dodawanie że się wypisuje ileś jeden po drugim i się mówi że są po kolei No i to jest dobry porządek to się nawet nazywa Omega razy Omega w tych arytmetyce liczb porządkowych jakbyśmy chcieli to tak udowodnić żeby się nikt nie przyczepił to to co to powiedzmy że a jest pod zbiorem n plus do kwadratu z porządkiem log graficznym on jest niepusty ja chcę w nim konkretnie znaleźć element najmniejszy No to ja patrzę na rzut a na pierwszą współrzędną to jest dokładnie zbiór tych wszystkich x że istnieje taki y należący do a że xy należy do A i teraz mówię że to jest podzbiór Natural oczywiście jest
Niepusty No to jest tak na rzut na pierwszą współrzędną Patrzcie kto przyszedł jeszcze mrucz jakoś muszę pogodzić twoje co ja mam z tym zrobić Tak ona ona generalnie tak czasem lubi chować twarz mojej ręce to jest naw współrzędną El przy zbioru a i on będzie miał swoją pierwszą współrzędną No to to niech x gwiazdką to będzie najmniejszy element pi
A w szczególności dla każdego xy któ należy do a x jest większe niż x g No to teraz Wystarczy wziąć niepusty zbiór tych y że x gwiazdk y należy do a on jest niepusty to jest pocz więc minimum niech to minimum się nazywa y gwiazdką To teraz ja chcę udowodnić że x gwi y gwi jest najmniejszym elementem a bez wątpienia skoro to jest faktycznie to jest element najmniejszy tego zbioru to jest realizowany gdzieś to znaczy x z gwiazdką y z gwiazdką należy do A i teraz we jakikolwiek xy No to to jest to bardzo krótkie Drew x x wi xwi to xy oczywiście wiks niż x y a jeśli x jest równe x gwiazdką to
Nasza para jest postaci x gwiazdk y ale y z gwiazdką to był najmniejszy spośród wszystkich takich że x gwi y należy y y x y większe rów niż x g wzy świetnie udowodniliśmy mogliśmy jeszc bardziej na partyzanta udowodnić na przykład że na przykład że jakbym chciał zrobić nieskończone schodzenie to bym musiał to musiał co i tak na argument jakoś tak musiałby wyglądać No bo ja bym musiał udowodnić że ja schodzę za każdym razem nieskończone schodzenie to za każdym razem ja zejdę Ja zapłacę tylko skończenie Wiele elementów ciągu żeby wyjść z danego z danej kopii więc w końcu trafię tutaj i próbuję mieć nieskończone schodzenie WC udowodniliśmy tutaj udowodniliśmy twierdzenie że n plus kwad z porządkiem leksykograficznym jest
Dobry no i porządek dobrego porządku jest dobry to jest w zasadzie oczywiste No bo teraz k naprawdę wcieranie twarzy w w tablet to jest to co chcesz robić I co co ja z nią mam no dobrze To może ja będę pisał po nie tej stronie tabletu co za kod wi jak to zrobimy to się dostało lewą stronę tabletu po prawej Dostaniesz dostaniesz chrupką co Patrz jest chrupek tu jest kawałek tabletu k pnie chrupkiem o No tu masz Tak ona szuka chrupka którego widziała Szuka pod moją ręką to nie jest najdłużej szy K W każdym razie no lewą ręką chrupkami
Wi że masz ich sporo w miseczce takich zdrowszych te są też zdrowe to jest Pi kurczaka to jest 100% mięsa natomiast na to się rzuca jak głodny student na kebaba dobr Nakarm chod patrz tu jak się nauczysz To będziesz mogła zarobić na swoje chrupki mamy ten nasz śmieszny podzbiór Tak mieliśmy naszą inkluzja Która z ze zbioru W zadaniu robiła podzbiór n r n tak ogólnie jak mam jakikolwiek jakikolwiek podzbiór b tego tego naszego dobrego porządku to to wtedy b z tym porządkiem graficznym obciętym tym obciętym do b r b to też jest dobry bo jeśli a to jest jakiś podzbiór b to to jest podzbiór n kwadrat który ma
Dobry porządek Więc najmniejszy więc więc tak więc dowolny podzbiór b ma element najmniejszy Tak on należy do A to to nie jest coś relatywnego do do ten do całego tego bycie dobrym porządkiem to jest pewna własność to jest własność pod d jesta Met dziedzicz to znaczy jeśli ja mówię że każdy mój podporą ma element najmniejszy to każdy mój podporą wtedy też wie że każdy jego podporą ma element najmniejszy bo każdy pod porządek pod porządku jest pod porządkiem także tak powiedzieliśmy powiedzieliśmy że jest jest dobrym porządkiem to jest tak naprawdę dowód Nazwijmy te inkluzje J żeby potem się móc na nie
Powoływać to jest to co zadanie nazywało b a teraz nas pytają o elementy szczególne dobrze z największymi to widać że że będzie ciężko tak samo z maksymalnymi maksymalnych brak Brak bo co ja twierdzę że n jest zawsze mniejsze niż n r n + 1 Dlaczego Dlatego że alfa od n jest mniejsza niż Alfa od n x n + 1 bo Alfa nam zlicza liczbę różnych dzielników Bo jeśli jakikolwiek dzielnik pierwszy który dzieli n plus 1 to p nie dzieli n więc Alfa n plus 1 plus 1 ma więcej dzielników inaczej napiszemy także
Zbiór zbiór dzielników o zbiór takich d że d dzii n plus 1 jest jest jaki tu będziemy mieli d raz plus 1 x n jest większy niż zbiór d taki że d dzii n bo ten zawiera jakąś liczbę pierwsz plus a ten już nie więc tak jak nie maksymalnych bardzie najmniejszych Czy są jakieś minimalne pewnie trzeba brać takie które mają minimalną Alfę Myślę że mylę że J jest najmniejszy bo jka ma tylko jeden dzielnik oraz dla każdego na większego od 1 Alfa ten jest większy równy 2 bo 1 dzieli n oraz n dzieli n i one są różne
By the na to alfa jest wzór jawny o można go nazwać jawnym ten jakoś tak szedł że jak n się rozkłada na czynniki pierwsze raz PK do Alf k AK gdzie p1 do PK to są różne liczby pierwsze kolei wane wszystkie wszystkie czynniki pierwsze które ma n tak żeby się nie powtarzały i wtedy siłą rzeczy Alfy są naturalne znaczy możemy Możemy nawet im pozwolić mieć zero Tak możemy tutaj redundantnie dopisać jakąś liczbę pierwszą wykładniku zero to to nie wpływa na wynik to wtedy to co nam się nazywa Alfa od n to chyba to jest to co w te części nazywa to jest po prostu iloczyn to jest czysta kombinatoryka czysta komka jest taka że jak ja chcę mieć dzielnik n jeśli D dzieli n to d musi być nie może mieć żadnej liczby pierwszej spoza tych więc
Musi być postaci p1 do B1 raz raz r PK do BK iżż bj tak możliwości wyboru tego b plus stąd ten iloczyn każdy wykładnik możem wybierać zno można Wysowa to się nazywa SIG to jest w suma po wszystkich zobaczyłeś ducha bo że whisky Coś przewrócił i nagle ma takie chcesz do pudełka będzie w pudełku jest w pudełku to jest suma po wszystkich
Możliwych wyborach b każde przebiega po swoim zbiorze to jest niezależnych indeksach z czegoś co jest co jest iloczynem oddzielonych zmiennych czyli p1 do B1 r raz PK do BK toet Panda wie że jak się wymnożyć su B2 z P2 do B2 i tak dalej BK PK bk Jak wymnożyć na każdą z tych sum to to jest paragraf to jest suma od 1 do A1 No toż to jest szereg geometryczny tu jest po prostu iloczyn od 1 do K każde takie coś się sumuje do PJ do do której potęgi kończymy na aj czyli do aj + 1-1 prz PJ -
1 wzór jak wzór najbliżej tego co byśmy mogli nazwać wzorem jawnym na na sumowanie dzielników na liczbę jest trochę prostsze tymczasem zadanie 12 12 jest o tym samym z drugiej strony to znaczy ja mógłbym bo ja się tak pował na to że my wszyscy wiemy co to jest porządek graficzny i wiemy jak się dazi jego własności a tu jest akurat inny Tu jest taki porządek chamski po obu współrzędnych to znaczy nie dobrze No nie da się zrobić wykładu o z podstaw matematyki o porządkach i nie powiedzieć o porządku Leks graficznym więc zakładam że że były napisane znaczki które dowodzą że to jest że to jest porządek liniowy a nawet jak nie to to jest oczywiste A dobra m ZEM 12 jest taki chamski porządek po współrzędnych to znaczy taki w którym nie wszystko się daje porównać A jak się już daje porównać to obie współrzędne są są nierówności to jest także jak ja chcę narysować przedział jak ja chcę narysować mam jakiegoś konkretnego z w tak jak oni tutaj mają O ja chcę
Narysować zbiór tych zów które są mniejsze równe w wygląda tak dobra tak tutaj to że ten zbiór został nazwany C to to nie ma znaczenia to jest PiS na wodę tutaj struktura algebraiczna liczb zespolonych nie ma żadnego znaczenia No to dowodzimy No jeśli z jest mniejsze mniejsze w tym porządku Od w i w jest mniejsze od z część rzeczywista z jest mniejsza niż część rzeczywista w oraz część rzeczywista w jest mniejs rów niż część rzeczywista z to idzie tu i to idzie tu Czyli z tego Rez rów się RW dokładnie tak samo z częściami urojonymi jest w czyli z tych z tych dwóch rzeczy wynika że z świetnie to było trywialne np jest tak samo trywialne to znaczy że jeśli z jest mniejsze równe w mniejsze równe u no to
Wtedy część rzeczywista z mniejsze równa część rzeczywista w część rzeczywista u no Czyli No czyli tu jest nierówność tak samo tak samo z częściami urojonymi tu jest też nierówność czy jest liniowy No to jest dokładnie tak jak był ten mem z pierwszego odcinka serialu Archer jak ktoś chyba upuścił tort na ziemię i czy chcesz żeby to były mrówki bo dokładnie to jest ten jeden sposób który się sprowadza mrówki do biura tak samo tu to jest dokładnie ten jeden sposób który się robi nieliniowy porządek że się porównywalne bo 1 + 2i i 2 + 1i tu nie ma nierówności i tu nie ma nierówności w drugą stronę tak żeby były mniejsze No to owszem jen jest mniejszy od dwóch ale wtedy już dwójka nie jest mniejsza od 1eden Jakby to miało być większe to w ogóle nie jest bo bo ten bo
Dwójka jest większe od 1 a czy jest gęsty oczywiście tak bo jeśli mam jakikolwiek z mniejsze równe w w tym porządku No to to co to ja mogę wziąć średni arytmetyczną mogę powiedzieć że z jest mniejsze równe niż z plus w PR 2 na obrazku to wygląda tak jak tak jak tutaj widzieliśmy tylko Wedy jaktor z to znie WM porządku gdzieś po drodze jest śmy część rzeczywista w tak samo dla urojonych bo to mnożę przez D pomnożę przez D No i tu jest raz mniejszy równy RW a tu jest RW też rz
Mniejszy równy niż RW dobra by w tym zadaniu 12 to w ogóle liczby to że to by liczby nie ma znaczenia to by liczby rzeczywiste też z nie ma znaczenia jak wezmę jakikolwiek porządek to mogę zrobić z niego taki taki chamski tensor to znaczy że wezmę jego kwadrat kartezjański akurat mł r i na tym kwadracie zrobię taki porządek że muszą być obie współrzędne porównywalne jakoś nazywa porządek produktowy coś podobnego jeszcze jakbyśmy chcieli być bardzo pompatycznie to byśmy napisali że ten śmieszny porządek jest pod zbiorem porządku graficznego taka prawda porządek to jest relacja czyli to jest zbiór tu jest inny zbiór no i jeśli jakaś para jest porównywalna w tym silnym porządku to jest porównywalna też w tym odwrotnie
Niekoniecznie więc jest taki śmieszny napis dobra i w zadaniu 13 13 do czynienia z funkcjami które idą w częściowy porządek jest bardzo podob do tego co było wcześniej Pamiętam że było to było takie zadanie że mamy funkcje które idą z na w jakiś zbiór przypadkiem to jest też n i są porównywalne jeśli na każdej współrzędnej są porównywalne w tym porządku przeciwdziedziny f i tutaj rola tego na i tego na była w ogóle oddzielona tak to to nie miało znaczenia że tu jest n i tu jest n to mog być jakikolwiek zbiór a tu mielibyśmy porządek na to były tak samo brzmiące zadanie tutaj jest właśnie przejaw tego zjawiska że możem to samo tylko że przeciw inny porządek Zobaczcie że jakby tu jakby na przykład w zadaniu tak jakby tu zamiast by zbiór d
Elementowy Zami prostu pary i na każdej wspó porównywalność to było dokładnie zadanie 12 teraz mamy tak nawę ciągi podzbiorów to że to że jest funkcją z n w podzbiory funkcja Toy CG i CG to prik funkcja makaron to pregowany kuskus i kuskus to pregowany makaron więc każdy taki f możemy o nim myśleć albo w ten sposób po prostu myśleć o tym że f to jest ciąg zbiorów częściowo porządku się dowodzi tak prostu z automatu tak No wystarczy że ten porządek tutaj jest
Częściowy tu może by tak naprawdę tu może być byle co A tu jest częściowy porządek to wtedy f od n zaczy f mniejsze równe g i a oni w ogóle tutaj zurow napis mniejsze równe będziemy pisać Tak żeby się odróżniało od normalnego mniejsze równe z tego z tego co wynika z tego wynika że dla każdego n Fn zawiera się w g a ponad zawiera się w związku z tym jeśli jeden zbiór jest związku z tym jeś jeden zbiór jest zawarty w drugim i drugi w pierwszym to to z natury rzeczy to to są równe zbiory czyli dla każdego jest takie coś więc f jest rów G No i tak samo jeśli tu jest ciąg porównywalności to dla każdego n Fn zawiera się w tym to się zawiera wca to jest rów
Świ elementy najmniejsze i największe najmniejsze to chba łatwo napisać poż z tego pn nie wyrzuci nie wyrzucił końców No to ten jest najmniejszy jak ja powiem że dla każdego n f n jest równe cały n to on jest największy więc one są jednym elementem minimalnym i maksymalnym z liniowości to to to widzimy że jak do porównywalności żądają od nas porównywalności na każdej współrzędnej to Wystarczy wziąć na dwóch różnych współrzędnych porównywalne w dwie strony jeśli f od 1 jest równe n i f od n jest równe zbiór pusty dla n większych równych 1 a z drugiej strony G od 1 jest równe zbiór pusty
F 2 to jest nic to zrobimy za dwójką No i tu tu zrobimy n no to nie ma bata to się nie porówna nie jest prw g bo f nie zawiera się w G1 oraz Nie jest prawdą że f jest większe równe g bo F2 nie zawiera G2 jak jest pytanie jak ten jak nas pytają czy czy jest liniowy okazuje się że nie potem pytają o dobroś porządku tam gdzie Ja się wychowałem to dobry porządek z automatu musiał być liniowy chyba że tu jest jakaś inna nomenklatura chociaż w sumie to nawet nie miałoby sensu bo jak ja mam porządek który nie jest mam porządek który nie jest liniowy
Czyli m takie eig nieporównywalne No to w ogóle to jest niepusty podzbiór No nie ma Jak mieć elementu najmniejszego bo w ogóle nie ma w nim porównywalności tak obcięcie porządku do niego to jest tylko to że f jest rów f g koniec nie ma nie ma żadnych innych elementów obcięcia relacji mniejsze równe do do tego czegoś zły bo nieliniowy czyli w czymś takim nie ma elementu najmniejszego po angielsku jest to jest tak że dobry porządek to nie order tyko co jest TR herezją gramatyczną to chyba się wzięło z czasów kiedy kiedy ten kiedy się mówiło że nie mó o porządkach uporządkowania to
Się mówiło że ordering i wtedy akt porządkowania ordering to dostawał jak to się nazywa Jak się nazywa ADB po polsku to się nazywa przysłówek jak ja określam rzeczownik to mam przymiotnik jak określam czasownik przysłówek No i jak się jest NAC gramatyczny to się to nie jest tak że ty czynisz dobro tobie coś idzie dobrze powinieneś mówić doing więc akurat się przyjęło że że dobry porządek Porządek to się nazywa well ordering albo mówi się że że jak jest jakiś zbiór
Porządkiem to się mówi że jest Nie mówi się że jest Bad order albo Evil order jak jak dopuszczenie skończone schodzenia i też i też to jest tak że po angielsku czasami się mówi natomiast zazwyczaj się mówi Total order czasami się mówi linar każdy się domyśli jak ktoś powi linar tymczasem dobra jak się dobr wczytać w treść zadania to to to jest to samo było Co to jest to samo co było na tych liczbach zespolonych Tak możemy ogólnie wprowadzić taką notację że jak ja mam X który ma swój porządek może być częściowy porządek xy i mam to produktowe porządków to jest z definicji produkt z
Z czymś takim I teraz to jest iloczyn kartezjański ja tutaj robię chciał być naprawdę purystyczny to tut napisał tensor albo cokolwiek żeby nie pisać iloczynu kartezjańskiego bo to jest prawie że iloczyn kartezjański natomiast złośliwcy powiedzą że nawiasy się nie tak układają Dlaczego ja tu bym chciał zrobić taki brutalny porządek produktowym chciał powiedzieć że x1 x2 jest mniejsze w tym porządku produktowym od y1 Y2 duż y żeby się nie mylił tylko wtedy to to co widzieliśmy X1 jest mniej rów po xemu to że się głupie napisa to miało być y1 To miało być x 2 to Y2 X1 jest mniejsze po x od x2 oraz y1 jest mniejsze po y niż y definicja Dlaczego ja używam OC kartezjański to jest prawie że kartezjański relacji teraz Spójrzcie ten ten ktoś tutaj No to to jest w definicji zbiór tych wszystkich par złożonych z pary x1 y1 x2
Y2 takich że x1 x2 należą Doo x oraz y12 nż do porządku yow Dlaczego teraz się na pisanie zależności przez para do relacji zamiast poprzednik relacja następnik że było widać że to jest po prostu przez przestawienie współrzędnych jak ja mam pary z par uporządkowanych to są prostu ciągi czteroelementowe to zawiera tyle samo informacji co ciąg czteroelementowy to nie jest to samo ma inaczej ustawione nawiasy natomiast no jest naturalna identyfikacja to przez taką identyfikację która bierze bierze cę a CD cę dwie pary i robi z nich pary AC bd to to jest identyfikowalne z
X1 x2 y1 Y2 takim mi że zachodzi to co jest tutaj napisane Toż to z definicji jest joczyn kartezjański to jest zbiór takich par których poprzedniki następniki jest para Ale to to jest mniej istotne zbiór takich par że poprzednik jest w czymś A następnik jest w czymś innym To to jest dokładnie tak tu jest w sensie porządków w sensie produkowania porządku a tu jest po prostu iloczyn kartezjański w sensie zbiorów WC ta notacja jest odrobinę nieścisłe przechodzi przez identyfikacje natomiast taką ilość nieścisłości jeśli jeśli te D są częściowym
Porządkami angielsku jest taka że to się nazywa i zazwyczaj się w skrócie jeś to są częściowe porządki to ten produkt też jest częściowym porządkiem zawarty w No zawarty w porządku leksykograficznym związanym z tymi dwoma że daje oczywi zrobić na więcej zbiorów tak samo możemy powiedzieć że jak ja mam ciąg X1 z jakimś swoim pierwszym porządkiem i tak dalej x z jakimś swoim porządkiem albo mogę w ogóle sobie zrobić funkcję z jakiegoś zbioru indeksów w
W co No w zbiór wszystkich zbiorów uporządkowanych ogólnie zbiór wszystkich zbiorów to trochę zbój No to możemy powiedzieć że zbiór wszystkich porządków na podzbiorach wszystkich podzbiorów wszystkich zbiorów uporządkowanych postaci postaci x jakiś swój porządek gdzie x jest pod zbiorem jakieś ambient przestrzeni No to taka funkcja No to nad każdym punktem tego j m porządek No to ja mogę powiedzieć że teraz taki produkt tego f to jest duży znaczek iloczynu kartezjańskiego to to jest dokładnie iloczyn kartezjański zbiorów f j być naprawdę purysta to powiedział że
To jest zbiór porządek i na tym jest porządek taki jaki Właśnie defini przed chwilą mam produkt należącym do J J tego porządku No i porównywalność jest współrzędnych to znaczy ciąg ciąg aj jest mniejszy równy niż ciąg BJ wtedy tylko wtedy gdy dla każdego j a j jest porównywalne w JM sensie do BJ dokładnie z robienie takiej notacji ucieka się od lud podstaw matematyki No to co my widzieliśmy j to był zbiór dwuelementowy albo elementowy albo albo cały N na przykład
Natomiast żeby zrobić porządek leksykograficzny to ja muszę mieć porządek na jci żeby zrobić taki produktowy nie muszę tu akurat J jest dwuelementowy tu akurat w zadaniu 14 które że zacząłem 14 tu jest tak że ja po zbiorę liczb naturalnych to ja mogę naturalnie utożsamić z podzbiorami zbiorów parzystych i pozorami zbiorów nieparzystych No to jest takie najbardziej trywialne możliwe utożsamienie to znaczy naturalnych mam przegrodę miałem to jakiś podzbiór tu są parzyste tu są nieparzyste więc każdemu pod zbiorowi Przyporządkuj parę złożoną z tego co ma po lewej stronie i tego co ma po prawej stronie czyli zbiór tu przechodzi na parę a przecięte z par a przecięte z n par a tu jakieś dwa zbiory powiedzmy
U i v taka para przechodzi na sumę siłą rzeczy rozłącz bo to są podzbiory dwóch rozłącznych zbiorów No i to jest częściowy porządek z tego ogólnego powodu z tego że to jest częściowy porządek No więc to jest wersja taka hiper abstrakcyjna odrobinę bardziej przyziemna jest taka że jak dla J od 1 do n mamy zbiór XJ ze swoim jym porządkiem to wtedy produkt XJ z porządkiem zdefiniowanym przez No tak jak tam jest napisane tak ciąg aj mniejszy rów niż ciąg b gdy dla każdego j a j jest po jemu mniejszy niż BJ jest jest częściowym
Porządkiem No i to dowodzi za każdym razem tak samo to znaczy po współrzędnych tak Toy fkk jeśli a mniejsze od B mniejs od A to wtedy dla każdego j a j mniej rów po J od BJ to mniej rów po J aj czyli tu dla każdego j a j jest równe BJ z faktu że ten J porządek jest porządkiem C tak b c to dla każdego J na JM poziomie są porównywalności po jemu Czyli teraz przechodniości tego porządku a j jest mniejsze równe po jemu od CJ z tego wynika że a jest mniejsze równe od c i już koniec dowodu tu tu jest to ogólne twierdzenie dla n rów 2 Pierwszy zbiór to są parzyste pierwszy porządek to jest po
Prostu porządek mniejs obcięte do liczb parzystych i tak samo x2 to są nieparzyste porządek drugi to jest porządek mniejszy równe obcięty do Przepraszam absolutnie kłami to nie jest zadanie to jest to zadanie WM jest zbi poow pot i tu jest zabieranie każdy podzbiór ma dwie współrzędne każda z tych pierwsza współrzędna to jest podzbiór Lic parzystych a druga współrzędna to jest podzbiór licz nieparzystych tak to to jest automatycznie stwierdzenia porząd produktowy No i to znowu jest takie głupie zadanie z tym największym najmniejszym tak no bo ja mogę po prostu wziąć z zbiorę pusty to jest najmniejszy i
Wi o Przepraszam ja źle przeszłem treść zadania to jest ogólna prawda A nie to praktycznie nic się nie zmienia teraz pierwsza relacja porządku To jest po prostu równość równość jest częściowym porządkiem bardzo małym ale jest No to jest właśnie Piękne to twierdzenie o produkowaniu porządków jest na tyle ogólne że nie bało się tego że ja tutaj kursora nie widać kursory jak nie aktywuje okna śmieszne W każdym razie tak jakby to było zawieranie to byłby porządek produktowy tu to jest ta to jest takie podzbiór porząd nie w porządku produktowym tak naprawdę można nawet napisać to to jest produkt porządku równa się i porządku zawieranie A można nawet napisać że zawieranie z lek graficzn pop parzystych i nieparzystych jest równe ten nasz
Porządek zadania su Dobra to nie jest suma rozłączna ale to jest to suma porządek produktowy x jest mniejsze równe y graficznemu gdy para jest mniej graficznemu gdy jest nierówność a nie czekajcie to nie jest tak tu musiał mieć zawieranie i tu razy pełna pełna relacja tak to Musia mieć pełny porządek to znaczy taki że każde dwa i ten wtedy nie jest porządek tak u nas ten ten śmieszny porządek to
Jest do tu napiszemy że zbiór takich parę zbiorów że a takich par złożonych z par zbiorów A1 B1 a2 b2 po prostu takich że a1 jest właściwym podzbiorem A2 ten już nie jest porządkiem tu jest na to jest jno możemy zrobić a teraz ten nasz porządek tym zadaniu Zobaczcie to jest tak że w ogóle jak są dwa jaką d pary które nie mają tego samego poprzednika toże to jeszcze najpierw jest potem jest parzyście nie ma znaczenia żeby nie zad zawier No ni parzystych jest to jest suma prosta tak to jest tak
Jakby Zac su prosta suma rozłączna po wszystkich a które są pod zbiorami n par jak już mam ustalony A to na drugim mam zawieranie tak Czyli tak naprawdę ja tutaj a pomnożone przez porządek zawierania na po zbiorach liczb parzystych to jest znowu odrobinę oszukany kartezjański prostu chodzi o to że wszystkie pary które są w tym to się ten porządek się rozpada na ile zbi A to ja tu wszystko co ja tutaj mam
To są zbiory postaci a z gwiazdką i coś i one są porównywalne jeśli B1 jest porównywalne z B2 ogólnie rozumienie porządku na ileś sposobów to nie jest element treści zadania ale ale warto wiedzieć No oczywiście to jest tak że właśnie jak to nie jest taki produktowy to z elementami element najmniejszego wić że nie jak był w którymkolwiek zbiorze to pozostałe są z nim nieporównywalne tak samo z największym najmniejszego i największego nie ma bo co bo
Każdy każda para postaci AB jest nieporównywalna No i jakoś zmienimy a jak najprościej zmienić a dopełnienie tak jak każda para jest czymś nieporównywalna to w szczególności kandydat element największy byłby z czymś nieporównywalny aego dualność przez dopełnianie to pytanie najmniejsze Minimal maksymal No myślę że minimalne są wszystkie postaci powiem że ab jest minimalny wy tyko wtedy gdy B jest rów zbiór pusty czyli najmniejszy No i teraz dlaczego jeśli jest jeśli B jest zbiorem
Pustym no to no to widać nie zajdziemy niżej tak jeśli B jest zbiorem pustym i jakieś a be z wąsem próbuje być mniejsze równe od naszego to to co to wtedy be z wąsem jest pod zbiorem z wąsem musi być równe a bez wąsem musi być pod zbiorem b który jest zbiorem pustym więc bez wąsem też musi być równy zbiór pusty a w drugą stronę Czy jeśli jest jedyne minimalne zbiorem pustym kontrapozycji b nie równa się zbiór pusty to wtedy istnieje bez wąsem który jest niepustym pod zbiorem nie pusty po prostu jest pod zbiorem właściwym istnieje bez wąsem takie i wtedy a bez wąsem jest mniejsze
Niż i maksymalny analogicznie Wedy gdy B jest całością całość to akurat się nazywała parzysta kst tak tak pamię jak mieliśmy ten porządek graficzny to było ś takich placków i one były po kolei tu jest ś placków i każdy jest w ogóle w innym świecie te placki są nie porównywalne to się nazywa su suma rozłączna porządków dobrze teraz Mówimy że x jest mniejsze od y lub a lub są w tym samym łańcuchu takim poach liczby pierwszej i OK
Ja twierdzę że jak ja zrobię takie pojęcie mam ciąg może być indeksowany zbiorem mam zbiory ze swoimi porządkami zrobiliśmy produkt teraz zrobimy Pojęcie które jest w pewnym sensie dualne ale nie chc się teraz tego tłumaczyć to znaczy sumę Rozłącz sum rozłącz to w oznacza każde z nich są częściowo uporządkowane no powiedzmy od 1 do n może być nieskończoność Dlaczego to się oznacza takim wiadrem to nie jest wiadro to odwrocone pi Są tacy którzy Jak piszą iloczyn kartezjański rozciągnięty po zbiorach to to piszą pi SK Zarezerwowaliśmy zor napisem Pi ma sporo sens pruży syb kartezjańskiego żeby się nie myliło tego się też często używa węc tu się używa tego samego symbolu tyko że do góry nogami suma rozłączna to jest najgłupszy możliwy sposób złączenia porządków to
Znaczy to jest to jest rozłączenie sumy tych tutaj to znaczy ja mówię Dobra to są częściowe porządki dobra Zrobimy taką po prostu sumie rozłącz taką sumę rozłącznego tak jak ja mam ich przecięcie się w jednym potem chciał napisać zbi ilorazowy to pojęcie potem to zadanie prawie że to pojęcie plus je modyfikacja Powiedzmy że X1 są rozłączne jak nie są interesuje typ porządku jego niezmiennik izomorficzny to dowolne zbiory możemy zmusić do być rozłączny na tych samych elementach a teraz a teraz są sztucznie łączn No to roz jest co się wydaje to
Jest po prostu zbiór sumy x sum porządków Czyli jak X który jest sumie rozłącznej y to wtedy x jest w w tym porządku mniejszy od y gdy xy należą do istnieje takie jedno J że xy należą do do XJ oraz x m rów po J y to co widzieliśmy przed chwilą to była suma rozłączna w naszym zadaniu jest prawie to samo w naszym zadaniu jest tak
Ja mam j i od niej odchodzi ciąg 2 4 8 i tak dalej tu jest porównywalność potem na przykład mam trójkę tu odchodzi ciąg tak I tu jest porównywalność mam siódemkę A tak same liby pierwsze a cała reszta liczb naturalnych które nie są podcz pierwszych to są punkty izolowane czyli jak ja powiem że 1 PP kwadr i tak dalej z porządkiem efektywnie to jest porządek podzielności to jest częściowo uporządkowany to jest porządek podzielności obcięty do potęg liczby p czyli oznaczmy go tak takie coś to wtedy ten nasz porządek w
Zadaniu to jest po prostu suma tych Tutaj jest tak jak suma rozłączna tylko że jeszcze są sklejone jedynką i tyle żadnych innych porównywalności niż te które są tutaj nie ma dobra teraz ch udowodnić że on jest porządkiem częściowym No to x jest mnie rów y y jesty liby pierwsze jeśli nie istnieje p takie że x jest jakieś p k y rów l no to wtedy z automatu x jest rów y nie ma żadnego z tych konkretnych uporządkować rów y istnieje takie p No
Więc istnieje takie p albo po prostu x jest równe y tak ten porządek x jest mniejs x jest rów y albo k jest mniejsze od l oraz x jest równe y to jest ten drugi albo l jest mniejsze od k więc jeśli x nie jest równe y To musiały zachodzić to i to jednocześnie No i to tych dwóch się nie da pogodzić już jak x jest mniejsze niż y mniejsze niż z to jeśli x jest no No i znowu patrzymy na to czy one są na tej samej drabinie z potęg z potęg p i teoretycznie są przypadki ja bym by napisał że co napisał chamskość to rozbija na dwa
Przypadki tu jest x y są potęgami tego samego p tu tu zrób że nie są jak nie są to x jest równe y jak x jest równe y to to x skoro jest równe y jest mniejszy od z udowodnione teraz x jest równe P do k y jest równe P do L to teraz znowu być może z jest potęgą p być może nie jest jeśli z nie jest oraz Y jest mniejsze równe z to to implikuje że y jest równe z co implikuje że x jest mniejsze równe niż y który jest równy z czyli tak czy tak x jest mniejs rów z A jeśli z jest na tej samej drabinie z faktu że x jest rów y wynika że K jest rów z faktu że y z wynika że w związku z tym k jest
Rów k jest m rów m czyli albo x czyli tak czy tak x strasznie jest to masło maślane No natomiast oczywiście można tym było myśleć w terminach tej sumy rozłącznej porządku tyko ta jedynka Trę brzi Tyle że tu mam porządki trywialne tak elementy mamy a tu mamy prawie że rozłączne porządki które się stykają tylko Jedynce No i suma rozłączna porządków jest porządkiem jak jeszcze ona nie jest dokładnie rozłączna jak ona nie jest dokładnie rozłączna i tam się dzieje jedynka zaraz czy jestem w stanie prostu powiedzieć że weźmy to i podzielmy przez jeże zróbmy takie coś wtedy dokładnie tak jak napisaliśmy
Noac Nie chcę teraz mówić o tym że Rob zbi wspólną jak jedyne miejsce w którym tam się może psuć przechodniość i ta antysymetria to jest jak zatrud jedynkę i to jest właśnie takie wycinanie przypadków jak tutaj czyli czyli mamy obrazek jedyn udaje element najmniejszy No ale zaraz to te wszystkie tutaj jeszcze są te wszystkie są ni porównywane z niczym jakikolwiek element nieporównywalny z niczym to mi zabija w ogóle szansę na element maksymalny minimalny 2 x 3 nie porów walne z całą resztą z wyrzuconym 2 r
3 więc nie ma ani maksymalnych ani zaczy nie największego an najmniejszego Minimal toiem widać liczby pierwszej tylko jedynka jest minimalna bo każdą inną potęgę liczby pierwszej zbijemy w dół i będzie mniejsza 1 oraz n minus z wyrzucony potęg liczb pierwszych tak ten po prostu jest minimalny bo się przekonaliśmy te są izolowane każdy tut jest porównywany tylko z samym sobą No maksymalne to dokładnie tak samo Każdy jest izolowany więc jest minimalny i maksymalny tak na tych na tych ścieżkach SP potęg liczb pierwszych oczywiście nie ma
Maksymalnych bo każdy może pomnożyć przez swoją liczbę pierwszą No ci nad sobą nie mają nikogo bo są nie są z nim porównywalnie to jest minimalne To to napisaliśmy c jest koniec Tak to jest koniec to chyba tyle