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