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.