Relacje równoważności — zadania z logiki na IS AGH, zestaw 4, cz. 1
Zadania od widzów⏱ 2 h 14 min
Pierwsza część zestawu 4 z logiki na Informatyce Stosowanej AGH. Gwóźdź programu: relacje równoważności i ich trzy równoważne charakteryzacje, klasy abstrakcji, a potem porządki częściowe, izomorfizmy porządków i gęstość.
W tym nagraniu
Relacja równoważności, podział zbioru i równoważność „f(x) = f(y)”
Klasy abstrakcji: przystawanie modulo, proste y − x = const
Kiedy relacja nie jest równoważnością – psująca się przechodniość
Pierwsza część zestawu 4 z logiki na Informatyce Stosowanej AGH zaczyna się od miniwykładu o relacjach równoważności. Kluczowa jest równoważność trzech opisów: relacja zwrotna, symetryczna i przechodnia; podział zbioru na rozłączne klasy; relacja postaci „x ~ y wtedy i tylko wtedy, gdy f(x) = f(y)” dla pewnej funkcji f. Ostatni opis — klasy jako przeciwobrazy punktów — jest w nagraniu osobno uzasadniony.
W zadaniach 1a–1l sprawdza się konkretne relacje: klasy abstrakcji przystawania modulo n, proste y − x = const na płaszczyźnie i przykłady, w których relacja przestaje być równoważnością, bo psuje się przechodniość.
Zadania 2–9 przechodzą do porządków częściowych: diagramy Hassego, izomorfizm porządków, porządek odwrócony, porządki gęste (między dowolnymi dwoma różnymi elementami leży trzeci) i porządki na ciągach skończonych. To najdłuższe nagranie z serii logiki — wygodnie przeglądać je po rozdziałach, bo każde zadanie ma własny znacznik czasu.
Rozdziały
Kliknij czas, żeby przewinąć nagranie do wybranego fragmentu.
Miniwykład o relacjach równoważności
Zadanie 1a
Zadanie 1b
Zadanie 1c
Zadanie 1d
Zadanie 1e
Zadanie 1f
Zadanie 1g
Zadanie 1h
Zadanie 1i
Zadanie 1j
Zadanie 1k
Zadanie 1l
Zadanie 2
Uzasadnienie charakteryzacji relacji równoważności przez przeciwobrazy punktów
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. (11400 słów)
Widzimy tutaj Pandę Która właśnie wygrała walkę o pudełko z whisky który trochę po zasłaniał kamery i sobie poszedł a my rozpoczynamy walkę z zadaniami z logiki gwoździem programu będą relacje równoważności No i chciał zrobić krótki rap bo zgaduję że na wykładzie były dwie równoważne charakteryzacje nie było trzeciej jak jedną przyjmiemy za definicję to dwie pozostałe są twierdzeniami będę używa takiego Shu którego tak nawę używa się przez cały czas w matematyce To znaczy zamiast pisać że para należy do relacji to piszemy x r jako znaczek relacji y to jest tak naprawdę to to jak to jest zakodowane w tym kodzie maszynowym matematyki a to jest tak jak się o tym myśli jak się zazwyczaj pisze na przykład relacja mniejsza to jest jakiś podzbiór r r r No i generalnie ręka nam się zmęczyła gdybyśmy pisali 23 należy do relacji mniejsze Tak Zamiast po prostu d znaczek relacji 3 by the
Way kiedyś miałem okazję pomagać Z matematyką uczniom z pewnej szkoły prywatnej z pewnego kraju który nie jest polską i oni mówili że w takim na takiej platformie owej im co jakiś czas wypluwa że odpowiedź jest zła i w ogóle nie rozumieją dlaczego po jakimś czasie okazało się że w tej szkole powiedzi im toale żey na No oni powiedzieli No że się pisze że 5 jest jest jakie jest większe od 7 Dlaczego Dlatego że s jest takim krokodylem który swoją paszczą pożera piątkę i literalnie trójka studentów przeszła przez przez szkołę średnią i pojawiła się w szkole wyższej myśląc że tak się pisze pi mniejs od si to naprawdę byłoby śmieszne gdyby nie to że było prawdziwe tymczasem relacja
Równoważności to jest taka najsuchsza definicja taka w której niby nie widać bezpośrednio o co chodzi ale ona służy do tego żeby warunki które są postawione były najprostsze możliwe do sprawdzania już twierdzenie kłych zało daje mocną tezę to potem nasza robota jest prostsza potem wystarczy że będziemy sprawdzać słabsze założenie i do tego służy to jako definicja w ogóle to jest zabawne zjawisko językowe że po angielsku są osobne słowa relation i relation A my my jedno i drugie rzutuj na relacja Bo my nie mamy tak tak samo działające mechanizmu tego suf on działa tak że na przykład jest jest jakiś rzeczownik który jest czymś co coś robi na przykład craftsman i potem akt robienia tego czegoś To jest właśnie to SH właśnie craftsmanship to jest rzemiosło a a my to znaczy przynajmniej to tłumaczenie matematycznego relation na relacja to to było od zawsze tłumaczenie relationship na relacja a nie na związek
To jest przynajmniej z mojego oglądu mojej bańki kulturowo językowej to jest kwestia ostatnich 10 lat także tak język ewoluuje kto pomyślał różnica między nam naszym językiem a językiem g Anonima to jest całka po czasie z ewolucji języka anyway narzucamy trzy warunki wyobrażamy sobie to jako jako takie coś że że elementy x się trzymają za łapki tu jest napisane że x się trzyma łapkę z samym sobą to że jak x y to y z x w szczególności jak y z x to też x z y tak naprawdę Row ważność wystarczy sprawdzać impac w jedną stronę no i prch odnieść tak jak x się trzyma zki z y y z z to tak duchowo x też z X to nazywa też natomiast już wymyśliliśmy Polski termin zwrotna i To akurat jest dokładnie tak samo jak to działa w gramatyce to co znaczy to co po angielsku nazywa się ref pron na przykad czyli zaimki które odnoszą
Się do tego samego kto tak jak ja powiem że i admire tak to jest ja wykonuję jakąś czynność ona się odnosi do mnie i to jest ta zwrotność to po angielsku się nazywa tak samo w polskim opowiadaniu po polsku o angielskiej gramatyce to się nazywa zimek zwrotny symetria jest sam wyjaśniająca się Trans jest takie że jak jedziemy ciężarówką tranzytowa x do y i potem z y do z to Dojechaliśmy z X do z i dlaczego te trzy warunki akurat są fajne dlatego że jest twierdzenie W założeniach mamy relację równoważności na jakimś zbiorze r jest znaczkiem a RR jest racją równoważności może piszmy duże r tak jak jest w częściach zadań żeby się nie myliło to wtedy istnieje rozbicie xa na klasy abstrakcji tak tak żeby miał pozory zdania wtedy
Wtedy jest rodzina zbiorów chcemy Nie chcemy tego zrobić w zbyt szczególny sposób więc te rodziny zbiorów x jest rze istnieje taka rodzina powiedzmy Ai po i przebiegającym jakiś zbiór indeksów taka że taka że co Po pierwsze te zbiory są rozłączne i różnego od J po drugie suma wszystkich to jest dokładnie x i po trzecie x jest w Eze Z Y wtedy tylko wtedy gdy gdy są w tym samym z tych zbiorów czyli ten zbiór x się dzieli na na jakieś takie kawałki także każde dwa każde dwa elementy w tym samym kawałku są połączone r natomiast żadnych dwóch z różnych kawałków się nie łączy r istnieje takie i że x y oba należą do
A ponadto z dowodu tego twierdzenia tak naprawdę wynika że rodzina tych wszystkich zbiorów to jest rodzina wszystkich zbiorów które ja uzyskam przez branie klasy abstrakcje konkretnego x klasa X w tej relacji to jest to co się wydaje to jest to że odnajdujemy x gdzieś tutaj i wtedy mówimy że ten kawałek w którym on jest to się nazywa klasą X gdzie klasa X to jest dokładnie zbiór wszystkich y że x ry tu są wylistowane Wszystkie zbiory z tego rozbicia każdy pojedynczo tu jest strasznie nadmiarowa notacja każda klasa w tym napisie tutaj pojawi się tyle razy ile ma elementów natomiast tu jest zbiór zbiór jest strukturą danych która nie nie czyta ani kolejności ani powtórzeń to są klasy abstrakcji bo w ogó abstrahować to jest odejmować i
To że nam się wydaje że abstrakcja to jest Takie wchodzenie na wyższy poziom to owszem to jest prawda natomiast etymologicznie w ogóle geneza tego pojęcia jest taka że jak w ogóle ludzie zaczęli myśleć o sposobach w jakich myślą pojęcia to oni tak nawę odejmują od nich jakieś jakąś ich szczególną realizację i zostawiają sedno No jak na przykład jak zunifikowanie jabłka przez ziemię i przeciąganie Ziemi przez słońce to była w jakimś sensie abstrakcja tu mieliśmy dwa obiekty które były konkretne tu mamy dwa inne obiekty które są konkretne wyabstrahować i w ten sposób też można o tym myśleć że klasa abstrakcji x to jest zapomnienie jakieś części informacji o x jeśli mamy X w X trzymał jakąś informację to ona się składa tak napraw z dwóch etapów jedno To jest wybór klasy abstrakcji a potem gdzie jestem w tej klasie ta klasa abstrakcji to jest to co
Zostaje z x po odjęciu tej drugiej części informacji oczywiście archetyp czegoś takiego to jest produkt archetyp jest taki x to jest produkt a r b Iloczyn kartezjański po polsku ja powiem że jak mam X1 to jest A1 B1 x2 to jest a22 X1 w relacji z x2 gdy czasem jest konwencja taka żeby rel oznaczać r czasami taka że Falk zazwyczaj Falk się oznacza relacje które są rż właśnie równoważności to to to jest tyko znaczek gdy to ja chciałbym powiedzieć że gdy B1 jest równe B2 No i obrazek jest taki że ja mam dwie informacja o xie jedna to jest jaką ma pierwszą współrzędną a druga to jest to
Jaką ma drugą współrzędną tak tu jest zbiór a i tu jest zbiór b jak ja mam jakiegoś xa tutaj o tu jest jakieś A1 tu jest jakieś B B1 I to co ja robię Ja utożsamiam te x które mają to samo b czyli to jest jedna klasa abstrakcji bo każde takie d x tutaj mogą mieć różne A oczywiście chciałem zrobić odwrotnie Chciałem powiedzieć że jest generalnie sama idea teraz jak x jakiegoś to on może mieć inne b natomiast wszyscy tutaj każdy jeden z drugi jest w tej w tej relacji One wszystkie mają to samo A i to jest jedna klasa abstrakcji zbi klas abstrakcji jego można utożsamić zbiorem A WM klasa x jeśli x jest rów
AB to wtedy klasa X w tej relacji to jest dokładnie zbiór wszystkich rzeczy postaci ustalone a i Cokolwiek co przebiega zbiór b zbiór a nie jest zbiorem abstrakcji takim naturalnym enumerator abstrakcji jakbym był naprawdę narwańcy od teorii kategorii to wam zaczął rysować że to jest rzutowanie na zbiór a i i ten i to ma jakąś własność uniwersalną i i coś tam ogólnie jak wam ktoś chce opowiadać o teorii kategorii to zazwyczaj warto go posłuchać i Zazwyczaj to będzie kosztowało ileś wysiłku intelektualnego który zazwyczaj się opłaca ale może jeszcze nie teraz w ogóle to twierdzenie tutaj to jest zrobione tak w trybie implikacji mam Niech będzie dana relacja wtedy istnieje taka rodzina to jest twierdzenie 1 to możemy zrobić przy okazji twierdzenie us1 jeśli rodzina Ai
Spełnia dwa warunki z tego z tego twierdzenia tak pierwsze i drugi to znaczy to jest rozbicie naszej przestrzeni z twierdzenia 1 to jeśli ja zdefiniuje relacje w ten sposób adaj do jednego z nich to tak zdefiniowana relacja jest równoważności Czyli każda relacja równoważności to jest rozbicie i każde rozbicie produkuje relacje równoważności to jest odpowiedniość 1 do je między relacjami i rozbici potem gdybyście mieli taki naprawdę naprawdę dopak przedmiot dyskretna tam byłoby na przy zliczanie Ile jest na danym zbiorze liczenie funkcj tego ciągu patrzenie że tak każda permutacja zadaje relacj równoważności przez orbity To wszystko są fajne rzeczy Jak się liczy Akurat tutaj tylko czysto jakościowo No to powód dla którego chciałem o tym opowiedzieć jest taki że
Jest twierdzenie 2 i ona też jest w takiej formie w jedną i drugą stronę to znaczy ienie 2 jest trywialny to znaczy że jeśli jeśli Falka jest na na X to jeszcze jedn rzez chciał zrobić rożno to są k abstrakcji jescze r to jest dokładnie ten nasz zbiór dzielenie bierze się z tego archetypu jak informacji Więc jak liczność x na początku to była liczność a raz liczność b relacja nam ukradła więc każdy X w X
Niósł ze sobą tyle informacji relacja nam ukradła b informacji i zostaje z tego a czyli AB prz b stąd stąd ten znaczek iloraz wtedy masło maślane że powiemy że wtedy projekcja związana z tą relacją r z X w X podziel przez r takie coś zdefiniowane wzorem PR x rów klasa X jest jakaś tam funkcja wtedy takie coś po jeszcze że jest surjekcją co jest doś oczywiste No bo każda klasa jest klasą któregoś elementu jak jestem klasą to jestem niepusty tu bym chciał że zbiór pusty to z dowolnym innym
Niepustym miałby puste przecięcie i by się nie Wait w ten sposób a tak jeśli mam takie coś 012 to się nazywa kanoniczne dozorowanie ilorazowe jeś rac równoważności to trywialne twierdzenie jest takie że x jest w relacji z y wtedy tylko wtedy gdy projekcja z tą naszą relacją od x jest równa projekcji zą y jest stwierdzenie że wpadają w te samą klas równoważności abstrakcji ale twierdzenie min2 jest dużo lepsze każ że każda funkcja produkuje swoją równości przez patrzenie kogo n skleja to znaczy niech f będzie jakąś funkcją z X powiedzmy z to jest absolutnie byle jaka funkcja to wtedy
Falka f zdefiniowane przez x Falka fy wtedy tylko wtedy gdy projek właśnie gdy f od x jest równe f y jest relacją ważności każda funkcja przez powiedzenie kogo ona skleja produkuje relacje równoważności i każda relacja równoważności bierze się takiej procedury być może czasem się zdar że tej funkcji się nie da napisać wzorem jeśli ten zbiór Il razowy jest przedziwny natomiast bardzo często to jest tak że te funkcje tutaj można Albo wziąć tę albo jakąś inną która działa tak samo Zauważcie jeszcze że to daje taką baby wersję tego twierdzenia o rozkładzie przekształcenia liniowego na powied Nazwijmy ją z X do z mogę ja mogę Saka mogę zrobić
Tak tak jak było tam ja mogę x najpierw podzielić przez relacj związaną z ty informac którą niszczy f potem na każdej klasie abstrakcji tej relacji f jest stały więc tu mam dobrze zdefiniowanego f podzielonego przez Falka f to idzie do obrazu f ob jest pod zbiorem tak tu jest injekcja tu jest surjekcja z natury jest twierdzenie o tym że każda funkcja się rozkłada na na trzy prostsze rzeczy że najpierw najpierw Zapomniałem trochę informacji potem idziemy do innego świata a potem tylko idziemy idziemy injekcja oczywiście można powiedzieć że tu jest injekcja w tym bardziej widać o co chodzi Dobra to po tym przy Długim wstępie bierzemy konkretne napisy i patrzymy czy
Spełniają warunki albo czy spełniają którąś z tych charakteryzacji bierzemy zadanie pierwsze i punkt A to jest co mamy zbiór liczb parzystych i relacja to jest relacja przystawania Modul 3 No to jak dla mnie to jest to jest równoważności przystawanie Mod dziedziczy na liczbach parzystych naturalnych to ona dziedziczy byci różności całego z jakby ktoś nam bardzo kazał to możemy albo powiedzieć że sprawdzamy po kolei albo zrobić taką śmieszną funkcję jak ja mam tu nasz zbiór x w nim jakiś mały x to ja z niego zrobię x Mod 3 to 0 No to jak ja to znowu to nazwę Fem No to gołym okiem widać że w tym zadaniu x r y wtedy tylko wtedy gdy FX jest rów f y 3 dzieli różnicę liczb wtedy tylko wtedy
Gdy dają te samo resztę z dzielenia przez 3 czyli z automatu że jak szukamy klas Spójrz na to jak mamy to generowanie z funkcji myślimy o tym w ten sposób że mam zbiór i tu mam in zbiór tu są jakieś jakieś wartości jakieś punkty które mają na jest s tu mam jakieś inne punkty na których jest inna wartość tu mam jeszcze jakieś inne punkty i ten obrazek mówi tyle że myślimy o f w ten sposób że najpierw on mruży oczy tak żeby to był jeden punkt to drugi to trzeci potem potem to odwzorowanie zamienia te Punk punkt ten duży punkt na ten i ten duży punkt na ten A potem te trzy punkty mówi że jak jestem pod zbiorem to funkcja i x
Rów x idzie ze mnie w nad zbiór czyli obrazek jest taki że tu jest x Tu jest z tu jest f tu jest to odwzorowanie ilorazowe tu jest zunifikowana klasa wszystkich które miały czerwoną wartość tutaj klasa tych które miały zieloną tutaj k ty które miał różową teraz jest moje zredukowane f blob jest punktem w tym zbiorze i przyporządkowuje wartość tego BL i tem t no to jest Prost identyczność ten idzie na siebie ten idzie na siebie ten idzie na siebie sztucznie zwiększoną przeciwdziedzinę więc że abstrakcji w teac są poci przeciwobraz Punk jest
Zależności oraz klasy abstrakcji tego czegoś są postaci f minus pi od z gdzie z przebiega nasz zbiór do któ do wszystkiego każdy punkt jest w czymś przeciw obrazie bo każdy punkt na coś przeszedł są rozłączne różnych zów No bo każdy punkt ma dokładnie jedną wartość f to przez przym tego spojrzenia tutaj to jest jeszcze bardziej oczywiste klasy to jest f do minus pi od 0 f do minus pi od 1 pi od 2 czyli to jest zbiór tych x które są liczbami parzystymi że x przystaje do zer 3 czyli Innymi słowy zbiór tych 2k gdzie k jest naturalne oraz 2k przystaje do zera Mod 3 dwójka nie pomaga nie przeszkadza więc
To jest dokładnie zbiór rzeczy postaci 2k gdzie k przystaje do zer Mod 3 No czyli z dwukrotności rzeczy podzielnych przez 3 czyli tak naprawdę to jest zbiór sześciokrotności naturalnych tutaj min Pi 1 tak samo tylko trzeba bardziej uważać z dzieleniem to jest tak samo jak tut możemy zrobić do jed czyli Czyli co Czyli takie 2k że 2k przystaje do 2 r 2 mod 3 No czyli 2 raz k-2 ma się dzielić przez 3 3l + 2 w zależności od tego czy macie zer naturalnych czy nie To akurat przyjmuje że mam czyli to jest zbiór napisu postaci 6 l plus 4 dwa
Razy a zaraz a tak to jest dobrze Ja po prostu szuk dziury w cały tak to s doład liczby które się dzieją przez 3 przez 2 oraz przez 3 dzieli się przez 2 i PR Mod 3 MOD 3 to jest 0 a 4 jest 1 No i dokładnie tak samo tak samo się patrzy na przeciwobraz dwójki tak robi się takie same rachunki wychodzi nam że to są rzeczy postaci 6l plus 2 można to było zrobić na 100 innych sposobów można było powiedzieć że zbadajmy resztę Mod 6 bo tylko od resz przez 2 oraz przez 3 należy przynależność do X oraz przynależność do klasy abstrakcji jak k w proste Zan dużo rozwiązań b różnica równa się 2 No to to nie pójdzie to nie pójdzie na wszystkie możliwe sposoby to zaprzecza każdej z tych trzech własności
Które mieliśmy sprawdzić w punkcie B przede wszystkim jest tak że nieprawda że x jest w relacji z X nie takie coś bo X min X nie równa 2 nie ma symetrii bo X min y rów 2 forsuje że y min X nie rów 2 i tak samo nie x ry y rz to nie implikuje x rz bo bo co bo x z to jest x y tak to ma być pierwsze minus drug tak min y min z No i to jest 2 min 2 czyli 0 to jest strasznie głupia relacja to są oczywiście ktoś powie że to jest krawędź w grafie chromatycznym no znaczy w tym w tym grafie którego się używa do zfin liczby chromatycznej natomiast nie to to bardzo
Nie jest to tak tak ABS jest złoś napisane jakby tam była dowolna liczba zamiast dwójki to byłby fałsz to by nie był dwójki znak nie ma znaczenia 2 dzi x plus y Wedy tyko wtedy gdy 2 dzi X min y od tego miejsca do tego po prostu zmodyfikował się o liczbę parzystą która nie zmienia podzielności prze No więc to jest przystawanie modula tak to jest przystawanie Modul na sam czyli nasza relacja r to jest dokładnie przystawanie Modul 2 No to klasy wiadomo jakie są w przystawanie 2 są parzyste nieparzyste symetryczne to to nie jest 1 kwadr jest mniejs niż 2 kW ale już nie jest prawdą że 2 kwadrat jest mniejs niż 1 kwadrat więc nie jest
Symetryczna więc nie jest ważności tu się zaczna coś ciekawego wielomiany stopień różnicy ma być co najwyżej 2 No to ogólnie warto napisać warto sobie napisać że jak ja mam jak ja mam Izę powić Dobra to może kiedy indziej W każdym razie to jest relacja ro ważności jak mam wielomian stopień takiej różnicy w zależności od tego kogo pytać powie zer drugi minus nieskończoność widziałem tacy takich którzy mówią że stop wy zer jest powoduje że jest mniej pisania naturalną konwencją jest że stopie nieskończoność bo my chcemy
Trzymać wyryte w Kamieniu to że stopień p r q W normalnych warunkach to się końc x do 5 x do jak wymnożyć q jest Rów 5 no to p r q ma ten sam najwyższy wykładnik tu się nic nie zmienia więc stopień wiel zerowego jest stałego jest zer ale jak ten wian stały złośliwie jest wszędzie równy zer no to wtedy stopień p razy zerowy To zawsze musi być zer Niezależnie od tego jaki p był duży węc jedną taką liczbą żeby ona zwracała właśnie zer tylko musi być wyjść taki jak wielomianu zerowego więc jedną liczbą która zwraca 100 plus ona rów ona jest minus nieskończoność więc konwencja jest taka że stopień wielomianu który bierze x i zwraca 0 jest równy minus nieskończoność tymczasem w naszym zadaniu no bez wątpienia stopień różnicy jest mniejszy rów 2 stopień różnicy wielomianów to jest
Stopień minus różnicy wielomianów q min p No i teraz najtrudniejsze stopień p minus to jest duże r to mogę tak napisać p min r równa się zatrudni MID stopień su niż maksimum stopni czasem będzie mniejszy min X do 7 plus x do 5 x stopnie są 7 natomiast ich stopień jest równy sumie jest równy 5 oczywiście nie dostanę x z większym wykładnikiem niż ten maksimum min q q min r więc jak w szczególności maksimum dó jest mniejsze równe niż ich niż ich suma Albo nie inaczej tak jeśli p jest w r z q i q jest w r z R
To i teraz już mam to Założ mniejszy równe 2 ten stopień ten stopień jest mniejszy równy 2 No i maksimum z dwóch licz mniejszy równy 2 jest mniejszy równy 2 świetnie Czyli pokazałem że ta relacja spełnia warunki i Nie jestem ani krok bliżej do pokazania klas abstrakcji No więc jak o tym myśleć należy o tym myśleć tak że nasza relacja zapomina informacj o tym co się stanie jak dodany wielomian jak dodan tak jak dodam wielomian co najwyżej kwadratowy czyli jak ja mam jakiś wielomian który tu ma jakieś anx do n plus plus plus plus a3x s No i teraz plus A2 z wąsem x kW + A1 z wąsem x+ A0 No to to jest w tym erze bo różni się o składnik co stopnia co najwyżej 2 to jest w tym erze z czymś takim Zobaczcie
Zapominanie informacji jest o pierwszych o tych najmniejszych trzech składnikach WC można tym myśleć W ten sposób że mam funkcję która bierze wielomian to by akurat wymiany od zmien ale to wszystko jedno Jak ona się nazywa w co w ciągi to są ciągi które się terminujący składników a niez potęgowe No to to moja funkcja f od wielomianu właśnie takiego to jest zapominamy pierwsze trzy wyrazy po prostu spisujemy a3 a4 bla BL bla an i potem same przeciwobrazy tej funkcji to są
Klasy żadne wielomiany które nie mają tego początku tutaj to nie są w tej relacji z powodów innych niż po prostu że są równe każde dwa takie wielomiany które są w erze to mają różnic stop najwyżej ale zaraz ich różnica jest zaczy się od TR to po prostu każd współczynnik przy wszystkim większym od dwóch musi być równy zer klasy to są dokładnie takie napisy zbiór takich rzeczy ze zmiennymi A2 z wąsem A1 z wąsem A0 z wąsem No i już w fie nas
Pytą wię podnie tylko że zamiast małego stopnia mam mie w współczynniki tylko parzyste tut w ogóle nie myślimy wielomianach tutaj myśl prosto o ciągach nie ma mnożenia wielomianów nie ma niczego niczego inherentnie wielomianowego ten pierścień wielomianów zmiennej t no to to jest to samo co co to co takie c z czyli a nawet nie to są ciągi indeksowane liczbami naturalnymi które terminu się od pewnego miejsca to znaczy są zerem pewnego miejsca o wartościach całkowitych czyli zbiór takich napisów jak a a1 a2 i tak w którymś momencie uderzamy w zero jak po wszystkich możliwych A0 an całkowitych no
To no to tłumaczy na ciąg współczynników a tu nas pytają o różnice które mają być parzyste czyli Czyli co Czyli tak naprawdę jak się zrzutu je na bit tutaj to jedna klasa to jest ustalenie parzystości tak tak No to ja twierdzę że te klasy to będą po prostu wszystkie wielomiany postaci dany wielomian plus wielomiany współczynnikach parzystych tak Na to wygląda takie coś dla A1 od A0 do an które są zerem albo
Jedynką bo tak porównuje ja mę że dwa są w klasie współczynniki odp modulo 2 to to jest to samo co współczynniki od q Modul 2 wic moje klasy co ja mogę osiągnąć mogę osiągać ciągi z klas to c krzyz czy dokładnie takie potem mogę modyfikować wian który ma wszystkie współczynniki parzyste g x r y Jestm nieparzysta No to jak dla mnie to po prostu znaczy tyle że x jest
W z y wtedy tylko wtedy gdy obaj zbioru nieparzystych No to jak dla mnie to jest rż No bo ona tak nawę skleja nam skleja nam wielkie mnóstwo liczb w jedną klasę Tak wszystkie nieparzyste się lubią za wszystkimi inmi nieparzystymi żadna liczba parzysta nie będzie z nikim A już rozumiem ona nie jest zwrotna 2 r 2 jest równa 4 D nie jest w tej relacji z dwójką po prostu tyle
Dobra Tu są takie pary liczb że iloczyn jest kwadratem i to jeszcze liczby naturalnej to wietrze podstęp No bo Spójrzcie to że ocz jest kwadratem liczby naturalnej to się wydaje jakby ten jakby to nie mogło być dobrze bo to jest iloczyn a nie iloraz ilorazy się stackują jak ja miał x PR y r y PR z to byłoby x PR z tu akurat iloczyn i ma być liczbą naturalną do kwadratu No to co ja twierdzę ja twierdzę że można poznać czy x y są w tej samej klasie przez badanie parzystości wykładników ja twierdzę że x Y wtedy tylko wtedy gdy dla każdego p które jest liczbą pierwszą zliczanie p w rozkładzie x plus zliczenie p w rozkładzie y to jest dwukrotność czegoś tak na tym polega bye kwadratem że moje wykładniki Przy liczbach pierwszych są dwukrotności dla pewnego
T Czyli po prostu ma być tak że to jest parzyste Czyli po prostu ma być tak że zliczanie p w X Ma przystać Mod 2 do zliczania p w y No to d każdego p tak pokazaliśmy znowu funkcję biorę x i robię z niego ciąg patrzcie na moje wykładniki Przy liczbach pierwszych ale po drodze jeszcze preprocessing to zrob 2 jak to jest f to xy rż z tym że więc to jest rel równości z klasami jak będzie z klasami będzie tak że każde d mają się różnić w iloczynie o jakąś liczbę która nie jest kwadratem ale myślę znowu nam przychodzą
Przeciwobrazy z pomocą prostu jakieś CGI więc dla każdego Dla każdej funkcji powiedzmy g z liczb pierwszych w 01 tak to jest bez zer takiej że G od P jest równe taki że g p jest równe to występowanie liczby p w rozkładzie na czynniki czyli to być równe 0 dla dostatecznie dużych p taki klasą jest taki zbiór że ja tu zarządzę gp tak tak bo takie są możliwe wartości tego ciągu ciągu parzystości wykładników tak ja mogę zrobić zbiór zbiór czego zbiór liczb o wykładnikach takie parzystości jak każe
To czyli tu mam zbiór x równy iloczyn PK do Alf k takich że d każdego k Alfa k przystaje do G od naszej k liczby pierwszej Mod 2 czyli to są takie iloczyny które Każdą liczbę pierwszą mają w potędze 1 albo 0 tak Czyli takim en numeratorem tych klas są liczby bez kwadratowe każda liczba bez kwadratowa ma swoją klasę każda liczba bez kwadratow ma swoją klasę tych liczb które ma t samą parzystość wykładników liczb pierwszych co ona jak ja mam liczbę 2 r 3 x 7 to klasa tego czegoś to jest 2 x 3 x wojna to jest zbiór takich rzeczy także
To są Mają być te same parzystości co co te więc mogą być tylko większe to jest efektywnie zbiór wszystkich rzeczy tak od razu tak mogę napisać to jest selektor więc klasy zbiór klas to jest zbiór wszystkich liczb postaci x raz T do kwadratu gdzie x jest liczbą to jest k y to po y bez kwadratow WM sensie widzieć przewagę tego spojrzenia prze przez funkc Bo to jest tak że łatwo
Jest sprawdzić z definicji że ta relacja jest relacj równoważności to po prostu się bierze i się się liczy x kwadrat jest kwadratem jak xy jest kwadratem to yx jest kwadratem Jak się sprawdza że jak xy jest równe t kwad YZ jest równe powiedzmy s kwad To czym jest x x c naturalne to jest t k s k PR y k tak a nie ma takich specjalnych cudów jeśli kwadrat liczby wymiernej jest liczbą naturalną to i ta liczba wymierna musi być naturalna jeśli to jest naturalne to znaczy że każda liczba pierwsza dziel y k w wykładniku mniejszym lub równym t k s k czy jak podzielimy te wykładniki przez D to wychodzi że dzieli y w wykładniku mniejszym lub równym to co jest w t plus to co jest w s więc Łatwo się sprawdza że to jest relacja równoważności potem dużo ciężej
Się szuka kas abstrakcji ogólnie to jest świetny znaczek jest od występowanie przez tylko przez v tylko to To jest New to się przyjęło jako jako znak towarowy na także p od x jest równe k wtedy i tylko wtedy gdy P do K dzieli x oraz p do K plus pi już nie dzieli x No i to jest znaczek który na którym czasem się daje robić jakieś rachunki tak jego najbardziej koronnym zastosowaniem które się pokazuje jest to że jest jawny wzór na na to ile razy zmieści się p w n silnia to jest zdawałoby się kark rzecz do policzenia bo trzeba policzyć ile razy się zmieści w i tak dalej niektórych się może mieścić wyższe różne potęgi się mogą mieścić w różnych liczbach jak się dobrze zrobi buchalter na tym to wychodzi że to jest suma od z nieskończoności część C Oczywiście to jest pompatyczna suma do nieskończoności odpowi dużych k p się zrobi większe od n więc ułamek
Będzie mniejszy od podłoga będzie zer węc to jest skończona suma tak naprawdę to się nazywa jak ktoś bardzo lubi rachunki to można użyć tego wzoru do udowodnienia że n silia prz k cał bo to nie jest za darmo Tak wiemy że to jest całkowita ponieważ ta silnie się tłumaczy na kombinatorykę natomiast jak Spotykamy kogoś kto nigdy w życiu nie widział an nie pomyślał interpretacji kombinatoryczne to on nie widzi bezpośrednio Dlaczego to się skraca teownik skem min 1 r razy n min k + 1 przez k silnie jak ktoś widzi od razu argument z działaniem grupy na zbiorze który pokazuje całkowitości tego to szapoba ale normalnie tego nie widać brutalnie się pakuje ten ten wzór i się mówi że się zlicza ile jest wystąpień PW k silnia wka silnia ient silnia to się dodaje i się okazuje że jest mniej
Niż tu co najwyżej tyle co na górze tego się też uzywa do dowodzenia bardziej subtelnych rzeczy na przykład że jak mam jak do jakieś potęgi po coś co nie jest podzielne przez P to Mogę wyciągać odpowiednio dużo sztuk p ale tak to to jest wariacja na temat pojęcia które pojawiło się w naturalny sposób w tym zadaniu który mówi że mamy punkty na Kracie tu jest n Zakładam że jest zerem są sobie punkty kratowe i ta relacja nam mówi że one się trzymają za łapki jeśli a plus y jest rów b plus x no więc to jest głupio wyglądający warunek to jest w z xy tylko wtedy gdy a plus y jest równe b plus
X ale to można przekształcić można napisać w terminach po jednej stronie jednego z tych obiektów a drugiej stronie drugiego to jest x y No i teraz możemy albo zrobić geometryczną intuicję i powiedzieć że to znaczy tyle że jak mam ustaloną różnicę współrzędnych to jest jakaś prosta postaci y min X rów stał czy y x plus stał czyli te wszystkie klasy abstrakcji to będą jakieś takie proste tu będzie klasa abstrakcji tu będzie klasa abstrakcji tu będzie jeszcze inna kl abstrakcji albo można tym jkk która nam biegnie z tego naszego zbioru czyli x to było n r n w a niech i będzie w r taką że F od pary A to jest a min b No i znowu nasza relacja równoważności to jest połączenie łapkami tych punktów które są sklejane przez danego f tego konkretnego więc klasy to będą przeciwobrazy więc
Klasy to są takie coś czyli zbiór tych AB że a min B jest równe c ab wiadomo one są w X czyli a i b są naturalne już to są te co są na obrazku te poniżej te prawie tęcz złej kolejności tymczasem dobra mamy pary liczba całkowita liczba całkowita bez zera to pachnie ułamkami i tak jest w istocie to co jest zadane w jod to jest to tak naprawdę Jak się konstruuje liczby wymierne bo można myśleć o podstawach analizy w ten sposób że my pozy tujemy ilość aksjomatów o liczbach rzeczywistych No i potem już wymierne prostu wyciągamy jako Ile razy liczby naturalne generujemy jako najmniejszy zbiór który ma jedynkę oraz jeśli ma x to ma x plus 1 całkowite dorzucamy minus naturalne a
Wym można my rzeczywistych to wymaga jakiegoś tam udzia sobie rąk dość sporego w szczególności Najprościej jest zrobić konstrukcj Która właśnie najpierw konstru naturalne albo bier podstaw całkowite właś potem dokładnie przez takie coś jak jest w punkcie jby wymierne myślimy łamach i to jest wymierna ale to jest ta sama liczba tak z punktu widzenia syntak to ten napis to jest para 23 tyko Prost napisana w taki śmieszny sposób minus informacja którą gubimy jeśli dozw mnożenie i dzielenie licznika przez to samo i to jest dokładnie ta relacja która jest opisana w j w tym jpe y są w relacji gdy takie coś Ale Mój zbiór to są tu liczby całkowite i tu liczby całkowite bez
Zera więc b i y żeby jeśli napis się kompiluje to b y są różne od zera więc ja mogę z czystym sumieniem Podziel prz b x y i dostać a PR b rów PR y No i znowu można sprawdzać trzy warunki i tak się robi kiedy się konstruuje liczby wymierne natomiast na tym przedmiocie przyjmujemy za za dane to że działają struktury arytmetyczne w związku z tym to znowu to jest funkcja jest funkcja z X w r a nawet w q po prostu taka że f pary AB jest równe a PR b no i to jest równoważne z tym że F od jednej pary jest równe f od drugiej pary czyli klasy to są przeciwobrazy klasy to są zbiory takich par AB że a prz B jest równe q Dla q które są po prostu wymierne bo to jest dokładnie przeciwobraz q W
F to jest q i to jest na dobra podzbiory Era parę podzbiorów i ona ma być w relacji jeśli jest zawieranie w którąkolwiek stronę to nie pójdzie na liczbach to by działało Nie było tak że a mniejsze od B lub B mniejsze od a to to jest a nie też by nie tak jest Prost a nierówne b zaprzeczenie rel równoważności bardzo Rzadka jest rel równoważności tak zaprze dwie klasy graf takie dwi klasy to są dwie kliki zaprzeczenie tego to jest pełny graf dwudzielny są totalnie antyczne obiekty odwrócenie porządku jest porządkiem relacj równoważności nie jest rż więc w tym k No to zrobimy to jakkolwiek właśnie trzeba jeszcze ustalić czy autor zadań używa znaczka podzbiór jako mniej jako podzbiór lub lub równy czy jako właściwie podzbiór wnioskuj że jako właściwy
Podzbiór No to w związku z ty k się nie kompiluje to że no a nie jest w relacji z A bo a nie jest właściwy pod zbiorem symetria Owszem jest natomiast przechodniość nawet jakby to było mniejsze równe a nie równe to przechodniość się bardzo psuje jak zbiór a zbi b jaki mam zbiór mam zbiór C Nie zaraz ZM chciał tak oczywiście tak można zrobić k przykład jak ja zrobię tak i zbiór C zrobię w taki sposób zrobi innym kolorem żeby się odróżniał No to tu ewidentnie widać to znaczy na tym obrazku mamy A jest w relacji z b bo B jest pod zbiorem
A b jest w relacji z c bo B jest pod zbiorem C ale już nie jest prawdą że A jest w relacji z c bo niów szwajcarem noty który nie zaakceptuje obrazka na którym widać o co chodzi natomiast na wypadek gdyby był to zawsze można obrazek przekuć na na przykłady Tak można powiedzieć że niech A to będzie zbiór 12 b to będzie zbiór 2 a c to będzie zbiór 23 a jest porównywalne z b bo a jest większe od b czyli arb B jest porównywalne z c bo B jest mniejsze od c czyli BRC ale już nie Arc bo ani a się nie zawiera w c ani c w a dobra l patrzymy na po zbiory liczb naturalnych i łączymy je kiedy jedynka jest w którymkolwiek z nich y Coś tu jeśli jedynka jest w którymkolwiek z
Nich No myślę że myślę że to jest nie równoważności Znowu przechodniość się psuje tak znowu ja mogę powiedzieć że A to jest 1 inaczej nie A to będzie 2 b będzie równe 1 c będzie równe jak był oszczędny to wziął 2 ale nie będę i wezmę 3 No to bez wątpienia A jest w relacji z b bo jedynka należy do a b dokładnie tak samo b BRC bo jedynka należy do b suma c b suma c jest teraz 13 ale nie zachodzi Arc bo J nie należy do sumy
Ac która jest 23 to jest zadanie z treścią to jest zadanie o tym że jeśli robimy projekty w parach jest para jest dobra jeśli przynajmniej jedna osoba ogarnia to nie ma przechodniości jak Zbyszek robi projekt z Zenkiem i Zenek ogarnia Zbyszek nie aem Zdziś to potem Zbyszek ze Zdzisi bez Zenka to już nie dadzą rady i o tym jest zadanie dobra Zadanie następne pojęcie podziału udowodnić to co to co napisaliśmy jako twierdzenie które powinno być na wykładzie znaczy Trochę mnie martwi to że to jest jako zadanie bo zaczy tego nie było na wykładzie o czym inny nie chc udowodnić to to ten to mówimy to tak hiper formalnie tak to znaczy definiujemy równoważności tak jak
Mówiliśmy to znaczy że x lubi się z Y gdy istnieje takie i że oba należą do jednego ze zbiorów z podział No to sprawdzamy po kolei x lubi się z xem bo bo co bo z faktu że x należy do X który jest sumą wszystkich a istnieje napisałem słowem istnieje jakieś konkretne Nasze ulubione i gwiazdką takie x to x również należy więc x się z X świetnie udowodnione to to jest trywialne bo jeśli oba siedzą w Ai to oba siedzą w Ai tak naprawdę tak zdefiniowana relacja jest funkcją zbioru xy No i teraz KOR tematu Czyli
Przechodniość to oraz Y lubiące się z z implikuje X lubiące się z z bo z tego że x się lubi y x y należy do jakiegoś konkretnego A i A ponad to y się lubi z z więc y z należą do a j czyli y należy do przecięcia a i a j a przecież by założenie rozłączności z rozłączności tej rodziny a to musi być ten sam zbiór jedyny sposób na to żeby nie było sprzeczności generowane przez to założenie jest taki że ta klasa w którą wpadł y tutaj i tutaj to jest ta sama bo y jest tylko w jednej klasie jeszcze nie wiemy że to są klasy ale właśnie z rozłączności to jest tak że jak y jest
Zorze jakim to musi być ten sam zbiór tej rodziny więc jest rów j więc więc co więc x oraz z oba należą do a bo x do który jest rów czyli x się lubi z i tego mieliśmy dowieść a tu jest Żeby udowodnić drugą stronę Ja w sumie mogłem tu zrobić taki wykładowy kawałek natomiast wykładowy kawałek To są dwa zdania o tej funkcji o tym że to to jest oczywiste że jeśli jest równoważności to x się lubi Z Y wtedy tylko wtedy gdy wpadają do tej samej klasy w drugą stronę to się prostu sprawdza na palcach Tak możemy to napisać jest tak mały że się zmieści na marginesie w przeciwieństwie Fermata x się fowo lubi z X bo FX jest
Równe f x x się lubi fowo z y implikuje że f impu że y się lubi f z x jeśli x się lubi f z y a ten się lubi fow z z to wtedy f jest równe y ale on jest równe F Z przechod archetypiczne relacj równoważności jaką jest równość to FX jest równe f z czyli xbi z abst postaci takie coś to jest znow oczywista oczywistość zbiór tych y że y się fowo lubi z X to jest dokładnie zbiór tych y że f y rów czyli jest to dokładnie przeciwobraz
FX trochę nad uży notacji Tak zazwyczaj to matematycy robią tak że jak z kontekstu wynika że f jest bijekcją przynajmniej iniekcją i ma funkcję odwrotną przynajmniej po przecięciu przeciwdziedziny to wtedy f min to jest funkcja inaczej jak się p od liczby Punk to wtedy jest przeciwobraz pisał to w klamerkach a jeszcze większym pry to nie do minus pi tylko f ze strzałeczka o co chodzi Tak to jest dokładnie przeciwobraz FX Czyli każda klasa jest przeciw obrazem punktu No a każdy punkt przeciw dziedzinie jest f x więc każ przeciwobraz punktu jest tego typu zaczy Przepraszam inaczej są postaci dobra tu trochę skłamałem tak one są postaci takiej gdzie z należy do obrazu f bo jak z wezmę nie z obrazu faa to mi wyjdzie zbiór pusty zbiór
Pusty nie jest klasą Równa się f do min pi od cokolwiek z obrazu f co zrobiłem cokolwiek z obrazu no tu byłem dotknę długopis tego w tym miejscu bo on udaje że nie ma tego paska Patrzcie jaki złośliwiec jestem pod wrażeniem jego złośliwości chc dopisać naes to go tak załatwię i co głupia maszyno zyg ZG marchewka twierdzenie zostało zrobione
Na wykładzie zrobionym przez pracownika państwowej uczelni finansowanej z waszych podatków Ergo można się powić na ten fakt na rozwiązaniach zadań na kolokwium tymczasem zadanie trzecie mam relacj równoważności i dobra i mamy teraz właśnie op że zorem czujemy że relacja to jest jakieś łączenie rzeczy ale intuicja mało myśli o tym że tak naprawdę to jest zakodowane jako zbiór który eneru Wszystkie pary które zbiór w którym są wszystkie pary które są w relacji bez kolejności No to rzecz jest taka że przecięcie zrobion żeby to działało tak to znaczy jeśli
X dobra Nazwijmy to jak Nazwijmy Nazwijmy to r przecięcie to jest r1 przeci r2 No to bez wątpienia x jest w r przecięcie z xem tak tu w zasadzie lepiej byłoby korzystać z tej notacji że para należy do do relacji bo para XX należy do R1 oraz należy do r2 świetnie jeśli x jest w r przecięcie z y to wtedy co to wtedy XR 1y oraz xr2 zaraz z tego wnioskuj że y jest x y też jest r2 z X czyli y jest z X w przecięciu tych relacji świetnie A teraz przechodniość pójdzie tak samo jeśli x y są takie i y i z takie to
Wszystko koniunkcja to x R1 y y R1 z Ponadto xr2 y Ponadto y r2 z No to z pierwszych dwóch wnioskujemy tu z przechodniości R1 że x jest R1 z tu z przechodniości r2 że x jest r2 z czyli x jest w obu relacjach z z świetnie Czyli to jest relacją równoważności bo i ten cały argument sumą bywa gorzej jak się o tym przekonamy nie na przykład jak m przystawanie modulu 2 Suma praw 3 No to No to jest ciężko no bo dwójka przystaje dwójka przystaje modulo 2 do 6 szóstka przy stajemy od 3 i teraz tu
Chcę napisać coś co nie przystaje doi do tak tak więc w szczególności powiem że to to jest taka alternatywa więc 2 jest te śmiesznej relacji z dą bo 2 nie przestaje ani Modul 2 do d ani 2 nie przestaje modu 3 do d więc się nie da Oczywiście są przypadki w których zaczy odpowiedzią tego zadanie jest jest to że przeze niekoniecznie jakbyśmy chcieli wejść w to głębiej to generalnie widać że to to psuje strukturę tak zaczy jak ja mam overlap puj klasy to mi się robią to mi
Się robią większe klasy tak można robić domknięcie równoważności tego co co wychodzi a generalnie chyba to jest tak że jak jedna się zawiera w drugiej to z automatu suma oczywiście jest racją równości bo suma po prostu jest tą drugą i chyba się dowodzi że że jeśli nie ma zawierania w żadną stronę to suma nie jest jesteś w stanie to udowodnić Przypuśćmy że R1 nie zawiera się w r2 oraz r2 nie zawiera się w R1 czy jakieś xy takie że x R1 y x nie R2 tu mam też napisane że mam także A tak a2b oraz a oraz b oraz a nie r1b czy z tego wy wnioskujemy
Że a że suma nie jest Przechodnia Oczywiście że można zrobić kontr przykład w tym sensie że właśnie to to nie jest tak prosto tak to znaczy nie tylko kiedy jedna się zwiera w drugiej albo druga w pierwszej nie tylko wtedy suma jest jest relacją równoważności możemy to z czego chcieliśmy zrobić tutaj sprzeczność to możemy zrealizować Możemy zrobić tak że będzie cerwone r2 bdzie Ziel mogę zrobić x y które są w 1 oczywiście każdy sobą jest również w 2 ale one już nie są połączone w i mogę obok zrobić AB k już nie w ale oczywiście same same ze sobą jest diagram czerwona relacja ma trzy klasy tu dwu elementow tu jelow jed elementow zielona relacja ma też trzy klasy tu jed jedną dwu elementow i dwi
Jednoelementowe no Więc jak ja narysował R1 suma r2e bo nie ma implikacji między Tak jestem w R1 a nie jestem w r2 czy nie ma implikacji r2 a tu jest odwrotnie nie wygrał pudełko tak naprawdę to daje się udowodnić takie coś to jest twierdzenie nietrudne że jeśli R1 sum r2 jest racją równoważności to wtedy to wtedy klasy są albo rozłączne albo się w sobie zawierają tych r1 i r2 znaczy ten to rozbicie jest takie że ja mam rozbicie zbioru na takie zbiory i takie zbiory One wszystkie są rozłączne inaczej to i tak się wnioskuje
Z obrazka to prostu napiszemy tyle że dla każdych A to jest klasa abstrakcji R1 b to jest jakaś klasa piszę b to jest klasa To wtedy albo a jest rozłączne z b lub a zawiera się w B lub zawiera się w czyli tak naprawdę to jest tak że jest ileś takich klas jak klasę r1 to wszystkie inne klasy r2 albo są z nią rozłączne zawio w środku w środku w parkietow tymi klasami r r1 i mogą być też takie sytuacje że mam klasę zaczy r2l r2 On jest wypow w środku klasami R1 co więcej czy ja mogę mieć nestow takich
Rzeczy Nie no nie bardzo No bo czerwone klas już muszą być rozłączne więc to musi być suma rozłączna takich żuczków żuczków z czerwoną obwódką i zielonymi prążkami i takich odwrotnych nie to pytali zad warto wiedzieć właśnie jest pokazana to są k abstrakcji zapewne jeśli chcą prostszego opisu to to co to klasami abstrakcje mają być takie zbiory takich liczb że one są ust wed tyko wtedy gdy istnieje taki x że a i b całkowity są w zbiorze prostu w odcinku x plus
1 ale liczby w tym odcinku to się charakteryzują jedną konkretną rzeczą postaci x plus co a jest rów x rów część całkowita b czyli po prostu istnieje takie liczby które jest równe obu jest równoważne z tym że część całkowita a jest równa część całkowita b to świetnie napisaliśmy relacj równoważności już prościej się nie da tymczasem Tak oczywiście przeciwobraz liczb całko funkcji podłoga To są dokładnie te klasy które tam są napisane pią z relacj której klasami są okręgi Okej jakby jakiś złości prawnik przeczytał treść tego zadania to powiedział No panie to nie ma takiej relacj okręgi się nie płaszczyzny punkt 00 nie jest okręgiem no z kogo spytać jak dla mnie punkt 00 jest okręgiem o promieniu zer ale to to
To kwestia gustu w szczególności żeby zadanie miało sens to tak musi być no to to jest bardzo prosto tak no klasą abstrakcji ma być taki taki okrąg No to ogólnie jak już zauważyliście że to jest tak że jakś zbi wyst fkż funkc każdemu przyporządkowuje jakąś liczbę albo jakiś obiekt i ten obiekt jest różny dla każdego ze zbiorów rozbicia czyli funkcję różnowartościowa w jakiś inny zbiór to to jest ta funkcja która zadaje relacj równoważności Jak już napiszę tak jakby wzór na relacj równoważności cozi jest okrąg r No to relacja jest taka że x jest w relacji z y wko wtedy gdy długość wektora x jest równa długość wektora y to jest po polsku odległość od zera nza fkc
Y jest na promieniu o środku zer Izy na okręgu prien okręgu środku zer i promieniu równym długość wektora x dobra porządki częściowe to jest zabawne że i relacje równoważności i porządki mają własność przechodniości nawet nie czuję że rymuje natomiast trudno pomyśleć o dwóch bardziej da się pomyśleć ale to są strasznie enty czne rzeczy tak jedno to jest po prostu taka nieuporządkowana zupa złożona z klik w których wszystkie wewnątrz elementy są nieodróżnianie dokładnie stratyfikacji tylko mają właśnie częściową czasem jest stratyfikacja natomiast taka pełna że są że na przykład jakaś funkcja na naszym zbiorze niekoniecznie różnowartościowa i wtedy x jest porządku częściowy mniejsze od y jeśli funkcja od x jest mniejsza od funkcji od y a i tak nie zawsze jest są porządki któ się nie da opisać w ten sposób u nas mamy relacje podzielności w
Takim śmiesznym zbiorze No to najprościej narysować diagram No i tak samo jak Jedni ludzie wieszają papier toaletowy w dobrą stronę a inni w złą tak samo Jedni rysują diagramy porządku częściowego od góry do dołu a drudzy od dołu do góry tu akurat Nie mam zdania która strona jest lepsza jest to generalnie wszystko jedno tak to znaczy ogólna ogólne prawo natury jest takie że relacja porządek prim określona w ten sposób że a porządek prim B wtedy tylko wtedy gdy b porządek a też jest zzy jeśli ten jest porządkiem częściowym to takie coś też jest w tych porządkach częściowych strona tak naprawdę nie ma znaczenia strona się przekonana nazewnictwo
To jak są jakieś takie k na przykład mają element najmniejszy a nie największy No to jak odwrócę to odwrotnie ale to jest w pewnym sensie ten sam obiekt tak te same aksjomaty Żor oden żeż cys góry od dołu to to jest sama informac opis inacze mamy co mamy 2 czy n dwójką jest 4 na TR 5 jest gdzieś obok potem 6 jest n mniejszy do większych potem mamy pi potem mamy 6 napisaliśmy 8 tu jest strzałeczka tak No oczywiście od dwójki też jest do ósemki ale skoro jest implicytne to że to jest porządek Więc jest przechodni więc nie musimy rysować dodatkowej strzałki od dwójki do ósemki 9 jest koniecznie nad trójką a pią wó samej
Sobie jest jeszcze gdzieś 12 tu jest 12 i 24 jest nad emką i nad 12 o na Piątka jest elementem izolowanym po prostu Piątka Jest tylko mniejsze równa od samej siebie No to tu najmniejszych wnie to jest okropne że w polskim nazewnictwie minimum funkcji maksimum funkcji to jest z definicji albo zbioru to jest najmniejszy największy element a element minimalny i maksymalny to już właśnie jest ta to coś co bywa w częściowych porząd ale musi być nie do pobicia przez przez żaden inny nie po angielsku też tak jest tak po angielsku też się mó Minimal maximal element i i też to jest ten porządk częściowy A faktycznie najmniejszy większy to się
Mówi Small albo Greatest albo zależności od tego jaką się nomenklaturę w każdym razie tutaj Tu najmniejszego największego ewidentnie brak nie ma jakiegoś takiego który jest mniejszy od wszystkich nie ma takiego który jest większy od wszystkich próbowała ale nie pobije dziewiątki ani piątki czyli najmniejszych i największych brak No i minimalne to są jakie dwójki nikt nie pobij w byciu minimalnym trójki i piątki maksymalne tego nikt nie pobije tego nikt nie pobije i piątka jest minimalna i maksymalna wy ko rosnącej porządku naturalnych to jest tylko mojej notacji w tym zadaniu porządek liczb naturalnych jest owszem on się w ten sposób że jeśli Jestem mniejszy w tym porządku to Jestem mniejszy w porządku liczb naturalnych tak sensie jako relacja ten nasz porządek tutaj jest pod zbiorem relacji
Mniejsze równa na liczbach naturalnych także tak No ten jest najmniejszy największy zaczy minimalny i maksymalny bo właśnie przez to że jest Niwy z żadnym innym Czy istnieją akurat trzy elementowe łańcuchy No istnie jest ich mnóstwo raz dwa TR raz dwa TR trzy elementowych łańcuchów jest mnóstwo tak na przykład zbiór 36 12 jak weźmiemy ten zbiór obetniemy relacje te którą mamy w tym zadaniu czyli podzielności do tego zbioru to ten zbiór z obciętą relacją już jest liniowo uporządkowany bo tu można porównać każde dwa elementy by jak jesta relacji podzielności Zauważcie takie takie dwie
Rzeczy tak jakby dwa archetypy porządków wice pierwszy który widzimy to jest porządek naach naturalnych to rozumiemy z R I tak to jest porządek liniowy porządek najbard pod takie coś zawieraniem to jest wielkie mnustwo nieporównywalnie warstwie singletony tu jest 0 tu jest 1 tu jest 2 i tak dalej potem trochę wyżej mam zbi dwuelementowe potem tu mam zbiór 01 tu mam zbiór 02 z napisać na przykład tak i owszem ten jest mniejszy od tych ten jest mniejszy od tego i mniejszy od tego niekoniecznie od tych dwóch No i jest taka sobie jest w tym sensie stratyfikacja że zawsze jeśli jeden zbiór jest pod zbiorem drugiego to jest w niższej warstwie liczności niż w wyższej Natomiast nie nie każdy z
Niższego strat jest str jest maksymalne maksymal niepalność oczywiście jest jak mamy po prostu same punkty izolowane to jest relacja równości równości jest porządkiem w tym sensie nieostrym no i Zauważcie że porządek że na porządku podzielności na liczbach naturalnych na nim się da zaimplementować jen i drugi to znaczy jeden i drugi jest pod porządkiem porządku podzielności w jaki sposób jak ja sobie wybiorę moją ulubioną liczbę pierwszą na przykład 17 No to ja mogę n z mniejsze równe ja mogę zanurzyć w n nawet może być n bez zera z relacją podzielności tak to to jest podzielność a nie 1 po prostu w ten sposób że n przejdzie min na 17 do potęgi nte n jest mniejsze równe od m wtedy i tylko wtedy gdy wystarczy stronę wtedy gdy 17 do n jest mniejsze lub równe
Podzielne dzieli 17 do M w tym wielkim porządku znalazłem takim taki malutki łańcuszek potęg 17 który jest jako zbiór z porządkiem izomorficzny relacj ale str stronie ty którzy chcą m Mał porównywalności jest porządek na podzbiorach plus uwagi to wszystko jedno i tu jest zabieranie to ja twierdzę że ja to zę w taki sposób dlaczego Bo n jest liniow uporządkowane każdy podzbiór jest tożsamy z rosnącym podciągiem jakol rosnący ciąg prostu w klamerki mam zbiór jak mam zbiór kt jest pod zbiorem licz naturalnych to go uporządkuje No to zbiór który się składa z n1 N2 N3 i tak dalej tak
Gdzie n1 mniejsze niż N2 mniejsze niż N3 i tak dalej to ja powiem że niech PK to będzie k ta liczba pierwsza w dowolnym porządku dla ustalenia uwagi rosnącym to ja taki ciąg zaczy taki podzbiór przerzucę na iloczyn p n k dokładnie po tym pod zbiorze chciałbyś bardziej prostu napiszę A nie przepraszam ja tu zrobiłem jedno drobne oszustwo ja chciałem żeby tutaj były skończone podzbiory oczywiście wszystk Dokładnie tak jest jak ja się skończę na NK to tak ja prostu Zamienię to na pn1 raz razy raz PNK przeszedłeś czyni zniszczenie w
Sumie wgląda prz wgląda jakby prosiła zadanie o chrupki zadanie mówiło że dopiero jak je rozwiążesz to dostaniesz chrupka tymczasem i tak samo tutaj to jest dość Jasne że jak jak po prostu mnożę różne liczby pierwsze to podzielność się stanie tylko wtedy jak to będzie podbi a jest pod zbiorem bedy GD pl b dobra o SI jest zsza tym nietrywialne podzbiory to znaczy nie zbi przez inkluz No więc element największy najmniejszy No to bardzo rzadko się zdarza tak właśnie wyrzuciliśmy ten najmniejszy zbiór pusty to piszemy że nie istnieje nie istnieje
Najmniejszy tak na powinni się najpierw znajdować minimalny a potem stwierdzić że skoro jest więcej niż jeden minimalny to nie ma najmniejszego więc tak naprawdę zaczniemy to damy tutaj No i to generalnie goły okiem Widać że singletony są znaczy najmniejsze co jest po wyrzuceni zbioru pustego s singletony jeśli jeśli liczność zbioru a jest większa od 1 to wtedy istnieje jakieś a należące do a takie że a min a nie jest puste czyli Wtedy a jest większe od a z wyrzuconym a oraz ten jest w naszym Uniwersum więc a nie jest minimalny no to wtedy A to jest po prostu Singleton jakieś A czyli jeśli B zawiera się w
A każde b zawarte w a jest równe a zbiór pusty on w ogóle nie jest w naszym Uniwersum czyli dla każdego b należącego do Uniwersum które jest mniejsze równe niż a w naszym porządku zachodzi b rów A czy definicji a jest minimalny to jest takie TR masła to widać goł że elementy prostu zbiór z wyrzuconym jednym punktem albo można zrobić przez dualność to znaczy mądre powiedzenie tego jest takie że ja zrobię taką funkcję Sigma która idzie z u w u po prostu taką że Sigma od A to jest dopełnienie a bez wątpienia Jeśli zbiór jest po zbior
Naturalnych który nie jest zbiorem pustym i całością to jego dopełnienie również nie jest doł zbioru pustego czyli całością i nie jest doł całości czyli zbiorem pusty czyli faktycznie działa zów siebie No i oczywiście jeśli a zawiera się w b to to jest Toż same z tym że SIG od a jest Wi odwrócony to jest praktycznie to samo ten sam typ danych bada się w ten sam sposób czyli elementy maksymalne maksymalne tego porządku To czym one są Sigma od elementów maksymalnych tego czegoś są dokładnie elementy minimalne tak ter Sigma od elementów maksymalnych to są tak to są po prostu elementy minimalne znaczy jak chciał być bardzo pompatyczny to bym powiedział że Sigma
Od elementu maksymalnego tego porządku to jest element maksymalny porządku odwróconego tak czy ja mógł powiedzieć tu pisze takie coś to jest odwrócony czyli to jest funkcja rosnąca tak naprawdę jest różnowartościowe SIG jest różnowartościowe a że jest inol to jest bcj to wtedy Sigma jest izomorfizmem z porządkiem takim na na albo to wszystko jedno to izomorfizm na z porządkiem odwróconym maksymalny porządku odwróconego czyli z natury rzeczy element minimalny No to
Już i w drugą stronę też czyli elementy maksymalne tego porządku To są dokładnie zbiory postaci wyz czyli siglon i oczywiście to to był punkt B Jak chc mieć odpowiedź tak w formacie napisanie odpowiedzi natomiast jest więcej niż jen element minimalny więcej niż jeden element maksymalny To z tego wynika że nie ma najmniejszego i największego jak był dokładnie element minimalny to to co to czy to znaczyło że że on jest najmniejszy Nie znaczyłoby no bo Myślałby kto że zrobimy tak że dokładnie
Minimalny i on chciałby nie być najmniejszy czyli byłby ktoś kto ktoś taki że on nie byłby od niego większy na obrazku by to było tak że ja tu mam ten jeden minimalny wizy od tego co byśmy zrobiliśmy w dół byśmy w końcu spotkali jakiś element tutaj na końcu on musiał być minimalny więc musiał być równy tem więc jest większy od tego oczywiście to się nie musi skończyć jeśli ja tutaj pójdę w nieskończoność to tu to jest jedny element minimalny A to nie jest element najmniejszy ogó praw tak mam element najmniejszy to oczywiście jest dokładnie J minimalny te strony nie na przykład jaki porządek zrobimy na przykład jak wezmę min n suma
Panda panda jest nieporównywalna z żadną liczbą naturalną zaczy nie całkowitą ona jest elementem minimalnym minus n każdy element z minus n nie jest minimalny bo poniżej jego jest ktoś w Panda jest jny elementem minimalnym ale nie jest najmniejszym bo ona nie szacuje z dołu całego zbioru liczb naturalnych ile tego jeszcze zostało to robimy dwa elementy maksymalne jeden minimalny i bez elementu najmniejszego prawie narysowali dwa elementy maksymalne dokładnie jeden minimalny No i nie ma największego zrobić tak że mam mam o wiem jak to zrobię mam minus liczby
Naturalne razy 1 suma rozłączna Natural 2 ą powiedzmy 0 x 3 i mój porządek mówi tyle że x jest mniejsze równe od y gdzie x to jest x kiepskie nazwy a jest rów b gdzie a jest rów a1 a2 B jest równe B1 B2 gdy żeby by porównywalne muszą być na tym samym poziomie czyli gdy b gdy B2 jest rów A2 oraz a1 jest mniejsze równe niż B1 to jest ten to samo tylko napisane w takim boleśnie formalnym wydaniu tak pierwsze to jest Minn r 1 On nie ma elementu minimalnego ma ten J
Maksymalny potem jest min r 2 zrobić inny kolorem już trudno i potem co potem 0 r 3 i o co nas pytają dwoma elementami maksymalnym a nie z przykład span był dokładnie dobry to tak to możemy wyrzucić w ogóle I teraz tak tak tak Tu jest maksymalny tu jest drugi dwa maksymalne jeden minimalny bo ten też jest minimalny i nie ma najmniejszego elementy 0 1 i 02 są maksymalne i element 0 bo 3 akurat 03 również jest
Minimalny dobra Zadanie d porównywalność po współrzędnych taka najbardziej chamska porównywalność funkcji jaka moga być Zauważcie że jak mam zadanie d to w ten nasz porządek na N zanurza się porządek w wszystkich podzbiorów to znaczy ja mogę zanurzyć 2 do z zawieraniem w pod przerzucę na indykator jest Niewątpliwą prawdą że a zawiera się b wtedy tylko wtedy gdy dla każdego x indykator a x jest mniejszy równy niż indykator b x bo tu jest napisane że xem x zer to wszystko jed A jak już ten jest jen to drugi też musi być je to jest dokładnie to samo zabieranie zbiorów to jest bardzo wielki porządek który zawiera porządek na wszystkich podzbiorach naturalnych Ponadto jest to
Dokładnie Dobra nie jest to nie jest to porządek na nie jest to porządek podzielnością bo żeby mieć podzielność to owszem to jest funkcja pier wykładniki ale to jest funkcja skończony może m tyko skończenie wartości różnych zer dobra no to dowodzenie że to jest częściowy porządek to jest jakieś trywialne tak to mówimy że f jest mniejsze równe f to jest to że akurat flor częściowego porządku jest taki że to jest mniejsze równe można te sam aksjomaty robić kamerkę niestety piski ma pierwszeństwo jak jest teraz chcę spojrzeć w lewo a nie to jest mirane jest rów dlatego jest taki porządek zą tak cała teoria Poraż teor cze drugiego różni przekątną to jest to samo pojęcie
Efektywnie co jeszcze Chcemy chcemy żeby Żeby co Żeby z tego że f mniejsze równe g oraz G mniej równe f wynikało że f jest równe G No tak jest w istocie No bo to jest po współrzędnych tak dla każdego na Fn mniejsze równe GN oraz dla każdego n g n mniejsze równe f n to oczywiście implikuje że dla każdego na jedno i drugie tak A to jest dokładnie z definicji równoważne temu że z definicji z powiedzenia Czym jest równość tak naprawdę to z faktu że mniejsze równe jest porządkiem porządkiem częściowym i to się nazywa równość funkcji fig czego jeszcze Chcemy od porządku częściowego tylko tyle żeby nie było nie było głupich cykli tak żeby nie było tego że jeden wygrywa z drugim drugi z pierwszym przechodniości to jest tak samo trywialnie się sprawdza f m rów g rów implikuje że dla każdego n zachodzi f n
Mniejsze rad dż mniejsze równe niż h n z tego że kwantyfikator ogólny to jest tak naprawdę wielka koniunkcja i tu jest też koniunkcja to to jest wszystko jedna zupa koniunkcyjna którą można wymieszać i napisać że dla każdego n f n jest mniejsze równy niż GN to jest mniej równe niż h n czyli dla każdego n Fn jest mniejszy równy niż h n czyli f jest w śmiesznym porządku mniejsze równe niż h tak to jest tylko tylko tyle co chcemy od porządku częściowego bo nie nie nie chcemy wymuszać nie chcemy wymuszać porównywalności no i znowu B jest jakieś tam męczenie się dobra z Zakładam że n jest zer na szczęście z to nie Weź z0 od n równa się z definicji to oczywiście dla każdego f z
Tego naszego Uniwersum zer szacuje się z góry przez f bo to jest element najmniejszy w szczególności jedy minimalny co jeszcze Chcemy największym No to to ciężko będzie No bo to tak jak w tej starej zabawie że kto poda większą liczbę zawsze można podać większ nie ma elementów maksymalnych bo dla każdego f f jest mniejsze równe niż f plus 1 f plus 1 to jest po prostu dodanie jedynki Wszędzie mogę napisać jedynkę w ten sposób żeby było widać że to jest funkcja która zwraca jedynkę wszędzie a nie funkcja plus liczba mimo tego że funkcja plus liczba to widać że to jedna rzecz która to może którą to może oznaczać to jest dodanie po wartościach Python to wie C niekoniecznie dobra nieskończony
Łańcuch No to bardzo prosto mam indykator zbioru od zer do n Niech to się nazwie Fn No to bez wątpienia Fn jest mniejsze równe niż Fn plus 1 tak bo bo co bo dla każdego xa zachodzą zachodzi dychotomia dla każdego x mniejszego równego niż N A nie przepraszam to to to jest właśnie w drugą stronę prawda to jest d każdego xa takiego to Fn x jest równe 1 mniejsze równe niż plus 1 od x które jest też równe 1 dla x równ n + 1 Fn x jest równe 0 które jest bez wątpienia mniejsze
Równe 1 A jak x jest większy od ten plus 1 to OB są zerami No świetnie tam nieskończony łańcuch oczywiście nie może być nieskończony może być nieskończony w dół w sumie tak tu jest po prostu pytanie tylko nieskończony łańcuch czy jest liniowy oczywiście nie jest liniowy bo indykator zbioru 5 i indykator zbioru 7 nie mają żadnej nierówności czy jest gęsty czyli czy czy między Każde dwie funkcje da się wstawić jakąś jedną między każ FK Myślę że tak Przypuśćmy że mam F mniejsze faktycznie nie jest równe a jest mniejsze od g no to wtedy jak nie jest równe między dwie równe
Oczywiście nie wstawi różnej od nich wtedy istnieje takie konkretne n z gwiazdk takie że f gwiazd jako że się nie równa a jest mniejsze równe No to to jest po prostu mniejsze No to bardzo prosto teraz ja powiem że niech h to będzie f plus indykator Singleton n z gwiazdką po prostu ten fą Bardo często być jest jakiś taki jeden hi w którym w którym g jest większy o je Nie czekajcie ja chyba źle powiedziałem Tak ja źle powiedziałem jak one się różnią tylko o jeden tak tak tak się wycofuje nie jest gęsty bo bo co f to jest po prostu samo zer i g to jest indykator zbioru
5 one spełniają f mniejsze od gze i nie jest równe oraz jeśli mam h które jest wciśnięte między jno i drugie to co to dla każdego n różnego od pi h ten jest równe 0 a d Pi jest dychotomia jeśli h od 5 a ten jest rów A poza tym może msze równe Ni g 5 czyli 1 No to jeśli H 5 jest to w takim razie Ono ma tylko dwie liczby do wyboru więc jeśli H 5 jest równe 0 to wtedy h wszędzie jest równe 0 a jeśli jest równe 1 to to już TR indykator czyli przez to że
Każde zwiększenie od f do g to ono zmniejsza o je sumę f min GN owszem czasem jest nieskończona natomiast jak jest skończona to nie ma bata jak jak ta suma jest większa od 1 to można wstawić coś pośrodku w takich pojedynczych przypadkach których f różni się tylko w jednej wartości tylko o je to w takich się nie da wstawić jednego w środek i to zaprzecza yyy hipotez że jest gęsty dobra zbiór ciągów skończonych Jesus jest druga y generalnie mógłbym to skończyć dzisiaj natomiast jak pewnie słychać z mojego głosu to jestem bardziej metabolitem kawy niż człowiekiem więc ciąg dalszy po przerwie na spanie