Pinky: Móżdżku, co będziemy robić dzisiaj wieczorem?
Mózg: Dokładnie to samo, zawsze, Pinky, zdobędziemy władze nad światem!

Dowód P zdania B to uporządkowany ciąg zdań, {a_{0},a_{1},a_{2} \cdots ,a_{n}} gdzie {a_{n} = B}, zaś zdania numerowane od {1, \cdots n-1} to aksjomaty, tautologie lub wcześniej dowiedzione twierdzenia. 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}}.

Modelowym systemem dowodzenia będzie dla nas system Hilberta dla predykatów, czyli system aksjomatów logicznych oraz dwie reguły inferencji – modus ponens i reguła podstawiania, wszakże nie ma powodów by nie rozważać systemów bogatszych. Modelowo zakładamy jednak że mamy system Hilberta z dwoma regułami wnioskowania a obie te reguły maja taką cechę że dają się zapisać jako pobierające 2 zdania i produkujące 3-cie zdanie.

Schematy aksjomatów systemu Hilberta:

\displaystyle (a_{0}) \emptyset

\displaystyle (a_{1}) \phi \Rightarrow ( \psi \Rightarrow \phi )

\displaystyle (a_{2}) (\phi \Rightarrow ( \psi \Rightarrow \vartheta )) \Rightarrow ((\phi \Rightarrow \psi) \Rightarrow (\phi \Rightarrow \vartheta))

\displaystyle (a_{3}) \neg \neg \phi \Rightarrow \phi

Uwagi: zbiór pusty { \emptyset} jako aksjomat pozwala na używanie wszystkich tautologii logiki, które sa jego konsekwencjami logicznymi.

Reguły inferencji:

(modus ponens MP )

\displaystyle R(\phi, \phi \Rightarrow \psi) = \psi

(podstawianie zmiennej PD)  – jeżeli {p} jest zdaniem a {A} schematem aksjomatu zawierającym zmienną P {A(P,Q,S \cdots)} to

\displaystyle {A(P,Q,S \cdots ) |(P=p) = A(p,Q,S \cdots)}

jest dozwolonym zdaniem systemu. Oczywiście podstawiamy za wszystkie wystąpienia zmiennej {P}, a zatem w części oznaczonej {\cdots} zmienna {P} już nie występuje.

Alternatywnie posługując się się notacją za pomocą {R} mamy

\displaystyle R(P=p,A(PQS \cdots)) = A(p,Q,S \cdots)

.

Dalej czynimy istotne założenie (??): Każda reguła wnioskowania R używanego systemu dowodowego da się zastąpić pewnym zbiorem reguł 2 argumentowych ( rozmownie identyczne jak dla rachunku funkcyjnego w którym funkcja o arności n zostaje sprowadzona do formuły 1-dno argumentowej zwracającej funkcję o n-1 argumentach jako wynik). Występowanie reguł wnioskowania które jako argumenty pobierają więcej niż dwa zdania systemu, nie jest przeszkodą dla tego co opiszemy dalej, wszakże fakt, że każda taka reguła może być zastąpiona zbiorem reguł 2-argumentowych ma niebanalne znaczenie dla całej koncepcji postępowania.

Oznaczmy przez P dowód w systemie. Kolejne zdania w dowodzie P spełniają pewne relacje:

  1.  w dowodzie P niektóre 3 kolejne zdania są powiązane regułami wnioskowania, to znaczy istnieje reguła R taka że {R(a_{i},a_{(i+1)}) = a_{(i+2)}}.
  2. dla pewnego {i} zdanie {a_{i} } jest tautologią a więc jest konsekwencją logiczną zbioru pustego – a tym samym jest wynikiem rozumowania opartego na jednym z aksjomatów.
  3. dla pewnego {i} zdanie {a_{i}} jest aksjomatem ( aksjomat może występować jako zdanie na dowolnym miejscu w dowodzie).

Konsekwencja relacji 1-3 jest taka, że możemy powiązać niektóre zdania dowodu w podciągi 3-wyrazowe. Tworzymy zatem podciągi zdań dowodu P, zwane dalej 3-kami. Czynimy to w następujący sposób:

  1. jeśli zdania {a_{i}, a_{j}, a_{k}} są powiązane regułą wnioskowana {R(a_{i},a_{j}) = a_{k}} tworzymy trójkę {(a_{i}, a_{j}, a_{k})}
  2. jeżeli zdanie {a_{i}} jest tautologią, a jego wystąpienie w dowodzie P służy wyprowadzeniu ( za pomocą reguły wnioskowania R) zdania {a_{k}}, to zdanie {a_{k}} uważamy za konsekwencje zbioru pustego {\emptyset } który jest jednym z aksjomatów i tautologii {a_{i}}. Tym samym mamy {R(\emptyset,a_{i}) = a_{k}} i dodajemy podciąg {(\emptyset,a_{i},a_{k})}

Identycznie postępujemy w wypadku aksjomatów ( nie potrzeba tu żadnej dodatkowej reguły bo aksjomaty sa zdaniami i obejmuje je postępowanie z pt. 1 )

Dokonaliśmy zatem odwzorowania ciągu zdań dowodu P w zbiór uporządkowanych ciągów 3-elementowych zbioru zdań P. Zbiór ten będziemy nazywali dalej triangulacją dowodu.

Zatem dowód {P = (a_{0},a_{1},a_{2},\cdots,a_{n} )} zaś jego triangulację {T= \{(a_{i},a_{j},a_{k}),\cdots (a_{s},a_{p},a_{q}) \} }

Wróćmy na chwilę do kwestii reguł wnioskowania które wymagają większej niż dwa, liczby argumentów. Nic nie stoi na przeszkodzie aby rozważać odwzorowania w podzbiór ciągów m-elementowych ( m<n) np. kiedy rozważamy wprost reguły inferencji o arności m. Zgodnie jednak z założeniem oznaczonym (??) każde takie odwzorowanie możemy sprowadzić do rozpatrywania 3-jek zdefiniowanych jak powyżej, co można określić jako możliwość triangulacji.

Tym samym zdefiniowaliśmy triangulację dowolnego dowodu.

Popatrzmy na przykład w systemie Hilberta. Dowiedźmy w systemie Hilberta że {p \Rightarrow p}

Uwagi do poniższego dowodu – dodawane nowe – a więc nie będące aksjomatami – zdania dowodu numerujemy od {a_{4}} gdyż {a_{0} \cdots a_{3}} sa numerami aksjomatów.

W nawiasach kwadratowych na końcu każdej linii dowodu wypisuję 3-kę jaką dodajemy do triangulacji dowodu. W uwagach na dole wpisu umieściłem komentarz do pewnej subtelności w dowodzie związanej z stosowaniem podstawienia.

\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 ;-)

W liniach 10,11,12 dla zaoszczędzenia miejsca, nie wypisałem stosownej formuły logicznej a jedynie napisałem o jaką formułę chodzi np. w linii 10 w miejscu kropek powinna zostać wpisana formuła powstała z operacji podstawienia (PD) formuły 8 w schemat aksjomatu {a_{2}}. Dla przebiegu dalszych dywagacji, nie ma znaczenia czym są formuły w tych liniach, istotna jest za to trójka wypisana po prawej stronie, na końcu tych linii.

Otrzymaliśmy zatem dowód {(a_{1} \cdots a_{15})} wraz z 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}) \}

TaaDaa! Mamy zatem kompleks symplicjalny ;-) i bawimy sie Sage:


sage: K=SimplicialComplex([[1,4,5],[6,5,7],[8,5,9],[10,2,11],[6,11,12],[4,12,13],[9,13,14], [7,14,15]]);K
Simplicial complex with 14 vertices and 8 facets
sage: K.dimension()
2
sage: #porównać!!! : http://en.wikipedia.org/wiki/Euler_characteristic
sage: #http://en.wikipedia.org/wiki/Cubohemioctahedron
sage: K.euler_characteristic()
-2
sage: K.cohomology()
{0: 0, 1: Z x Z x Z, 2: 0}
sage: #brak połączonego komponentu mógłby oznaczać lukę w dowodzie!
sage: K.connected_component() == K
True
sage: #hm...
sage: K.fundamental_group()
Finitely presented group
sage: Show(K.graph())

sage: K.betti()
{0: 1, 1: 3, 2: 0}

Ostatnia wynik oznacza że mamy 3 dziury – koła – w kompleksie reprezentującym dowód ( nie ma to żadnego znaczenia dla logiczne poprawności dowodu. Słowo dziura jest tu użyte jako nazwa na obiekt topologiczny w przestrzeni kompleksów krawędziowych na którą odwzorowujemy dowody).

W oparciu o powyższe chyba niewiele da się zrobić. Niemniej nawet z tak nieskomplikowaną maszynerią, można silić się na jakieś działania. Można na przykład zapytać jakie związki zachodzą pomiędzy dowodami posiadającymi triangulacje o tych samych własnościach homologicznych ( jak liczba Betii – czyli liczba „dziur” w kompleksie symplicjalnym). Powątpiewam by wynikało z tego coś epokowego, czy nawet ważnego. Wydaje sie tak być choćby z tego powodu że cała powyższa maszyneria jest właściwie ślepa na logikę. Jedyne co zostało odwzorowane w tej konstrukcji, to informacja o następstwie zdań w dowodzie i ich wzajemne relacje ( co z czego wynika) a i to na poziomie numeracji, bez zachowania jakichkolwiek informacji o strukturze zdań, aksjomatów itp. Niemniej jako ciekawostka ( a może i jako fakt sam w sobie) nie są to rzeczy całkiem głupie, jak sądzę.

Warto także zauważyć, że powyższa konstrukcja, co zupełnie pominąłem, daje pewne szanse na zabawę krawędziami, drzewem rozpinającym dla kompleksu symplicjalnego, a może nawet homotopią na kompleksie, z czym można by wiązać pewne nadzieje.

No oczywiście interesują nas konfitury. Co zrobić z sprzecznością? Chcielibyśmy aby sprzeczność pojawiała sie jako nieorientowalnośc kompleksu symplicjalnego ( a wiec istniałyby zbiory zdań sprzeczne, ale nie byłyby orientowane ich triangulacje. Spełnialność zdań == orientowalność)

Należałoby postąpić tak. w przykładzie powyżej każde zdanie było punktem, a każde zastosowanie reguły wnioskowania definiowało 3-elementowy simplex. Zdefiniujemy 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 { (a_{i},a_{k},a_{j}) = T \to 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.

W wyniku takiej operacji dualizacji kompleksu triangulacji dowodu uzyskujemy kompleks dualny zawierający w sobie informacje o negacji zdań. Informacja ta zawarta jest w orientacji krawędzi kompleksów dualnych.

Twierdzenie; Jeśli zbiór zdań M jest niesprzeczny to dualizacja jego triangulacji jest orientowalna.

Dowód ( poglądowy): Każdy trójkąt dualny ma określoną orientację, wynikającą z porządku jego wierzchołków. Załóżmy że 2 trójkąty mają wspólna krawędź p. Zachodzą następujące przypadki:

  1. pewne zdanie ( reprezentowane przez tą krawędź) jest wynikiem 2 wnioskowań za pomocą MP lub PD ze zdań ( twierdzeń) teorii.
  2. istnieją 2 rozumowania oparte o MP lub PO w których wykorzystano tą samą przesłankę p
  3. istnieje zdanie p które jest wynikiem rozumowania MP oraz innego rozumowania PD.

Jeśli teraz orientacja tych 2 trójkątów na wspólnej krawędzi jest przeciwna ( czyli kompleks nie posiada spójnie zdefiniowanej orientacji) to albo 2 użycia MP lub PO prowadzą do wniosków p i ~p ( orientacja! ) albo w rozumowaniu użyto jako przesłanki raz p a innym razem {\neg p}, albo wyprowadzono zdanie p za pomocą MP a w dowodzie użyto go w znaczeniu {\neg p} za pomocą PD . cbdo.

Na przykład obliczeń homologii dla przypadku dualnej reprezentacji dowodu powyżej przyjdzie państwu nieco poczekać…bo muszę się nauczyć homologii singularnej ;-) A na poważnie, bo triangulacja na nieznanym terenie wymaga czasu i skupienia.

Uwaga: symbol { \phi=p} należy rozumieć jako fragment reguły podstawiania zdania p do aksjomatu na liście zdań dowodu. Sytuacja ta wymaga komentarza. Do dowodu nie wolno sobie wpisywać zdań które nie są twierdzeniami, a p nie jest twierdzeniem w naszym systemie. Jednak w systemie tym obiekty nazwane wyżej aksjomatami, w istocie nimi nie są! Zdania {a_{0} \cdots a_{3}} sa schematami aksjomatów. Jeśli zatem dysponujemy pewną liczbą zdań {p,q,r,s \cdots }, a może ich być skończona lub nieskończona liczba, powinniśmy uważać że system ma stosowną liczbę aksjomatów, powstających jako wynik podstawienia za wszelkie zmienne {\phi, \psi \cdots } występujące w ich schematach zdań systemu. Inaczej – aksjomaty zawierają zmienne – oznaczane greckimi literami – zaś zdania oznaczone są małymi literami łacińskimi. Przy takim postępowaniu, reguła podstawiania nie jest potrzebna, zaś w miejsce „wprowadzenia zdania {p}” wypisalibyśmy po prostu stosowny aksjomat. Należałoby jednak wówczas ponumerować – i przytoczyć – wszystkie – używane w dowodzie -aksjomaty… Ekonomiczniej będzie dodać zdanie {\phi=p} rozumiejąc przez ten fakt, że chodzi o zdefiniowanie stosownego podstawienia w odpowiednim schemacie aksjomatu.)

Dodatkowe komentarze do przemyślenia:

  1. sprzeczność może się pojawiać jako syntaktyczna ( p i ~p sa twierdzeniami teorii, alternatywne formy) albo semantyczna ( przy wartościowaniu, brak spójnego wartościowania). Co z tym zrobić?
  2. większość opisanych w literaturze paradoksów jest „nisko-wymiarowa” to znaczy są relatywnie prostymi zdaniami które maja w związku z tym relatywnie prosta triangulację (sprzecznych) dowodów. W topologii wiadomo że minimalne przestrzenie nieorientowalne sa relatywnie niskiego wymiaru ( wstęga, butelka). Przypadek? Chyba nie…zwłaszcza jeśli reprezentacja spójności za pomocą orientowalności jest sensowna.
  3. orientacje są tyko dwie, niezależnie od wymiaru przestrzeni. Istnieją logiki wielowartościowe. Wszakże sprzeczność albo niesprzeczność nie ma nic wspólnego z prawdziwością a ta z wartościowaniem….
  4. ostatnio pokazano że są przestrzenie nietriangulowalne, co by to miało być w tym obrazku, gdyby istniał funktor odwrotny? Być może nic, a może obiekty które nie dają się aksjomatyzować skończoną ilością aksjomatów –> niezupełność fundamentalna? Niezupełność nie musi być z ty związana, choć brzmi atrakcyjnie. Przykład takiego obiektu jest nieorientowalny ( ale nie wiem czy takie obiekty muszą być nieorientowalne) – tylko paradoksalne teorie nie dopuszczają lokalnie skończonej aksjomatyzacji?

Źródła:

  1. Duda „Wprowadzenie do Topologii” T1 i 2
  2. Grell „Wstęp do matematyki. Zbiory, struktury, modele.”
  3. Trzesicki „Logika i teoria Mnogości”
  4. http://en.wikipedia.org/wiki/Singular_homology
  5. linki w tekście