jak-dzieci.jpg
Wielkanoc Klimka

Wielkanoc trwa w najlepszą noc.
A ja zasnę. Dobranoc!
Koc zasuwam
Wesołych Świat życzę Wam!

Wstaję i pędem do stolika gnam
jej wstałem sam!
Biorę trąbkę na niej gram
Ram ta tam!
Wszyscy się budzą!
Czemu na trąbce gram?
Zdradzę Wam:
Bo to przecież Wielkanoc!

Biorę koszyk w ręce
Pakuję baranka, flagę
Ubrać zajączka pomogę
A jeszcze bułeczka,
kromeczka,
a do środka szyneczka
i jajo, nie to Jaja
Jedną namalowałem ja
i hop do kościoła!

Bez redakcji.
Autor: Klimek Kurz, lat 9

krasiczyn.jpg

Niedawno z Programu 2 Polskiego Radia z Rozmów o Sztuce od pani Bożeny Fabiani dowiedziałem się że *archimimus* – to sobowtór zmarłego, wynajmowany na pogrzeb w trakcie tzw. pompa funebris w Rzeczpospolitej szlacheckiej. Niektórzy archimimusi byli niebywale podobni do zmarłych, starano sie oczywiście by podobieństwo było jak największe. Jego rolą było uczestnictwo w pogrzebie tak by przybyli uczestnicy mieli wrażenie namacalnej obecności zmarłego, zaś kulminacją tych działań mógł być wjazd konny takiej osoby do kościoła i spektakularny upadek z konia przed trumną.

Generalnie pogrzeby szlachty i bogatszego mieszczaństwa w barokowej Polsce, celebrowano w niezwykle huczny sposób. Sama ceremonia, podczas której rodzina zjeżdżała sie z całej Rzeczpospolitej by nawiedzić zmarłego, trwała z powodu dużych odległości, nieraz kilka miesięcy a uczestniczyło w nich nieraz kilka tysięcy osób. Bogato zdobiono zmarłego, trumnę, budowano zdobny katafalk, urządzano przedstawienie pogrzebowe podczas którego łamana o o trumnę broń ( co było zwykle źródłem okaleczeń i wypadków). Kolorami żałoby były czarny i czerwony, i tak przyozdabiano trumnę, wóz na którym ją wieziono w trakcie pogrzebu, katafalk, a nawet konie.

Na szczególną uwagę zasługuje konterfekt – portret trumienny będący swoistym elementem kultury sarmackiej, szczególnie rozwiniętym i powszechnym na terenach  Rzeczpospolitej.  Pierwszym takim portretem był kontrefekt Stefana Batorego , niewielkich rozmiarów, być może namalowany przez Marcina Kobera. W kolejnych latach pomysł chwycił, i portret trumienny zrobił w dawnej Polsce niezwykłą karierę. Początkowo niewielkich rozmiarów ( ten na obrazku ma tylko 10 cm średnicy) rozrósł sie do 70 cm i kształtów odpowiadających przekrojowi trumny. Znacząco wzrosła także jego powszechność. Z początku będący zwyczajem magnackim, przekształcił sie w ogólnoszlachecki a pod koniec XVIII wieku portrety takie masowo fundowali sobie wszyscy bogatsi ludzie, w tym mieszczaństwo i protestanci. Masowość szła w parze z całkowitą anonimowością twórców. Jak to już pisałem na blogu, w Polsce ważniejszą postacią jest twórca wychodka niż artysta malujący portrety, bo faktura dla cieśli opiewa na więcej pieniędzy i dotyczy pracy zespołu ludzi, zaś artysta, zwłaszcza użytkowy pracował zwykle sam i nikt raczej nie poważał jego pracy.

Na portrecie trumiennym nieboszczyka zwykle przedstawiono w portrecie en face 3/4 z oczami utkwionymi w widza. Postać zmarłego ukazywano w pysznym, paradnym, strojnym ubraniu.  Na ogół był to strój w którym chowano zmarłego, pełen ozdób, bogato wykończony, z futrem itp. Zwyczaje pogrzebowe były pod tym względem tak niezwykłe, że jeden z odwiedzających kraj francuzów zanotował, że bardziej przypominają one święcenie triumfu czy zwycięstwa w bitwie, niż złożenie do grobu.  Co niezwykłe, choć inne elementy pogrzebu, jak przedstawienia czy mowy, pełne były przesady i zmierzały w kierunku gigantycznego pochlebstwa w stosunku do nieboszczyka, portret zmarłego zwykle był realistyczny. Powszechne są realistyczne przedstawienia osób brzydkich, portrety o sporych walorach psychologicznych ( jak choćby ten na obrazku), przedstawiające nieboszczyka bez upiększeń.

Niektóre osoby nie życzyły sobie hucznego pogrzebu, a przykład matka Jana Sobieskiego, zawarła taką klauzulę w testamencie. Aby uczynić za dość woli zmarłej, dokonano zatem 2 pogrzebów. Pierwszy odbył sie w sposób _nader skromny_ to znaczy uczestniczyło w nim 200-300 osób, zaś ceremonię pogrzebową celebrowało około 30 szeregowych księży. Po takim wykonaniu testamentu, dokonano bardziej oficjalnego pochówku z udziałem kilku biskupów, paradnym konduktem, biciem w dzwony, muzyką i kilkoma tysiącami gości….

hierarchiaKanonicznej

Na marginesie moich rozważań na temat homologii budowanych na przestrzeniach zdań logicznych, opisze poniżej pewien ogólny pomysł dotyczący postaci kanonicznych obiektów. Postać kanoniczna obiektu matematycznego to pojecie natury właściwie estetyczno -praktycznej i mam wrażenie że jego istnienie zostało nieco przeoczone przez główny nurt matematyki, co nie znaczy że jest niedocenione. Po prostu nie spotkałem sie z jakąś systemową jego analiza, może poza jednym przypadkiem jego książki Marko Petkovsek, Herbert Wilf and Doron Zeilberger „A=B”. Książka choć zdecydowanie dotyczy kombinatoryki to jednak w kilku zdaniach dyskutuje zagadnienie formy kanonicznej wyrażenia. W szczególności autorzy piszą „A canonical form is a clear-cut way of describing every object in the class, in a one-to-one way. So in order to find out whether object A equals object B, all we have to do is find their canonical forms, c(A) and c(B), and check whether or not c(A) equals c(B).” Widać wyraźnie że autorzy książki doceniają znaczenie postaci kanonicznej – w ich ujęciu jest to fundamentalna postać syntaktyczna pozwalająca na rozstrzyganie o równości czy równoważności obiektów. Z drugiej strony postacie kanoniczne nie wydają się ( poza aspektem praktycznym) być systemowo analizowane na gruncie matematyki w aspekcie syntaktycznym. Oczywiście szeroko opisywane i głęboko badane sa ich własności wewnętrzne, ilość parametrów związana z bardzo ważnym pojęciem przestrzeni moduli i inne tego typu, matematyczne własności. Zarazem własności czysto syntaktyczne, związane z przekształceniami „napisów” nie są o ile wiem, systemowe analizowane. Właściwie wydaje sie to być rzeczą trywialną, analizować taki aspekt sprawy, ale z jednej strony moje zainteresowania odnoszą sie bardziej do systemów logicznych, a w nich syntaktyka ma wiele do powiedzenia. Z drugiej zaś strony, z wykształcenia jestem fizykiem, zaś obszar moich zainteresowań obejmował kiedyś technikę grupy renormalizacji. Można bez przesady stwierdzić, ze pewne formy grupy renormalziacji to w istocie systemowe badanie symetrii wyrażeń algebraicznych pod wpływem odwzorowania iteracji – o czym kiedyś chciałem napisać, i kto wie, może jeszcze napiszę… Tym samym zagadnienie jest osadzone całkiem konkretnie.

Zdefiniujmy aktorów:

Mamy zbiór obiektów {A = \{ a_1,a_2, \cdots \}} Standardowe odwzorowanie D ze zbioru A w grupę przemienną G polega na rozpatrywaniu formalnych obiektów

\displaystyle S = \Sigma_i g_i a_i

które można oczywiście sumować, wypadku grupy addytywnej:

\displaystyle g_1 a_1 + g_2a_1 = (g_1+g_2)a_1

Stosowne przekształcenie może być także zdefiniowane dla grupy przemiennej multiplikatywnej:

\displaystyle P = \Pi_i g_i a_i

i można je mnożyć:

\displaystyle (g_1 a_1) (g_2 a_1) = (g_1 g_2) a_1

I oczywiście pojawia się problem czy można mnożyć elementy {a_1} i {a_2} tak by nadać sens wyrażeniom {a_1 a_2} – czasami jest to możliwe, przykład poniżej.

Jeśli istnieje zbiór {B = \{ b_1,b_2, \cdots \}} oraz rodzina odwzorowań {f: A \mapsto B} o stosownych własnościach ( łączność, element neutralny, generalnie odwzorowania muszą być monoidem) to możemy mówić o kategorii zbiorów „A” i wszystkich konsekwencjach wynikających z faktu że zbiory A,B… tworzą wraz z odwzorowaniami kategorię. Poniżej mówimy o przypadkach w których B jest podzbiorem zbioru A i prosiłbym czytelnika o takie właśnie nastrojenie umysłu ;-).

Jeśli odwzorowanie D „jest zgodne” z całą maszynerią kategorii, to przeprowadza elementy zbioru A i zbioru {B=f(A)} w elementy grupy G, zachowując „funkcyjność” czyli stosowne diagramy kategorii są zgodne. Tym samym D staje sie funktorem z kategorii zbiorów A,B… w kategorię grup.

O ile czegoś nie pokićkałem to standardowy obrazek ( a jak pokićkałem, łatwo to naprawić…) a przynajmniej taki był mój zamiar ( niczego nowego tu nie opisałem).

Lepiej się myśli na przykładach, więc załóżmy teraz że zbiory A czy B to coś w rodzaju rodziny wielomianów, albo zdań logiki, reprezentowanych w rozmaitym zapisie, zaś odwzorowania f pomiędzy nimi to jakiegoś rodzaju przekształcenia tych obiektów ( dodawanie wielomianów, mnożenie, łączenie zdań logiki za pomocą operatorów negacji, alternatywy, koniunkcji itp.). Przekształcenia sa rozmaite, a wśród nich istnieje arcyciekawa rodzina przekształceń: przekształcenia do postaci kanonicznej.

Postać kanoniczna to specyficzna forma „syntaktyczna” obiektów, określona przez jakiegoś rodzaju wymóg „wygody”, „jednoznaczności”, „urody” – pojecie w zasadzie tyle estetyczne co praktyczne. Ma ona jednak tą cechę, że:

  • postać kanoniczna jest pojęciem syntaktycznym ( chodzi o formę graficzną, powiedzmy przedstawienie {(x - x_0)(x - x_2)...(x - x_k)} w wypadku wielomianów).
  • każdy obraz obiektu ze zbioru A pod wpływem przekształcenia do postaci kanonicznej – nadal jest obiektem zbioru A ( czyli postać kanoniczna wielomianu, lub zdania logicznego, nadal jest wielomianem lub zdaniem logicznym). Tym samy jest to rodzina przekształceń z zbioru A do A.
  • przekształcenie kanoniczne {K:A \mapsto A} ma własność, że jeśli wyróżnimy elementy w postaci kanonicznej jako zbiór C, to są oczywiście są podzbiorem elementów A. Teraz {K:A \mapsto C} jest suriekcją na C ( ale nie na A! ).
  • postać kanoniczna nie jest pojęciem syntaktycznie jednoznacznym, i choć w praktyce jest zwykle jasne z jaką postacią kanoniczną mamy do czynienia, to dany zbiór obiektów może mieć kilka „przedstawień kanonicznych” użytecznych w rożnych kontekstach.
  • jeśli mamy rozmaite formy kanoniczne dla obiektów z zbioru A, powiedzmy {C_1, C_2} ( z uwagi na rozmaite potrzeby, np. wielomian raz możemy prezentować w postaci iloczynowej {( x - x_0)(x - x_1)...(x - x_k)} a raz jako sumę {\Sigma x^k a_k}. Dla zdań logiki raz możemy je prezentować w postaci alternatywo-koniunkcyjnej a raz – jak w przykładzie poniżej z mojego bloga gdzie wprowadzałem grupę oczepioną homologii – interesowała nas forma kanoniczna zdania {a} lub { \neq a} z całkowitym pominięciem bardziej złożonej struktury wewnętrznej ) to istnieje odpowiedniość pomiędzy tak powstałymi zbiorami {C_1} i {C_2} ( gdyż reprezentują te same obiekty w rozmaitych postaciach normalnych. )
  • Nawet jeśli postać kanoniczna została określona, zwykle miewamy do czynienia z pewną dozą dowolności związaną z przedstawieniem z dokładnością do pewnego zbioru przekształceń, jak uporządkowanie zmiennych, permutacje itp.  ( na przykład w wypadku wielomianów w dziedzinie rzeczywistej, możemy wymagać by pierwiastki {x_0,...x_k} w wyrażeniu {(x - x_0)(x - x_2)...(x - x_k)} były uporządkowane w sposób rosnący. W wypadku liczb zespolonych wymóg taki nie występuje i mamy pewną dowolność/niejednoznaczność syntaktyczną. Proszę zwrócić uwagę że jest to cecha wewnętrzna przestrzeni nad którą budujemy wielomiany a nie jest to bynajmniej kwestia konwencji! )

Mamy zatem strukturę zbioru wraz z przekształceniami jego elementów do postaci kanonicznej i zapytamy: czy możliwe jest prawidłowe zdefiniowanie funktora D z kategorii takich obiektów do kategorii grup?

Wydaje sie oczywiście że jest to możliwe. Na przykład:

  • dla zdań logicznych postać kanoniczna to powiedzmy postać alternatywo-koniunkcyjna. Każdy jednoznacznie określony przez zdania {p_{i_{k}}} ciąg koniunkcyjny {a_i = p_{i_{1}} \land p_{i_{2}} \land p_{i_{3}} \land \cdots \land p_{i_{k}} } odwzorujemy pod wpływem funktora D w pewien obiekt {g_i a_i} zaś elementy alternatywy mapujemy jako „sumy”. Teraz każdemu zdaniu w postaci {a_1 \lor a_2} itp. ( gdzie {a_i} jest w postaci czysto koniunkcyjnej) przypiszemy element {g_1 a_1 + g_2 a_2}. Elementy odwrotne to oczywiście negacje. Jak widać odwzorowaliśmy postać alternatywo-koniunkcyjną zdania logicznego w grupę addytywną. Proszę zwrócić uwagę, że struktura wewnętrzna części koniunkcyjnej nie została określona. Nie założyliśmy np. żadnej formy uporządkowania zdań {p_{i_{k}}} ( i prawdę mówiąc dla ogólnego zbioru zdań logiki taki porządek właściwie nie istnieje, choć oczywiście można by postulować jakieś półśrodki, jak złożoność syntaktyczna mierzona np. głębokością drzewa syntaktycznego, albo ilością znaków albo na inne, nierównoważne zresztą, sposoby). Analizując ten przykład dalej widzimy że wynikowa grupa jest grupa przemienna generowana przez „grupy zdań” w postaci czysto koniunkcyjnej ( a więc {a_i = p_{i_{1}} \land p_{i_{2}} \land p_{i_{3}} \land \cdots \land p_{i_{k}} }). Gdybyśmy ograniczyli się do obiektów o maksymalnie N elementach, grupa ta będzie miała skończoną liczbę generatorów, przy czym każdy możliwy ciąg koniunkcyjny zdań będzie generatorem. W następnym kroku możemy „zejść głębiej” i narzucić w takiej przestrzeni kolejną postać kanoniczną wyższego rzędu, np. wprowadzając porządek w kolejności zdań w postaci koniunkcyjnej itp.
  • dla wielomianów ustalmy że postać kanoniczna to zaprezentowanie wielomianu jako iloczynu {(x - x_0)^{s_0} (x - x_1)^{s_1} ...(x - x_k)^{s_k} }. W zbiorze C wielomianów w postaci kanonicznej operacja iloczynu nie wyprowadza poza zbiór C ( a operacja sumy – syntaktycznie wyprowadza). Zatem wielomian w postaci kanonicznej {w_1} odwzorujemy w obiekt {g_1 w_1} wielomian {w_2} w wielomian {g_2 w_2} zaś wielomian {(g_1 g_2) w_1 w_2} nadal będzie w postaci kanonicznej. Właściwie nie mamy tu elementów odwrotnych – tym samym odwzorowanie wprowadza monoid a nie grupę. Rozpatrzmy ten przykład nieco szerzej. Ogólny wielomian zwykle przestawiany jest jako suma monomianów {\Sigma a_k x^k}. W naszym przypadku dokonamy oszustwa i będziemy rozważać wyrażenia w postaci iloczynowej, o krok bliższej pełnej formie kanonicznej, jak {(x-x_4) (x-x_0) (x-x_0) (x - x_1)(x-x_0)}. Zwróćmy uwagę że wyrażenia {(x-x_0) (x-x_0) (x-x_0) = (x-x_0)^2 (x-x_0) = (x-x_0) (x-x_0)^2} to trzy rożne zapisy tego samego wielomianu w postaci kanonicznej {(x-x_0)^3}. Widzimy tutaj że „ogólny wielomian w postaci iloczynowej ma znacznie więcej „swobody syntaktycznej” niż wyrażenie kanoniczne {(x-x_0)^3}. Właśnie o tego typu rozróżnieniach rozmawiamy.
  • rozważmy jeszcze raz przestrzeń wielomianów nad liczbami rzeczywistymi, tym razem o ustalonych ( i uporządkowanych!) pierwiastkach {x_0 \cdots x_k }. Wszystkie tego typu wielomiany mają kanoniczną postać {(x - x_0)^{s_0} (x - x_1)^{s_1} \cdots (x - x_k)^{s_k} }. Wielomian w takiej przestrzeni jest jednoznacznie zadany przez podanie stopni pierwiastków czyli przez ciąg liczb { s_0 , s_1 , s_2 , \cdots s_k }. Przekształcenie D mapuje wielomian {w} na obiekt {g w} przemiennej grupy multiplikatywnej. Mnożenie wielomianów w tym wypadku polega na dodawaniu stopni stosownych pierwiastków. Tym samym przestrzeń taka, wielomianów w postaci kanonicznej o ustalonych pierwiastkach rzeczywistych, jest równoważna k-wymiarowemu monoidowi {Z_{+}^{k}} liczb dodatnich z operacją dodawania. Wydaje sie możliwe uogólnienie tej konstrukcji by uwzględnić ujemne „krotności” pierwiastków i tym samym w miejsce monoidu wprowadzić grupę. A pełna przestrzeń wielomianów o ustalonych k pierwiastkach( oszukujemy jak poprzednio, wszystkie niech będą w postaci iloczynowej, oszukujmy dalej, pierwiastki są uporządkowane! )? Ponieważ wyrażenia {(x-x_0)^2 (x-x_0)} i {(x-x_0) (x-x_0)^2} uważamy tym razem za różne, ma ona znacznie bardziej złożoną strukturę!

Jak widać mamy zatem sytuację że D odwzorowuje obiekty zbioru A na elementy grupy (monoidu) G, a zarazem elementy podzbioru A – te elementy które sa w postaci kanonicznej – na elementy podgrupy G.

Mamy obraz całego zbioru A pod wpływem funktora D, oraz obraz całego zbioru A pod wpływem złożenia {D( K (A \mapsto C ) ) \mapsto Sub(G)} gdzie {Sub(G)} oznacza podgrupę G. Inaczej { img(DK) \subseteq img(D)} – elementy złożenia odwzorowań {DK} są podzbiorem elementów D – gdzie wszystkie odwzorowania działają na zbiorze A.

Jeśli mamy podgrupę to zachodzi pytanie: *Jak wygląda iloraz grupy G przez podgrupę związaną z elementami w postaci kanonicznej?*

\displaystyle H_x \stackrel{?}{=} img(D) / img(DK)

I tu mamy jakąś analogię z homologią….

W przykładzie ze zdaniami logicznymi powyżej wspomniałem o postaci kanonicznej zdefiniowanej głębiej, na kolejnym poziomie syntaktycznym. Analogia do grup homologii jest tu tym wyraźniej widoczna, bowiem mamy kolejne odwzorowanie, kolejne grupy ilorazowe itp. Właściwie być może należałoby całą konstrukcję oprzeć na pojęciu ogólnej postaci syntaktycznej, następnie zdefiniować drzewo syntaktyczne i na każdym jego szczeblu definiować stosowne odwzorowania i grupy ilorazowe. Zagadnienie zaczyna w ten sposób być bliższe tematom z jakimi mają do czynienia informatycy podczas konstrukcji parserów…

Z mojego wpisu na blogu wynika, że w pewnych przypadkach dla zbiorów zdań logiki grupa ilorazowa jest nietrywialna. Sytuacja taka miała miejsce dla pewnych szczególnych postaci odwzorowania D – badałem strukturę związaną z regułą modus ponens – co dla tego co tu opisano jest bez znaczenia, zaś postać kanoniczna którą rozważałem była *związana z negacją* czyli z formą zdania {a} lub {\neg a} . Przypadek taki oznacza że zbiór zdań jest ( syntaktycznie!) sprzeczny. W przypadku homologii odczepionej grupa ta może być trywialna ( w zbiorze zdań nie występują zdania {a} i {\neg a}, zbiór zdań jest niesprzeczny). Może ona jednak być także złożona z 2 elementów ( występuje zdanie {a} i {\neg a}, teoria jest syntaktycznie sprzeczna), albo z n elementów ( czego nie pokazałem ale przypuszczam że tak jest w wypadku zdań w paradoksie „koła kłamców” gdzie pierwszy z kłamców mówi: „następny kłamie!”, następny mówi to samo… i tak n – 1 osób, zaś ostatnia osoba mówi „następny mówi prawdę!” ). Widać więc że dla pewnych form kanonicznych i pewnych zbiorów – grupa ilorazowa może być nietrywialna, a zdarzenie to jest związane z ważną cechą zbioru A – w wypadku logiki była to sprzeczność ( syntaktyczna).

Jak to jest w wypadku innych zbiorów obiektów i innych postaci kanonicznych?

 PS. Przypomniałem sobie że jednak temat postaci kanonicznej, kanoniczności przekształcenia itp. padł w pewnym konkretnym kontekście. I szukając w głowie gdzie i kiedy to było przypomniałem sobie dawną batalię z zawodowymi matematykami jaką stoczyłem przy okazji pytania jakie zadałem na mathoverflow, Miało ono postać: Jakie pojęcia nie są ściśle zdefiniowane we współczesnej matematyce?”  Jak sie okazuje są profesjonalni ( i świetni!)  matematycy którzy nie są w stanie zrozumieć takiego pytania! Tak czy śmak, pytanie odniosło wielki sukces, udzielono na nie ( wbrew opinii grupy „nierozumiejących” ale trzymających władzę…) 29 odpowiedzi, a obejrzano je ponad 9 tysięcy razy! Jedna z odpowiedzi dotyczyła pojęcia kanoniczności. Nie jest wykluczone jednak że popełniam tu błąd ekwiwokacji

Pinky: Móżdżku, co będziemy robić dzisiaj wieczorem?

Mózg: Dokładnie to samo, zawsze, Pinky, zdobędziemy władze nad światem!

woda.jpg

W poprzednim wpisie opisałem sposób wyliczania odczepionej grupy homologii dla prostego ( ale już nie trywialnego) przykładu dowodu sprzecznego. Przypomnijmy że dla grup kompleksów łańcuchowych tego obiektu geometrycznego tworzymy ciąg grup homologii {H_n} za pomocą schematu pomocniczego:

\displaystyle 0 \overset{\partial_3}{\longrightarrow} C_{2} \overset{\partial_2}{\longrightarrow} C_{1} \overset{\partial_1}{\longrightarrow} C_{0} \overset{\partial_0 = 0 }{\longrightarrow} 0

n-ta grupa homologii to grupa ilorazowa:

\displaystyle H_n = ker(\partial_n)/img(\partial_{n+1})

W przypadku grupy odczepionej {H_a} postąpiliśmy nieco inaczej. Zdefiniowałem mianowicie dodatkowe mapowanie {\partial_a} który przyporządkowywał wierzchołkom grafu obiekty geometryczne ( dla wierzchołka {a} taki obiekt geometryczny oznaczałem{|a|} ) wraz z informacja o ich wewnętrznej strukturze. W naszym przypadku, a stale mówimy o obiektach geometrycznych będących odwzorowaniem obiektów logicznych – ciagów dowodowych w systemie formalnym z regułą modus ponens -mapowanie {\partial_a} miało następującą własność:

\displaystyle \partial_a(\neg q) = - \partial_a(q)

gdzie {q} w poyższym wyrażeniu jest zdaniem logicznym. W następnym kroku definiowałem odszczepioną grupę homologii {H_a} jako:

\displaystyle H_n = ker(\partial_a)/img(\partial_{1})

Przyglądnijmy się bliżej mapowaniu {\partial_a}.

Obecny wpis zacznijmy może od tego że przypomnę miejsce odwzorowania {\partial_a} w diagramie grup kompleksów łańcuchowych:

HomologiaOdczepiona

Widzimy wyraźnie że zdefiniowałem nowy kompleks łańcuchowy {C_a} który jest dziedziną odwzorowania {\partial_a}. Zbiór ten jest obrazem grupy cykli krawędziowych {C_1} pod działaniem odwzorowania {\partial_1} Jego elementami nie są jednak wierzchołki, a obiekty posiadające wewnętrzną strukturę. Z jednej strony bowiem spełniają one zależności wynikające z faktu bycia brzegiem grupy cykli krawędziowych {C_1}, czyli w wypadku tych obiektów, ich struktura niesie dodatkową informację o fakcie że są one spięte w pętle simpleksów reprezentujących reguły modus ponens. I faktycznie, jak czytelnik może pamięta, pisałem że: { img (\partial_1) = <b-a,c-b,c-a> } oraz, że dodatkowo {x+y-z=0} gdzie {x,y,z} reprezentowały wierzchołki złożone w krawędzie simpleksu reprezentującego {MP(a,b)=c}. Innymi słowy działanie mapowania {\partial_1} jest identyczne jak w wypadku normalnej definicji grup homologii. Operator {\partial_a} działa na grupie cykli wierzchołków. Formalnie rzecz biorąc, grupa ta to {C_0} i na diagramie grupa taka znajduje sie w „ciągu głównym” grup łańcuchów. W naszym jednak przypadku mapowanie {\partial_a} działa na tym zbiorze wyciągając z niego dodatkową informację, stąd właściwym jest odróżnienie go od zwykłego zbioru {C_0} który zawiera przecież tylko wierzchołki. Co więcej, obrazem {\partial_a} w działaniu na zbiór {C_a} nie jest bynajmniej 0, pomimo iż tak właśnie narysowałem na diagramie powyżej. Czytelnik wybaczy to oszustwo, w istocie w miejscu 0 powinna znajdować sie grupa ( powiedzmy) {C_{0a}} która zawiera punkty geometryczne wierzchołków uzupełnione o informację o ich strukturze wewnętrznej. Nie jest to jednak grupa łańcuchowa równoważna {C_0} gdyż w obiekcie tym nie leży żaden obraz {\partial_1}. Jest tak, gdyż działanie operatora {\partial_a} skutecznie usuwa z tej struktury informacje o spięciu w krawędzie. Przyznam że spędziłem jakiś czas usiłując „włożyć” grupę {C_a} pomiędzy {C_1} i {C_0} ale nie widzę za bardzo takiej możliwości ( chyba ze kosztem znacznego skomplikowania). Prawdziwy diagram grup łańcuchowych powinien wiec wyglądać tak:

HomologiaOdczepionaPoprawnie

Przyglądnijmy sie teraz działaniu odwzorowania {\partial_a}. Odwzorowanie to przypisuje elementowi grupy łańcuchów 0-wymiarowych, element w grupie abelowej {C_0a}. W grupie tej różnym elementom {C_a} przypisywane są różne elementy, poza sytuacją kiedy elementy {C_a} związane sa relacją:

\displaystyle p = \neg q

dla pewnych zdań {p} i {q}. Widać wyraźnie ze tego typu odwzorowanie uwzględnia dodatkową informację o negacji zdań logicznych.

Być może czytelnikowi umknęła jeszcze jedna subtelność, którą chciałbym tu wyciągnąć na światło dzienne. Mianowicie w pierwszym dowodzie mieliśmy następująca sytuację: w grafie złożonym z zdań {a="a",b="a\rightarrow a",c="a"} zdania {a} i {c} zostały potraktowane jako różne. Właściwie to jest to błąd. Zdania te to w istocie jedno i to samo zdanie, którego obrazem w grupie {C_a} jest jeden element. Gdyby było inaczej, w grupie tej istniałby nietrywialny cykl (postaci {a-b} gdzie a i b byłyby dwoma obrazami tego samego zdania {q} ) i grupa homologiczna odczepiona dla dowodu niesprzecznego byłaby nietrywialna, czego wolelibyśmy uniknąć. Takie „sklejenie” zdań w obrazie {\partial_a} pozwala uniknąć nietrywialnych pętli występujących z powodu powtarzania sie zdań w dowodzie. Jednocześnie zdania zanegowane przekształcane są na rożne ( przeciwne!) elementy grupy {C_a} co pozwala nam nietrywialnie reprezentować sprzeczność dowodu.

Możemy podsumować. Odwzorowanie {\partial_a} działa w następujący sposób:

  • jego dziedziną jest zbiór  {C_a} wierzchołków grafu reprezentującego dowód
  • jego obrazem jest grupa przemienna {C_{0a}} łańcuchów 0-wymiarowych z uwzględnieniem struktury wewnętrznej zdań z poprzedniego punktu
  • na obecnym etapie uwzględniamy wyłącznie negację. Obrazami zdań {p} i {\neg p} są elementy wzajemnie odwrotne grupy {C_a} tak, że {\partial_{a} (p) + \partial_{a} (\neg p) =0}.
  • obrazami wierzchołków {p}  i {q = "p"}  w których mamy zdania syntaktycznie tożsamych jest ten sam element {|p|}  grupy  {C_a}

Grupa homologii jest {H_a} zdefiniowana jako grupa ilorazowa jądra przekształcenia {\partial_a} przez obraz {\partial_1} operatora brzegów jednowymiarowych na zbiorze krawędzi {C_1}. Właściwie to całe zagadnienie tym samym sprowadza sie do zdefiniowania {H_a} i do pojęcia grup homologii odnosi sie w zapewne dosyć odległy, a a na pewno nie jakiś szczególnie nietrywialny sposób. Z drugiej strony starałem sie złapań jakieś intuicje związane z pojęciem sprzeczności, i chyba całkiem nieźle sie to udało, biorąc pod uwagę, że w ramach przedstawionych rozważań jest w miarę oczywiste że skończone zbiory sprzeczne będą miały nietrywialne ( i skończone!) grupy {H_a} zaś zbiory niesprzeczne – grupy trywialne.

Dlaczego jest to interesujący fakt sam w sobie? Otóż od dłuższego czasu zastanawiało mnie, dlaczego sprzeczności logiczne, mają tak prostą postać syntaktyczną. Proszę porównać najprostszy ze znanych paradoksów w teorii zbiorów, paradoks Russella z aksjomatyką tej teorii ( na przykład w wersji naiwnej, albo ZFC). W każdym wypadku paradoks jest prostszy niż sama teoria! A paradoks kłamcy? Czy nie jest tak, że „każdy głupi go zrozumie”? A rozwiązanie? ło, doktoraty można robić… Tarski całą teorię modeli na tym zbudował. Mamy zatem paradoksy, a ich reprezentantami wydają się być niewielkie, a czasami nawet znaczeniowo, koncepcyjnie proste, zbiory zdań. Tymczasem okazuje sie że przy zastosowaniu odczepionej grupy topologii, sprzeczność ma odpowiednik w prostej postaci takiej grupy! Kontekst geometryczny nie jest tu całkiem od rzeczy. Widać że relatywnie proste rozumowanie ( dowód sprzeczny jaki podałem jako przykład odpowiada paradoksowi kłamcy) ma nietrywialna reprezentację geometryczną, w postaci simpleksu w którym grupa odczepiona jest nietrywialna. Dlaczego zatem paradoksy są tak proste? Chciałoby się odwrócić całe rozumowanie: „Bo struktury geometryczne proste są same w sobie”. Czy istnieją „skomplikowane paradoksu”? Oczywiście istnieją takie które wymagają wielu zdań by je zapisać, i zapewne odwzorują się w skomplikowaną strukturę geometryczną. Ale z tego co napisałem/zdefiniowałem wydaje się że nadal nie będziemy mieli w takich paradoksach niczego istotnie innego niż w tych prostych. Zapewne będą im odpowiadały bardziej złożone grupy odczepione, ale należy przypuszczać że nadal będą to sumy proste grup {Z_2}( po jednej grupie dla każdej pary zdań sprzecznych, lub wy wypadku paradoksów typu „koło kłamców” grupy cykliczne rozmiaru n, co będziemy zapewne analizować w jednym z przyszłych wpisów) a ta występuje już w bardzo prostym przypadku rozumowania sprzecznego. I to jest coś co wydaje mi się ciekawe…

A co dalej? Kolejne działania powinny polegać na analizie struktur coraz bardziej złożonych, a na koniec nieskończonych zbiorów zdań związanych relacją konsekwencji syntaktycznej modus ponens.I zapewne będę o tym jeszcze pisał.

Wymieńmy możliwe uogólnienia:

  • moglibyśmy analizować bardziej złożoną strukturę wewnętrzną zdań w wierzchołkach. W miejsce operatora {\partial_a} można by wprowadzić inny, który byłby czuły na występowanie alternatywy, koniunkcji lub jeszcze bardziej złożonych struktur. Pewne przekształcenia syntaktyczne mają całkiem ładną strukturę wewnętrzną, powiedzmy prawa de Morgana odznaczają sie sporą dozą (syntaktycznej) symetrii, co pozwalałoby odwzorowywać wierzchołki w grupy o niebanalnej strukturze. Marzy mi sie coś w rodzaju teorii Galois dla logiki, budowanej w języku algebry homologicznej…
  • można sobie wyobrazić cały ciąg grup odczepionych, który gubiłby informację o geometrii triangulacji dowodu ( właściwie nie jest ona jak na razie szczególnie ciekawa…) ale wyciągałby na światło dzienne, informacje o wewnętrznej strukturze zdań. Być może to jest najbardziej obiecujące uogólnienie/droga rozwoju tego pomysłu?
  • od strony teorii homologii, pomysł wydaje sie być dosyć oryginalny ( ale nie wiem czy interesujący). Operacje odczepienia można bowiem wykonać nie tylko dla wierzchołków! Możliwe jest przecież obdarzenie krawędzi simpleksów, ich elementów 2-wymiarowych i w ogólności n-wymiarowych, w jakąś dodatkową strukturę. Na każdym etapie n, można „coś odczepić” definiując odpowiednie operatory {\partial^n_a} analizujące strukturę symetrii takich obiektów w relacji do ich „umieszczenia” w całym kompleksie, która jest zadana przez klasyczny operator {\partial_n}. To czego nie widać ( i co nieco rozczarowuje) to fakt, iż nie bardzo mam pomysł jak powiązać ( i czy w ogóle istnieje takie powiązanie!) grupy odczepione na różnym poziomie n. A priori, w strukturze abstrakcyjnej można oczywiście budować tu jakieś abstrakcyjne obiekty, mnie wszakże interesowałoby podanie jakiegoś modelu takiego zjawiska. Modelu – czyli struktury która by niosła ciekawą informację w grupach odczepionych a jednocześnie pozwalała je definiować dla kilku poziomów struktur….

I to na tyle dziś.

Pinky: Móżdżku, co będziemy robić dzisiaj wieczorem?

Mózg: Dokładnie to samo, zawsze, Pinky: zdobędziemy władze nad światem!

W poprzednim wpisie pokazałem jak wyliczać grupy homologii na (trywialnym) przykładzie pojedynczego simpleksu. W tym wpisie pokaże jak, modyfikując mechanizmy teorii homologii, uwzględnić kwestie logiczne którym poświęciłem już kilka wpisów. Aby uniknąć odwoływania się do innych wpisów, poniżej krótkie przypomnienie zagadnień logicznych o jakich będzie mowa.

Mamy zadany system formalny, czyli zbiór zdań logicznych złożony z zdań wyróżnionych, zwanych aksjomatami,oraz pewnego zestawu reguł przekształcania napisów zwanych regułami inferencji, dedukcji lub wnioskowania. Reguły wnioskowania akceptują pewną formę zdań ( w sensie czysto graficznym, syntaktycznym, jako napisy) i pozwalają na podstawie takich argumentów, uznać że do systemu wolno nam dopisać kolejne, określone w swojej formie syntaktycznej przez „mechanikę reguły wnioskowania”, zdanie. Modelowym przykładem reguły wnioskowania jest znana z poprzednich wpisów reguła modus ponens. Symbolicznie będę tą regułę zapisywał w formie {MP(P,Q) =S} co jest oczywiście równoważne zapisowi {MP(a \rightarrow b,a) = b}. Regułę tą rozumiemy czysto syntaktycznie, jako napis.

Dowodem zdania {S} w systemie logicznym zawierającym aksjomaty i regułę dedukcyjną modus ponens jest uporządkowany ciąg zdań {a_{0},a_{1},a_{2} \cdots ,a_{n}} gdzie {a_{n} = S}, zaś zdania numerowane od {1, \cdots n-1} to aksjomaty, tautologie lub wcześniej dowiedzione zdania. Ponieważ wcześniej dowiedzione twierdzenia mają dowody ( a więc ciągi zdań…), możemy przyjąć ( zastępując każde zdanie w powyższym ciągu jego dowodem) że zdania {a_{1}, \cdots a_{(n-1)}} to aksjomaty lub tautologie. Dla każdego podciągu uporządkowanego {a_{0} \cdots , a_{k},a_{(k+1)}} istnieje reguła wnioskowania ( inferencji, dedukcji), która pozwala wyprowadzić zdanie {a_{(k+1)}} z zdań {a_{0},\cdots , a_{k}}. Jest to klasyczna definicja dowodu, czytelnik spotkał sie z nią zapewne wielokrotnie. W tym co nastąpi będę wiele razy pisał o graficznym przedstawieniu dowodu, o dowodach sprzecznych itp. W każdym takim wypadku pisząc dowód mam na myśli ciąg uporządkowany zdań jak powyżej, i jest całkowicie obojętne jakie twierdzenie zostaje odwiedzone. W istocie dyskusja dotyczy więc pewnego skończonego zbioru konsekwencji syntaktycznych zadanego zbioru aksjomatów. I tak należy rozumieć obiekt który poniżej nazywam dowodem.

Załóżmy że mamy zdania {a,b,c} o budowie syntaktycznej wiążącej te zdania reguła modus poens ( proszę zwrócić uwagę na kolejność!) {MP(b,a) =c}. Zdaniom tym przyporządkujemy graf, w postaci jak na rysunku poniżej:

MOdusPoens-general

Prosiłbym by czytelnik zwrócił uwagę, że graf jest skierowany, porządek ten zaś wynika z uporządkowania zdań w regule modus ponens. Przyjęliśmy mianowicie konwencję w której pierwsze zdanie to implikacja, drugie to przesłanka, a trzecie to następnik implikacji. Na grafie zaś reprezentujemy to odwracając kolejność implikacji i przesłanki. W poprzednim wpisie, dla takiego ogólnego obiektu wyliczyliśmy, w celach edukacyjnych, grupy homologii.

Tak jak poprzednio przy tak zdefiniowanej reprezentacji graficznej reguły modus ponens możemy kolejne użycia jej w dowodzie przypisać kolejnym trójkątom a w wyniku otrzymamy graf złożony z uporządkowanych trójkątów posklejanych wierzchołkami w miejscach gdzie powtarzają sie w dowodzie przypisane im zdania. Graf ten w swoich wierzchołkach zawiera zdania, zaś jego krawędzie to związek pomiędzy wierzchołkami polegający na tym że wystąpiły one w jednej regule modus ponens. W tym miejscu następuje pewien poważny przeskok koncepcyjny. Dotychczas rozważaliśmy grafy, teraz dołączmy do naszego postępowania także to co znajduje sie pomiędzy nimi. Będziemy uważać, rysunek powyżej przedstawia nie tyle graf z wierzchołkami i krawędziami co element powierzchni – czyli 2 wymiarowy simpleks i konsekwentnie, graf reprezentujący dowód stanie się „zlepkiem” takich simpleksów, czyli kompleksem simplicjalnym.

Podkreślmy że w zbiorze tym simpleks występuje tylko tam, gdzie 3 zdania będące jego wierzchołkami są użyte w pewnej regule modus ponens. Nie ma żadnej możliwości uzupełnienia krawędzi ( np. do postaci simpleksów 3 wymiarowych czyli czworościanów posiadających pewną objętość) tam gdzie reguła modus ponens nie występuje.

W tak otrzymanej strukturze geometrycznej, będziemy rozważać grupy homologii. Dodamy jednak do owej struktury dodatkowa informację o negacji pełnych zdań ( a więc o zdaniach postaci {A= \neg p} dla pewnego zdania {p}. Jakiekolwiek występowanie negacji w innej formie syntaktycznej nie będzie nas interesować, toteż jej użycie np. w koniunkcji, wewnątrz nawiasów itp jest dla nas całkowicie pomijalne. Przypomnijmy dodatkowo że dowód jest sprzeczny, kiedy na liście jego zdań występuje zarówno zdanie {A} jak i {\neg A}.

Formalizacje odwzorowania zbioru dowodu w grupy homologii rozpoczniemy od pokazania obliczeń na przykładzie najprostszych dowodów. Pierwszy z nich ma postać:

\displaystyle a_{0}. a \rightarrow a

\displaystyle a_{1}. a

\displaystyle a_{2}. MP(a_{0},a_{1} ) = a

Mamy zatem do czynienia z prostym simpleksem ( trójkątem skierowanym ) jak na rysunku poniżej:

AiA

gdzie zdanie b jest równe zdaniu a_0 z dowodu powyżej.  W odróżnieniu jednak od obliczeń które pokazaliśmy w poprzednim wpisie, tym razem w trójkącie tym dwa wierzchołki, a i c, są identyczne w tym sensie że zawierają to samo zdanie a.

Moglibyśmy teraz wyliczać ciąg grup kompleksów łańcuchowych tego obiektu, wg. znanych i nie bardzo złożonych zasad rachunków algebry homologii. Rozpoczęlibyśmy zatem od zbudowania ciągu grup abelowych kompleksów łańcuchowych, w następującej postaci:

\displaystyle 0 \overset{\partial_3}{\longrightarrow} C_{2} \overset{\partial_2}{\longrightarrow} C_{1} \overset{\partial_1}{\longrightarrow} C_{0} \overset{\partial_0 = 0 }{\longrightarrow} 0

Postąpimy jednak nieco inaczej. Obliczenia jak powyższe dają taki sam wynik, jak dla trywialnego przykładu pokazanego wcześniej i nie będziemy tutaj powtarzać tych obliczeń. Natomiast wprowadzimy pewien dodatkowy kompleks łańcuchowy {C_a} oraz odpowiadające mu odwzorowanie {\partial_a}. Grupa {C_a} będzie zawierała wierzchołki wraz z informacją o strukturze związanej z negacją zdań logicznych, zaś odpowiadający jej operator brzegu będzie działała na grupie łańcuchów 0-wymiarowych, a jego działanie będzie zależeć od wewnętrznej struktury związanej z wierzchołkami. Ciąg grup kompleksów łańcuchowych będzie zatem wyglądał tak:

HomologiaOdczepiona

Jak widać „rozdwoiliśmy końcówkę” ciągu grup łańcuchowych, możemy ją nazwać „odczepem” i mówić o „odczepionej” grupie homologii {H_a}. Aby określić działanie operatora {\partial_a} opiszemy jego działanie na generatorach grupy wierzchołków {C_0} zaś jego działanie na elementach pełnej grupy, które są, przypomnijmy, formalnymi sumami elementów zbioru wierzchołków, otrzymamy przez standardowe liniowe rozszerzenie.

Operator {\partial_a} definiujemy za pomocą następującej relacji:

\displaystyle \partial_a ( u) = |u| = u = - \partial_a( \neg u)

I to wszystko.

Zauważmy że działanie operatora {\partial_a} pozostawia działanie innych operatorów brzegu całkowicie niezmienionym. Nie wpływa zatem na wyliczanie żadnych grup homologii, poza swoją własną, oznaczmy ja {H_a}.

Przypatrzmy sę teraz jak wygląda {H_a}. mamy zależność:

\displaystyle H_a = ker( \partial_e ) / img (\partial_1)

Obrazem operatora brzegów {\partial_1} na zbiorze krawędzi, jest oczywiście grupa złożona ze wszystkich wierzchołków, w naszym wypadku {<a,b>}. Czym jest zbiór {ker(\partial_a)}? Jeśli zbiór wierzchołków zawiera wyłącznie różne wierzchołki, to nie istnieje pomiędzy nimi żadna relacja związana z operatorem {\partial_a}. Jest tak, gdyż operator ten przekształca każdy wierzchołek „z orientacją” na tożsamy mu wierzchołek „geometryczny”. Załóżmy że mamy zbiór N takich „wierzchołków z orientacją”. Nawet jeśli niektóre z „wierzchołków z orientacją” zawierają negacje, jeśli są to parami różne zdania, wynik nadal zawiera N wierzchołków, niektóre z nich co najwyżej mają znak minus.

Tak właśnie wygląda sytuacja dla simpleksu przedstawionego na rysunku powyżej. Wyliczmy bowiem jak zostaną przekształcone jego wierzchołki pod wpływem operatora {img (\partial_a)}:

\displaystyle \partial_a(a) = |a| = a

\displaystyle \partial_a(b) = |b| = b

\displaystyle \partial_a(c) = |c| = c

Jak widać zaczęlismy od 3 wierzchołków i na trzech wierzchołkach kończymy. W efekcie grupa homologii {H_a}jest równa:

\displaystyle H_a = 0 / <a,b,c> = 0

A co z pozostałymi grupami homologii? W przykładzie jaki tu rozważamy występuje istotna różnica w stosunku do przykładu trywialnego. A mianowicie zdanie {a = c}, czyli rozważany przez nas trójkąt ma sklejone dwa wierzchołki. Mamy zatem w trójkącie krawędzie {x,y,z} jednak krawędź {z} zaczyna i kończy sie w tym samym punkcie:

\displaystyle \partial_1(x) = b-a

\displaystyle \partial_1(y) = a-b

\displaystyle \partial_1(z) = a-a = 0

Oznacza to iż

\displaystyle Z_1 = ker(\partial_1) = <z,x+y>

Pierwszy generator jadra wynika bezpośrednio z rachunku {\partial(z) =0} zaś ostać drugiego generatora wynika oczywiście z faktu, że w sklejonym trójkącie, dwie pozostałe krawędzie, {x,y} tworzą samodzielny cykl. Tymczasem obraz brzegu trójkąta, to oczywiście suma jego krawędzi tak jak poprzednio:

\displaystyle B_1 = img(\partial_2) = <x+y-z>

Tym samym grupa homologii {H_1} jest równa:

\displaystyle H_1 = ker(\partial_1) / img(\partial_2) = <z,x+y> / <x+y-z> = Z

Grupa {H_0} która mierzy ilość spójnych składowych, jest izomorficzna z {Z} ( mamy tylko jedną składową i jest taka sama jak w poprzednim wypadku ( i dotyczy to wszystkich pozostałych grup).

Podsumujmy – sklejenie wierzchołka {a=c} doprowadziło do zmian w głównym ciągu grup homologii. Sklejenie to spowodowało powstanie dodatkowych jednowymiarowych pętli, zmieniając grupę {H_1}. Jednocześnie grupa odczepiona, jak ją nazwaliśmy, dla teorii niesprzecznej jest grupą trywialną równą grupie złożonej z jednego, tożsamościowego równego 0 elementu addytywnego.

Sytuacja wygląda zupełnie inaczej gdy rozważmy następujący dowód ( sprzeczny):

\displaystyle a_{0}. a \rightarrow \neg a

\displaystyle a_{1}. a

\displaystyle a_{2}. MP(a_{0},a_{1} ) = \neg a

Co odpowiada grafowi jak na rysunku poniżej

AinotA

Podkreślmy że nie ma w tym wypadku mowy o sklejeniu wierzchołków ( na wcześniejszych rysunkach oznaczanych {a} i {c}) gdyż tkwią w nich inne zdania, mianowicie zdania {a} i {\neg a} odpowiednio. Tu obecny pomysł istotnie rożni sie od opisów z kilku poprzednich wpisów. Wynika z tego że mamy do czynienia geometrycznie z przypadkiem trywialnym, odpowiadającym w sensie grup homologii dokładnie obliczeniom z pierwszego przykładu, opisanym w poprzednim wpisie. Zobaczmy jednak jak wygląda odczepiona grupa homologii {H_a}. Sprawdźmy jakie jest działanie operatora {\partial_a} na zbiorze wierzchołków:

\displaystyle \partial(a) = |a| =a

\displaystyle \partial(b) = |b| = b

\displaystyle \partial(c) = - \partial(a) = -|a|

Widzimy wyraźnie, że w zbiorze tym istnieje relacja która sprawia, że pewna suma generatorów {<a,b,c>} jest równa zeru, mianowicie {a+c = 0}. Czyli {Z_a=ker(\partial_a ) = <a+c>}. Natomiast obraz {B_0= img(\partial_1)} czyli zbiór brzegów, ma standardowe generatory {<b-a,c-b,c-a>} wraz z relacją, że wierzchołki te są spięte w cykl brzegu trójkąta. Grupa ilorazowa:

\displaystyle Z_a / B_0 = <a+c> / <b-a,c-b> = Z / 2Z = \{ 0,1 \}

Wyjaśnijmy. W mianowniku mamy tylko 2 a nie trzy generatory, gdyż relacja „spinająca trójkąt” pozwala wyeliminować jeden z generatorów związanych z wierzchołkami. Mamy zatem grupę ilorazową grup o jednym generatorze wolnym ( w liczniku) i 2 generatorach ( w mianowniku). Grupa w liczniku jest izomorficzna z zbiorem liczb naturalnych, zaś w mianowniku z suma prosta 2 takich grup. Iloraz jest grupą skończoną, złożoną z 2 elementów, 0,1, izomorficzną do grupy Z mod 2. Innymi słowy jest to grupa cykliczna, skończona o 2 elementach.

Mamy zatem następująca sytuację – dla przypadku teorii sprzecznej, odczepiona grupa homologii jest nietrywialną grupą skończoną, zaś pozostałe grupy homologii pozostają bez zmian.

Powyżej mieliśmy do czynienia z sytuacją wystąpienia jednej pary zdań sprzecznych. Wystąpienie większej liczby takich par, zwiększa wymiary grupy odczepionej – zyska ona nowe generatory. Jednocześnie będziemy oczekiwać, że nadal pozostanie ona grupą skończoną ( co wynika z faktu że ilość generatorów w jądrze operatora brzegu wynika z ilości par zdań sprzecznych, zaś w mianowniku z ilości cykli związanych z krawędziami. Analizowany graf ma w pewnym sensie minimalną liczbę krawędzi, i w bardziej skomplikowanych grafach liczba cykli złożonych z krawędzi będzie tylko większa )

I to by było na tyle w temacie grup homologii. Podane przykłady łatwo uogólniają sie na bardziej złożone teorie logiczne/kompleksy łańcuchów. W dalszych wpisach z tego cyklu będziemy z pewnością analizowali rozmaite konsekwencje przytoczonych definicji. W tym miejscu chciałbym sie jednak zastanowić nad ogólną sytuacją i możliwymi uogólnieniami.

Po pierwsze, pokazany ciąg homologii z doczepioną homologią odczepioną wygląda nieco sztucznie, ma jednak tą zaletę że w zerowym stopniu modyfikuje pozostałe grupy homologii.

Po drugie operator {\partial_a} został zdefiniowany w sposób uwzględniający własności negacji – jej zachowanie – na przykład zasada wyłączonego środka – przypomina oczywiście działanie grupy alternującej. Stąd propozycja definicji {\partial_a} podana powyżej. Nic jednak nie stoi na przeszkodzie, by zamiast obiektów logicznych rozpatrywać ogólne sympleksy, zaś zamiast zdań i ich negacji w każdym wierzchołku umieszczać obiekt z jakąś bogatą strykturą wewnętrzną, reprezentowaną przez grupę ( skończoną lub nie?). Odczepiona grupa homologii mierzy „zgodność” wierzchołków która, w odróżnieniu od własności mierzonych przez pozostałe grupy homologii, nie jest związana z własnościami geometrycznymi a jednocześnie nie jest lokalna. Wyobraźmy sobie sieć spinów, gdzie każdy z wierzchołków zawiera element grupy spinorowej. Grupa odczepiona może wówczas mierzyć własności związane z nierozróżnialnością cząstek umieszczonych w takim „krysztale spinowym”. Nie spotkałem sie z taką konstrukcją nigdzie, a nie wydaje sie być ona całkowicie pozbawiona zabawnych cech, czy może nawet praktycznych właściwości ( opis kryształu z pełną delokalizacją cząstek w określonej liczbie rozróżnialnych stanów spinowych). Widać, że uogólnienie w tym kierunku jest zarówno możliwe jak i niebanalne!

Po trzecie, dla przypadku logiki, konstrukcja homologii odczepionej, przedstawiona powyżej, wydaje się być dosyć przejrzysta. Kolejnym krokiem ( obok analizy homologicznych konsekwencji przedstawionych pomysłów) jest analiza teorii kohomologii. Kohomologia to teoria zajmująca sie odwzorowaniami liniowymi nad grupami homologii, albo alternatywnie, teoria analizująca związki odwrotne w stosunku do homologii. W wypadku homologii mieliśmy grypy łańcuchowe {C_k,C_a} analizowaliśmy które z cykli sa identyczne z dokładnością do brzegów obiektów o jeden większego wymiaru. W wypadku kohomologii sprawdzamy brzegami jakich obszarów większego wymiaru, są zadane cykle. nie posiadam obecnie wiedzy by napisać na ten temat cokolwiek sensownego, dlatego chętnie sformułuję przypuszczenie, że w kontekście logiki oznacza to analizowanie następującego zagadnienia. Brzegiem jakiego kompleksu symplicjalnego ( będącego geometrycznym modelem jakiegoś logicznego systemu formalnego, w tym kontekście – zwykle będzie to kompleks nieskończony! ) może być dowód sprzeczny?

ModusPoens2

Pinky: Móżdżku, co będziemy robić dzisiaj wieczorem?

Mózg: Dokładnie to samo, zawsze, Pinky, zdobędziemy władze nad światem!

Mam wrażenie że udało mi się wreszcie sformalizować intuicje związane z odwzorowaniem zbioru zdań dowodu w systemie formalnym ( ogólniej – zbioru zdań konsekwencji syntaktycznych zadanego zbioru zdań) w zbiór grup homologii. Ostateczna wersja dosyć istotnie odbiega od pomysłów poprzednich, jest bardziej elegancka jak sądzę, pozwala na ciekawe uogólnienia ( także w sensie teorii homologii) i ma pewien potencjał rozwojowy ( teorie kohomologii, o których na razie zbyt mało wiem by rozważać coś więcej). Formalizacja którą opisze poniżej, odbywa się w pewien konserwatywny, czy minimalny sposób, i polega na rozszerzeniu ciągu grup kompleksów łańcuchowych o dodatkowy element związany z odwzorowaniem wierzchołków w grupę alternującą. Aby jednak uniknąć opisywania abstrakcyjnego nonsensu, całość zostanie przedstawiona na przykładach obliczeń, które dosyć łatwo uogólnić.

Tradycją tego bloga, i moją ambicją, było dotychczas aby tekstu tu prezentowane mogły być czytane przez osoby z minimalnym przygotowaniem, toteż starałem się podawać cały potrzebny materiał, tak przystępnie jak tylko byłem w stanie. I tym razem postąpimy podobnie, zaczniemy od wprowadzenia pojęcia homologii, a w kolejnym wpisie odniesiemy ją do logiki.

Przypomnijmy że cała idea sprowadza się do tego że jeśli mamy zdania {a,b,c} o budowie syntaktycznej wiążącej te zdania reguła modus ponens ( proszę zwrócić uwagę na kolejność!) {MP(b,a) =c}, to zdaniom tym przyporządkujemy graf, w postaci jak na rysunku poniżej:

MOdusPoens-general

I dla takiego prostego obiektu będziemy starali sie, w celu edukacyjnym i by przygotować się do bardziej ambitnych wyzwań,  skonstruować grupy homologii.

Po pierwsze wyjaśnijmy co jest ta rysunku! Na rysunku powyżej, mamy obiekt płaski, trójkąt {X}. Jest to element powierzchni obdarzony orientacją zadaną przez kierunek obiegu jego krawędzi. Krawędzie te oznaczymy {x,y,z}. Krawędzie te łączą wierzchołki, na rysunku oznaczone {a,b,c}. Wypisane obiekty mają następujące wymiary: trójkąt jest obiektem 2 wymiarowym, krawędzie skierowane sa 1-dno wymiarowe, zaś wierzchołki to obiekty 0-wymiarowe. Brak na rysunku obiektów o wymiarach większych niż 2 i mniejszych niż 0 oczywiście. Obiekty te nie są bynajmniej niezależne, ale połączone sa w dosyć szczególny sposób. Na przykład każda krawędź ma dwa wierzchołki, zaś fakt iż złożenie krawędzie jest tak szczególne że tworzą pętlę – brzeg trójkąta – wynika że wierzchołek będący końcem jednej z krawędzi jest początkiem następnej i sytuacja ta powtarza sie tworząc cykl wierzchołków, w którym każdy z nich pojawia sie dwa razy – raz jako początek a raz jako koniec pewnej krawędzi.

Wyjściem dla budowania teorii homologii, która stara sie uchwycić właśnie takie wzajemne relacje pomiędzy elementami składowymi obiektu geometrycznego ( ogólniej topologicznego) jest zdefiniowanie dla każdego wymiaru części składowych, formalnego odwzorowania w grupę przemienną. Na przykład rozważmy sumę krawędzi {x+y}. Sumę ta będziemy traktować czysto formalnie, niemniej warto spostrzec, że chcąc być konsekwentny musimy uznać iż spełniona jest własność: {x+y=z} lub inaczej: {x+y-z=0} gdyż położenie wzajemne krawędzi jest takie ze tworzą one pętlę. Ponieważ suma jest czysto formalna, nic nie zabrania nam rozważać obiektów bardziej wymyślnych, na przykład {3x-4y+5z}. Konsekwentne postępowanie wymaga jednak by przyjąć że {mx+my-mz = m(x+y-z) =0} bo taka kombinacja zawsze oznacza ( moglibyśmy starać się to zinterpretować) m-krotne obejście pętli brzegu trójkąta. Całkiem identyczne obiekty, sumy formalne, możemy rozważać w wypadku wierzchołków czy wnętrza trójkąta i innych, więcej wymiarowych obiektów gdyby takowe występowały.

Grupę abelową obiektów o wymiarze {n} oznaczamy {C_n} i nazywamy n-tą grupą łańcuchową kompleksu X ( który w naszym przypadku jest szczególnie prosty, jest bowiem pojedynczym sympleksem). I tak grupa krawędzi, a więc 1-sza grupa łańcuchowa naszego trójkąta, jest generowana przez 3 elementy {<x,y,z>}. Nie jest to jednak grupa wolna ( a więc nie wszystkie elementy te są niezależne!). Z faktu istnienia relacji {x+y-z = 0} wynika że istnieje pomiędzy generatorami grupy związek, zaś sama grupa ma co najwyżej 2 niezależne elementy ( i tu już mamy pełną dowolność, mogą być to dowolne dwa boki trójkąta, np. {x,y} lub ich dowolna kombinacja liniowa). Jak widać niektóre związki pomiędzy elementami grupy łańcuchowej {C_1} ( krawędzi) w naszym przypadku były interesujące, czyli grupy takie mają czasami wewnętrzną strukturę! Istnieją także związki pomiędzy grupami o różnych {n}!

Weźmy grupę jaka jest związana z wnętrzem ( powierzchnią) trójkąta. Mamy tylko jeden trójkąt, cała grupa {C_2} jest zatem dosyć uboga, zawiera bowiem tylko jeden element {<X>}. Wszystko co możemy z takim elementem nawyczyniać, sprowadza sie do dodawania ( bądź odejmowania) go pewną liczbę razy, np. elementami grupy sa wyrażenia: {X+X, 34X, -7X} Brak jest też jakichkolwiek związków ograniczających ten element, jest więc to grupa wolna abelowa o jednym elemencie, czyli grupa izomorficzna ze zbiorem liczb całkowitych {Z}. Jednak brzeg tej figury, czyli zbiór jej skierowanych krawędzi, jak widzieliśmy ma niebanalną strukturę! Zdefiniujmy operator, oznaczany symbolem {\partial_2}, który działając na 2 wymiarowy trójkąt {X} przyporządkuje mu element grupy łańcuchowej wymiaru 1-mniejszej, a więc element z {C_1}, który będzie reprezentował brzeg figury {X}. Oczywiście wyliczenie wygląda następująco:

\displaystyle \partial_2 (X) = x+y-z

Całkiem podobnie możemy postąpić w wypadku krawędzi. Krawędzie są skierowane, zdefiniujmy więc podobne odwzorowanie do obiektów o wymiarze 1- mniej, w tym wypadku do grupy wierzchołków, które owo skierowanie będzie brało pod uwagę. Naturalne jest przyjęcie że operator {\partial_1} który każdej krawędzi przyporządkuje element grupy łańcuchowej wierzchołków będzie działał w sposób następujący:

\displaystyle \partial_1 (x) = b-a

\displaystyle \partial_1(y) = c-b

\displaystyle \partial_1(z) = c-a

Aby sprawdzić że się nie pomyliliśmy, policzmy ile wynosi {\partial_1 (x+y-z)} Mamy:

\displaystyle \partial_1 (x+y -z ) = \partial_1(x) + \partial_1 (y) - \partial_1 (z) = b-a +c -b -c +a = 0

co zgadza sie z obserwacją, że krawędzie trójkąta domykają się w pętlę.

A co z brzegiem wierzchołka? Czy możliwe jest zdefiniowanie operacji {\partial_0} ? Ile wynosi na przykład {\partial_0 (a)} ? Arbitralnie przyjmiemy że wynik to 0 w każdym wypadku.

Mamy zatem następująca sytuację.

\displaystyle 0 \overset{\partial_3}{\longrightarrow} C_{2} \overset{\partial_2}{\longrightarrow} C_{1} \overset{\partial_1}{\longrightarrow} C_{0} \overset{\partial_0 = 0 }{\longrightarrow} 0

Zera na początku i na końcu pokazanego ciągu grup i wzajemnych odwzorowań oznaczają że w trójkącie nie ma obiektów o wymiarze mniejszym niż 0 i większym niż 2.

Widzieliśmy powyżej, że operator {\partial_1(x+y-z) = 0}. Zbiór elementów grupy {C_1} których obrazem w grupie {C_0} przy przekształceniu {\partial_1} jest 0, określa się nazwą jądra ( kernel) operatora. Oczywiście suma czy różnica takich elementów także daje zero, co oznacza, jest to zresztą ogólna właściwość algebraiczna, że elementy jądra tworzą podgrupę. Zbiór ten w naszym przypadku złożony jest z jednego elementu, reprezentującego kompleks łańcuchowy odpowiadający brzegowi trójkąta. Symbolicznie zapisujemy to w następujący sposób:

\displaystyle Z_1 = ker (\partial_1 )

Zwróćmy uwagę, ze brzeg ów, jest z kolei obrazem całego trójkąta (X) przy odwzorowaniu {\partial_2} (M proszę zwrócić uwagę na indeks przy literze {B}):

\displaystyle B_1 = img (\partial_2)

I tym razem mamy do czynienia z podgrupą, gdyż suma formalna brzegów figur, jest brzegiem figury będącej ich sumą. Operator brzegu przypisuje figurom płaskim ich brzegi, a brzegi takie są zawsze łańcuchami cyklicznymi, czyli zamkniętymi pętlami. Nic więc dziwnego, że elementy grupy {B_1} leżą w grupie {Z_1} ( bo każdy cykl w przekształceniu {\partial_1} jest mapowany na 0). W naszym wypadku grupy te są wręcz równe, wynika to jednak z faktu że rozważamy wyjątkowo prosty przykład. Gdyby zamiast trójkąta rozważać figurę która zawiera „dziurę” w swoim wnętrzu, istniałyby także cykle krawędzi, które nie są brzegami żadnej powierzchni ( nie mają żadnego „wypełnienia” ). W takim wypadku grupa {B_1} byłaby podgrupą właściwą, zaś grupa {Z_1} cykli krawędziowych zawiewałaby obok elementów będących brzegami rozmaitych pól płaskich na jakie dzielilibyśmy taką figurę, także elementy będące cyklami pomimo iż nie otaczają „niczego”. Pierwszą grupą homologii {H_1} nazywamy grupę ilorazową grup {Z_1/ B_1}. Analogicznie n-tą grupą homologii jest grupa ilorazowa grup {Z_n/ B_n}:

\displaystyle H_n = Z_n/ B_n = ker(\partial_{n} ) / img(\partial_{(n+1)})

.

Wyliczmy zatem grupy homologii dla naszych grup łańcuchowych {C_k}. Dla k=2 jądro jest puste, gdyż żadna kombinacja 2-wymiarowych elementów ( a mamy tylko jeden: X ), nie sumuje sie do zamkniętej powłoki. Oczywiście nie ma także żadnych 3-wymiarowych obiektów… Zatem:

\displaystyle H_2 = ker( \partial_2 ) / img (\partial_3 ) = 0 / 0 =0

widać zatem że wszystkie grupy homologii {H_n} dla {n \geq 2} są równe 0.

\displaystyle H_1 = ker (\partial_1 ) / img (\partial_2 ) = <x+y-z> / <x+y-z> = 0

Zwróćmy tu uwagę, że w powyższym równaniu 0 po prawej stronie oznacza trywialną grupę złożona z jednego elementu – identyczności w grupie abelowej – a więc 0.

Teraz wyliczmy grupę homologii dla n=0. Ponieważ arbitralnie przyjęliśmy, że {\partial_0 = 0} to jądrem tego odwzorowania jest cała grupa wierzchołków, a wiec jądro to trójelementowa grupa wolna o 3 generatorach {<a,b,c>}. Przypomnijmy że powyżej wyliczyliśmy jakie sa elementy produkowane z krawędzi przez odwzorowanie {\partial_1} ( na przykład {\partial_{1}(x) = b-a} ). Obraz ten produkuje 3 elementy, które jednak, jak już wspominaliśmy nie są niezależne, bowiem wierzchołki owe spinają się w pętle brzegu trójkąta. Mieliśmy relację {x+y-z = 0} ( którą formalnie powinniśmy zapisać za pomocą symboli wierzchołków {a,b,c}, gdyż rozumiemy ja jako relację w zbiorze {C_0} a nie {C_1} którego elementami są {x,y,z}). Tym samym w zbiorze {<b-a,c-b,c-a>} tylko dwa elementy są niezależne, a trzeci można wyeliminować. Zatem grupa brzegów {img( \partial_1)} jest grupą wolną o generatorach {<b-a,c-b>} zaś trzeci element {c-a} jest od nich zależny ( łatwo sprawdzić że jest ich sumą!). Mamy:

\displaystyle H_0 = ker( \partial_0) / img (\partial_1) = <a,b,c>/<b-a,b-c>

Zauważmy że możliwe jest przejście od {<a,b,c>} do {<a,b-a,c-b>} bo polega ono na zamianie generatorów {a,b,c} przez ich liniowe i niezależne kombinacje co jest operacją dopuszczalną ( gdyż nie zmienia struktury grupy, stare generatory są liniowymi kombinacjami nowych i nie zmieniliśmy liczby generatorów niezależnych). Mamy zatem:

\displaystyle H_0= <a,b-a,c-b>/<b-a,c-b> = <a> = Z

Wynik nie jest zaskakujący, zwłaszcza że grupa {H_0} ma geometryczną interpretację: mierzy ilość składowych spójnych figury, w naszym wypadku trójkąta, który oczywiście ma tylko jedną składową spójną. Pozostałe grupy homologii, w naszym wypadku trywialne, także dają się geometrycznie interpretować. Mierzą one mianowicie ilość dziur o stosownych wymiarach. I tak np. grupa {H_1} mierzy ilość „pustych oczek” czyli dziur w figurze otoczonych jednowymiarowymi łańcuchami cyklicznymi które nie są wypełnione ( nie są brzegiem żadnej figury płaskiej pełnej). Z kolei {H_2} mierzy ilość cykli 2-wymiarowych które otaczają 2 wymiarowe otwory ( coś jak wnętrze walca, rurki, lunety), które nie są brzegiem żadnej figury posiadającej objętość ( wyplenionej).

Zauważmy że branie grupy ilorazowej we wzorze na grupę homologii właśnie taki ma cel – eliminuje z pełnej grupy cykli na n-tym poziomie te cykle, które są brzegami figur wymiaru n+1. Stąd homologia mierzy wzajemne położenia (homo-gogie) składowych o rożnych wymiarach w figurze geometrycznej. Teoria homologii została zapoczątkowana przez Poincare w trakcie jego prac nad topologia, obecnie zaś została znacząco uogólniona i rozszczepiona na wiele dziedzin o wspólnych korzeniach, od czysto geometrycznej klasycznej teorii homologii, przez rozmaite uogólnienia jak teoria (ko)homologii Cecha, aż do obiektów całkowicie abstrakcyjnych jak homologia kombinatoryczna i algebra homologiczna. Cechą wspólną wszystkich tych teorii pozostaje występowanie ciągu grup jak na diagramie grup kompleksów łańcuchowych wraz z przekształceniem \partial o stosownie ( do czego wrócimy) zdefiniowanych, nieraz aksjomatycznie, własnościach. Jeśli kogoś ciekawią zagadnienia topologii algebraicznej której teoria homologii jest twardym rdzeniem, polecam ten ciąg wykładów autorstwa N.J.Wildbergera. Forma wykładów jest bardzo elementarna, zaś przykłady obliczane w sposób bardzo szczegółowy, można skoczyć od razu w okolice wykładu 30-tego gdzie znajdują się zagadnienia związane z teorią homologii właśnie.

To już wszystko w tym wpisie. Przygotowałem sobie aparat za pomocą którego w kolejnym będę w stanie opisać jak zmodyfikować ciąg grup łańcuchowych {C_k} tak by zawierał informacje o zdaniach logicznych które w naszym wypadku będą leżały w wierzchołkach figury. Zapraszam.

 
 

kawalek-szczescia-pasek

 
 
 
 
Topolog Szachrajka
 
 
     

Chcecie bajki? oto bajka!
Był raz topolog szachrajka,
co budował bardzo śliczne
stacje kosmiczne.

Finitysta czy platonik,
tyra w kieracie jak konik:
takoż i topologowie.
A nad nimi są szefowie.

A nad szefem – są księgowi
co hołdują morfizmowi:
(zawsze wyjdzie taki bzdet )
budżet w kategorię FinSet

Szef raz zleca zespołowi
„Kosmodrom zbudować nowy!
„macie blachy sto arkuszy,
na więcej brakło funduszy”

Smutne miny, żałość wszędzie:
„Z tyla blachy? ciasno będzie”.
Logik ścisnął ręce w kieszni:
„mało będzie tam powierzchni”

Wtem Topolog nasz szachrajka
wpadł na pomysł: „to jest bajka!”
Klasnął, skoczył, wyginał wręgi
na kształt mobiusowej wstęgi!

Wraz robota jest skończona!
Stacja w kosmos wystrzelona.
Szef jest kontent że aż miło:
„tak przestronnie się zrobiło!”

„Teraz dla przecięcia wstęgi
przyjedzie marszałek tęgi.
Nieźleśmy to zbudowali!”
I wyszedł z uśmiechem z sali.

Kosmiczna orkiestra, przyleciał marszałek
Patrzy: jest korytarz, cały szereg gałek.
Panu marszałkowi siusiu się chce.
Pyta: „a gdzie tu jest wu-ce?”

Szef jest przerażony, woła Topologa.
„Topolog, no gdzie wu-ce?, jesuuu, o laboga!”
A topolog rzuca: „nie ma żadnej sprawy”
„niech idzie przed siebie i szuka po prawej…”

 
Zadanie dla zdolnych dzieci: stacja kosmiczna wykonana z blachy ma podłogę w kształcie wstęgi Mobiusa ( otoczoną stosownie ścianami, tak że można przejść ją całą w kółko ;-) Pan marszałek nie do końca pamięta, która ręka jest prawa, więc Szef zaproponował by topolog skoro taka mądrala, narysowała na podłodze panu Marszałkowi strzałki, zawsze w prawą stronę. Jak wiadomo wstęga Mobiusa – a wiec podłoga stacji, jest powierzchnią jednostronną, więc w końcu, rysując strzałki, topolog wróci do miejsca skąd zaczęła.
Pytanie: jak będą w tym miejscu wyglądały strzałki?

Wskazówka: A może warto sobie skleić wstęgę z papieru?

Słowniczek przydatnych terminów:
Morfizm – gdzie byś nie obracał, i tak wyjdzie na to samo
FinSET – kategoria zbiorów niestety skończonych
Wstęga Mobiusa – nieźle zakręcony kawałek przestrzeni

 
 

Pinky: Móżdżku, co będziemy robić dzisiaj wieczorem?

Mózg: Dokładnie to samo, zawsze, Pinky: zdobędziemy władze nad światem!

ModusPoens2

W poprzednich odcinkach opisałem pomysł odwzorowania zbioru zdań dowodu w systemie formalnym, na strukturę topologiczną typu zbioru simplicjalnego ( czyli zbioru złożonego z „porządnie” posklejanych simpleksów). Ponieważ spostrzegłem wiele niejasności i sam nie mam pewności czy konstrukcja ta jest sensowna, postanowiłem że zacznę od nowa, od najprostszych przypadków. Wpis ten ma pokazać na kilku obrazkach istotę konstrukcji dla pewnych elementarnych i bardzo krótkich dowodów. Będę się przy tym starał opisać całą konstrukcję raz jeszcze ( a więc z konieczności będę się powtarzał) wszakże obecnie wyrobiłem sobie nieco inny obraz całej sytuacji i mam nadzieję że będzie on bardziej czytelny niż poprzednie wpisy.

Zacznijmy od tego czym system formalny i dowód w ramach takiego systemu. System formalny to zbiór zdań logicznych złożony z zdań wyróżnionych, zwanych aksjomatami,oraz pewnego zestawu reguł przekształcania napisów zwanych regułami inferencji, dedukcji lub wnioskowania. Reguły wnioskowania akceptują pewną formę zdań ( w sensie czysto graficznym, syntaktycznym, jako napisy) i pozwalają na podstawie takich argumentów, uznać że do systemu wolno nam dopisać kolejne, określone w swojej formie syntaktycznej przez „mechanikę reguły wnioskowania”, zdanie. Modelowym przykładem reguły wnioskowania jest reguła modus ponens, mająca postać: jeśli w zbiorze zdań występuje zdanie { P= ''A \rightarrow B'' }, oraz zdanie {Q=''A''} to możemy dopisać zdanie {S=''B''}. Symbolicznie będę tą regułę zapisywał w formie {MP(P,Q) =S} co jest oczywiście równoważne zapisowi {MP(A \rightarrow B,A) = B}. Powiedzmy tutaj jasno że modus ponens jest regułą syntaktyczną zaś zdania w cudzysłowach,a wiec faktyczna postać syntaktyczna zdań, jest kluczowa dla jej zastosowania. Nie ma sensu używanie reguły {MP(P,Q) = S} dla „abstrakcyjnych” zdań {P,Q,S}. Jeśli poprawnie zastosowano regułę modus ponens, zdania {P,Q,S} miały określona ( i wypisaną jawnie powyżej) postać syntaktyczną ( to znaczy istniały takie zdania {A,B} że {P=''A=B''}, {Q=''A''} … itp. cudzysłowu używam w tym kontekście po to by jednoznacznie określić co jest zdaniem o które nam chodzi – mianowicie na przykład wyrażenie {P=''A \rightarrow B''} oznacza że istnieją zdania {A i B} takie że zdanie {P} ma postać jak w cudzysłowie. )

Dowodem zdania {S} w systemie logicznym zawierającym aksjomaty i regułę dedukcyjną modus ponens jest uporządkowany ciąg zdań { \{ a_{0},a_{1},a_{2} \cdots ,a_{n} \} } gdzie {a_{n} = S}, zaś zdania numerowane od {1, \cdots n-1} to aksjomaty, tautologie lub wcześniej dowiedzione zdania. Ponieważ wcześniej dowiedzione twierdzenia mają dowody ( a więc ciągi zdań…), możemy przyjąć ( zastępując każde zdanie w powyższym ciągu jego dowodem) że zdania {a_{1}, \cdots a_{(n-1)}} to aksjomaty lub tautologie. Dla każdego podciągu uporządkowanego { \{ a_{0} \cdots , a_{k},a_{(k+1)} \} } istnieje reguła wnioskowania ( inferencji, dedukcji), która pozwala wyprowadzić zdanie {a_{(k+1)}} z zdań {a_{0},\cdots , a_{k}}. Jest to klasyczna definicja dowodu, czytelnik spotkał sie z nią zapewne wielokrotnie.

Pewnej uwagi wymaga kwestia uporządkowania zdań w dowodzie. Co do zasady aksjomat lub zdanie uprzednio dowiedzione może się pojawiać na liście w dowolnym miejscu i dowolną ilość razy. Nowe zdania ( takie których nie ma na liście ) pojawiają się wyłącznie dzięki stosowaniu reguł dedukcji, w naszym przypadku – wyłącznie modus ponens. Jednocześnie, jak wspomnieliśmy aksjomaty, są zdaniami. Jest to konwencja różna od zwyczajowo stosowanej, mianowicie zwykle rozważa sie schematy aksjomatów. Oznacza to że np. wyrażenie ( założone jako aksjomat na przykład w systemie logiki Hilberta)

\displaystyle \phi \Rightarrow ( \psi \Rightarrow \phi )

nie reprezentuje zdania logicznego ale cały zbiór zdań, powstałych przez zastąpienie występujących w nim zmiennych {\phi,\psi} przez wszelkie możliwe i poprawne składniowo kombinacje zdań elementarnych ( które oznaczamy {P,Q,S...}) uzyskane przez zastosowanie spójników logicznych ( alternatywa, koniunkcja, implikacja, negacja itp.). Tym samym zbiór aksjomatów jest oczywiście zbiorem nieskończonym, przeliczalnym, zaś jego numeracja może odpowiadać pewnej arbitralnej ale określonej konwencji na przykład zdefiniowanej za pomocą złożoności składniowej zdania itp. Nie jest to w tej chwili kwestia istotna, głównie z tego powodu, że standardowy dowód to skończony ciąg zdań, a zatem i zawiera skończoną liczbę „realizacji” schematu aksjomatu i każde z tych zdań może mieć przypisany kolejny numer ( a nawet możemy przypisać różne numery tym samym zdaniom, np. ten sam aksjomat może być zdaniem 2, 10 i 12 na liście). Zauważmy, że choć w dalszym ciągu wywodu będę używał pojęcia dowodu, jak zdefiniowane powyżej, nie ma tu potrzeby by ograniczać się do dowodów konkretnych i określonych twierdzeń. Możemy powiedzieć, ze badamy po prostu uporządkowane ze względu na regułę modus ponens ciągi zdań z wyróżnionym, skończonym podciągiem startowym zwanym zbiorem aksjomatów i tego typu ogólność będziemy stale utrzymywali.

Załóżmy że mamy zdania {P,Q,S} o budowie syntaktycznej jak wypisana powyżej. Zdaniom tym przyporządkujemy graf, w postaci jak na rysunku poniżej:

ModusPoens

Prosiłbym by czytelnik zwrócił uwagę, że graf jest skierowany, porządek ten zaś wynika z uporządkowania zdań w regule modus ponens. Przyjęliśmy mianowicie konwencję w której pierwsze zdanie to implikacja, drugie to przesłanka, a trzecie to następnik implikacji. Konwencja ta nie jest całkowicie arbitralna i choć właściwie nigdzie nie będziemy w dalszym ciągu się na nią powoływać ponad fakt, że została określona i będziemy konsekwentnie jej używać, to ma ona dalece idące konsekwencje koncepcyjne. Nie przemyślałem tego faktu dostatecznie głęboko, wszakże konwencja wynikająca z korespondencji Currego-Howarda każe odnieść modus ponens do pojęcia „aplikacji funkcji” i można w tym kontekście przyjąć że nasza konwencja oznacza iż podajemy wpierw funkcję ( której odpowiada implikacja) a następnie jej argument czyli przesłankę implikacji, zaś w wyniku otrzymujemy następnik implikacji. Tymczasem w grafie postępujemy odwrotnie i odwracamy kolejność strzałek tak by pierwsza była przesłanka ( argument funkcji) który zgodnie ze strzałkami trafia pod działanie funkcji ( implikacja) i w wyniku dostajemy następnik implikacji. Owo odwrócenie kolejności ma znaczenie dla dalszych rozważań – stawiając przesłankę i następnik po „przeciwnych stronach” obiektu który zostanie dalej zdefiniowany a zwany jest plakietką ( proszę czytelnika o cierpliwość, kolejny przykład wyjaśni co mam tu na myśli).

Przy tak zdefiniowanej reprezentacji graficznej reguły modus ponens możemy kolejne użycia jej w dowodzie przypisać kolejnym trójkątom a w wyniku otrzymamy graf złożony z zorientowanych trójkątów posklejanych wierzchołkami. Graf ten w swoich wierzchołkach zawiera zdania, zaś jego krawędzie to związek pomiędzy wierzchołkami polegający na tym że wystąpiły one w jednej regule modus ponens. W tym miejscu następuje pewien poważny przeskok koncepcyjny. Dotychczas rozważaliśmy grafy, teraz dołączmy do naszego postępowania także to co znajduje się pomiędzy ich krawędziami. Będziemy uważać, że rysunek powyżej przedstawia nie tyle graf z wierzchołkami i krawędziami co element powierzchni – czyli 2 wymiarowy simpleks i konsekwentnie, graf reprezentujący dowód stanie się „zlepkiem” takich simpleksów, czyli kompleksem simplicjalnym ( bo z konstrukcji złączenie następuje wyłącznie w wierzchołkach lub wzdłuż krawędzi – o tym za chwilę).

Podkreślmy że w zbiorze tym simpleks występuje tylko tam, gdzie 3 zdania będące jego wierzchołkami są użyte w pewnej regule modus ponens. Nie ma żadnej możliwości uzupełnienia krawędzi ( np. do postaci simplesków 3 wymiarowych czyli czworościanów posiadających pewną objętość) tam gdzie reguła modus ponenes nie występuje. Operacje wstawiania i usuwania krawędzi, są istotne dla dalszych uogólnień, na razie jednak nie jestem w stanie podać ich spójnej definicji.

Typową sytuacją w zbiorze o jakim piszemy jest wspólny wierzchołek pomiędzy dwoma regułami modus ponens, to jest następująca sytuacja: istnieją zdania {A,B,C,D,E} takie że {MP(A,B) =C} oraz {MP(C,D)=E}. Jak widać mamy tu dwa simpleksy {(B,A,C)} oraz {(D,C,E)} ( zwracam uwagę na zmienioną kolejność wierzchołków w geometrycznej reprezentacji w stosunku do kolejności w regule modus ponens!) które mają wspólny wierzchołek.

Inna możliwa sytuacja to wspólna krawędź:

\displaystyle MP(A,B)=C

\displaystyle MP(B,C)=D

W tym przypadku mamy simpleksy {(B,A,C)} oraz {(C,B,D)} posiadające wspólna krawędź {(B,C)} czyli wspólny simpleks jednowymiarowy. Przykład takich zdań to: {A=''(s \rightarrow q) \rightarrow s''}, {B=''s \rightarrow q''}, {C=''s''}, {D=''q''}. Proszę sprawdzić że relacja powyżej jest spełniona.

Ciekawym pytaniem jest czy możliwe jest zbudowanie czworościanu, czyli simpleksu 3-wymairowego, o właściwej strukturze syntaktycznej zdań tak by każda ściana reprezentowała modus ponens i czworościan był właściwie zorientowany ( na zewnątrz, regułą lewej dłoni). Innymi słowy czy możliwa jest następująca konstrukcja:

\displaystyle MP(A,B)=C

\displaystyle MP(B,C)=D

\displaystyle MP(A,B)=D

\displaystyle MP(C,A)=D

dla różnych zdań {A,B,C,D}. Podkreślmy że ostatni warunek jest tu istotny. Polecam czytelnikowi jako ćwiczenie z zabawy tautologiami próbę zbudowania takiego obiektu. Zwrócę tu dodatkowo uwagę, że choć jak przypuszczam w ogólności nie jest to możliwe ( regułą modus ponens nie jest tranzytywna, własność tranzytywności ma natomiast sama implikacja), to być może stosowna konstrukcja jest możliwa przy dodatkowym założeniu o prawdziwości występujących w niej zdań np. że prawdziwe jest zdanie „B i C” itp…

Przy przyjętych założeniach, powstały graf wyraża wyłącznie strukturę wynikła ze stosowania reguły modus ponens. Odwzorowanie powyższe, pomiędzy dowodem a kompleksem symplicjalnym całkowicie pomija wewnętrzną strukturę zdań. Nic więc dziwnego że właściwie niewiele z niego wynika. Chciałbym dodać do obrazu powyżej informację na temat sprzeczności w dowodzie.

Przypomnijmy że dowód jest sprzeczny, kiedy na liście jego zdań występuje zarówno zdanie {A} jak i {\neg A}. Oczywiście w praktyce szukamy dowodów niesprzecznych, nic jednak nie stoi na przeszkodzie by analizować i sprzeczne. Co więcej, we wszystkich rozważaniach rozpatrujemy jedynie konsekwencje syntaktyczne, tak więc nie mówimy np. o wartościowaniu zdań, nie analizujemy które z nich są prawdziwe itp. Nie ma więc przeszkód by analizować uporządkowane ciągi zdań zawierające także i wyrażenia {A} i {\neg A}. Przy takich założeniach ciąg zdań, który nazywamy dowodem nie jest ciągiem sprzecznym tak długo jak długo nie występuje w nim para zdań sprzecznych! O ile w logice czy teorii modeli zwykle stosuje sie natychmiastowe uogólnienie polegające na dołożeniu do danego zbioru zdań, wszystkich ich konsekwencji syntaktycznych lub semantycznych, i o sprzeczności mówi sie w kontekście takie, nieskończonego obiektu, o tyle tu podkreślmy wyraźnie rozmawiamy wyłącznie o skończonych zbiorach zdań. Tym samym zbiór zdań, wśród którego konsekwencji występują sprzeczności, będzie przez nas rozważany jako zbiór niesprzeczny tak długo, jak długo owe zdania sprzeczne nie zostaną jawnie wyprowadzone ( dołączone do zbioru, doklejone kompleksu simpleksów) regułą modus ponens.

Rozważmy bardzo prostą zabawkową teorie o następujących aksjomatach:

\displaystyle a_{0}. A \rightarrow A

\displaystyle a_{1}. A

Bezpośrednie zastosowanie {MP(a_{0},a_{1} )} dale w wyniku zdanie A. Przedstawimy tą sytuację za pomocą następującego grafu.

MP-A-A

Tak jak na pierwszym rysunku, relacja modus poens między zdaniami jest przedstawiona za pomocą ciągłych, skierowanych linii, zaś kierunek przepływa od przesłanki przez implikację do następnika implikacji. Tym razem jednak każde kolejne zdanie, poprzednio reprezentowane jako punktowy wierzchołek, zostało pokazane jako odcinek obdarzony kierunkiem. Można uznać że w naszym odwzorowaniu każdemu wierzchołkowi przyporządkowaliśmy uporządkowaną parę punktów. Nadal moglibyśmy odwoływać sie do obiektu na rysunku powyżej jako do simpleksu ( dokonując dodatkowych odwzorowań wierzchołków w grupę alternującą itp. wierze że taka konstrukcja jest możliwa, zapewne gdyby ja wykonać teoria zyskałaby na ścisłości ) wszakże dla prostoty przedstawienia konsekwencji takiego rozszerzenia będę obiekty jak na rysunku powyżej nazywał plakietkami.

Po pierwsze linie ciągłe nadal reprezentują regułę modus ponens i ich orientacja jest nadal ustalona w taki sam sposób jak wcześniej. Zwróćmy uwagę że zdanie {A} występuje na rysunku dwukrotnie – raz jako przesłanka a raz jako następnik. jest to jednak to samo zdanie, możemy zatem ‚skleić” naszą plakietkę. Przymnijmy że mówimy tu o „geometrycznej” czy „topologicznej” reprezentacji, a więc o powierzchni. Otrzymamy w wyniku figurę topologicznią izomorficzną z powierzchnią boczną walca. Zauważmy że cały efekt uzyskaliśmy dzięki stosownej orientacji zdania {A} w wierzchołku w którym występuje on jako następnik implikacji ( wniosek).

Jako kolejny przykład rozważmy następującą, inną, teorię:

\displaystyle b_0. A \rightarrow \neg A

\displaystyle b_1. A

Bezpośrednie zastosowanie {MP(b_{0},b_{1} )} daje oczywiście zdanie {\neg A}. Oczywiście „teoria” którą się tu bawimy jest jawnie sprzeczna ( i faktycznie regułą modus ponens produkuje nam sprzeczność syntaktyczną po jednokrotnym jej zastosowaniu). Tym razem reprezentacja graficzna ma następująca postać:

MP-A-notA

Proszę zwrócić uwagę na odwróconą kolejność wierzchołków reprezentujących zdanie {\neg A}, oraz na to że kierunki strzałek reprezentujących przepływ w regule wnioskowania są identyczne jak na obrazku dla trywialnej teorii niesprzecznej. Otrzymany obiekt zawiera, podobnie jak poprzedni graf, dwukrotnie to samo zdanie {A} tyle że „inaczej podłączone”. Przy takiej reprezentacji, sklejenie którego musimy dokonać ( biały punkt do białego, czarny do czarnego) daje nam klasyczną reprezentacje wstęgi Mobiusa czyli powierzchni nieorientowalnej.

Co więcej, możemy przyjąć, że krawędzie  plakietki indukują na niej orientację, przy czym orientacja wynika owa z faktu, ze w regule modus ponens przesłanka i implikacja są zdaniami dowiedzionymi ( bo występują w zbiorze zdań z numerami wcześniejszymi niż następnik implikacji ). Tym samym załóżmy że plakietki możemy zorientować zgodnie z kierunkami „większości strzałek” reguły modus ponens.

Cały pomysł jaki chciałbym przeanalizować opiera sie na konstatacji że moja intuicja podpowiada mi że w przedstawionej reprezentacji, dowodom syntaktycznie sprzecznym, odpowiadają powierzchnie nieorientowalne, zaś dowodom niesprzecznym – orientowalne.

Zauważmy że „sklejenie” plakietek które pokazano na rysunku, zachodzi wzdłuż krawędzie przerywanych reprezentujących zdania ( a nie wzdłuż krawędzi reprezentujących reguły modus ponens). Jeśli teoria jest sprzeczna to wśród zdań które generuje sa zdania {A} i {\neg A}. Oznacza to że istnieją dwie krawędzie o przeciwnych orientacjach, które zostaną sklejone. Każda z nich jest jednocześnie jedną z krawędzi plakietki reprezentującej odpowiedni modus ponens. Zauważmy, że choć w teorii mogą istnieć izolowane plakietki ( bo możemy wypisać niezwiązaną z innymi regułę modus ponens), to jednak fakt że teoria jest sprzeczna oznacza że co najmniej jedna plakietka ( co najmniej ta na rysunku powyżej) jest sklejona. Istnieje tym samym droga zamknięta przechodząca po plakietkach od krawędzi {A} do {\neg A}. Wzdłuż tej drogi niemożliwe jest określenie orientacji plakietek ( orientacja ta nie musi mieć nic wspólnego z orientacjami indukowanymi z reguły modus ponens. Być może ma – ale bynajmniej tego nie twierdzę, wymaga to analizy).

Odwrotnie, niech pewna składowa spójna powierzchni sklejonych plakietek będzie nieorientowalna. Istnieje wówczas droga zamknięta, oraz krawędź zdaniowa przez którą przechodzi ona po plakietkach ( bo plakietki są sklejone wyłącznie wzdłuż krawędzi zdaniowych), wzdłuż której nie można określić orientacji. Jednocześnie orientacje lokalne wzdłuż krzywej raz indukują na owej krawędzi zdaniowej orientację typu {A} a raz ( „z drugiej strony”) {\neg A} – czyli teoria jest sprzeczna.

W dalszej części chciałbym zająć się kwestią definicji odwzorowań charakterystycznych dla teorii homologii – są to odwzorowania i-tej ściany {d_i} simpleksu ( ang. face map ) i odwzorowania degeneracji {s_i} ( ang. degeneration map). Pierwsze z ich mapuje simpleks na ścianę przeciwległą do i-tego wierzchołka, drugie zaś mapuje simpleks n wymiarowy na zdegenerowany o (n+1) wymiarach, poprzez powtórzenie i-tego wierzchołka. Zagadnienia te nie sa oczywiste gdyż dopisanie lub eliminacja wierzchołków odpowiada eliminacji lub dopisywaniu zdań do reguł modus ponens.

felicjan.jpg

Kasyno to jest taki biznes w którym przegrywają tylko ci co typują złe numery…  Wszyscy jesteśmy zmuszeni brać w tym udział z powodu posiadania brzucha! Niewiarygodne jest to że są ludzie inteligentni upatrujący w tym sprawiedliwości, efektywności, konieczności itp.  bo wierzą, że ci co przegrali są sami sobie winni – powinni przecież typować liczby, które wygrywają!

Pinky: Móżdżku, co będziemy robić dzisiaj wieczorem?

Mózg: Dokładnie to samo, zawsze, Pinky: zdobędziemy władze nad światem!

W poprzednim odcinku dowiedliśmy twierdzenia { p \Rightarrow p} w systemie dowodowym Hilberta. Dowód przebiegał w następujący sposób:

\displaystyle 1. (a_{1})

\displaystyle 2. (a_{4}) \phi=p

\displaystyle 3. (a_{5}) p \Rightarrow (\psi \Rightarrow p) (PD 2 w (a_{1}) ) [ (a_{1},a_{4},a_{5}) ]

\displaystyle 4. (a_{6}) \psi = p

\displaystyle 5. (a_{7}) p \Rightarrow (p \Rightarrow p) (PD 4 w (a_{5}) ) [ (a_{6}, a_{5},a_{7})]

\displaystyle 6. (a_{8}) \psi = p \Rightarrow p

\displaystyle 7. (a_{9}) p \Rightarrow ((p \Rightarrow p) \Rightarrow p) (PD 6 w (a_{5}) ) [ (a_{8},a_{5},a_{9})]

\displaystyle 8. (a_{10}) \vartheta = p

\displaystyle 9. (a_{2})

\displaystyle 10. (a_{11}) ... (PD 8 w (a_{2}) ) [(a_{10},a_{2},a_{11})]

\displaystyle 11. (a_{12}) ... (PD 6 w (a_{11}) [(a_{6},a_{11},a_{12})]

\displaystyle 12. (a_{13}) ... (PD 2 w (a_{12})) [(a_{4},a_{12},a_{13})]

\displaystyle 13. (a_{14}) (p \Rightarrow ( p \Rightarrow p)) \Rightarrow (p \Rightarrow p) (MP a_{9} - (a_{13}) ) [(a_{9},a_{13},a_{14})]

\displaystyle 14. (a_{15}) p=>p ( MP a_{7} - a_{14} ) [(a_{7},a_{14},a_{15})]

QED ;-)

Dowód ten zawierał zdania {(a_{1},a_{4},a_{5},a_{6},a_{7},a_{8},a_{9}}, {a_{10},a_{2},a_{11},a_{12},a_{13},a_{14},a_{15})}, zaś postępowanie opisane we wcześniejszym wpisie pozwoliło zdefiniować odwzorowanie tego ciągu w następujący simplicjalny kompleks kombinatoryczny (co nazwaliśmy triangulacją ):

{ \{(a_{1},a_{4},a_{5}),(a_{6},a_{5},a_{7}),(a_{8},a_{5},a_{9}),(a_{10},a_{2},a_{11}) \} }

{ (a_{6},a_{11},a_{12}), (a_{4},a_{12},a_{13}),(a_{9},a_{13},a_{14}), (a_{7},a_{14},a_{15}) \} }

Przypomnijmy że zdania są zgrupowane w trójkę kiedy stosując pewną regułę dedukcyjną, w oparciu o 2 z nich, dostaliśmy trzecie.

Triangulacja ta posiada następujące przedstawienie graficzne ( graf ten jest nieplanarny) sagehom Graf powyższy jest obrazem odwzorowania z zbioru zdań logiki powiązanych regułami dedukcyjnymi, w przestrzeń ( symplicjalnych ) kompleksów kombinatorycznych. Odwzorowanie to przenosi informację o zastosowaniu reguły dedukcyjnej, całkowicie jednak ignoruje zarówno to jaka reguła została zastosowana, jak i jak wyglądały zdania które w niej wystąpiły. Uzyskaliśmy więc ciekawe a może nawet zabawne odwzorowanie, kosztem zgubienia prawie całej interesującej z punktu widzenia logiki informacji. Aby uczynić to narzędzie nieco bardziej użytecznym, w kolejnym kroku postaramy się odzyskać cześć informacji o budowie wewnętrznej zdań. Konkretnie uczynimy odwzorowanie czułe na występowanie negacji, w nadziei że pozwoli to w przyszłości uzyskać jakieś obrazowanie zdań sprzecznych jako cech grafu. Poniżej konstruuję stosowne przekształcenie, tu jednak dodam, że „czułość” na wystąpienie negacji należy w nim rozumieć czysto syntaktycznie, chodzi wyłącznie o wystąpienie pewnej formy graficznej ~ p nie zaś o „znaczenie” zdania czy jego dalsze konsekwencje. Powtórzmy że mamy nadzieję iż dowody niesprzeczne ( szerzej zbiory konsekwencji syntaktycznych zbioru aksjomatów) będą odwzorowywane na kompleksy kombinatoryczne orientowalne, zaś zbiory zdań sprzecznych – na zbiory nieorientowalne. W konsekwencji jakaś część aparatu teorii homologii ( a może i homotopii) mogłaby być zastosowana w analizie zbiorów zdań.

W poprzednim wpisie zdefiniowaliśmy następujące przyporządkowanie:

  1. każdemu zdaniu {a_{i}} przyporządkowujemy krawędź skierowana zdefiniowana jako {(d^{s}_{i} d^{e}_{j} )}.
  2. jeśli zdanie {a_{i}} ma postać { \neg a_{k}} dla jakiegokolwiek {k<i}, to przyporządkowujemy mu parę {( d^e_k, d^s_k )} ( odwrócona kolejność!) która występuje już w triangulacji ( p.1 ).
  3. jeśli zdania {a_{i}, a_{j}, a_{k}} były w relacji R: {R(a_{i},a_{j}) = a_{k}} to w miejscu trójki {(a_{i},a_{j},a_{k})} wpisujemy {R(dd,dd) =dd} ( za każde zdanie {a_{i}} wpisujemy stosowną parę symboli d zdefiniowaną w pt. 1 i 2. patrz dalej pt.4 )
  4. każda 3-ka ( trójkąt) zostaje tym samym zamieniona na wyrażenie \displaystyle (a_{i},a_{k},a_{j}) = T -> DT = (d^{p}_{i},d^{q}_{i},d^{r}_{k},d^{s}_{k},d^{t}_{j},d^{u}_{j}) gdzie {i,j,k \in {0...n}} są numerami zdań z dowodu, zaś {p,q,r,s,t,u \in \{s,e\}}. DT jest trójkątem dualnym dla T ( zależność boki – wierzchołki!).
  5. W każdym wyrażeniu DT dokonujemy remuneracji i redukcji tak by opisywało trójkąt zdefiniowany przez 3 wierzchołki. Oznacza to że utożsamiamy pary wierzchołków w których odcinki odpowiadające zdaniom z trójkąta bazowego T są sklejone.

Przedstawimy teraz jego realizację dla powyższego dowodu. Zrezygnowałem z pisania symboli {d^{p}_{i}} dla prostoty przedstawienia konkretnego grafu. Zapis taki przydatny jest kiedy analizujemy sytuację symbolicznie, natomiast dla konkretnej realizacji wygodniej jest używać po prostu numerów wierzchołków ( punktów). Tym samym zamiast pisać {d^{s}_1 d^{e}_1} dla oznaczenia obrazu zdania {a_{1}} w triangulacji dualnej, zostało zapisane jako zdanie {1} a przyporządkowano mu punkty dualne {(1,2)}, zaś na przykład zdanie {a_{14}} zostaje zapisane jako {14} oraz odwzorowane w parę {(25,26)}. Poniżej lista wszystkich zdań z triangulacji oraz przyporządkowanych im odcinków skierowanych w triangulacji dualnej:

\displaystyle 1 \rightarrow (1,2)

\displaystyle 2 \rightarrow (3,4)

\displaystyle 4 \rightarrow (5,6)

\displaystyle 5 \rightarrow (7,8)

\displaystyle 6 \rightarrow (9,10)

\displaystyle 7 \rightarrow (11,12)

\displaystyle 8 \rightarrow (13,14)

\displaystyle 9 \rightarrow (15,16)

\displaystyle 10 \rightarrow (17,18)

\displaystyle 11 \rightarrow (19,20)

\displaystyle 12 \rightarrow (21,22)

\displaystyle 13 \rightarrow (23,24)

\displaystyle 14 \rightarrow (25,26)

\displaystyle 15 \rightarrow (27,28)

po lewej stronie strzałek w powyższym przedstawieniu, znajdują sie zdania – wierzchołki grafu dowodu, pochodzące z triangulacji dowodu. Po prawej stronie strzałek znajdują się przyporządkowane im odcinki skierowane, oznaczone jako pary punktów grafu dualnego. Oznacza to że graf triangulacji dowodu:

\displaystyle \{(a_{1},a_{4},a_{5}),(a_{6},a_{5},a_{7}),(a_{8},a_{5},a_{9}),(a_{10},a_{2},a_{11})

\displaystyle (a_{6},a_{11},a_{12}), (a_{4},a_{12},a_{13}),(a_{9},a_{13},a_{14}), (a_{7},a_{14},a_{15}) \}

zostaje odwzorowany w graf dualny który ma następująca postać ( odwzorowanie zapisane jako pierwsza strzałka w zestawieniu poniżej):

\displaystyle [1,4,5] \rightarrow [(1,2),(5,6),(7,8)] \rightarrow [(8,1),(2,5),(6,7)]

\displaystyle [6,5,7] \rightarrow [(9,10),(7,8),(11,12)] \rightarrow [(12,9),(10,7),(8,11)]

\displaystyle [8,5,9] \rightarrow [(13,14),(7,8),(15,16)] \rightarrow [(16,13),(14,7),(8,15)]

\displaystyle [10,2,11] \rightarrow [(17,18),(3,4),(19,20)] \rightarrow [(20,17),(18,3),(4,19)]

\displaystyle [6,11,12] \rightarrow [(9,10),(19,20),(21,22)] \rightarrow [(22,9),(10,19),(20,21)]

\displaystyle [4,12,13] \rightarrow [(5,6),(21,22),(23,24)] \rightarrow [(24,5),(6,21),(22,23)]

\displaystyle [9,13,14] \rightarrow [(15,16),(23,24),(25,26)] \rightarrow [(26,15),(16,23),(24,25)]

\displaystyle [7,14,15] \rightarrow [(11,12),(25,26),(27,28)] \rightarrow [(28,11),(12,25),(26,27)]

Graf taki składa sie z skierowanych odcinków ( dalej będę pisał dla prostoty strzałek) łączących pary punktów zapisane w nawiasach. Tym samym pierwsze odwzorowanie powyżej realizuje punkty 1-4. Chcemy teraz zrealizować punkt 5. Postąpimy w następujący sposób. Strzałki zapisane w nawiasach kwadratowych powinny zostać połączone w trójkąty, gdyż są wynikiem działania pewnej reguły inferencji co oznacza że możemy zachowując kolejność ( z dokładnością do przestawienia cyklicznego – chodzi bowiem o porządek w zamkniętych wielokątach) połączyć w pary te punkty które zostaną ‚sklejone”). Realizuje to drugie odwzorowanie przedstawione w zestawieniu powyżej.  Ułożenie nawiasów po zastosowaniu „pierwszej strzałki” odpowiadało przyporządkowaniu zdaniom – par punktów. Ułożenie nawiasów w po zastosowaniu „drugiej strzałki” odpowiada relacji „sklejenia” z dokładnością do cyklicznego przestawienia etykiet wierzchołków ( poniżej dyskusja w oparciu o rysunek). Tak otrzymany graf przedstawia sie w następujący sposób ( proszę kliknąć by zobaczyć większy obrazek w nowym oknie):

grafDualny

Na obrazku tym zaznaczono stosowne strzałki odpowiadające zdaniom ( czarne strzałki narysowane liną ciągłą) oraz sklejenia ( zaznaczone przerywanymi strzałkami kolorowymi). Jeśli dwa wierzchołki są połączone linią przerywaną, oznacza to że musimy je „skleić” lub utożsamić. Rożne kolory odpowiadają w tej operacji różnym „klasom utożsamienia”. Np. kolor niebieski oznacza że sklejone powinny zostać punkty {{18, 3}}, zaś kolor zielony oznacza że sklejamy zbiór punktów { \{4,6,7,10,14,17,19,20,21 \} }. Zauważmy że na grafie powyżej mamy 4 kolory przerywanych strzałek i oznacza to ni mniej ni więcej, że w grafie dualnym będziemy mieli tylko cztery punkty. Po wykonaniu operacji ściągnięcia uzyskamy następujący obrazek:

grafDualny-sciagniety

Sprawdzenie ( ręcznie lub komputerowo) prowadzi nas do wniosku że graf ten jest Eulerowski ( istnieje ścieżka przechodząca przez wszystkie krawędzie grafu, każdą tylko raz) co oznacza że można w nim zadać spójną orientacje krawędzi. Właściwie to wszystko. Jak widać na przykładzie cała operacja jest wykonalna, dosyć dobrze określona, produkuje coś co daje się narysować ;-) Pozostaje wypróbować całe podejście dla dowodu zdania sprzecznego ( jako prototyp użyty najpewniej zostanie paradoks Russella ). Ale to raczej w kolejnym wpisie.

Dodatek Graf powyżej został uzyskany za pomocą rysunku. Narysowałem triangulację dowodu, a następnie ręcznie nałożyłem na siebie jego wierzchołki. Poniżej przedstawię jak uzyskać graf jak na rysunku powyżej – czysto algebraicznie. Punktem wyjścia będzie obraz odwzorowania uzyskany powyżej:

\displaystyle [(8,1),(2,5),(6,7)]

\displaystyle [(12,9),(10,7),(8,11)]

\displaystyle [(16,13),(14,7),(8,15)]

\displaystyle [(20,17),(18,3),(4,19)]

\displaystyle [(22,9),(10,19),(20,21)]

\displaystyle [(24,5),(6,21),(22,23)]

\displaystyle [(26,15),(16,23),(24,25)]

\displaystyle [(28,11),(12,25),(26,27)]

Jak wspominałem zaznaczono w nim relacje sklejenia w trójkątach, czyli liczb w nawiasach są punktami połączonymi kolorowa strzałką na rysunku grafu. Jeśli w parze mamy wierzchołki {(8,1)} a powinniśmy je skleić, to oznacza to że musimy wyeliminować z całej tabeli wszystkie punkty {8} i wszystkie punkty {1} i zastąpić je tym samym wierzchołkiem, powiedzmy oznaczonym {a}. W pierwszym kroku eliminujemy zatem wszystkie 8-ki i jedynki:

\displaystyle [(a,a),(2,5),(6,7)]

\displaystyle [(12,9),(10,7),(a,11)]

\displaystyle [(16,13),(14,7),(a,15)]

\displaystyle [(20,17),(18,3),(4,19)]

\displaystyle [(22,9),(10,19),(20,21)]

\displaystyle [(24,5),(6,21),(22,23)]

\displaystyle [(26,15),(16,23),(24,25)]

\displaystyle [(28,11),(12,25),(26,27)]

W kolejnych krokach wyeliminujemy wszystkie {11,15} również zastępując je literą {a}:

\displaystyle [(a,a),(2,5),(6,7)]

\displaystyle [(12,9),(10,7),(a,a)]

\displaystyle [(16,13),(14,7),(a,a)]

\displaystyle [(20,17),(18,3),(4,19)]

\displaystyle [(22,9),(10,19),(20,21)]

\displaystyle [(24,5),(6,21),(22,23)]

\displaystyle [(26,a),(16,23),(24,25)]

\displaystyle [(28,a),(12,25),(26,27)]

w następnym zastąpilibyśmy literą {a} wszystkie {26,28} a potem kolejne „sąsiadujące z {a} w parach punkty. Po skończonej liczbie kroków w całej tabeli będą tylko pary w postaci {(a,a)} oraz pary w postaci {(liczba,liczba)}. Wtedy następnej parze złożonej z liczb przyporządkowujemy literę {b} i wykonamy konsekwentnie podstawienia za wszystkie liczby które sąsiadują z nią w jakiejkolwiek parze. I tak dalej i tak dalej, aż uzyskamy następujący wynik:

\displaystyle [(a,a),(b,b),(c,c)]

\displaystyle [(b,b),(c,c),(a,a)]

\displaystyle [(b,b),(c,c),(a,a)]

\displaystyle [(c,c),(d,d),(c,c)]

\displaystyle [(b,b),(c,c),(c,c)]

\displaystyle [(b,b),(c,c),(b,b)]

\displaystyle [(a,a),(b,b),(b,b)]

\displaystyle [(a,a),(b,b),(a,a)]

Jak widać dostaliśmy zdegenerowane „trójkąty” w których pewne wierzchołki są sklejone, zaś użyte litery to {a,b,c,d} co oznacza że otrzymaliśmy graf złożony z 4-rech wierzchołków.

Enter your email address to follow this blog and receive notifications of new posts by email.

Dołącz do 899 obserwujących.

Obserwuj

Otrzymuj każdy nowy wpis na swoją skrzynkę e-mail.

Dołącz do 899 obserwujących.

%d bloggers like this: