Post szczytowo-pompowy z rekomendacją

Dowiedziałem się, że elektrownie szczytowo-pompowe (takie jak na górze Żar) służą (nie jest to oczywiście ich podstawowa funkcja) w przypadku wielkich awarii w sieci energetycznej, kiedy wyłączają się całe elektrownie do ponownego rozruchu systemu. By bowiem uruchomić bloki energetyczne często potrzebna jest już spora energia. Wtedy zmagazynowana w takiej elektrowni woda służy do wygenerowania energii elektrycznej, która inicjuje resztę systemu. Jeśli więc przejść, prawem przenośni, od sytemu energetycznego do bloga, Homo Sapie... przeżywał kilkumiesięczną przerwę w działaniu i jakiś odpowiednik - coś małego na początek by system wprawić w ruch - elektrowni szczytowo pompowej mu się należy. Niech będzie to niniejszy krótki post (wybaczcie pewną sztywność i nieporadność stylistyczną - wyszedłem nieco z wprawy).

Tym razem rekomendacja: w dzisiejszym skrócie z arXiv zauważyłem bardzo interesującą króciutką pracę przeglądową Adama Grygiela dotycząca osiągnięć w Teorii Liczb na przestrzeni dekady 1999-2009. Omówienie podzielono zgodnie z dość powszechnie przyjętą klasyfikacją Mathematical Review. Praca jest naprawdę zwięzła i najlepiej przeczytać ją całą samemu - ja napisze tylko o moich osobistych refleksjach.

Co do części pierwszej poświęconej elementarnej teorii liczb kompletnie umknęło mojej uwadze rozwiązanie hipotezy Sierpińskiego dotyczącej rozwiązań równania z funkcją Eulera w roli głównej. Dziwne, choć rok publikacji 1999 - to środek okresu kilku lat absolutnego chaosu w moim życiu prywatnym i zawodowym, więc poniekąd czuję się usprawiedliwony.

Wzmiankowane w rozdziale “Sequences and Set of Integers” prace Gowersa, Greena i Tao są być może najbardziej spopularyzowanymi spośród omawianych wyników. W tych okolicach plasowały się w ostatnich latach Medale Fieldsa. Poza tym wspomniani matematycy prowadzą intensywną działalność popularyzatorsko-publicystyczną i Internecie, co przyczynia się również do popularności wiedzy o tych rezultatach. Niemniej jednak w metodach które kryją się za tymi wynikami czai się w moim odczuciu potężna siła. Z pierwocinami niektórych z nich (na ile cokolwiek rozumiem z tych metod) zetknąłem się w czasach studenckich intensywnie przeglądając książkę Furstenberga “Recurrence in Ergodic Theory and Combinatorial Number Theory”. Temat , choć jak wielu innych nie przetrawiłem go wówczas dogłębnie, wydał mi się fascynujący. Szczególnie w owym czasie przypadł mi do gustu dowód Furstenberga twierdzenia Van der Waerdena o postępach arytmetycznych. Po wielu latach poznałem z uroczej książeczki Chińczyna orygianlny dowód Van der Waerdena - sprytny, ale nie dał mi takiej satysfakcji jak Furstenberga. Twórcze rozwinięcie tych metod - to teraźniejszość i chyba przyszłość. Tego się warto nauczyć...

W dziale “Diophantine equations” - wielki sukces ostatnich lat czyli udowodnienie przez Mihailescu hipotezy Catalana. Zadziwiające, że poszło to metodami algebraicznymi (z którymi u mnie kiepsko). Kiedyś może spróbuję się zmierzyć z tym dowodem. Niemniej jednak zapoczątkowane przez Gelfonda potem rozwinięte przez Bakera a potem drążone przez Tijdemana metody analityczne, które zdawały się podchodzić tuż, tuż mimo, ze zawiodły wciąż mają moim zdaniem swój potencjał. Lubię je, bo sam ich kiedyś użyłem w małej co prawda sprawie, ale zawsze ;).

O dziale “Analytic numbers theory” za wiele nie umiem powiedzieć, poza tym, że o hipotezie Schinzla oczywiście słyszałem (i ona bardziej chyba niż słynny problem Colatza zasługuje na słowa Erdosa, ze jest poza zasiegiem współczesnej matematyki). Podobnie słyszałem wcześniej o wynikach Goldstona, Pintza i Yıldırıma o małych odstępach między liczbami pierwszymi, ale chyba nie doceniłem wagi wyniku.

Ostani dział, czyli obliczeniowa teoria liczb - trudno dziś o tym nic nie wiedzieć. To być może najbardziej praktyczny aspekt teorii liczb dzisiaj. Testy pierwszości o których mowa są bardzo wyrafinowane. To wyzwanie dla matematyków i informatyków. Przez nagminność stosowania teorioliczbowych metod w kryptografii dotykają te zagadnienia samych podstaw funkcjonowania masowej telekomunikacji w obecnym kształcie we współczesnym świecie. Ale mnie, szczerze mówiąc, jakoś ten temat dziś nie bardzo pociąga. Inaczej było wiele lat temu, gdy rozpoczynałem pracę - wtedy podniecał mnie dużo bardziej.

Na koniec refleksja natury ogólniejszej - artykuł został złożony do American Mathematical Monthly (więc pisma popularnego) ale wcześniej ukazał się w Wiadomościach Matematycznych po polsku. Szkoda, że nie propaguje się i nie promuje piśmiennictwa matematycznego w Polsce i po polsku należycie. Do Wiadomosci Matematycznych trudno się dostać a upubliczniają artykuły z dużym opóźnieniem. IMHO to kompletnie bez sensu. Jest to chyba jedyne polskie pismo które drukuje na poziomie popularnym ale dla matematyków i bardziej wyrobionych amatorów. Sporo wyżej niż nieoceniona Delta, ale jednak nie jest to periodyk stricte badawczy. Odczuwam dotkliwy deficyt “w tym segmencie rynku” w naszym kraju. Poza tym: czy ktoś słyszał o jakimś blogującym na bieżące tematy matematyku w tym kraju ? Po polsku - znalazł by się jeden (patrz rekomendacje blogów na marginesie). Ale newsy z pola walki ? - skazani jesteśmy na anglojęzyczne publikacje, blogi itp. Szkoda. Ale rozumiem...

Jeszcze jedna uwaga. Takie sympatyczne prace z krótkim omówieniem jak ta o której piszę szybko zostają zauważone - bo pozwalają ludziom zerknąć na trochę bardziej panoramiczny, choć mocno okrojony co do szczegółów obrazek. W moich twittowych subskrybcjach już ktoś o niej napomknął. Dla amatorów takich jak ja - zawsze wielka radość móc się z takim materiałem zapoznać. Co i moim porzuconym na miesiące czytelnikom polecam. Praca tu: http://arxiv.org/PS_cache/arxiv/pdf/1010/1010.2484v1.pdf

Natręctwo

Dręczy mnie mały problem matematyczny - nie wiem czy trudny (jak bym znał rozwiązanie to bym wiedział, ale wtedy bym nie pytał). Zgaduje, że jest znany w folklorze matematycznym. Prześladuje na tyle natrętnie, że przeszkadza mi trochę w pracy, więc postanowiłem się chociaż cześciowo uwolnić dzieląc się nim.
Zatem:
Na płaszczyźnie euklidesowej, dla zbioru ograniczonego S przez szerokość S w kierunku X gdzie X jest dowolną prosta, rozumiem kres dolny odległości prostych prostopadłych do X takich, że S mieści się w pasie między nimi. Oznaczmy go W(S,X).
Ograniczę się do zbiorów S będących homeomorficznymi obrazami okręgu - krzywych zamkniętych bez samoprzecięć. Dla S1 , S2 równość funkcji W(S1 , _) ≡ W(S2, _) na ogół nie oznacza, że S1 jest przystające do S2 . Najprostsze kontrprzykłady to krzywe niewypukłe, np brzeg kwadratu z małym wcięciem “do środka” na jednym z boków. Ale wypukłość też nie daje gwarancji - przykładem okrąg i trójkąt Roleaux (ten od silnika Wankla) o szerokości równej średnicy okręgu.
Pytanie jakie mnie nurtuje: A co jeżeli założmy, że krzywa jest wypukła (ogranicza obszar wypukły) i gładka (tzn. jest gładkim włożeniem okręgu) ? Czy wtedy W(S1 , _) ≡ W(S2, _) gwarantuje przystawanie S1 i S2 ?

Newton, Pascal i hermeneutyka - witajcie w świecie 4G

Mimo, że skończyłem szkołę w odległych i coraz szybciej, niestety, oddalających się czasach, pojęcie lektury obowiązkowej nie stało mi się obce. Tak więc, poza rzeczami które czytam z ciekawości, z chęci wzbogacenia poglądów, dla nauki, dla przyjemności, ze snobizmu etc. etc. zdarza mi się czytać rzeczy po prostu z obowiązku. Ostatnia lektura, która poczatkowo wydawała mi się koszmarnie nudna ale ciekawość moja rosła i wciąż rośnie oraz pojawiają się pewne oznaki satysfakcji z niej, to pewne fragmenty dokumentu o wiele mówiącym oznaczeniu 3GPP TS 36.213 V8.8.0 (2009-09) .

Tu dygresja: studiowanie dokumentów opisujących standardy telekomunikacyjne ma w sobie coś z sztuki walki, coś z rozwiązywania rebusa i coś ze studiowania świętej księgi. Zatem: Środki retoryczne jakimi posługują się autorzy owych dzieł ograniczają się zwykle do nadużywania trybu rozkazującego ("X shall Y..." - "Zaprawdę powiadam Ci, X będzie Y..." ). Powtarzalność schematów zdań ukrywa nagłe zwroty akcji. Jakakolwiek motywacja działań bohaterów jest szczelnie zakryta przed czytelnikiem. Zrozumienie wymaga długotrwałych medytacji i skomplikowanych egzegez. Wrogiem jest montonia, nuda, nieuwaga. Piszący owe standardy, w końcu, często nadzwyczaj jednostronnie biorą sobie do serca uwagę Gaussa o "zwiezłości, cesze którą należy brać pod rozwagę tak bardzo jak to możliwe".
Szczególnym gatunkiem owej literatury, do których przynależy i przywołany przeze mnie dokument, są opisy standardów komunikacji bezprzewodowej. Kapryśna i ograniczona natura medium i nieustający głód szybkości, pojemności i niezawodności prowadzi do tworzenia skomplikowanych piętrowych konstrukcji, nad którymi władzę absolutną sprawują Oszczędność, Zapobiegliwość i Kompromis.

Wracając do mojej lektury, okazuje się, że aby zadość uczynić surowym prawom owych trzech władców nadzwyczaj często należy uciec się do fortelu a pomocnikiem jest matematyka. O jednym fortelu , na który się natknąłem opowiem, bo to proste, ciekawe i - przynajmniej dla mnie - zaskakujące. Istotę tego fortelu należy jednak dopiero wyłuskać z opisu. Rzecz podana została bowiem do wierzenia.

Pomedytujmy, nad następującymi wersetami (przy okazji będącymi typową próbką stylu):




Co się za tym kryje. Otóż, chodzi o metodę pozwalającą w możliwie najzwięźlejszy sposób przekazać informację o wybranym M-elementowym podzbiorze w uporządkowanym zbiorze N - elementowym. Zakładamy przy tym, że obie strony znają N i M.

Uwaga - w dalszym ciągu na oznaczenie symbolu Newtona przyjmę (^N_M) - oznacza "N po M". Stosuję też konwencję jak w artykule (tj. dla N <>N_M) = 0).

Jak możnaby to zrobić? Pierwszy pomysł to wziąć N bitów i zapalić odpwiednie M z nich (stworzyć mapę bitową), następnie przesłać taką liczbę binarną. Ale, N może być duże i przesłać musielibyśmy wiele liczb. Ba, ten sposób pomija zupełnie informację, że M jest ustalone i potrzebuje więc zwykle [log₂N]+1 (czasem tylko log2N) bitów ale wykorzystuje tylko (^N_M)/2^N część owej przestrzeni możliwych map bitowych. Z punktu widzenia królowej Oszczędności sytuacja niedopuszczalna.

Możnaby z drugiej strony - korzystając z faktu, że jest (^N _M) kombinacji N elementów z M elementów - wymyślić jakąkolwiek funkcję przypisującą liczbom od 0 do (^N _M) -1 stosowny zbiór, umówić obie strony zeby ją znały i używały. Musielibyśmy wówczas jednak wymyślić bardzo wiele takich funkcji dla różnych par N i M - Zapobiegliwość nie byłaby z nas zadowolona.

Kompromisu w takich sytuacjach nakazuje s: znajdźmy uniwersalny sposób kodowania. Fortel - i mamy metodę opisaną w standardzie. Poniżej zajmę się jej objaśnieniem:

Po pierwsze, przypomnijmy sobie wzór dotyczący symbolu Newtona - nb. kluczowy dla konstrukcji trójkąta Pascala:

(ⁿ _k) + (ⁿ _k-1) = (ⁿ⁺¹ _k) (*)

Po drugie zauważmy, że jezeli n > m to
(ⁿ _k) >= (^m _k) (**)

To łatwo udowodnić indukcją (zadanie licealne) albo zobaczyć od razu (stosując indukcję niejako niejawnie) z (*). Po prostu

(ⁿ _k) = (^n-1 _k) + (^n-1_k-1) = (^n-2 _k) + (^n-2 _k-1) + (^n-1 _k-1) = [powtarzamy rozwinięcie pierwszego składnika] = (^m _k) + C

które to C jest >=0 (> 0 jeśli n > k).

Po trzecie zauważmy, że:

(^N-1 _M) + (^N-2 _M-1) +... + (^N-M ₁) = (^N _M) -1 (***)

Tym razem: szybka ale trochę fikuśna indukcja:

Oznaczmy F(n,m) = (^n-1 _m) + ... + (^n-m ₁)

Wtedy:
F(n,1) = (^n-1 ₁) = n = (ⁿ ₁) -1

Załóżmy, że dla ustalonego n i m F(n-1,m-1) = (^n-1 _m-1) -1

Wtedy F(n,m) = (^n-1 _m) + F(n-1, m-1) = (^n-1 _m) + (^n-1 _m-1) - 1 = (ⁿ _m) -1

(ponownie z (*) )

Teraz prosto do tajemnicy naszego indeksu.

Weżmy jakiekolwiek r ∈ {0,..., (^N _M)-1}.

Weźmy największe K = K(r, N, M) t. że (K(r,N,M) _M) <= r. Takie K(r, N, M) oczywiście istnieje i jest jedyne - z (**) Zauważmy, że r - (^{K(r, N, M)} _M) ≤ (^{K(r, N, M)} _M-1) - 1

to jasne bo w przeciwnym razie

r >= (^{K(r, N, M)} _M) + _{(^{K(r, N, M)} M-1}) = (^{K(r, N, M)+1} _M)

co jest sprzecznością bo K(r, N, M) było największe


Zatem, dla r' = (r - (^{K(r, N, M)} _M)) ∈ {0,...,(^K _M-1)-1} czynność możemy powtórzyć wyliczając K':

K > K' = K((r - (^K _M)), K, M-1)

itd. dla M-2, M-3 itd i kolejnych r otrzymując ciąg M różnych wartości.

W ten sposób podaliśmy, algorytm który danego r w jednoznaczny sposób przypisuje ciąg {K_i} spełniający warunek K_i > K_i+1

Proponuję - jako ćwiczenie, żeby nie było nudno - sprawdzić, że opisany algorytm wykonuje operację dokładnie odwrotną do tej opisanej w naszym cytacie. Dodam, że zdaje się, że by to stwierdzić nie trzeba już nic liczyć...

Równe

Wspomniałem w jednym z postów o ksiażce "A=B". W części ogólnej - bo potem zajmuje się tożsamościami z symbolem Newtona w roli głównej - zwraca ona uwagę na pewien stały motyw: jeżeli potrafimy policzyć coś na dwa sposoby, to dostajemy ciekawe prawo (matematyczne, fizyczne itp). Dla mnie tego typu dowody są bardzo atrakcyjne i estetyczne. Twórcze rozwinięcie tego motywu można znaleźć w uroczej książeczce "Proofs that really count: the art of combinatorial proof"

Jedno z moich pierwszych doświadczeń matematycznych, gdzieś głęboko w czasach szkoły podstawowej polegało właśnie na małym odkryciu w tym duchu. Otóż nudząc się jak mops na jakiejś lekcji (nie wykluczam, że matematyki) rysowałem sobie na kartce punkciki łącząc każdy z każdym.



Powtarzając tą mechaniczną czynność zauważyłem, że pierwszy łączę z n-1 pozostałymi, drugi już z n-2 (bo z pierwszym już połączony) itd. Lewa strona była więc gotowa, miałem połączeń: 1+2+3+...+(n-1)

Potem spostrzegłem, że każdy jest połaczony z (n-1) pozostałymi i każde połaczenie licząc w ten sposób jest powtórzone dwa razy: Wyłania się prawa strona : n(n-1)/2 . I w końcu dumny znak "=":


1+2+3+...+(n-1) = n(n-1)/2


Przeżyłem to - jakkolwiek nie zabrzmi to perwersyjnie - jako głęboką przyjemność. Być może tamta chwila zdecydowała w ogóle o moim wyborze wykształcenia.

Z świata celebrytów

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

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 = a₁∪(a ∩ b)∪a₂ gdzie

a₁ = {x : x∈ a\b , ∃ s ∈ b t. że x R s }

a₂ = {x: x∈ a\b , ∃ s ∈ b t. że s R x }

Podobnie b = b₁∪(b ∩ a)∪b₂ gdzie

b₁ = {x : x∈ b\a , ∃ s ∈ a t. że s R x }

b₂ = {x : x∈ b\a , ∃ s ∈ a t. że x R s }



Zauważmy, że a₁ ∩ a₂ = b₁ ∩ b₂ = 0

Gdyby bowiem x ∈ a₁ ∩ a₂ to ∃ y₁, y₂ ∈ b t.że y₁ R x i x R y₂

ale wówczas, (skoro b jest antyłańcuchem) y₁ = y₂ więc y₁ = y₂ = x. Ale a₁ (jak i a₂) z definicji nie ma elementów wspólnych z b. Przy okazji wynika z tego że

#a = #a₁ + #a∩b + #a₂

i podobnie

#b = #b₁ + #a∩b + #b₂

gdzie przez # oznaczam liczność zbioru.

Pokażę teraz, że:

inf(a, b) = a₁∪(a ∩b)∪b₂ i

sup(a, b) = b₁∪(a ∩ b)∪a₂


Zajmijmy się supremum. b₁∪(a ∩ b)∪a₂ jest antyłańcuchem. Mianowicie żadne dwa elementy zbioru b₁∪(a ∩ b) nie są porównywalne między sobą, podobnie (a ∩ b)∪a₂ , Zatem pozostaje pokazać, że elementy b₁ i a₂ nie są porównywalne.

Załóżmy że ∃x ∈ b₁ y ∈ a₂ t.że x i y są porównywalne.

Gdyby y R x mielibyśmy z definicji zbiorów b₁ i a₂ ż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 a₁∪(a ∩ b)∪b₂ jest antyłańcuchem.


Pozostaje pokazać, że oba łańcuchy są maksymalnej długości. Ale wiemy:

#a = #b więc #a₁ + #(a ∩ b) + #a₂ = #b₁ + #(a ∩ b) + #b₂

czyli

#a₁ - #b₁ = #b₂ - #a₂ ale:

# b₁∪(a ∩ b)∪a₂ = #b₁ + #(a ∩ b) + #a₂ =

#b - #(a ∩ b) - #b₂ + #(a ∩ b) + #a₂ = #b + (#a₂ - #b₂)

Podobnie

a₁∪(a ∩ b)∪b₂ = #a₁ + #(a ∩ b) + #b₂ =

#a - #(a ∩ b) - #a₂ + #(a ∩ b) + #b₂ = #b + (#b₂ - #a₂)


Gdyby więc #a₂ - #b₂ ≠ 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 (b₁∪(a ∩ b)∪a₂ ) 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 c₁ będzie maksymalnym elementem w A a x₁ elementem c₁. Teraz indukcyjnie dopóki nie wyczerpiemy elementów A, mając x₁...x_k elementów tworzących łańcuch w F takich, że x_i ∈ c_i i c_i poprzedza c_i-1 w A, definiujemy c_i+1 jako element bezpośrednio poprzedzający c_i w A a x_i+1 element c_i+1 t. że x_i+1 R x_i (element taki istnieje z definicji porządku RM w FM. Zauważmy, że nie musi być różny od x₁ !). Żądanym łańcuchem zbiór będzie {x₁,...,x_n} (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 ∈ a₁ wtedy z konieczności y ∈ b₁ i znowu j.w. a ∈ S i b ∈ S

- x ∈ b₂ wtedy z konieczności y ∈ a₁ 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

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.

...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ę.

(Meta)fizyka kombinatoryczna

Potraktujmy poniższe jako niezobowiązującą zabawę w skojarzenia.

Nie wiem czy i do jakiego stopnia Epikura należałoby nazwać filozofem. Stworzył on coś w rodzaju świeckiej religii, której celem było wyzwolenie człowieka od starchu, egzystencjalnego przerażenia. Drogą ku owej wolności , oprócz stosownych reguł życia był - chciałoby się powiedzieć: wyznawany - materializm, który miał usunąć "lęk metafizyczny" i strach przed śmiercią. Jest chyba podobieństwo pomiędzy epikureizmem a psychoterapią (niekoniecznie freudowską, np. jakąś Gestalt czy coś w tym guście - nie znam się zbytnio na psychoterapii), którą w czasach współczesnych ludzie stosują w dokładnie tym samym celu. Ale ja nie o tym właściwie chciałem.

Epikur nie pozostawił pisanej spuścizny opierając się na nauczaniu ustnym i kształceniu uczniów - praktyków jego filozofii i podejścia do życia - krzewiących jego idee dalej. Ten model okazał się zaskakująco skuteczny skoro "wyznanie" epikurejczyków, przetrwało jakieś 500 lat w świecie starożytnym. Elementy filozofii epikurejskiej pokazujące metafizyczne koncepcje stojące za nią dotarły w dużej mierze dzięki twórczości "szeregowych" epikurejczyków utrwalających naukę w swojej twórczości. Najbardziej znany z nich to Lukrecjusz, którego poemat "O naturze wszechrzeczy" to chyba najważniejsze a na pewno najbardziej znane pismo epikurejskie dotrwałe do naszych czasów. Mimo braku programowych ksiąg kodyfikujących doktrynę metafizyczną epikureizmu, trochę o niej wiemy. Przede wszystkim koncepcje bytu i natury świata nie były tu spekulacją prowadzącą do wniosków o charakterze praktycznym, ale wręcz przeciwnie - mądrość życiowa, odrzucenie strachu, droga do szczęścia i wolności człowieka, słowem filozofia życia Epikura wyprzedzał metafizykę, która miała dać dla niej jedynie teoretyczne podstawy, zakorzenić ją w wizji samej natury świata. Jak wspomniałem epikureizm opierał się na materializmie - materia, to co dotykalne, jest jedynym bytem a rządzą materią ustalone racjonalne prawa. Fizyka tego świata to atomizm. Atomy to niepodzielne i podstawowe elementy materii, różnych co prawda ale w ustalonym wyborze rozmiarów i kształtów. Oczywiście epikurejczycy nie mieli pojęcia o grawitacji w rozumieniu dzisiejszym, mieli natomiast naiwne pojęcie o ciążeniu, jako o sile działającej wzdłuż kierunku (a właściwie konstytuującej kierunek) góra-dół. Naturalnym ruchem atomów był więc spadek, poruszanie się w dół. Jednak aby nie stały się jedynie lawiną równolegle spadających cząstek należało wprowadzić coś co tchnie w nią "życie". Zatem do naturalnego ruchu w dół atomom epikurejskim arbitralnie dodano losowy ruch na boki nazwany climena - odchylenie. To remedium na nudny, nieskończenie trywialny determinizm. To climena powoduje, że pojawiają się interakcje atomów, ich zderzenia, łączenie się. Za jego sprawą pojawiają się, jako losowy produkt owych interakcji światy. Dokładnie tak: światy a nie jeden świat. Wśród losowych konfiguracji atomów epikurejczycy za pewne przyjmują pojawienie się kiedyś każdej możliwej ich kombinacji a zatem i każdego możliwego świata. Są to światy chwilowe, nietrwałe, wynikłe z tymczasowej konfiguracji atomów. Ich pojawienie się jest jednak w jakichś sposób konieczne.

Ten aspekt metafizyki, czy też fizyki epikurejskiej jakoś mnie uwiódł. Postaram się wytłumaczyć dlaczego. W oczywisty sposób widzę w nim pewne wczesne ale i daleko idące intuicje probabilistyczne. Np. taką, że nawet niesłychanie mało prawdopodobne zdarzenia w odpowiednio długiej serii losowań (a każda zmiana oparta o climena jest niejako nowym aktem losowania, czy raczej krokiem losowego błądzenia) w końcu z wielką dozą pewności w niej się pojawią.
Ale to pierwsza myśl. Drugie skojarzenie dotyczące intuicji epikurejskich - tym razem na pograniczu probabilistyki i logiki - to teoria tzw. praw zero-jedynkowych. To niesłychanie ciekawe twierdzenia, których protoplastą było prawo zero-jedynkowe udowodnione w latach 60 przez matematyków radzieckich (a przepraszam: sowieckich). Brzmi ono tak:
Niech phi będzie dowolnym zdaniem w języku pierwszego rzędu o skończonej sygnaturze relacyjnej (tzn. języku zawierającym jedynie symbole relacyjne i to w skończonej ilości) wtedy, lim_n->∞ μ_n(φ) = 0 albo 1, gdzie przez μ_n(φ) rozumie się ilość nieizomorficznych modeli rozmiaru n zdania φ.

Co mówi prawo zero-jedynkowe w bardziej ludzkim języku? Ano mówi, że względnie proste zdania o prostym, losowym świecie (w odległy sposób przypominającym co do zasady epikurejską rzeczywisość atomów), są albo trywialnie prawdziwe albo trywialnie fałszywe. Tzn, jeżeli dopuścić naprawdę wielki losowy świat, albo lepiej, coraz większe losowe światy, to prawdopodobieństwo prawdziwości bądź fałszywości owych zdań w tych światach staje się coraz większe. Innymi jeszcze słowy, w coraz większym procencie - rosnącym wraz z rozmiarami - owych światów opisywane przez te zdania struktury istnieją, bądź nie istnieją. Pożytecznym zastosowaniem praw zero-jedynkowych jest możliwość dowodzenia twierdzeń o niewyrażalności pewnych własności w językach pierwszego rzędu. Taką własnością - co wynika z zacytowanego prawa prawa zero-jedynkowego niemal natychmiast - jest parzystość liczby elementów w strukturze relacyjnej. Nie jest to intuicyjne - przynajmniej dla mnie. Prawa zero-jedynkowe są więc ciekawe.
Mnie zawsze kusi, choć to oczywiście zabawa i żart i nie należy traktować tego poważnie, żeby ekstrapolować treść praw zero-jedynkowych na tzw. real w następujący sposób: wszystko co powiemy jasnym i prostym językiem jest albo trywialnie prawdziwe albo trywialnie nieprawdziwe. (Dla potrzeb żartu odrzucam tu wszystkie, ale to absolutnie wszystkie możliwe zastrzeżenia i upraszczam sprawę maksymalnie. Zastrzegam się tak, żeby nie gorszyć ew. czytających te słowa - jednych pozostawiając z fałszywymi przekonaniami co do praw zero-jedynkowych, drugich co do mojej osoby). Gdyby zbudować model formalny epikurejskiej fizyki i udowodnić o nim coś na kształt prawa zero jedynkowego, oznaczałoby to, że pewne konfiguracje, czy światy są w nim niemal konieczne, muszą się pojawić i pojawiają się często, inne zaś, mimo że logicznie możliwe pojawiają się rzadko, przygodnie - w praktycznym rozumieniu tego słowa: nigdy.

Prawa zero-jedynkowe funkcjonują w świecie absolutnie sprawiedliwie losowym. Co jednak ze światami które oszukują, w któych istnienie bądź nieistnienie relacji nie zależy od rzutu uczciwą monetą ale oszukaną. Tu ciekawe rzeczy mówi nam np. teoria grafów (i ogólnie hipergrafów) losowych. Tam pojawiają się interesujące zjawiska w postaci wartości krytycznych prawdopodobieństw zachodzenia relacji przy których dane zdanie stanie się niemal pewnym itp. To w ogóle droga do ciekawej i modnej ostatnio dziedziny badań na styku rachunku prawdopodobieństwa, kombinatoryki, teorii liczb. Wiele się tam ekscytujących rzeczy ostatnio dzieje.

Witaj szkoło! (1?)

Moi bardzo młodzi acz niezbyt wierni czytelnicy zaglądający tu często w poszukiwaniu gotowców wypracowania (jak wynika z danych z google analytics) zaczynają właśnie szkołę. Mnie, bo zawsze mi to uświadamia jaki się stary powoli robię i ponieważ wbrew ogólnym tendencjom szkołę wspominam raczej dobrze, od razu łezka się w oku kręci. Szczęśliwe lata... Nie ma co!

Z dedykacją dla nich, dziś wpis przynależący do cyklu rekreacji matematyczno-informatycznych. Skoro szkoła, zatem i matematyka, skoro matematyka to algebra, skoro algebra to wielomiany, wzory skróconego mnożenia i inne tego typu przyjemności. Spróbujmy więc zobaczyć jak sobie poradzi z takimi zabawkami maszyna. Napiszemy ni mniej ni więcej tylko miniaturowy i prościutki system do obliczeń symbolicznych w języku Haskell.

Małe zastrzeżenia: nie będę używał tu całego potencjału języka, jak np. klas żeby jeszcze bardziej nie komplikować pojęciowo programu. Tematy jakie poruszę: algebra elementarna, wielomiany, typy danych, rekurencja, mapowanie list, składanie list, list comprehension (proponuję termin: ujawnianie postaci listy - nie wiem jak to przetłumaczyć dosłownie), odrobinę programowania generycznego.


Zaczynamy:

Ukłon w kierunku standardowej biblioteki, z której skorzystamy wkrótce:

import Char

Na poczatek, skoro algebra i wielomiany, to i zmienne, które będą dowolnymi łańcuchami znaków. Oczywiście to niebezpieczne założenie, bo może prowadzić do mylących nazw zmiennych, jak np taka: ", " ale nasz system będzie prościutki więc zaryzykujemy spychając konieczność pilnowania się na użytkownika. Zatem:

type Var = String

Zmienne w wielomianie występują w potęgach, a zapis potęgi danej zmiennej składa się z nazwy tej zmiennej i liczby całkowitej - potęgi w której występuje. W naszym systemie zareprezentujemy to jako parę (zmienna, liczba całkowita):

type Power = (Var, Integer)

Teraz jednomian (ale bez współczynnika jeszcze) czyli lista potęg zmiennych

type Monomial = [Power]

Jednomian ze współczynnikiem całkowitym (nazwany przeze mnie dla wygory PTerm-em) reprezentujemy przez parę:

type PTerm = (Integer, Monomial)

I w końcu wielomian, który jest listą PTermów:

type Polynomial = [PTerm]

Poćwiczmy rozumienie tych reprezentacji.

Przykład 1:

Wielomian x reprezentujemy jako jednoelementowa listę PTerm-ów, której jedynym elementem jest jednomian x^1 ze współczynnikiem 1. Zatem reprezentacja będzie wyglądać: [(1,[("x",1)])]


Przykład 2:

Wielomian x*y reprezentujemy jako jednoelementowa listę PTerm-ów, której
jedynyjm elementem jest jednomian x^1*y^1 ze współczynnikiem 1. Zatem
reprezentacja będzie wyglądać: [(1,[("x",1),("y",1)])]


Przykład 3:

Wielomian x^3*y+4*y^2*z+1 reprezentujemy jako trójelementową listę:

[ (reprezentacja PTermu x^3*y), (reprezentacja PTermu 4*y^2*z), (reprezentacja PTermu 1)] =

[(1, reprezentacja jednomianu x^3*y), (4,reprezentacja jednomianu y^2*z),
(1, reprezentacja jednomianu pustego)] =

[(1,[reprezentacja potęgi x^3, reprezentacja potęgi y^1]), (4, [reprezentacja ptęgi y^2, reprezentacja ptęgi z^1]), (1,[])] =

[(1,[("x",3),("y",1)]), (4,[("y",2),("z",1)]), (1,[])]


OK. Uznaję, że zrozumieliśmy jak reprezentujemy wielomian i przy okazji przy tych rachunkach na palcach trochę polizaliśmy metody "schodzenia w głąb struktury" którą będziemy konsekwetnie stosować.

Na moment porzućmy wielomian i przejdźmy do użytecznej funkcji, której użyję wkrótce. Do sortowania. Oto prosty kod generycznej implementacji algorytmu quicksort, którego użyjemy:


Deklaracja:

sort :: (x -> x -> Bool) -> [x] -> [x]

i implementacja:

sort _ [] = []
sort f (a:rs) = (sort f [x|x<-rs, f x a]) ++ [a] ++ (sort f [x|x<-rs, f a x]) 

Deklaracja mówi nam, że jako argumenty funkcja sort przyjmie:

- funkcję przyjmującą dwa argumenty pewnego nieokreślonego typu i zwracającą dla nich jedną z wartości typu Bool (True lub False)

- listę elementów owego typu

Jako wynik działania otrzymamy znowu listę elementów tego typu.


Po cichu zakładamy, że argumenty są dobre, tzn. owa funkcja będąca pierwszym argumentem dla sort jest operacją mniejszości (z wszystkimi konsekwencjami takimi jak antysymetria i przechodniość wyznaczonej przez nią relacji).
Implementacja sort intensywnie korzysta z rekurencyjnej natury quicksorta. Zasadą algorytmu quicksort, która pozwala zrozumieć go bez trudu, a którą ujawnia wprost niniejszy kod jest taka: Weźmy pierwszy element z listy, którą chcemy posortować, potem wrzućmy do pewnej listy wszystkie elementy mniejsze od niego i posortujmy (znowu quicksortem), do drugiej listy wrzućmy wszystkie elementy większe od niego i też posortujmy. Wyliczmy następnie listę wynikową przez sklejenie rezultatów sortowania listy pierwszej, elementu wziętego na początku i rezultatów sortowania listy drugiej. W ramach ćwiczenia można spróbować indukcyjnie udowodnić sobie poprawność tego algorytmu (tzn. że rzeczywiście sortuje).

Zapis (a:rs) jest wzorcem do którego intepreter dopasuje listę z argumentu. Po dopasowaniu w zmiennej a znajdzie sie element stanowiący jej głowę, w zmiennej rs lista (być może pusta) bedąca jej ogonem.

Operacja ++ jest operacją konkatenacji czyli złączenia list, natomiast konstrukcja [ x|x<-rs, f a x ] jest operacją "list comprehension", co ja nazywam operacją "ujawnienia postaci listy" ¹.

Oznacza ona, w tym wariancie, stworzenie listy tych elementów x listy rs, które spełniają f a x, gdzie f jest stosowną funkcją a a jest ustalone w danym kroku rekurencji.


Wykonajmy:

Test 1:

Wgrywamy plik w dotychczasowej postaci

Hugs> :load "C:\\Users\\Artur\\Documents\\tar.hs"

i wywołujemy:

Main> sort (<) [1,2,4,3,2,6,9,0] [0,1,2,3,4,6,9] 

Nasza funkcja sort rzeczywiście czasami działa. Oczywiście warto pobawić się i przekonać że działa rzeczywiście często :) i w różnych przypadkach.


Kolejną funkcją usługową, z której w różnych kontekstach skorzystamy, będzie funkcja simplify (uprość). Próbuję w niej zawrzeć pewien szczególny sposób upraszczania wyrażeń.
Deklaracja funkcji:

simplify :: (x -> x -> Bool) -> (x -> x -> x) -> [x] -> [x]

i implementacja:

simplify _ _ [] = []
simplify eq gr (h:t) = simplify_step h $ simplify eq gr t where
                       simplify_step f lst =
                           (foldl gr f [x | x <- lst, eq f x]) : 
                                      [x | x <- lst, not $ eq f x ] 

Funkcja simplify bierze jako argument dwie funkcje dwuargumentowe działające na nieznanym apriori typie danych oraz listę elementów tego typu, zwraca zaś listę elementów tego typu.

Pierwsza z funkcji wziętych w argumencie przyjmuje dwa argumenty i zwraca wartość typu Bool (tzn. True lub False). Będzie pełniła rolę operatora porównania. Druga, dla dwu argumentów danego typu produkuje element tego typu i będzie pełniła rolę funkcji kumulacji.

simplify, działa tak, że przebiega listę wyszukuje wszystkie elementy listy równe ze względu na funkcję eq (pierwszy argument) i zastępuje je wszystkie elementem będacym ich kumulacją. Jak to działa w konkretnych przypadkach i dlaczego ma, jak wspomniałem, uchwycić pewną formę upraszczania zobaczymy za chwilę.


Z punktu widzenia języka, implementacja funkcji wprowadza sporo nowych konstrukcji poza znanym już dopasowaniem wzorca. Mamy więc operator $ oznaczajacy, że Haskell wyliczy wartość tego co po prawej stronie i użyje wyliczonej wartości w miejscu $.

Druga konstrukcja to wywołanie rekurencyjne nie zadeklarowanej ani nie zdefiniowanej wcześniej funkcji simplify_step. Funkcja ta jest zdefiniowana lokalnie po słowie where które oznacza własnie, że zdefiniowane zostaną lokalne funkcje. Typ funkcji simlify_step Haskell wydedukuje samodzielnie natomiast jej działanie jest następujące: funkcja bierze jako argument element typu takiego jaki użyty jest w argumentach wołającej ją funkcji simplify i listę elementów tego typu. Następnie wybiera te elementy listy lst którym argument f jest równy względem funkcji eq. Potem składa a właściwie kumuluje używając funkcji foldl wartości tej listy używając funkcji gr i wartości początkowej f. Ostatecznie dostaje pewien element typu takiego jak f. Następnie element ten użyty będzie jako głowa listy której ogonem bedzie lista tych elementów listy lst które nie będą równe f według relacji zadanej przez eq. Złożenie tej listy z głowy i ogona dokonuje się za pośrednictwem konstruktora listy : .

Nieco tajemnicza operacja foldl (której dokładną implementację warto podglądnąć w standardowym module Haskella Prelude) działa w taki sposób, że przyjmuje jako argumenty dwuargomentową funkcję typu (x ->x->x), czyli funkcję biorącą dwa argumenty pewnego typu x i zwracającą element typu x, wartość początkową typu x zgodnego z typem użytym w funkcji i listę elementów typu x . Następnie, jeżeli lista jest niepusta, oblicza wartość funkcji podanej jako argument na dwóch argumentach: zadanej wartości początkowej i głowie listy. Rezultat traktuje jako wartość początkową w rekurencyjnym wywołaniu samej siebie z tą samą funkcją jako argumentemi ogonem listy jako listą. Efektywnie, powoduje to zwijanie listy od lewej strony i kumulowanie wyniku.

Popatrzmy na przykład:

Przykład 4:
Jako funkcji w argumencie foldl użyjemy operatora + działąjącego na argumentach typu Int, jako wartości początkowej 1 a jako listy dwuelementowej listy zawierającej 2 i 3. Kto chce się sprawdzić niech spróbuje bazując na tym co napisane powyżej przewidzieć wynik. A oto rezultat Haskella

Hugs> foldl (+) 1 [2, 3]

Wracamy do wielomianów. Wysiłek jaki włożyliśmy w ogólność funkcji simplify zwróci się teraz przy upraszczaniu jednomianów. Ponieważ jednomian jest listą potęg i na liście tej potęgi tej samej zmiennej moga znaleźć się więcej niż raz, wprowadźmy funkcję upraszczającą eliminującą ową patologię. Oto jej deklaracja i definicja będąca specjalizacją zdefiniowanej powyżej funkcji simplify w której jako funkcja porównująca użyte będzie porównanie pierwszych elementów pary (a więc zmiennych), a jako funkcja kumulująca dodawanie wykładników (co odpowiada mnożeniu potęg):

simplify_mon :: Monomial -> Monomial

simplify_mon = simplify (\x y->fst x == fst y)
                    (\x y -> (fst x, snd x + snd y))

Mamy tu dwie nowe i ciekawe konstrukcje. Po pierwsze funkcje porównującą i kumulującą zdefiniowaliśmy jako funkcje anonimowe używając tzw lambda-abstrakcji. Przy takiej definicji po lewej stronie operatora -> deklarujemy argumenty funkcji poprzedzając je backslashem (będącym w tym kontekście daleko idącą stylizacją greckiej litery lambda), po prawej umieszczamy zaś stronie definicję działanie funkcji na argumentach.

Drugi interesujący element: nie wyspecyfikowaliśmy argumentu dla simplify_mon. Nie jest to jednak konieczne. Funkcja simplify jest trójargumentowa a w definicji simplify_mon ustalone zostały pierwsze dwa argumenty trzeci z nich pozostaje zmienny. Zatem ustalenie argumentów uczyniło z funkcji simplify funkcję jednoargumentową simplify_mon, przyjmującą jako argument argument ospowiadający trzeciemu argument funkcji simplify.


Kolejnym nowym elementem są dwie standardowe funkcje z modułu Prelude, mianowice fst i snd. Służą one do wybrania pierwszego (fst) i drugiego (snd) elementu pary.


Sprawdźmy teraz działanie simplify_mon. Musimy nasz jednomian zadać wprost

Test 4:

Hugs> :load "C:\\Users\\Artur\\Documents\\tar.hs"

Main> simplify_mon [("x",1), ("x",1)]
[("x",2)]

Uff. Coś działa.


Teraz jednomian sprowadzimy do postaci kanonicznej, co będzie oznaczało, że oprócz uproszczenia posortujemy jeszcze listę go reprezentującą względem porządku alfabetycznego zmiennych. Oto funkcja:

canonize_mon :: Monomial -> Monomial

canonize_mon mon = sort (<) $ simplify_mon mon 

Inteligentny Haskell, dzięki modułowi Prelude wie jak porzenieść porządki zdefiniowane dla elementów pary leksykograficznie na porządek par. Funkcję sort już znamy. Zobaczmy canonize_mon w działaniu:


Test 5:

Main> canonize_mon [("x",1), ("x",1), ("a",5)]
[("a",5),("x",2)]

Zgodnie z oczekiwaniami.



Teraz sprowadźmy do postaci kanonicznej cały wielomian. Załatwimy sprawę jedną funkcją używając definicji lokalnych:

canonize_poly :: Polynomial -> Polynomial

canonize_poly p = sort (>) $
                simplify (\x y -> snd x == snd y)
                         (\x y -> (fst x + fst y, snd x)) $
                            map (\x -> (fst x, canonize_mon $ snd x) ) p

Nowym elementem tu jest interesująca funkcja map zdefiniowana w standardowym module Haskella Prelude, która przenosi działanie fukcji którą dostaje w argumencie na działanie na listach. Innymi słowy podając fukcję pewnego typu (x->y) jako argument do fukcji map otrzymujemy fukcję typu [x]->[y], która działa na liście w ten sposób, że tworzy nową listę każdy element której jest obrazem elementu fukcji wejściowej przez fukcję podaną jako argument do map.


Przykład 5:

Prelude> map (4*) [1,2,3]
[4,8,12]
Prelude> map (\x -> [x]) ["a", "b", "c"]
[["a"],["b"]["c"]]

Sprawdźmy w działaniu funkcję canonize_poly (póki co wielomian zadawać będziemy explicite - jeszcze tylko króciótko się tak pomęczymy)


Test 6:

Main> canonize_poly [(3,[("x",1),("x",1)]), (2,[("x",2)]), (5,[("x",2),("a",4)])]

[(5,[("x",2)]),(5,[("a",4),("x",2)])]

Teraz zajmiemy się przedstawieniem naszych wielomianów w czytelnej dla nas formie, jako łancuchów znakowych. Zapisywać wielomiany będę oczywiście w sposób internetowy używając ASCII jedynie. Pedantycznie przepisywać bedę '*' w miejsce mnożenia i '^' przy potęgowaniu, jako ustępstwo na rzecz ładnego stylu dbając jedynie o unikanie gdzie nie potrzeba potęg pierwszych i mnożenia explicite przez 1. Przedstawię cały kod a potem omówię nowe elementy:

tostring_mon :: Monomial -> String

tostring_mon [] = ""
tostring_mon [(x,y)] | y == 1 = x
                 | otherwise = x++"^"++ (show y)
tostring_mon (a:rest) = (tostring_mon [a] ) ++ "*" ++ (tostring_mon rest)

tostring_pterm (c, []) = show c
tostring_pterm (1, m) = tostring_mon m
tostring_pterm (c, m) = (show c) ++ "*" ++ tostring_mon m

tostring_poly :: Polynomial -> String

tostring_poly [] = ""
tostring_poly [f] = tostring_pterm f
tostring_poly (f:tl) = foldl (++) (tostring_pterm f) $
                                  map (("+"++).tostring_pterm) tl

W funkcji tostring_mon użyłem wariantowej definicji funkcji, przypominającej mocno zapis matematyczny w postaci tak zwanej klamry, z drugiej zaś trony konstrukcję if...elsif.....else albo bardziej zaawansowany (bo nie oparty o typ numeryczny switch() .. case znany z C, C++ i Javy. Po znaku '|' mamy kolejne warunki spełnieni których przez argumenty oznacza, że wartością funkcji będzie to co po znaku równości.

Kolejna nowość tam to funkcja show stosująca się do pewnych typów przynależnych do klasy Show. Zamienia ona elementy tych typów (w naszym przypadku Integer jest takim typem) na łańcuchy znaków (typ String).
Przy okazji wyszło szydło z worka - String jest po prostu listą znaków (typ Char) i można wobec niego stosować te same operacje co wobec innych list.


Teraz pierwsza radość - zamienimy na napisy pierwsze wielomiany. Zacznijmy od wielomianów z testu 6:


Test 7:

Main> tostring_poly [(3,[("x",1),("x",1)]), (2,[("x",2)]), (5,[("x",2),("a",4)])]

"3*x*x+2*x^2+5*x^2*a^4"

Main> tostring_poly $ canonize_poly [(3,[("x",1),("x",1)]), 
(2,[("x",2)]), (5,[("x",2),("a",4)])]
"5*x^2+5*a^4*x^2"

Teraz mam nadzieję, że lepiej widać na czym polega kanonizacja.

Po mału doszliśmy do miejsca w którym możemy zdefiniować operacje na wielomianach. Zacznijmy od dodawania, które będziemy oznaczać fantazyjnym operatorem ~+, a które zdefiniujemy w zaskakująco prosty sposób.

infix 1 ~+

(~+) :: Polynomial -> Polynomial -> Polynomial
x ~+ y = canonize_poly $ x ++ y

Dodawanie jest więc jak widać konkatenacją list reprezentujących wielomiany. My, dla porządku jeszcze dodakowo od razu wynik konkatenacji skanonizujemy.

Ciekawy element to operator, który deklarujemy jako infix, czyli że argumenty dostawał będzie nie jak funkcja po swojej prawej stronie, ale jak porządny operator po obu swoich stronach. Dla potrzeb deklaracji jednak, musimy zaminieć go na chwilę na normalną funkcję (zdjąć z niego niejako "infiksowość") przez obłożenie go nawiasami.


Podobnie prosto zdefiniujemy mnożenie:

infix 2 ~*

(~*) :: Polynomial -> Polynomial -> Polynomial

p1 ~* p2 = canonize_poly [(c1*c2, m1++m2) | (c1, m1) <- p1 , (c2, m2) <- p2] 

Tym razem korzystamy z faktu, że mnożenie wielomianów (będących sumą jednomianów) jest sumą wszystkich możliwych iloczynów par jednomianów, z których jeden pochodzi od pierwszego a drugi od drugiego wielomianu. Plus oczywiście kanonizacja dla porządku. Załatwiamy to jedną operacją ujawnienia postaci listy.


Czas na:


Test 8:

Spróbujemy pomnożyć x*(x+y+z*x^2):

Main> tostring_poly $ x ~* (x ~+ (y ~+ z ~* (x ~* x))) where (x,y,z) = 
([(1,[("x",1)])],[(1,[("y",1)])],[(1,[("z",1)])])
"x^3*z+x^2+x*y"

Cały wielomian zrealizowany został jako wynik operacji na trywialnych wielomianach x, y, i z które zdefiniowane są po słówku where, wszystkie na raz w jedej krotce.

Wynik znowu zgodnie z oczekiwaniami.

Mając już takie narzędzia, zajmijmy się na chwilę klasyką, tj. tadam... dwumian Newtona. Policzmy go dla potęgi 5 dajmy na to:

Test 9:

Main> tostring_poly $ ((((a ~* a) ~* a) ~* a) ~*a) where a = [(1,[("x", 1)]),(1,[("y", 1)])]
"10*x^3*y^2+10*x^2*y^3+5*x^4*y+5*x*y^4+y^5+x^5"

Cóż, w nieco nieortodoksyjnym porządku, ale to czego należało się spodziewać.


Jak czytelnik pewnie zauważył zadawanie wielomianów w naszej surowej postaci nie jest wygodne, z tego względu pokusimy się o bardzo prosty parser, zamieniający reprezentację wielomianu jako zrozumiałego dla człowieka łańcucha znaków na reprezentację wewnętrzną. Ogólnie pisanie parsera wymaga sporo delikatności i uwagi, ale my napiszemy coś naprawdę bardzo prostego cedując na użytkownika staranność w zadawaniu wejścia dla parsera.

By zrealizować nasz parser, potrzebować będę tokenizera, tj funkcji zaminiającej łańcuch znaków na listę łańcuchów znaków będących rezultatem podzielenia listy oryginalnej na fragmenty rozdzielone z góry zadanym znakiem. Np napis "Ala ma kota" po "tokenizacji" względem znaku ' ' (spacja) stanie się listą ["Ala","ma","kota"]


Oto nasza funkcja tokenize, bioraca jako argument znak i łańcuch znaków a zwracającą stosowną listę łańcuchów:

tokenize :: Char -> String -> [String]

tokenize v "" = []
tokenize v x = tokenize_raw v x [] [] where
   tokenize_raw v [] [] rv = rv
   tokenize_raw v [] cs rv = (rv++[cs])
   tokenize_raw v (f:r) cs rv | f == v = tokenize_raw v r [] (rv++[cs])
                              | otherwise = tokenize_raw v r (cs ++ [f]) rv

Sprawdźmy działanie naszego tokenizera:


Test 10:

Main> tokenize ' ' "Ala ma kota"
["Ala","ma","kota"]

Dokładnie jak się spodziewaliśmy.


Wykorzystamy teraz funkcję tokenize do parsowania wielomianów. Strategia jest następująca. Najpierw łańcuch podzielimy funkcją tokenize względem znaku '+', następnie każdy z tak otrzymanych kawałków podzielimy wgledem znaku '*' a potem każdy z nich względem znaku '^'. Stosownie do tego co otrzymamy w ostatniej fazie podziału spróbujemy odbudować wielomian odpowiednie interpretując otrzmane kawałki jako wielomiany i kombinując je w wielomian funkcją foldl, kumulując je już to funkcją ~* już to funkcją ~+ stosownie do tego reprezentację jakich fragmentów scalamy.

parse_poly :: String -> Polynomial

parse_poly = foldl (~+) [] $ map parse_coeff $ tokenize '+' s where
parse_coeff r = foldl (~*) [(1,[])] $ map parse_mono $ tokenize '*' r where
 parse_mono x = parse_raw $ tokenize '^' x where
   isNumber l = and $ map isDigit l
   convertToInt l = toInteger $ foldl (\x y -> 10*x + y) 0 $ map digitToInt l
   parse_raw [] = []
   parse_raw [a,b] = [(1,[(a, convertToInt b)])]
   parse_raw [a] | isNumber a = [(convertToInt a,[])]
                 | otherwise = [(1,[(a,1)])]

Z nowych elementów wystąpiły tu fukcje z załadowanego na początku modułu Char, tj. isDigit (mówiąca czy znak odpowiada cyfrze) i digitToInt (zamieniająca znak odpwiadający cyfrze na odpowiadającą tej cyfrze liczbę).



Przetestujmy:

Test 11:

Main> parse_poly "x+y"
[(1,[("y",1)]),(1,[("x",1)])]
Main> parse_poly "x+2*y*z^2+123"
[(123,[]),(2,[("y",1),("z",2)]),(1,[("x",1)])]
Main> tostring_poly $ parse_poly "x+2*y*z^2+123"
"123+2*y*z^2+x"

Jako ostatnią póki co zaimplementujmy jeszcze jedną operację - operację podstawiania. Pozwoli nam ona w prosty sposób zadawać nawet dość trudne wielomiany. Operacja podstawiania polega na tym, że za pewną zmienną w zadanym wielomianie podstawiamy inny wielomian, dokonujemy na tak otrzymanym wyrażeniu operacji algebraicznych by w efekcie otrzymać wielomian. Poniżej fukcja przyjmująca w argumencie zmienną za którą podstawiamy, wielomian do którego podstawiamy i wielomian podstawiany. Dotychczasowa wiedza powinna wystarczyć do samodzielnej jej analizy.

subst :: Var -> Polynomial -> Polynomial -> Polynomial

subst v bs with = foldl (~+) [] $
map (\(c, p)-> tms c $ subst_mono v p with) bs where
tms c = map (\(x,y)->(c*x, y))
subst_mono lv m w = foldl (~*) [(1,[])] $
  map (\(x,n)-> if x==lv then foldl (~*) [(1,[])] $ [w|i<-[1..n]]
                         else [(1,[(x,n)])]) m

Sprawdżmy w działaniu.


Test 12:

Znowu dwumian Newtona - ale tym razem poszalejmy:

Main> tostring_poly $ subst "a" (parse_poly "a^15") (parse_poly "x+y")
"6435*x^8*y^7+6435*x^7*y^8+5005*x^9*y^6+5005*x^6*y^9+3003*x^10*y^5+3003*x^5*y^10+1365*x^11*y^4+1365*x^4*y^11+455*x^12*y^3+455*x^3*y^12+105*x^13*y^2+10
5*x^2*y^13+15*x^14*y+15*x*y^14+y^15+x^15"

Hmmm... Ręcznie sprawdzić będzie ciężko.

Jak widać Haskell mógłby sobie jakoś poradzić z prostą szkolną algebrą

Na dziś kończymy zabawę. Wkrótce postaram się ulepszyć i rozbudować (nieco) tę zabawkę i poigrać trochę z takimi tematami jak wielomiany symetryczne, wyróżnik, a może i dalej : eliminacja kwantyfikatorów i twierdzenie Tarskiego.


Na razie: wszystkim uczniom i nauczycielom (szczególnie matematyki) życzę powodzenia i cierpliwości w zaczynającym się roku szkolnym.




1
Operacja ujawnienia postaci listy jest z natury podobna do matematycznego zapisu zbiory (bądź klasy) w postaci { : }, gdzie po lewej stronie znaku ':' pojawia się funkcja (być może identyczność) dla argumentów spełniajacych warunek po stronie prawej logiczny warunek opisujący wybrane elementy. Pamiętajmy jednak - listy to nie zbiory!

Film!

Google video uraczyło mnie dziś głośnym swego czasu i nagradzanym filmem animowanym, "Outside in". Film sygnowany jest m.in. przez jedną z największych gwiazd powojennej matematyki, laureata Medalu Fieldsa (którego wręczono mu nb. na Międzynarodowym Kongresie Matematycznym w Warszawie), Williama Thurstona. Pierwszy raz chyba zobaczyłem to dzieło w całości (wcześniej widziałme jedynie urywki) i uważam, że jest rewelacyjne. Kto ma dziś migrenę, kaca, dolegliwości żołądkowe czy innye podobne przypadłości lepiej niech odłoży oglądanie na inny dzień, w każdym razie ja nie biorę odpowiedzialności za ew. sensacje.
Zatem, usiądźcie wygodnie na stabilnym siedzisku, wyostrzcie zmysły, oczyśćcie umysł i wysilcie wyobraźnię (przede wszystkim przestrzenną) - film tylko pomaga zobaczyć!

O zwartości burzowym latem

gdy umysł i ciało wołają urlopu...
Dziś trochę matematyki, jaką ostatnio się podbawiałem.



1. Twierdzenie z topologii o uniwersalności kostki Cantora dla przestrzeni zwartych


W topologii ogólnej dowodzi się następującego twierdzenia:



Twierdzenie 1:

Każdej przestrzeń zwarta X o ciężarze m jest ciągłym obrazem kostki Cantora C_m =  {0,1}^m (gdzie na C_m mamy topologię Tichonowa).

Gwoli wyjaśnienia, ciężarem przestrzeni topologicznej nazywamy minimalną liczność bazy tej przestrzeni.



2. Specjalny przypadek zwartych przestrzeni metyrycznych: dowód

Nas interesować będzie szczególna wersja tego twierdzenia, mianowicie
taka, gdy X jest przestrzenią zwartą metryczną. Ponieważ zwarta
przestrzeń metryczna ma ciężar nie przekraczający ω, twierdzenie,
którym przez moment się zajmiemy będzie miało postać:

Twierdzenie 2:

Każdej przestrzeń metryczna zwarta X jest ciągłym obrazem kostki
Cantora C_ω  =  {0,1}^N. 

(gdzie na C_ω mamy metrykę
zadaną wzorem: d_C(x,y)=0, dla x=y i d(x,y) = (1/2)^-n, gdzie n = min {i| x(i)≠y(i)} w przeciwnym wypadku).

Oczywiście pracujemy tu w ogóle w kategorii porzestrzeni metrycznych z odwzorowaniami ciągłymi jako morfizmami, bowiem {0,1}^N jest metryzowalna (i co więcej da się tak zmetryzować, że będzie izometryczna ze zbiorem Cantora mieszkającym jak wiadomo na odcinku). Dla potrzeb poniższych rozważań, żeby nie gryźć się w język co chwilę, pojęcia kostki Cantora używał będeż zawsze w rozumieniu kostki Cantora o ciężarze ω. Podobnie - z uwagi na to co powiedziałem powyżej, mogę też użyć terminu "zbiór Cantora" jako synonimu dla "kostki Cantora".

Przedstawię dowód twierdzenia 2 jaki sobie na własny użytek przeprowadziłem:


Zacznijmy od definicji. ε-sieć  to zbiór S punktów w przestrzeni metrycznej (X,d), t.że X = ∪ {K(x, ε) | x ∊ S}.

Dla przestrzeni metrycznych zwartych, dla kazdego epsilon istnieje (na ogół nie jedna) skończona ε-sieć.




W celu konstrukcji naszego odwzorowania, weźmy ciąg ε_n = (1/2)ⁿ . Dla n, niech S_n oznacza pewną wybraną ε_n-sieć.


Niech φ(0) = #S₀


φ(n) = max {#S_n ⋂ K(x, ε_n-1)| x ∊ S_n-1}


Niech Φ(n) := [log₂(φ(n))]+1


niech

ψ(0): {0,1}^Φ(0) -> S₀


ψ(n): {0,1}^Φ(n) × S_n-1 -> S_n taka, że:


ψ(0) jest surjekcją


ψ(n)(_,x): {0,1}^Φ(n) -> K(x,ε_n-1)) ⋂ S_n jest surjekcją


Φ(n) jak można zauważyć jest wystarczająco duże, tak że ψ(n)(_,x) da się dobrze określić dla każedego x ∊ S_n-1. Zbiory postaci {0,1}^Φ(n) × {x} dla x ∊ S_n-1 są rozłączne i łącznie pokrywają całą dziedzinę funkcji ψ(n), zatem ψ(n) da się określić dla każdego n.


Teraz zdefiniujemy dwie funkcje:


Rtp : {0,1}^N -> {0,1}^Φ(0) × {0,1}^Φ(1) × ...

i

Sq: {0,1}^Φ(0) × {0,1}^Φ(1) × ... -> X^N


Rtp jest zdefiniowana naturalnie:


(c₀, c₁, ..., c_Φ(0)-1, c_Φ(0) ..., c_{Φ(0)+Φ(1)-1}, c_Φ(0)+Φ(1), ...) -> ((c₀, c₁, ..., c_Φ(0)-1), (c_Φ(0) ..., c_{Φ(0)+Φ(1)-1}), (c_Φ(0)+Φ(1), ...),...)


Przyporządkowanie Sq zaś, określone jest następująco:

((c₀, c₁, ..., c_Φ(0)-1), (c_Φ(0) ..., c_{Φ(0)+Φ(1)-1}), (c_Φ(0)+Φ(1), ...),...) -> (x₀, x₁, ...)

gdzie:

x₀ = ψ(0)(c₀, c₁, ..., c_Φ(0)-1)

x_n = ψ(n)((c_{Φ(0)+...+Φ(n-1)}, c_{Φ(0)+...+Φ(n-1)+1}, ..., c_{Φ(0)+...+Φ(n)-1}), x_n-1)


Zauważmy, że dowolny ciąg należący do obrazu funkcji Sq jest zbieżny.
Wynika to z określenia ciągu (x_n) i doboru funkcji ψ(n).
Mamy bowiem:
d(x_n, x_n-1) <= ε_n-1
więc
d(x_l, x_k) < Σ_i=min(l,k)^∞ (1/2)ⁱ  = (1/2)^min(l,k)-1


Zatem(x_n) jest ciągiem Cauchy'ego - a więc zbieżnym w przestrzeni zwartej.

Możemy teraz zdefiniować funkcję:

Cant : {0,1}^N -> X

Cant(s) = lim_n->∞(Sq(Rpt(s)))(n)

Do zakończenia dowodu należy jeszcze pokazać, że:

1. Cant, jest funkcją ciągłą
2. Cant jest suriekcją

Punktu 1 dowodzi się podobnie jak istnienia granicy:

Zauważmy, że d(Sq(Rpt(s))(j), Cant(s)) < (1/2)^(j-1) (*)

Teraz, jeżeli Cant(s) = x i weźmiemy dowolne ε > 0, możemy wybrać δ > 0, tak małe, że:

z d_C(s,t) < δ wynika, że s(i) = t(i) dla i = 0,...,N, gdzie N > Φ(0)+....+Φ(k) i gdzie (1/2)^k < ε/2

Wtedy Sq(Rpt(s))(i) = Sq(Rpt(t))(i) dla i = 0,...,k

i

d(Cant(s), Cant(t))<d(Sq(Rpt(s))(k), Cant(s))+d(Sq(Rpt(s))(k), Cant(t)) = d(Sq(Rpt(s))(k), Cant(s))+d(Sq(Rpt(t))(k), Cant(t)) < ε

co dowodzi ciągłości.

Zatem Cant(C_ω) jest domknięty (zwarty) w X. Pokażę teraz, że jest również gęsty w X, co da nam suriektywność i skończy tym samym dowód. Wybierzmy pewne dowolne ε i punkt x ∊ X. Pokażę, że w otoczeniu K(x, ε) punktu x istnieje punkt z obrazu funkcji Cant. Zauważmy, że dla każdego j Sq(Rpt(_))(j) : C_ω -> S_j jest surjekcją (**). Wybierzmy więc j tak duże, że S_j jest ε/2-siecią i (1/2)^(j-1) < ε/2. Z nierówności (*) i faktu (**) wynika, że istnieje s takie, że d(Cant(s), x)<ε .



3. Ale po co

Samo twierdzenie wydawało mi się zawsze ciekawe. Jakoś ostatnio nachodziło mnie (i wtedy też je sobie udowodniłem) w kontekście nieco filozoficznych rozważań o naturze obiektów matematycznych. Jest bowiem tak, że w twierdzeniu jest ukryty pewien sposób konstruowania przestrzeni zwartych w kombinatoryczny (może finitystyczny) sposób. Funkcje pomocnicze, które były wykorzystywane na potrzeby konstrukcji funkcji Cant zależą od dość dowolnych wyborów stosownych ε-sieci i odpowiednich suriekcji (słowem: Cant powinna mieć przeliczalną liczbę indeksów opisujących jakąż parametry od których zależy) . Ciekawe może być pytanie o warunki jakie należy narzucić na ciąg zbiorów skończonych (Z_n) i funkcji F_n: Z_n->P(Z_n+1) (P(X) to zbiór poszbiorów zbioru X) i malejący ciąg liczb (ε_n) aby istniała przestrzeń metryczna dla której Z_n będą ε_n-sieciami? Jak odpowiedź zależy od tego, że założymy że będę to ε_n-sieci minimalne (tzn. żaden właściwy podzbiór Z_n nie będzie już en siecią)?  Przy założeniach minimalności są chyba jakieś ciekawe związki między ciągiem #Z_n z wymiarem Hausdorffa przestrzeni X? Dołożyć do systemu wymaganie obliczalności systemu funkcji F_n - co dostaniemy? Czy jakąś obliczalną teorię przestrzeni zwartych, w której da się ściśle i dokładnie powiedzieć co to znaczy np. że okrąg lub odcinek jest "prostym" zbiorem natomiast taki płatek Kocha bardziej złożonym (a może wręcz przeciwnie prostszym)? Może ma to jakieś praktyczne znaczenie - np dla kompresji "kształtów" a więc i np. obrazów?

Czy jest jakiś związek (właśnie się uczę tej teorii zaintrygowany ninejszym pytaniem) między twierdzeniem tu dowodzonym a możliwością przedstawiania przestrzeni zwartych jako algebr definiowalnych równościowo?

Bedę wracał do tych tematów mam nadzieję, bo żywo mnie ostatnio zajmują.

Debiut Tricki

Parę godzin temu pojawił się anons, że strona o której już tu jakiś czas temu pisałem jest aktywna i dostępna dla użytkowników. Chodzi o projekt "Tricki" - czegoś rodzaju wiki tyle, że z opisem sposobów, sztuczek, wytrychów, metod itd. które można zastosować w pracy matematyka. To wyjątkowy pomysł - nie monografia, nie encyklopedia, nie wykład. To nauka warsztatu. Bezcenna sprawa. Pomysł sygnują i kontrybuują do projektu wybitni matematycy współcześni, w tym laureaci medalu Fieldsa: Timothy Gowers i Terence Tao.
Polecam - sam już oblizuję się na myśl czego się można już i czego się można będzie w przyszłości z materiałów tam zamieszczonych nauczyć.
Szczególnie polecam tej, bliskiej mi mentalnie grupie ludzi (której istnienie i liczność przekraczającą jeden na nikłych przesłankach antycypuję), którzy zdobyli formalne wykształcenie matematyczne (lub pokrewne) i matematyką się interesują "twórczo", tzn. lubią popracować nad jakimś problemem, a z różnych przyczyn znaleźli się poza szeroko rozumianym środowiskiem akademickim. Internet, a szczególnie takie inicjatywy to wielka szansa dla nas, aby nie stracić kontaktu z prawdziwą nauką. Szkoda tylko, że w polskojęzycznym Internecie tak mało się w owym światku dzieje.