Spacerując nie tak dawno sobotnim wieczorem w okolicach Małego Rynku wpadłem po raz pierwszy od dobrych 7-8 lat do mieszczącej się tam księgarni ezoterycznej CUD (Ciało Umysł Duch). Przez nią wchodzi się zresztą do knajpy na piętrze i w dawnych czasach kiedy pracowałem w "krążowniku" u zbiegu Wielopola i Starowiślnej wpadałem do owej knajpy czasem z koleżeństwem - stąd mam niejaki sentyment do tego miejsca. Wracając do księgarni CUD, to oczywiście jak podobne jej miejsca wypełniona jest mieszaniną rzeczy jakoś tam wartościowych z kompletnymi bzdurami od teorii spiskowych począwszy przez chiromancję, geomancję, astrologię, różne filozofie wschodu po programowanie neurolingwistyczne, że skrócę wyliczankę do kilku ledwie.
Jest tam też oczywiście dedykowana półka albo i dwie nawet specjalnie na książki z zakresu numerologii. Ja oczywiście nie wierzę w teorie numerologiczne, ale wierzę w istnienie numerologii i w to, że owo istnienie może nam coś ciekawego powiedzieć np. o ludziach. Pierwsze wrażenie jest takie, że jest tych książek - nie w sensie ilości egzemplarzy ale w sensie ilości tytułów sporo. Zazdrość bierze, bo chyba więcej niż książek poświęconych teorii liczb dostępnych w sprzedaży. Wziąłem się za kartkowanie z ciekawości, z pewną nadzieją, że o ile są to bzdury to przynajmniej natknę się gdzieś na bzdury na swój sposób wyrafinowane. Pokrewne numerologii np. rozważania miłośników Kabały bywają bowiem czasem całkiem intrygujące i o ile mi wiadomo kilku mistycznie nastawionych niezłych matematyków oddawało się i oddaje owemu szaleństwu. Niestety: wszystko wydaje się tam być zupełnie płaskie i sprowadzone do najzupełniej prymitywnego katalogowania liczb i wiązania ich z jakimiś wpływami, cechami charakteru ludzi itp. Najbardziej wyrafinowana operacja matematyczna na jaką można się tam natknąć to dodawanie a i to w zakresie dostępnym dla drugo, jeśli nie pierwszoklasity.
Ale generalnie liczby ludzi fascynują i chętnie czegoś w nich szukają. Mam kolegę, który bawi się w giełdę i tam - w ślad za jakąś nie do końca zdaje się uzasadnioną heurystyką zwaną teorią fal Elliota, niektórzy stosują jakąś formę przewidywania czy wróżenia z ciągu Fibonacciego. Od czasu do czasu zatem zadawał całkiem sensowne pytania teorio-liczbowe, na które starałem się jak umiałem odpowiedzieć. Cóż, nie sądzę żebym mu pomógł w zdobyciu fortuny (jeśli ją ma to skrzętnie ukrywa). A nawet jeśli - będę wspaniałomyślny i nie zażądam "działy". "Stalking" (dziś nauczyłem się tego słowa i dowiedziałem się co oznacza) stanowczo nie jest w moim stylu.
Niewykluczone, że w świecie pozamatematycznym liczby Fibonacciego zrobiły wśród ciągów liczbowych karierę największą. Raz, że rzeczywiście rekurencja której są może i najprostszym spośród spektakularnych przykładów rzeczywiście robi jakieś wrażenie nawet na ludziach nie znających matematyki, dwa, że powiązane są z kilkoma ciekawymi anegdotami historycznymi, trzy bo to temat przylegający do zagadnień praktycznych i pobudzajacych wyobraźnię - jak złoty podział i jego wszędobylskość np. Cóż - jest to jak widać twór przynależny już nie li tylko do matematyki ale do szeroko rozumianej kultury masowej (przypomnijmy sobie choćby Dona Browna).
Do rozmyślań o liczbach i kulturze bezpośrednio natchnął mnie fakt, że jeden z newsletterów jakie pronumeruje przyniósł mi dziś linka do strony jakiejś firmy powiązanej z FOREX-em, czyli instytucją (albo jak się to modnie mówi - platformą) organizującą światowy rynek walutowy. Ponieważ rynek ten jest chyba zupełnie skomputeryzowany, w czasach internetu obrósł firmami które pośredniczą w spekulacji na nim umożliwiając ją również maluczkim wyposażonym w konto bankowe i przeglądarkę WWW i stając się dla owych maluczkich jak sądzę skrzyżowaniem instytucji finansowej z szeroko rozumianą rozrywką hazardową. Co zauważyłem dziś - co odwraca niejako sytuację mojego kolegi gracza - w materiale promocyjnym owej firmy pisano przede wszystkim o ciągu Fibonacciego podając nawet całkiem ciekawe informacje historyczne delikatnie jedynie wspominając, że można go użyć do wspomnianego przeze mnie "przewidywania" w trakcie gry. Tak wiec firma promowała uczestnictwo w FOREX (a więc i nadzieję na bogactwo dla gracza i pewność prowizji dla siebie) używając ciągu Fibonacciego. Czyż to w dzisiejszych czasach nie nobilitacja wystąpić w reklamie ?
I ja na tym pewnie skorzystam bo mój dzisiejszy wpis dzięki Googlom przysporzy mi zapewne atrakcyjnymi słowami kluczowymi nowych, zawiedzionych, jednorazowych gości...
2010-04-08
2010-03-31
Zupełnie inna historia
Skusiło mnie, mimo, że to zupełnie inna historia jak wzmiankowałem tu (warto być może przed czytaniem tego postu zajrzeć do linkowanego), ażeby opowiedzieć coś o twierdzeniu Dilwortha. Spróbuję zmierzyć się z innym jego dowodem (w porównaniu ze znanym choćby z wikipedii) który pozwala zerknąć trochę na strukturę zbioru antyłańcuchów o maksymalnej liczności w skończonym zbiorze uporządkowanym. Nie wiem czy jest to jakiś nowy dowód – twierdzenie Dilwortha nie jest bardzo trudne więc spodziewam się, że wiele osób dla przyjmności, przypadkiem czy w ramach ćwiczenia udowodniło go sobie na wiele różnych sposobów.
Twierdzenie Dilwortha, mówi: W skończonym zbiorze F uporządkowanym przez relację R maksymalna długość antyłańcucha jest równa minimalnej ilości rozłącznych łańcuchów pokrywającej zbiór F.
Uwaga: będę używał dla R zapisu infiksowego, tj. fakt, że (a,b) ∈ R będę oznaczał przez a R b.
Definicja: Kratą nazywamy zbiór częściowo uporządkowany w którym każde dwa elementy mają unikalne supremum (a więc minimalne ograniczenie górne) i unikalne infimum (a więc największe ograniczenie dolne).
Lemat:
Niech dana będzie krata skończona X gdzie relacją porządku jest ≤. Niech W ma wasność: ∀ x, y ∈ X sup(x, y) ∈ W i inf(x, y) ∈ W => x ∈ W i y ∈ W. Wtedy, jeżeli pewien maksymalny łańcuch w X zawiera się w W, to W = X.
Uwaga: ≤ używam tu w zapisie infiksowym, tzn (a,b) ∈ ≤ zapisuję jako a ≤ b . a < b oznacza zaś a ≤ b i a ≠ b
Dowód: Załóżmy nie wprost, że W ma sugerowaną własność, pewien maksymalny łańcuch M ⊆ W, ale W' = X \ W ≠ 0. Weźmy a - element maksymalny w W'. W M są elementy nieporównywalne z a, bo w przeciwnym wypadku M ∪{a} byłoby łańcuchem większym niż M a o M założyliśmy, że jest maksymalny. Weźmy o - najmniejszy z elementów łańcucha M nieporównywalny z a. Z maksymalności a w W' wiemy, że sup (a,o) ∈ W. (bo sup(a,o) > a ) Ponieważ a nie należy do W, wiemy też, że inf(a,o) ∉ W, (bo w przeciwnym razie z własności zbioru W mielibyśmy a ∈ W) Wiemy również, że o nie jest elementem minimalnym łańcucha, bowiem wtedy inf(a,o) < o musiał by być równy o a o jest nieporównywalne z a. Istnieje więc element b bezpośrednio poprzedzający o w W. Weźmy teraz element inf(a,o). Ponieważ b < a (jest porównywalne a nie może być mniejsze bo wtedy a < b < o a a nie jest porównywalny z o). Skoro tak, to b ≤ inf(a,o) (bo b < o i b < a wiec b ≤ inf(a,o) z definicji infimum). Gdyby b = inf(a,o) mielibyśmy znowu sup(a,o), inf(a,o) ∈ M ⊆ W i a ∈ W. Jeżeli zaś b < inf(a,o) < o to M ∪ {inf(a,o)} jest łańcuchem większym od M. Sprzeczność.
Zanim wykorzystam lemat, mała uwaga. Nie znałem wcześniej tego lematu i ciekaw jestem czy ma jakąś wartość (w sensie przydatności) poza dowodem, który tu przeprowadzam. Chętnie bym zobaczył szersze jego zastosowanie.
Druga uwaga - przypomina mi się żart, który opowiadał jeden z wykładowców w IM UJ (ale nie pamiętam który niestety) o dowodach nie wprost. Mianowicie: dowód nie wprost polega na tym, że ktoś pisze bzdurę a potem zaczyna wnioskując z niej wypisywać coraz większe i większe bzdury, aż w końcu wypisze coś tak niesłychanie bzdurnego, że wszyscy zgadzają się, że dalej już nie można kontynuować.
Wracając do tw. Dilwortha. Niech FM oznacza zbiór antyłańcuchów o maksymalnej długości w F uporządkowanym przez relację R. W FM wprowadźmy relację RM następująco: a RM b z definicji wtedy i tylko wtedy gdy ∀ x ∈ a ∃ y ∈ b t. że x R y
Pokażę, że jest to relacja porządku. A więc :
1) a RM a - oczywiste
2) Niech a RM b i b RM c . Mamy x ∈ a więc ∃ y ∈ b t. że x R y . Zatem ∃ z ∈ c t. że y R z. Z Przechodniości R mamy x R z. Więc a RM c
3) Niech a RM b i b RM a . Weźmy x∈a . Zatem ∃ y ∈ b t. że x R y. Więc ∃ z ∈ a t. że y R z. Ale wtedy x R z i oba należą do antyłańcucha, więc x = z. Mamy więc x R y i y R x, czyli y = x. Rozumując tak ∀ x ∈ a i korzystając z tego, że oba antyłańcuchy mają maksymalną liczbę elementów więc są równoliczne dostajemy a = b
Pokażę więcej, mianowicie FM z porządkiem RM jest kratą. Wystarczy pokazać, że:
∀ a b ∈ FM ∃ sup(a, b) i inf(a,b).
Ponieważ konstrukcje i dowody obu są identyczne z dokładnością do kierunków nierówności, szczegółowo przedstawię przypadek supremum, zostawiając - jak to mają w zwyczaju leniwcy infimum czytelnikowi. A więc, niech a i b ∈ RM .
Mamy a = a1∪(a ∩ b)∪a2 gdzie
a1 = {x : x∈ a\b , ∃ s ∈ b t. że x R s }
a2 = {x: x∈ a\b , ∃ s ∈ b t. że s R x }
Podobnie b = b1∪(b ∩ a)∪b2 gdzie
b1 = {x : x∈ b\a , ∃ s ∈ a t. że s R x }
b2 = {x : x∈ b\a , ∃ s ∈ a t. że x R s }
Zauważmy, że a1 ∩ a2 = b1 ∩ b2 = 0
Gdyby bowiem x ∈ a1 ∩ a2 to ∃ y1, y2 ∈ b t.że y1 R x i x R y2
ale wówczas, (skoro b jest antyłańcuchem) y1 = y2 więc y1 = y2 = x. Ale a1 (jak i a2) z definicji nie ma elementów wspólnych z b. Przy okazji wynika z tego że
#a = #a1 + #a∩b + #a2
i podobnie
#b = #b1 + #a∩b + #b2
gdzie przez # oznaczam liczność zbioru.
Pokażę teraz, że:
inf(a, b) = a1∪(a ∩b)∪b2 i
sup(a, b) = b1∪(a ∩ b)∪a2
Zajmijmy się supremum. b1∪(a ∩ b)∪a2 jest antyłańcuchem. Mianowicie żadne dwa elementy zbioru b1∪(a ∩ b) nie są porównywalne między sobą, podobnie (a ∩ b)∪a2 , Zatem pozostaje pokazać, że elementy b1 i a2 nie są porównywalne.
Załóżmy że ∃x ∈ b1 y ∈ a2 t.że x i y są porównywalne.
Gdyby y R x mielibyśmy z definicji zbiorów b1 i a2 że
∃s z ∈ b t.że s R x i x R y i y R z więc s R z czyli s = z = x = y co jest sprzeczne.
Gdyby zaś x R y wtedy ∃s z ∈ a t.że s R x i x R y i y R z i rozumujemy jak linijkę wyżej.
Podobnie pokazać można, że a1∪(a ∩ b)∪b2 jest antyłańcuchem.
Pozostaje pokazać, że oba łańcuchy są maksymalnej długości. Ale wiemy:
#a = #b więc #a1 + #(a ∩ b) + #a2 = #b1 + #(a ∩ b) + #b2
czyli
#a1 - #b1 = #b2 - #a2 ale:
# b1∪(a ∩ b)∪a2 = #b1 + #(a ∩ b) + #a2 =
#b - #(a ∩ b) - #b2 + #(a ∩ b) + #a2 = #b + (#a2 - #b2)
Podobnie
a1∪(a ∩ b)∪b2 = #a1 + #(a ∩ b) + #b2 =
#a - #(a ∩ b) - #a2 + #(a ∩ b) + #b2 = #b + (#b2 - #a2)
Gdyby więc #a2 - #b2 ≠ 0 jeden z tych dwóch antyłańcuchów miałby długość większą niż długość antyłańcucha o maksymalnej długości – co jest jawną sprzecznością.
Teraz pozostaje pokazać jeszcze, że supremum jest naprawdę supremum, tzn.
jeżeli a RM x i b RM x to sup( a , b ) RM x
Jeżeli a RM x to oczywiście każdy s ∈ a jest porównywalny z jakimś elementem antyłańcucha x (bo inaczej po dołączeniu do x tworzyłby większy antyłańcuch). Gdyby któryś z nich był silnie większy od pewnego elementu x to (patrząc na definicję porządku RM w FM) byłby również silnie większy a więc w szczególności porównywalny z jakimś innym elementem a co daje sprzeczność.
Podobnie można rozumować i dla b. Zatem (b1∪(a ∩ b)∪a2 ) RM x.
Niemal identyczne rozumowanie pokazuje, że zdefiniowane przez nas inf jest rzeczywiście infimum zbiorów w RM.
FM jest zatem kratą.
Weźmy teraz A maksymalny łańcuch w FM. Pokażę, że istnieje łańcuch C w F mający wspólny element z każdym elementem A. To proste: niech c1 będzie maksymalnym elementem w A a x1 elementem c1. Teraz indukcyjnie dopóki nie wyczerpiemy elementów A, mając x1...xk elementów tworzących łańcuch w F takich, że xi ∈ ci i ci poprzedza ci-1 w A, definiujemy ci+1 jako element bezpośrednio poprzedzający ci w A a xi+1 element ci+1 t. że xi+1 R xi (element taki istnieje z definicji porządku RM w FM. Zauważmy, że nie musi być różny od x1 !). Żądanym łańcuchem zbiór będzie {x1,...,xn} (tworząc z ciągu zbiór wyeliminowaliśmy powtórzenia).
Niech teraz, przy znaczeniu A i C jak wyżej, S będzie podzbiorem FM takim, że a ∈ S wtedy i tylko wtedy gdy a ∩ C ≠ 0. Łatwo zobaczyć z charakteryzacji inf i sup, że S ma własność z naszego Lematu, tzn że jezeli inf(a,b) i sup(a,b) są w S to i a i b są w S.
Jest tak rzeczywiscie: jeżeli x i y należą do C, x R y i x ∈ inf( a, b) i y ∈ sup (a, b) to albo:
- x ∈ a ∩ b - wtedy oczywiście a ∩ C ≠ 0 i a ∈ S i b ∩ C ≠ 0 i b ∈ S
- x ∈ a1 wtedy z konieczności y ∈ b1 i znowu j.w. a ∈ S i b ∈ S
- x ∈ b2 wtedy z konieczności y ∈ a1 i j.w.
Co więcej A jest łańcuchem maksymalnym w FM i jest (co wynika ze sposobu konstrukcji) zawarty w S. Na mocy Lematu zatem S = FM. Innymi słowy każdy antyłańcuch o maksymalnej liczbie elementów przecina się z łańcuchem A.
Teraz samo Twierdzenie Dilwortha.
Indukcyjnie. Twierdzenie jest porawdziwe gdy maksymalna długośc antyłańcucha jest 1. Załóżmy, że jest prawdziwe dla zbiorów uporządkowancyh z antyłańcuchem o maksymalnej długości k gdzie k < n. Weźmy teraz zbiór F, z antyłańcuchem o maksymalnej długości n. Z tego co udowodniliśmy powyżej wynika istnieje łańcuch C mający część wspólną z każdym anyłańcuchem maksymalnej długości w F. Wtedy F \ C jest zbiorem z antyłańcuchem o maksymalnej długości równej n-1 i z założenia indukcyjnego minimalna łańcuchów pokrywających go wynosi n-1. Zatem F da się pokryć przez n łańcuchów (łańcuchy pokrywające F\C i C). Jest to rzeczywiście liczba minimalna, bo gdyby dało się pokryć przez mniej (np. n-1) dwa elementy antyłańcucha o długości n musiałyby wpadać do tego samego łańcucha z pokrycia - co jest niemożliwe.
Uff
Twierdzenie Dilwortha, mówi: W skończonym zbiorze F uporządkowanym przez relację R maksymalna długość antyłańcucha jest równa minimalnej ilości rozłącznych łańcuchów pokrywającej zbiór F.
Uwaga: będę używał dla R zapisu infiksowego, tj. fakt, że (a,b) ∈ R będę oznaczał przez a R b.
Definicja: Kratą nazywamy zbiór częściowo uporządkowany w którym każde dwa elementy mają unikalne supremum (a więc minimalne ograniczenie górne) i unikalne infimum (a więc największe ograniczenie dolne).
Lemat:
Niech dana będzie krata skończona X gdzie relacją porządku jest ≤. Niech W ma wasność: ∀ x, y ∈ X sup(x, y) ∈ W i inf(x, y) ∈ W => x ∈ W i y ∈ W. Wtedy, jeżeli pewien maksymalny łańcuch w X zawiera się w W, to W = X.
Uwaga: ≤ używam tu w zapisie infiksowym, tzn (a,b) ∈ ≤ zapisuję jako a ≤ b . a < b oznacza zaś a ≤ b i a ≠ b
Dowód: Załóżmy nie wprost, że W ma sugerowaną własność, pewien maksymalny łańcuch M ⊆ W, ale W' = X \ W ≠ 0. Weźmy a - element maksymalny w W'. W M są elementy nieporównywalne z a, bo w przeciwnym wypadku M ∪{a} byłoby łańcuchem większym niż M a o M założyliśmy, że jest maksymalny. Weźmy o - najmniejszy z elementów łańcucha M nieporównywalny z a. Z maksymalności a w W' wiemy, że sup (a,o) ∈ W. (bo sup(a,o) > a ) Ponieważ a nie należy do W, wiemy też, że inf(a,o) ∉ W, (bo w przeciwnym razie z własności zbioru W mielibyśmy a ∈ W) Wiemy również, że o nie jest elementem minimalnym łańcucha, bowiem wtedy inf(a,o) < o musiał by być równy o a o jest nieporównywalne z a. Istnieje więc element b bezpośrednio poprzedzający o w W. Weźmy teraz element inf(a,o). Ponieważ b < a (jest porównywalne a nie może być mniejsze bo wtedy a < b < o a a nie jest porównywalny z o). Skoro tak, to b ≤ inf(a,o) (bo b < o i b < a wiec b ≤ inf(a,o) z definicji infimum). Gdyby b = inf(a,o) mielibyśmy znowu sup(a,o), inf(a,o) ∈ M ⊆ W i a ∈ W. Jeżeli zaś b < inf(a,o) < o to M ∪ {inf(a,o)} jest łańcuchem większym od M. Sprzeczność.
Zanim wykorzystam lemat, mała uwaga. Nie znałem wcześniej tego lematu i ciekaw jestem czy ma jakąś wartość (w sensie przydatności) poza dowodem, który tu przeprowadzam. Chętnie bym zobaczył szersze jego zastosowanie.
Druga uwaga - przypomina mi się żart, który opowiadał jeden z wykładowców w IM UJ (ale nie pamiętam który niestety) o dowodach nie wprost. Mianowicie: dowód nie wprost polega na tym, że ktoś pisze bzdurę a potem zaczyna wnioskując z niej wypisywać coraz większe i większe bzdury, aż w końcu wypisze coś tak niesłychanie bzdurnego, że wszyscy zgadzają się, że dalej już nie można kontynuować.
Wracając do tw. Dilwortha. Niech FM oznacza zbiór antyłańcuchów o maksymalnej długości w F uporządkowanym przez relację R. W FM wprowadźmy relację RM następująco: a RM b z definicji wtedy i tylko wtedy gdy ∀ x ∈ a ∃ y ∈ b t. że x R y
Pokażę, że jest to relacja porządku. A więc :
1) a RM a - oczywiste
2) Niech a RM b i b RM c . Mamy x ∈ a więc ∃ y ∈ b t. że x R y . Zatem ∃ z ∈ c t. że y R z. Z Przechodniości R mamy x R z. Więc a RM c
3) Niech a RM b i b RM a . Weźmy x∈a . Zatem ∃ y ∈ b t. że x R y. Więc ∃ z ∈ a t. że y R z. Ale wtedy x R z i oba należą do antyłańcucha, więc x = z. Mamy więc x R y i y R x, czyli y = x. Rozumując tak ∀ x ∈ a i korzystając z tego, że oba antyłańcuchy mają maksymalną liczbę elementów więc są równoliczne dostajemy a = b
Pokażę więcej, mianowicie FM z porządkiem RM jest kratą. Wystarczy pokazać, że:
∀ a b ∈ FM ∃ sup(a, b) i inf(a,b).
Ponieważ konstrukcje i dowody obu są identyczne z dokładnością do kierunków nierówności, szczegółowo przedstawię przypadek supremum, zostawiając - jak to mają w zwyczaju leniwcy infimum czytelnikowi. A więc, niech a i b ∈ RM .
Mamy a = a1∪(a ∩ b)∪a2 gdzie
a1 = {x : x∈ a\b , ∃ s ∈ b t. że x R s }
a2 = {x: x∈ a\b , ∃ s ∈ b t. że s R x }
Podobnie b = b1∪(b ∩ a)∪b2 gdzie
b1 = {x : x∈ b\a , ∃ s ∈ a t. że s R x }
b2 = {x : x∈ b\a , ∃ s ∈ a t. że x R s }
Zauważmy, że a1 ∩ a2 = b1 ∩ b2 = 0
Gdyby bowiem x ∈ a1 ∩ a2 to ∃ y1, y2 ∈ b t.że y1 R x i x R y2
ale wówczas, (skoro b jest antyłańcuchem) y1 = y2 więc y1 = y2 = x. Ale a1 (jak i a2) z definicji nie ma elementów wspólnych z b. Przy okazji wynika z tego że
#a = #a1 + #a∩b + #a2
i podobnie
#b = #b1 + #a∩b + #b2
gdzie przez # oznaczam liczność zbioru.
Pokażę teraz, że:
inf(a, b) = a1∪(a ∩b)∪b2 i
sup(a, b) = b1∪(a ∩ b)∪a2
Zajmijmy się supremum. b1∪(a ∩ b)∪a2 jest antyłańcuchem. Mianowicie żadne dwa elementy zbioru b1∪(a ∩ b) nie są porównywalne między sobą, podobnie (a ∩ b)∪a2 , Zatem pozostaje pokazać, że elementy b1 i a2 nie są porównywalne.
Załóżmy że ∃x ∈ b1 y ∈ a2 t.że x i y są porównywalne.
Gdyby y R x mielibyśmy z definicji zbiorów b1 i a2 że
∃s z ∈ b t.że s R x i x R y i y R z więc s R z czyli s = z = x = y co jest sprzeczne.
Gdyby zaś x R y wtedy ∃s z ∈ a t.że s R x i x R y i y R z i rozumujemy jak linijkę wyżej.
Podobnie pokazać można, że a1∪(a ∩ b)∪b2 jest antyłańcuchem.
Pozostaje pokazać, że oba łańcuchy są maksymalnej długości. Ale wiemy:
#a = #b więc #a1 + #(a ∩ b) + #a2 = #b1 + #(a ∩ b) + #b2
czyli
#a1 - #b1 = #b2 - #a2 ale:
# b1∪(a ∩ b)∪a2 = #b1 + #(a ∩ b) + #a2 =
#b - #(a ∩ b) - #b2 + #(a ∩ b) + #a2 = #b + (#a2 - #b2)
Podobnie
a1∪(a ∩ b)∪b2 = #a1 + #(a ∩ b) + #b2 =
#a - #(a ∩ b) - #a2 + #(a ∩ b) + #b2 = #b + (#b2 - #a2)
Gdyby więc #a2 - #b2 ≠ 0 jeden z tych dwóch antyłańcuchów miałby długość większą niż długość antyłańcucha o maksymalnej długości – co jest jawną sprzecznością.
Teraz pozostaje pokazać jeszcze, że supremum jest naprawdę supremum, tzn.
jeżeli a RM x i b RM x to sup( a , b ) RM x
Jeżeli a RM x to oczywiście każdy s ∈ a jest porównywalny z jakimś elementem antyłańcucha x (bo inaczej po dołączeniu do x tworzyłby większy antyłańcuch). Gdyby któryś z nich był silnie większy od pewnego elementu x to (patrząc na definicję porządku RM w FM) byłby również silnie większy a więc w szczególności porównywalny z jakimś innym elementem a co daje sprzeczność.
Podobnie można rozumować i dla b. Zatem (b1∪(a ∩ b)∪a2 ) RM x.
Niemal identyczne rozumowanie pokazuje, że zdefiniowane przez nas inf jest rzeczywiście infimum zbiorów w RM.
FM jest zatem kratą.
Weźmy teraz A maksymalny łańcuch w FM. Pokażę, że istnieje łańcuch C w F mający wspólny element z każdym elementem A. To proste: niech c1 będzie maksymalnym elementem w A a x1 elementem c1. Teraz indukcyjnie dopóki nie wyczerpiemy elementów A, mając x1...xk elementów tworzących łańcuch w F takich, że xi ∈ ci i ci poprzedza ci-1 w A, definiujemy ci+1 jako element bezpośrednio poprzedzający ci w A a xi+1 element ci+1 t. że xi+1 R xi (element taki istnieje z definicji porządku RM w FM. Zauważmy, że nie musi być różny od x1 !). Żądanym łańcuchem zbiór będzie {x1,...,xn} (tworząc z ciągu zbiór wyeliminowaliśmy powtórzenia).
Niech teraz, przy znaczeniu A i C jak wyżej, S będzie podzbiorem FM takim, że a ∈ S wtedy i tylko wtedy gdy a ∩ C ≠ 0. Łatwo zobaczyć z charakteryzacji inf i sup, że S ma własność z naszego Lematu, tzn że jezeli inf(a,b) i sup(a,b) są w S to i a i b są w S.
Jest tak rzeczywiscie: jeżeli x i y należą do C, x R y i x ∈ inf( a, b) i y ∈ sup (a, b) to albo:
- x ∈ a ∩ b - wtedy oczywiście a ∩ C ≠ 0 i a ∈ S i b ∩ C ≠ 0 i b ∈ S
- x ∈ a1 wtedy z konieczności y ∈ b1 i znowu j.w. a ∈ S i b ∈ S
- x ∈ b2 wtedy z konieczności y ∈ a1 i j.w.
Co więcej A jest łańcuchem maksymalnym w FM i jest (co wynika ze sposobu konstrukcji) zawarty w S. Na mocy Lematu zatem S = FM. Innymi słowy każdy antyłańcuch o maksymalnej liczbie elementów przecina się z łańcuchem A.
Teraz samo Twierdzenie Dilwortha.
Indukcyjnie. Twierdzenie jest porawdziwe gdy maksymalna długośc antyłańcucha jest 1. Załóżmy, że jest prawdziwe dla zbiorów uporządkowancyh z antyłańcuchem o maksymalnej długości k gdzie k < n. Weźmy teraz zbiór F, z antyłańcuchem o maksymalnej długości n. Z tego co udowodniliśmy powyżej wynika istnieje łańcuch C mający część wspólną z każdym anyłańcuchem maksymalnej długości w F. Wtedy F \ C jest zbiorem z antyłańcuchem o maksymalnej długości równej n-1 i z założenia indukcyjnego minimalna łańcuchów pokrywających go wynosi n-1. Zatem F da się pokryć przez n łańcuchów (łańcuchy pokrywające F\C i C). Jest to rzeczywiście liczba minimalna, bo gdyby dało się pokryć przez mniej (np. n-1) dwa elementy antyłańcucha o długości n musiałyby wpadać do tego samego łańcucha z pokrycia - co jest niemożliwe.
Uff
2010-03-14
Zagadnienie literackie
Ktoś czytał "Rękopis znaleziony w Saragossie" Potockiego? Zakładam, że film Hassa na motywach tejże powieści oglądał każdy (jest ponoć kultowy również poza Polską, pieniądze na restaurację i koloryzację filmu wyłożył M. Scorsese). OK, to nie odpytywanie z lektury, chodzi mi tylko o to by przypomnieć specyficzną konstrukcję owej powieści, (widzowie filmu mieli okazję poczuć jak to jest zrobione, ale w stopniu komplikacji film nie zbliża się nawet do książkowego oryginału). Jest owa konstrukcja mianowicie taka - pomysł zbieżny z wschodnimi "Baśniami tysiąca i jednej nocy" - mamy opowieść główną i głównego narratora, który przeżywając swoje przygody napotyka inne postaci, które opowiadają mu własne przygody (co narrator przytacza dosłownie więc narracja zawsze pozostaje narracją w pierwszej osobie), w tych opowieściach rekurencyjnie zaczynają się i kończą inne opowieści i tak dalej, przy czym "głębokość stosu" o ile mnie pamięć nie zawodzi sięga w najgłębszym miejscu czterech. To nie koniec, zdarza się, że poszczególne opowieści odwołują się do tych samych postaci i wydarzeń, mają wspólnych bohaterów i/lub są dobrze zlokalizowane w czasie względem wydarzeń historycznych.
Nie sporządziłem czytając, choć kusiło mnie niezmiernie i może kiedyś to zrobię, diagramu wszystkich tych opowieści. Gdyby miał powstać należałoby zrobić coś takiego:
-Wypisać wszystkie wydarzenia (zakładając upraszczająco ich punktowość w czasie) jakie miały miejsce do których odwołują się poszczególne opowieści.
-Wprowadzić relację późniejsze/wcześniejsze pomiędzy wydarzeniami w oparciu o:
a) następstwo chronologiczne wydarzeń wewnątrz opowieści.
b) fakt, że opowiadane są wydarzenia przeszłe w więc miały miejsce przed zdarzeniem polegającym na rozpoczęciu opowiadania
c) następstwo czasu względem wydarzeń historycznych wspomnianych w opowieściach
d) informacje o wieku bohaterów w opowieści w poszczególnych opowieściach
e) inne, które nie przyszły mi teraz do głowy
Teraz załóżmy że zaznaczymy sobie zdarzenia kropkami a fakt następowania zdarzeń po sobie oznaczymy strzałką skierowaną od zdarzenia wcześniejszego do późniejszego.
To co powinniśmy dostać - o ile Potocki sprytnie nie oszukał nas gdzieś (chcący), bądź nie popełnił złośliwego i niezauważanego przez jego samego i czytelników błędu (niechcący w tym wypadku) - to tzw. DAG (czyli Directed Acyclic Graph - skierowany graf bez cykli).
Właściwie, wysycając do końca informacje z punków a-e, powinniśmy uzyskać coś więcej, mianowicie graf reprezentujący silny porządek częściowy. To wysycenie sprowadza się do prostej uwagi, że następstwo w czasie jest relacją przechodnią (bardziej uczenie i z obca: tranzytywną), czyli jeżeli zdarzenie B następuje po zdarzeniu A a zdarzenie C po zdarzeniu B to zdarzenie C następuje po zdarzeniu A.
Sekunda na definicje:
DAG jest to para składająca się ze zbioru wierzchołków V i relacji R ⊆ VxV t.że dla każdego ∀a1...∀an t. że (ai,ai+1) ∈ R dla i = 1,...,n mamy a1 ≠ an
Porządek częściowy w zbiorze A jest to relacja R ⊆ AxA, która jest
1. zwrotna tzn. ∀ a (a,a) ∈ R
2. antysymetryczna tzn. (a,b) ∈ R i (b,a) ∈ R ⇒ a = b
3. przechodnia tzn. ∀ a b c (a,b) ∈ R i (b, c) ∈ R ⇒ (a,c) ∈ R
Nasz porządek wydarzeń w "Rękopisie" nazwałem "silnym porządkiem częściowym" co sprowadza się do tego, że modyfikujemy powyższą definicję i punkty 1 i 2 zastępujemy punktem:
1' antysymetryczna tzn ∀ a (a,a) ∉ R'
Mimo, że żaden porządek częściowy nie śmie być silnym porządkiem częściowym i vice versa (co przy okazji ilustruje nieco paradoksalne zjawisko semantyczne, że znaczenie rzeczownika z przymiotnikiem może nie mieścić się w zakresie znaczenia samego rzeczownika), to chwila zastanowienia pozwala stwierdzić, że są te relacje dobrymi krewnymi. Mianowicie (proste ćwiczenie) uzupełniając silny porządek R' o relację identyczności I = {(a,a), a \in A} dostajemy porządek częściowy, tzn R = R' ∪ I jest porządkiem częściowym. Podobnież, odejmując I od porządku R dostaniemy silny porządek częściowy (R'=R\I jest silnym porządkiem częściowym).
Dla pełnej konsystencji, wysycenie o którym wspomniałem w języku porządków sprowadza się do, nazwijmy to szumnie, twierdzenia:
Niech dany będzie DAG (A,R). Zdefiniujmy R'' = R ∪ RR ∪ RRR ∪ ... gdzie napisanie relacji jedna po drugiej oznacza operację ich złożenia. Wówczas (A, R'') jest silnym porządkiem częściowym. W fachowej nomenklaturze R'' nazywa się domknięciem tranzytywnym R. Częściej niż ja to zrobiłem tutaj, i dając lepsze konotacje nazwie "domknięcie tranzytywne" definiuje się ją tak: ∏ {S | s relacja tranzytywna na A} a potem dowodzi, że R'' jest postaci takiej jaką podałem za definicję. Ale operować w myślach, dla zbiorów skończonych przynajmniej, łatwiej znacznie konstruktywnym opisem.
Wracając do naszego modelu. Dla ułatwienia, ponieważ porządki częściowe to to z czym w matematyce pracujemy częściej, w dalszym ciągu wywodu nasz silny porządek częściowy, opisanym wyżej sposobem, zmienimy na porządek częściowy. W naszym kontekście literackim oznacza to, że przyjmujemy założenie z którym łatwo się pogodzić, że każde zdarzenie jest jednoczesne z samym sobą.
OK, zadajmy więc arcyliterackie Pytanie: ile maksymalnie zdarzeń opisanych w powieści mogło rozgrywać się jednocześnie ?
I natychmiast strawestujmy je w języku relacji porządkujących w następujący sposób: mając porządek częściowy w zbiorze skończonym, znaleźć maksymalną możliwą liczbę elementów wśród których żadne dwa nie będą porównywalne. Nazwiemy to szerokością zbioru uporządkowanego.
Można zrobić to na wiele sposobów, z których najprostszy i najbardziej pracochłonny to dla każdego podzbioru zbioru A sprawdzić czy jego elementy są parami nieporównywalne, jeżeli tak zapisać liczność tego zbioru i z zapisanych liczb po przejrzeniu całości wybrać liczbę największą.
Proponuję sposób następujący. Najpierw znowu pooznaczam:
A - zbiór skończony, R - relacja częściowego porządku w A, dla a ∈ A R+(a) = {x| aRx} \ {a} , R-(a) = {x | xRa}\{a}
Zdefiniuję teraz:
łańcuchem w (A,R) nazywamy podzbiór A który jest liniowo uporządkowany względem relacji R zawężonej do niego
antyłańcuchem w (A,R) nazywamy podzbiór w A w którym żadne dwa różne lementy nie są porównywalne. Szerokość zbioru oznaczę przez SZ.
Twierdzę teraz, że:
∀ a SZ(A) = max(SZ(A \ (R+(a) ∪ {a})), SZ(A \ (R+(a) ∪ {a})), 1+SZ(A\(R+(a) ∪ R-(a) ∪ {a})))
Jest tak gdyż:
Dla dowolnego elementu a, jeżeli
Przypadek 1) a należy do pewnego antyłańcucha o maksymalnej liczności. Wtedy antyłańcuch ten zawiera się w A\(R+(a) ∪ R-(a)) - bo ma a jako swój element i nie zawiera żadnego elementu porównywalnego z a. Wystarczy więc znaleźć jakiś antyłańcuch maksymalnej liczności w A\(R+(a) ∪ R-(a) ∪ {a}) i dołączyć do niego a (bo do każdego "dobrego" podzbioru elementów tego zbioru możemy dołączyć a dostajac ciągle dobry zbiór). Jego moc wynosi więc 1+SZ(A\(R+(a) ∪ R-(a) ∪ {a})).
Jeżeli zaś
Przypadek 2) a nie należy do antyłańcucha o maksymalnej liczności. Wtedy to pewien taki antyłańcuch zawiera się w A \ (R+(a) ∪ {a}) lub A \ (R-(a) ∪ {a}) (bo nie zawiera a, i nie może jednocześnie zawierać elementu z R+(a) i R-(a))
Ostatecznie szukając maksymalnej liczności antyłańcucha można sprowadzić do poszukiwania w podzbiorach jak w tezie (+1 dla wyniku w zbiorze A\(R+(a) ∪ R-(a) ∪ {a})) ) i wyboru maksymalnej z tych liczb.
Twierdzenie to sprowadza nam poszukiwanie SZ(A) do wyboru dowolnego elementu a i powtórzenia procedury dla trzech istotnie mniejszych zbiorów a następnie scalenia wyników przy pomocy prostej arytmetyki sprowadzającej się do inkrementacji jednego z wyników i funkcji maximum. To gotowy algorytm rekurencyjny.
Arbitralność wyboru elementu a otwiera pewne perspektywy w ew. optymalizacji algorytmu, ale mniejsza o to.
Ćwiczone na zajęciach z algorytmiki, wykładach z matematyki dyskretnej lub kombinatoryki, względnie ogólnie zainteresowane oko zauważy pokrewieństwo serwowanego problemu z twierdzeniem znanym pod nazwą twierdzenie Dilwortha. Mówi ono mianowicie, że w zbiorze częściowo uporządkowanym liczność maksymalnego (w sensie inkluzji) antyłańcucha w jest równa minimalnej ilości rozłącznych łańcuchów, których suma daje cały zbiór. To jednak jak to mówią, zupełnie inna historia.
Ciekawe, czy na zajęciach dajmy na to z teorii literatury na polonistyce nietaktem byłoby zadać nasze Pytanie ?
Przy okazji, do rozważań nad owym problemem i algorytmem sprowokowało mnie nie literatura wcale, ale pewne zagadnienie dotyczące alokacji zasobów w sieci telekomunikacyjnej. Ale to naprawdę inna historia.
Nie sporządziłem czytając, choć kusiło mnie niezmiernie i może kiedyś to zrobię, diagramu wszystkich tych opowieści. Gdyby miał powstać należałoby zrobić coś takiego:
-Wypisać wszystkie wydarzenia (zakładając upraszczająco ich punktowość w czasie) jakie miały miejsce do których odwołują się poszczególne opowieści.
-Wprowadzić relację późniejsze/wcześniejsze pomiędzy wydarzeniami w oparciu o:
a) następstwo chronologiczne wydarzeń wewnątrz opowieści.
b) fakt, że opowiadane są wydarzenia przeszłe w więc miały miejsce przed zdarzeniem polegającym na rozpoczęciu opowiadania
c) następstwo czasu względem wydarzeń historycznych wspomnianych w opowieściach
d) informacje o wieku bohaterów w opowieści w poszczególnych opowieściach
e) inne, które nie przyszły mi teraz do głowy
Teraz załóżmy że zaznaczymy sobie zdarzenia kropkami a fakt następowania zdarzeń po sobie oznaczymy strzałką skierowaną od zdarzenia wcześniejszego do późniejszego.
To co powinniśmy dostać - o ile Potocki sprytnie nie oszukał nas gdzieś (chcący), bądź nie popełnił złośliwego i niezauważanego przez jego samego i czytelników błędu (niechcący w tym wypadku) - to tzw. DAG (czyli Directed Acyclic Graph - skierowany graf bez cykli).
Właściwie, wysycając do końca informacje z punków a-e, powinniśmy uzyskać coś więcej, mianowicie graf reprezentujący silny porządek częściowy. To wysycenie sprowadza się do prostej uwagi, że następstwo w czasie jest relacją przechodnią (bardziej uczenie i z obca: tranzytywną), czyli jeżeli zdarzenie B następuje po zdarzeniu A a zdarzenie C po zdarzeniu B to zdarzenie C następuje po zdarzeniu A.
Sekunda na definicje:
DAG jest to para składająca się ze zbioru wierzchołków V i relacji R ⊆ VxV t.że dla każdego ∀a1...∀an t. że (ai,ai+1) ∈ R dla i = 1,...,n mamy a1 ≠ an
Porządek częściowy w zbiorze A jest to relacja R ⊆ AxA, która jest
1. zwrotna tzn. ∀ a (a,a) ∈ R
2. antysymetryczna tzn. (a,b) ∈ R i (b,a) ∈ R ⇒ a = b
3. przechodnia tzn. ∀ a b c (a,b) ∈ R i (b, c) ∈ R ⇒ (a,c) ∈ R
Nasz porządek wydarzeń w "Rękopisie" nazwałem "silnym porządkiem częściowym" co sprowadza się do tego, że modyfikujemy powyższą definicję i punkty 1 i 2 zastępujemy punktem:
1' antysymetryczna tzn ∀ a (a,a) ∉ R'
Mimo, że żaden porządek częściowy nie śmie być silnym porządkiem częściowym i vice versa (co przy okazji ilustruje nieco paradoksalne zjawisko semantyczne, że znaczenie rzeczownika z przymiotnikiem może nie mieścić się w zakresie znaczenia samego rzeczownika), to chwila zastanowienia pozwala stwierdzić, że są te relacje dobrymi krewnymi. Mianowicie (proste ćwiczenie) uzupełniając silny porządek R' o relację identyczności I = {(a,a), a \in A} dostajemy porządek częściowy, tzn R = R' ∪ I jest porządkiem częściowym. Podobnież, odejmując I od porządku R dostaniemy silny porządek częściowy (R'=R\I jest silnym porządkiem częściowym).
Dla pełnej konsystencji, wysycenie o którym wspomniałem w języku porządków sprowadza się do, nazwijmy to szumnie, twierdzenia:
Niech dany będzie DAG (A,R). Zdefiniujmy R'' = R ∪ RR ∪ RRR ∪ ... gdzie napisanie relacji jedna po drugiej oznacza operację ich złożenia. Wówczas (A, R'') jest silnym porządkiem częściowym. W fachowej nomenklaturze R'' nazywa się domknięciem tranzytywnym R. Częściej niż ja to zrobiłem tutaj, i dając lepsze konotacje nazwie "domknięcie tranzytywne" definiuje się ją tak: ∏ {S | s relacja tranzytywna na A} a potem dowodzi, że R'' jest postaci takiej jaką podałem za definicję. Ale operować w myślach, dla zbiorów skończonych przynajmniej, łatwiej znacznie konstruktywnym opisem.
Wracając do naszego modelu. Dla ułatwienia, ponieważ porządki częściowe to to z czym w matematyce pracujemy częściej, w dalszym ciągu wywodu nasz silny porządek częściowy, opisanym wyżej sposobem, zmienimy na porządek częściowy. W naszym kontekście literackim oznacza to, że przyjmujemy założenie z którym łatwo się pogodzić, że każde zdarzenie jest jednoczesne z samym sobą.
OK, zadajmy więc arcyliterackie Pytanie: ile maksymalnie zdarzeń opisanych w powieści mogło rozgrywać się jednocześnie ?
I natychmiast strawestujmy je w języku relacji porządkujących w następujący sposób: mając porządek częściowy w zbiorze skończonym, znaleźć maksymalną możliwą liczbę elementów wśród których żadne dwa nie będą porównywalne. Nazwiemy to szerokością zbioru uporządkowanego.
Można zrobić to na wiele sposobów, z których najprostszy i najbardziej pracochłonny to dla każdego podzbioru zbioru A sprawdzić czy jego elementy są parami nieporównywalne, jeżeli tak zapisać liczność tego zbioru i z zapisanych liczb po przejrzeniu całości wybrać liczbę największą.
Proponuję sposób następujący. Najpierw znowu pooznaczam:
A - zbiór skończony, R - relacja częściowego porządku w A, dla a ∈ A R+(a) = {x| aRx} \ {a} , R-(a) = {x | xRa}\{a}
Zdefiniuję teraz:
łańcuchem w (A,R) nazywamy podzbiór A który jest liniowo uporządkowany względem relacji R zawężonej do niego
antyłańcuchem w (A,R) nazywamy podzbiór w A w którym żadne dwa różne lementy nie są porównywalne. Szerokość zbioru oznaczę przez SZ.
Twierdzę teraz, że:
∀ a SZ(A) = max(SZ(A \ (R+(a) ∪ {a})), SZ(A \ (R+(a) ∪ {a})), 1+SZ(A\(R+(a) ∪ R-(a) ∪ {a})))
Jest tak gdyż:
Dla dowolnego elementu a, jeżeli
Przypadek 1) a należy do pewnego antyłańcucha o maksymalnej liczności. Wtedy antyłańcuch ten zawiera się w A\(R+(a) ∪ R-(a)) - bo ma a jako swój element i nie zawiera żadnego elementu porównywalnego z a. Wystarczy więc znaleźć jakiś antyłańcuch maksymalnej liczności w A\(R+(a) ∪ R-(a) ∪ {a}) i dołączyć do niego a (bo do każdego "dobrego" podzbioru elementów tego zbioru możemy dołączyć a dostajac ciągle dobry zbiór). Jego moc wynosi więc 1+SZ(A\(R+(a) ∪ R-(a) ∪ {a})).
Jeżeli zaś
Przypadek 2) a nie należy do antyłańcucha o maksymalnej liczności. Wtedy to pewien taki antyłańcuch zawiera się w A \ (R+(a) ∪ {a}) lub A \ (R-(a) ∪ {a}) (bo nie zawiera a, i nie może jednocześnie zawierać elementu z R+(a) i R-(a))
Ostatecznie szukając maksymalnej liczności antyłańcucha można sprowadzić do poszukiwania w podzbiorach jak w tezie (+1 dla wyniku w zbiorze A\(R+(a) ∪ R-(a) ∪ {a})) ) i wyboru maksymalnej z tych liczb.
Twierdzenie to sprowadza nam poszukiwanie SZ(A) do wyboru dowolnego elementu a i powtórzenia procedury dla trzech istotnie mniejszych zbiorów a następnie scalenia wyników przy pomocy prostej arytmetyki sprowadzającej się do inkrementacji jednego z wyników i funkcji maximum. To gotowy algorytm rekurencyjny.
Arbitralność wyboru elementu a otwiera pewne perspektywy w ew. optymalizacji algorytmu, ale mniejsza o to.
Ćwiczone na zajęciach z algorytmiki, wykładach z matematyki dyskretnej lub kombinatoryki, względnie ogólnie zainteresowane oko zauważy pokrewieństwo serwowanego problemu z twierdzeniem znanym pod nazwą twierdzenie Dilwortha. Mówi ono mianowicie, że w zbiorze częściowo uporządkowanym liczność maksymalnego (w sensie inkluzji) antyłańcucha w jest równa minimalnej ilości rozłącznych łańcuchów, których suma daje cały zbiór. To jednak jak to mówią, zupełnie inna historia.
Ciekawe, czy na zajęciach dajmy na to z teorii literatury na polonistyce nietaktem byłoby zadać nasze Pytanie ?
Przy okazji, do rozważań nad owym problemem i algorytmem sprowokowało mnie nie literatura wcale, ale pewne zagadnienie dotyczące alokacji zasobów w sieci telekomunikacyjnej. Ale to naprawdę inna historia.
2010-02-17
...o kole o ko...
Według wstępniaka w zamykającym całą zabawę numerze Journal of Memetics z 2005 roku, memetyka jako płodna metoda badawcza, czy wręcz nauka per se poniosła klęskę. Natomiast jako inspirująca metafora, co autor owego artykułu również przyznaje, broni się, w tym sensie, że z informacją, pomysłami, generalnie: myślowymi wytworami kultury, które dają się komunikować dzieje się coś co przypomina ewolucję. Można zatem również myśleć o elementarnych cegiełkach dziedziczenia replikujących się i przekształcających podobnie jak kod genetyczny. Nie należy lekceważyć metafory. Wpływowe systemy filozoficzne bywały wzniesione na jednej metaforze (lub zredukowały się do niej). Ustroje państw miały przypominać ciało ludzkie, rzeczywistość płynęła jak woda lub płonęła jak ogień, społeczeństwa miały być maszynami, zegarami, porządek wśród ludzi miał odzwierciedlać ten jaki panuje między gatunkami, w wieku pary rządziła termodynamika, w adwencie wieku komputerów wszystko zdawało się przypominać komputer, dziś jako paradygmat (który w jakimś stopniu daje się sprowadzić do wielkiej metafory) króluje sieć. Metafora DNA dla świata myśli i idei ludzkich nie jest więc niczym specjalnie dziwnym czy niezwykłym.
Podążając, nie do końca przecież świadomie jej ścieżkami bawić się można wyjaśnianiem, uprawianiem filogenetycznej taksonomii myśli - nie jak prawdziwy naukowiec czy filozof przecież, ale tak zabawowo, pozostając do owych prawdziwych w stosunku takim samym jak miłośnik astronomii do astronoma. Mnie osobiście ostatnio pociągają peryferie pomiędzy filozoficzną spekulacją (którą często cenię za jej pomysłowość, czasem za moc i wielkość wizji, bywa że za dziwność, rzadko jednak uznaję jej roszczenie do prawdy innej niż ta na którą samo jej istnienie jest dowodem) a matematyką (w której podobnież cenię pomysłowość, wielkość wizji, czasem dziwność, ale której jestem skłonny przyznać znacznie więcej w kwestii prawdy).
Idąc tym tropem, kolejna karkołomna zabawa w skojarzenia.
O ile zdaje się TEN (w rozumieniu taki) Pitagoras któremu tak wiele przypisywali starożytni nie istniał, prazałożyciel szkoły Pitagoras dał głównie imię idolowi wielu stuleci, firmując nim postać o cechach herosa. Istnieli natomiast niewątpliwie pitagorejczycy. I oczywiście - z oddalenia przecież obraz rozmywa się i zlewa - ta nazwa obejmuje wiele różnych i często różniących się ruchów. Ci, którzy mnie chwilowo interesują, to pitagorejczycy można rzewc oryginalni, z okresu archaicznego, przedsokratejskiego. Widzimy ich dzisiaj, choć raczej jako tło dla innych przedsokratyków, znanych z nazwiska i przeniesionych w strzępach informacji (eleatów, filozofów jońskich). Pitagorejczycy wierzyli w harmonię i liczbę budując jak się zdaje coś w formie religii czy mistyki geometryczno-matematycznej. Wiązało się to z kilkoma odkryciami np. z powiązaniem proporcji w długościach struny a harmonijnym brzmieniem dźwięków z niej wydobywanych, z geometrią liczb wiążącą własności abstrakcji jaką jest liczba z konkretem jakim jest geometryczna konfiguracja, rozmieszczenie, przedmiotów ze zbioru o określonej liczności. Podobno głęboko skrywaną przez nich przez długi czas tajemnicą - być może wywracającą ich świat na nice, porównywalną jezeli chodzi o moc intelektualnego wstrząsu jaki powodowało jej poznanie z twierdzeniami Godla we nowożytnej nauce - był dowód istnienia liczb niewymiernych (a konkretnie, w ich nomenklaturze, dowód niewspółmierności przekątnej i boku kwadratu).
Poza mistyką liczby, wielki wpływ na pitagorejczyków miały jak się zdaje misteria o charakterze religijnym. Mianowicie kult orficki, orfizm. Archaiczna religia dokoptowana do achajskiej przez mit Orfeusza zstępującego do Hadesu i opuszczającego go. (ćwiczenie: z jakim memem mamy tu do czynienia ?). Jedną z głównych idei orfizmu - powielaną w różnych mutacjach w różnych religiach i filozofiach była idea reinkarnacji, metempsychozy. W orfiźmie dusza miała przejść pewną ustaloną i zdaje się nie wynikającą z jej dotychczasowego życia ilość inkarnacji. W innych systemach bywa inaczej: reinkarnacja w hinduiźmie np. nie ogranicza się przechodzenia przez postacie ludzkie, ale dusza odradza się w istotach żywych, zajmując miejsce w ich hierarchii (od nailichszego robactwa do człowieka) a jeśli już wcieleniem jest człowiek: w hierarchii społecznej (systemie kastowym) w zależności od dotychczasowego życia. Karma czyli przeznaczenie jest więc wynikiem postępowania i wyboru. Poza reinkarnacją liniową - tak rozumiałbym orficko-pitagorejską, i reinkarnacją nieliniową jak hinduistyczna umieściłbym coś co do końca nie jest może reinkarnacją ale bardzo ją przypomina - by abuse of the language nazwijmy ją reinkarnacją kołową. Do takiej zaliczałbym fantastyczną wyznawaną np. przez stoików ideę absolutnej kolistości czasu i historii a więc cyklicznej, idealnej, powtarzalności losu nie tylko człowieka ale wszechświata jako całości. Wszechświat stoików w niesamowity sposób przypomina jedną z idei współczesnej kosmologii - podyktowaną analizą możliwych rozwiązań równań Einsteina - wszechświata pulsujacego pomiędzy jedną a drugą osobliwością, na przemian eksplodującego z punktu (o którym równania owe i sama teoria niewiele lub nic nie może powiedzieć) i ostatecznie ginącego w takim samym punkcie z którego wszystko być może (równania tracą sens w osobliwości i nie można wnioskować na pewno co będzie "potem") zaczyna się na nowo.
Ideę powtarzalności zdarzeń w ciekawy literacko sposób wykorzystał (i dostarczył mi w ten sposób w odległych licealnych czasach kilku czytelniczych przyjemności) znany kolekcjoner perwersji umysłowych Jorge Luis Borghes. Prócz powtarzania tego motywu w wielu opowiadanich popełnił jeszcze z Adolfo Bioy Cesaresem powieść "Wynalazek Morela" w której uczynili z niego oś rozgrywającej się akcji. Polecam.
Cykliczność to jeden z podstawowych motywów matematycznych, toposów (w sensie teorioliterackim nie teoriokategoryjnym - o tych drugich mam chętkę napisać osobno) możnaby powiedzieć, gdyby do matematyki podejść jak do literatury. Od wczesnych i nieuświadomionych co do swojej ogólności form analizy harmonicznej (np. takiej jak w astronomii ptolemeuszowskiej rozkładającej ruchy ciał niebieskich na złożenie stosownych cykli), przez jej formy dojrzałe, przez badanie cykliczności w równaniach różniczkowych po formy wyrafinowane kiedy ścisła kolistość i cykliczność zostaje porzucona na rzecz niedokładnej, przybliżonej - jak w twierdzeniach o powrocie Poincare'go, teorii ergodycznej i w końcu teorii chaosu temat cykliczności powraca cyklicznie. Oczywiscie w wypadku matematyki nie jest to kwestia żadnej mody ale wynika wprost z natury badanych obiektów matematycznych. Ale czy nie jest i tak z toposami literackimi ? Czy owe motywy wracające od jednej opowieści do drugiej nie wyrastają po prostu z naszej natury, z podobieństwa i powtarzalności sytuacji w jakich znajduje się człowiek, ze wspólnego doświadczenia stada ludzkiego, starszego o tysiąclecia od czegokolwiek co dziś za literaturę moglibyśmy uważać?
Koniec. I tak za dużo i zbyt chaotycznie jak na tak długa przerwę.
Podążając, nie do końca przecież świadomie jej ścieżkami bawić się można wyjaśnianiem, uprawianiem filogenetycznej taksonomii myśli - nie jak prawdziwy naukowiec czy filozof przecież, ale tak zabawowo, pozostając do owych prawdziwych w stosunku takim samym jak miłośnik astronomii do astronoma. Mnie osobiście ostatnio pociągają peryferie pomiędzy filozoficzną spekulacją (którą często cenię za jej pomysłowość, czasem za moc i wielkość wizji, bywa że za dziwność, rzadko jednak uznaję jej roszczenie do prawdy innej niż ta na którą samo jej istnienie jest dowodem) a matematyką (w której podobnież cenię pomysłowość, wielkość wizji, czasem dziwność, ale której jestem skłonny przyznać znacznie więcej w kwestii prawdy).
Idąc tym tropem, kolejna karkołomna zabawa w skojarzenia.
O ile zdaje się TEN (w rozumieniu taki) Pitagoras któremu tak wiele przypisywali starożytni nie istniał, prazałożyciel szkoły Pitagoras dał głównie imię idolowi wielu stuleci, firmując nim postać o cechach herosa. Istnieli natomiast niewątpliwie pitagorejczycy. I oczywiście - z oddalenia przecież obraz rozmywa się i zlewa - ta nazwa obejmuje wiele różnych i często różniących się ruchów. Ci, którzy mnie chwilowo interesują, to pitagorejczycy można rzewc oryginalni, z okresu archaicznego, przedsokratejskiego. Widzimy ich dzisiaj, choć raczej jako tło dla innych przedsokratyków, znanych z nazwiska i przeniesionych w strzępach informacji (eleatów, filozofów jońskich). Pitagorejczycy wierzyli w harmonię i liczbę budując jak się zdaje coś w formie religii czy mistyki geometryczno-matematycznej. Wiązało się to z kilkoma odkryciami np. z powiązaniem proporcji w długościach struny a harmonijnym brzmieniem dźwięków z niej wydobywanych, z geometrią liczb wiążącą własności abstrakcji jaką jest liczba z konkretem jakim jest geometryczna konfiguracja, rozmieszczenie, przedmiotów ze zbioru o określonej liczności. Podobno głęboko skrywaną przez nich przez długi czas tajemnicą - być może wywracającą ich świat na nice, porównywalną jezeli chodzi o moc intelektualnego wstrząsu jaki powodowało jej poznanie z twierdzeniami Godla we nowożytnej nauce - był dowód istnienia liczb niewymiernych (a konkretnie, w ich nomenklaturze, dowód niewspółmierności przekątnej i boku kwadratu).
Poza mistyką liczby, wielki wpływ na pitagorejczyków miały jak się zdaje misteria o charakterze religijnym. Mianowicie kult orficki, orfizm. Archaiczna religia dokoptowana do achajskiej przez mit Orfeusza zstępującego do Hadesu i opuszczającego go. (ćwiczenie: z jakim memem mamy tu do czynienia ?). Jedną z głównych idei orfizmu - powielaną w różnych mutacjach w różnych religiach i filozofiach była idea reinkarnacji, metempsychozy. W orfiźmie dusza miała przejść pewną ustaloną i zdaje się nie wynikającą z jej dotychczasowego życia ilość inkarnacji. W innych systemach bywa inaczej: reinkarnacja w hinduiźmie np. nie ogranicza się przechodzenia przez postacie ludzkie, ale dusza odradza się w istotach żywych, zajmując miejsce w ich hierarchii (od nailichszego robactwa do człowieka) a jeśli już wcieleniem jest człowiek: w hierarchii społecznej (systemie kastowym) w zależności od dotychczasowego życia. Karma czyli przeznaczenie jest więc wynikiem postępowania i wyboru. Poza reinkarnacją liniową - tak rozumiałbym orficko-pitagorejską, i reinkarnacją nieliniową jak hinduistyczna umieściłbym coś co do końca nie jest może reinkarnacją ale bardzo ją przypomina - by abuse of the language nazwijmy ją reinkarnacją kołową. Do takiej zaliczałbym fantastyczną wyznawaną np. przez stoików ideę absolutnej kolistości czasu i historii a więc cyklicznej, idealnej, powtarzalności losu nie tylko człowieka ale wszechświata jako całości. Wszechświat stoików w niesamowity sposób przypomina jedną z idei współczesnej kosmologii - podyktowaną analizą możliwych rozwiązań równań Einsteina - wszechświata pulsujacego pomiędzy jedną a drugą osobliwością, na przemian eksplodującego z punktu (o którym równania owe i sama teoria niewiele lub nic nie może powiedzieć) i ostatecznie ginącego w takim samym punkcie z którego wszystko być może (równania tracą sens w osobliwości i nie można wnioskować na pewno co będzie "potem") zaczyna się na nowo.
Ideę powtarzalności zdarzeń w ciekawy literacko sposób wykorzystał (i dostarczył mi w ten sposób w odległych licealnych czasach kilku czytelniczych przyjemności) znany kolekcjoner perwersji umysłowych Jorge Luis Borghes. Prócz powtarzania tego motywu w wielu opowiadanich popełnił jeszcze z Adolfo Bioy Cesaresem powieść "Wynalazek Morela" w której uczynili z niego oś rozgrywającej się akcji. Polecam.
Cykliczność to jeden z podstawowych motywów matematycznych, toposów (w sensie teorioliterackim nie teoriokategoryjnym - o tych drugich mam chętkę napisać osobno) możnaby powiedzieć, gdyby do matematyki podejść jak do literatury. Od wczesnych i nieuświadomionych co do swojej ogólności form analizy harmonicznej (np. takiej jak w astronomii ptolemeuszowskiej rozkładającej ruchy ciał niebieskich na złożenie stosownych cykli), przez jej formy dojrzałe, przez badanie cykliczności w równaniach różniczkowych po formy wyrafinowane kiedy ścisła kolistość i cykliczność zostaje porzucona na rzecz niedokładnej, przybliżonej - jak w twierdzeniach o powrocie Poincare'go, teorii ergodycznej i w końcu teorii chaosu temat cykliczności powraca cyklicznie. Oczywiscie w wypadku matematyki nie jest to kwestia żadnej mody ale wynika wprost z natury badanych obiektów matematycznych. Ale czy nie jest i tak z toposami literackimi ? Czy owe motywy wracające od jednej opowieści do drugiej nie wyrastają po prostu z naszej natury, z podobieństwa i powtarzalności sytuacji w jakich znajduje się człowiek, ze wspólnego doświadczenia stada ludzkiego, starszego o tysiąclecia od czegokolwiek co dziś za literaturę moglibyśmy uważać?
Koniec. I tak za dużo i zbyt chaotycznie jak na tak długa przerwę.
Subskrybuj:
Posty (Atom)
Posty
