Paradoks Yablo

 

Motto:

    “W książce Stephena Hawkinga z 1988 Krótka historia czasu (ang. A Brief History of Time) na początku pierwszego rozdziału jest opisana następująca anegdota, wymiana zdań pomiędzy naukowcem i starszą panią:

Znany naukowiec (być może filozof Bertrand Russell) wykładał astronomię dla ogólnej publiczności. Opisywał, że Ziemia porusza się wokół słońca, słońce porusza się wokół centrum galaktyki.
Pod koniec wykładu starsza pani siedząca w końcu sali wstała : “Wszystko to co pan nam powiedział to są doprawdy głupoty. W rzeczywistości świat jest wielką płytą podtrzymywaną na grzbiecie wielkiego żółwia”
Naukowiec uśmiechnął się i z przekąsem zapytał “A na czym stoi żółw”?
“Jest pan bardzo sprytny młody człowieku”, odpowiedziała starsza pani, “Po prostu tam są żółwie aż do samego końca”.”

    Zakładam że czytelnik wie na czym polega pojęcie antynomii. W wielu znanych antynomiach, jak antynomii kłamcy czy antynomii Rusella klas samozwrotnych mamy do czynienia z sytuacją w której nie jesteśmy w stanie przypisać w niesprzeczny sposób wartości logicznej zdaniom związanym z tymi paradoksami. Sprawa jest omawiana przez wszystkie podręczniki teorii mnogości, logiki itp.W popularnej kulturze szczególnie głęboko zapisało sie zdanie “Ja kłamię” zwane antynomią kłamcy. Jeśli osoba wypowiadająca to zdanie mówi prawdę, czyli zdanie P=”ja kłamię” jest prawdziwe, to stwierdza że kłamie czyli wypowiada fałszywe zdanie co oznacza że kłamie mówiąc ze kłamie więc mi prawdę. Ogólnie przyjętym rozwiązaniem jest eliminacja z języka zdań samozwrotnych a więc wypowiadających treści na swój własny temat.

    Rozwiązanie takie jest kosztowne. Z języka zostają wyeliminowane nie tylko antynomie jak antynomia kłamcy, ale i zupełnie nieszkodliwe zdania jak “ja mówię prawdę”.

    Powstaje pytanie na ile rozwiązanie to jest skuteczne. Powszechnie uważa się że jest. Nic jednak dziwnego że pojawiają się próby wynajdywania antynomii bez samozwrotności. Przykładem właśnie takiej wynalazczości jest paradoks Yablo. Ma on postać następującego, nieskończonego, przeliczalnego, ciągu zdań (dalej będę ów ciąg oznaczał przez (Y)):

(Y0) dla każdego n>0 zdanie Yn jest fałszywe
(Y1) dla każdego n>1 zdanie Yn jest fałszywe
(Y2) dla każdego n>2 zdanie …..
.
.
itp.

    Zanim zaczniemy analizować (Y) rozpatrzmy prostsze przykłady.

    Pierwszym niech będzie tzw. koło kłamców. Jest to ciąg k>1 zdań, o następującej konstrukcji. Pierwsze zdanie K0 stwierdza że zdanie K1 jest fałszywe (lub że osoba K kłamie). Zdanie K1 stwierdza że zdanie K2 jest fałszywe. … Ostatnie zdanie Kk stwierdza że K0 jest prawdziwe Dla tak zadanego ciąg zdań nie jesteśmy w stanie przypisać wartościowania, które zdania są prawdziwe a które fałszywe, w konsystentny sposób. Proszę by czytelnik zabawił się tym ciągiem dla 2 zdań P i Q, następującej treści P=”~Q” Q=”P”.

    Powyższy przykład jest o tyle ważny, że samozwrotność jest w nim wmontowana w pośredni sposób. Żadne ze zdań Ki nie jest samozwrotne, ale dzięki konstrukcji całego ich zbioru ( ostatnie zdanie wypowiada treść na temat prawdziwości pierwszego ) uzyskujemy sprzeczność. Czyli wykluczenie zdań samozwrotnych “atomowo” nie rozwiązuje problemu. W celu likwidacji antynomii związanych z samozwrotnością, należy wykluczać cale zbiory zdań samozwrotnych. W wypadku zbiorów skończonych sprawa wydaje sie dosyć dobrze określona.

    W wypadku nieskończonych ciągów zdań, rzeczy mają sie jednak inaczej. Rozpatrzmy jako drugi przykład następujący zbiór zdań ( dobrany tak by przypominał nieco sekwencję Yablo (Y)):

(P0) ~P1 ^ ~P2
(P1) ~P2 ^ ~P3
(P2) ~P3 ^ ~P4
(P3) ~P4 ^ ~P5
.
.
itd

    Zdanie P0 stwierdza że P1 i P2 są fałszywe. Zdanie P1 nie odnosi się w żaden sposób do treści zdania P0, i żadne z wypisanych ( i możliwych do wypisania) zdań tego zbioru nie wypowie żadnej treści o zdaniu P0. Wygląda na to że nie ma tu żadnej samozwrotności. Czy możemy ustalić jaka jest prawdziwość zdań tego systemu? Załóżmy że zdanie P0 jest prawdziwe. Oznacza to że fałszywe są zdania P1 i P2. Skoro zdanie P1 jest fałszywe, to prawdziwe jest następujące zdanie ~P1 = ~(~P2 ^ ~P3) = P2 v P3 gdzie użyliśmy prawa de Morgana dla negacji koniunkcji. Ale zdanie P2 jest fałszywe ( bo stwierdza to zdanie P0) zatem zdanie P3 musi być prawdziwe ( a zdanie P2 fałszywe). Wypisując uzyskany ciąg wartości prawdziwości zdań ( P0P1P2 itp.) uzyskujemy następujący ciąg (0-fałsz, 1-prawda): 1001

    Zauważmy że w wypadku zdania P3 uzyskaliśmy orzeczenie że jest ono prawdziwe. Ponieważ konstrukcja zdań P4 i następnych jest taka sama jak zdań poprzednich, wartościowanie zdania P4 przy uzyskanej prawdziwości zdania P3 odbędzie sie wg. tych samych zasad ( tego samego rozumowania) co w wypadku zdania P1 przy założonej prawdziwości zdania P0. Udało nam sie tym samym ustalić wartościowanie pełnego ciągu zdań,w postaci:
1001001001001001…

    Wynik ten łatwo uogólnić posługując się następującym rozumowaniem. Jeśli mamy ciąg zdań jak powyżej to zakładając że pierwsze zdanie P0 jest prawdziwe uzyskujemy następującą treść dla zdania ~P1: “spośród dwóch następnych zdań co najmniej jedno jest prawdziwe”. Jednak zdanie P0 stwierdza że fałszywe są zdania P1 i P2 więc prawdziwe musi być zdanie P3. Łatwe uogólnienie ma następującą postać.

    Niech będzie dany nieskończony ciąg zdań (P) = {P0,P1…Pk,…} o następującej konstrukcji:

(P0) ~P1 ^ ~P2 ^ ~P3 ^ … ^ ~Pk
(P1) ~P2 ^ ~P3 ^ ~P4 ^ … ^ ~P(k+1)
.
.
(Ps) ~P(s+1) ^ ~P(s+2) ^ … ^ ~P(s+k)

.

.

.

 

    Wówczas wartościowanie w którym P0 jest prawdziwe, po czym następuje k zdań nieprawdziwych, po czym P(K+1) jest prawdziwe i reszta ciągu jest okresowa jest prawidłowym wartościowaniem ciągu zdań (P).

    Tu uwaga na temat drzewka. Wartościowanie dla pierwszego ciągu powyżej, P0 = ~P1 ^ ~P2 itd. można narysować za pomocą drzewa. Każdy węzeł drzewa odpowiada zdaniu Pi dla pewnego i. Wierzchołek drzewa odpowiada zdaniu P0. Kiedy zdanie jest prawdziwe – idziemy do lewego dziecka, kiedy jest fałszywe do prawego. Określenie konsystentnego wartościowania oznacza że zbiór zdań wyznacza pewną ścieżkę na drzewie. Zdania nie są samozwrotne więc nie ma żadnych cykli i cała procedura sprowadza sie do znalezienia właściwej ścieżki. Zdanie P0 oznacza że 2 następne ścieżki po nim muszą być w lewo. Wchodząc na drzewo zakładamy że P0 jest prawdziwe czyli drzewo wisi na gałęzi skierowanej w lewo i zaczepionej w P0 ( która jednak nie jest częścią drzewa) Skoro zdanie P0 jest prawdziwe spośród 2 następnych ścieżek po ) 1 jedna musi być w prawo. Stosowna ścieżka istnieje, a rysunek trzeba sobie zrobić samemu. Bardzo to przypomina drzewo Sterna Brocota które także jest zawieszone na 2 gałęziach które jednak nie reprezentują liczb, a są jedynie generatorami grupy wolnej rozpinającej drzewo…

Podajmy kolejny, bardziej złożony koncepcyjnie przykład. Weźmy nieskończony zbiór zdań (Z) = {Z0,Z1,Z2,…} o następującej konstrukcji:

 

(Z0) ~Z1

(Z1) ~Z2 ^ ~Z3

(Z2) ~Z3 ^ ~Z4 ^ ~Z5

(Z3) ~Z4 ^ ~Z5 ^ ~Z6 ^ ~Z7

.

.

itd

 

    Zdanie Z(n) zawiera n+1 wyrazów każdy będący zaprzeczeniem zdań o kolejnych numerach rozpoczynających się od n+1. Posługując się podobnym rozumowaniem jak w wypadku zdań (P) uzyskamy stosowne, niesprzeczne wartościowanie zdań (Z). W szczególności jeśli zdanie Z0 jest prawdziwe, to co najmniej jedno ze zdań Z2 i Z3 musi być prawdziwe. Może być to zdanie Z2 ale wówczas zdanie Z3 musi być fałszywe. czyli ciąg może zaczynać się tak: Z0-Z1-Z2-Z3 = 1010 itp. Jeśli założymy że zdanie Z3 jest prawdziwe, Zdanie Z2 ma dowolne wartościowanie. Jak widać system Z jest mniej sztywny niż system P który dla założenia wartości logicznej zdania P0 określał jednoznacznie wartości logiczne pozostałych zdań.

    Jesteśmy gotowi do rozważenia paradoksu Yablo. Temat ten ma bogatą literaturę. Paradoks ogłoszono w 1993 roku, w pracy “Paradox without Self-Reference”. Większość dyskusji wokół tego tematu dotyczy oświadczenia autora że paradoks nie zawiera zdań samozwrotnych. I rzeczywiście trudno się ich w zbiorze zdań (Y) dopatrzyć. Pojawiają się jednak analizy które starają się zapisać cały ów zbiór jako jedno zdanie z dodatkowym kwantyfikatorem po numerze zdania. Oczywiście tak powstałe zdanie jest samozwrotne ale nie jest paradoksem ogłoszonym przez Yablo. Inne próby obalenia paradoksu dotyczą dowodzenia że teoria typów zbudowana na zbiorze (Y) nie jest dobrze ufundowana ( nie spełnia aksjomatu ufundowania Teorii Mnogości), co może oznaczać że teorie w których da sie zapisać paradoks Yablo ( a które tym samym mogą być niebezpiecznie bliskie sprzeczności!) nie mają typów zgodnych z aksjomatyką teorii mnogości co jest zdecydowanie patologią. Nie czuję sie na siłach komentować tych wielu prac, a w większości przypadków nawet nie rozumiem dowodu że zdania (Y) prowadzą do paradoksu. Spójrzmy na przykład do tekstu rzetelnego źródła – Bolander, Thomas, “Self-Reference”, The Stanford Encyclopedia of Philosophy (Fall 2012 Edition), Edward N. Zalta (ed.) Autor widzi sprawę tak:

“We can then derive a contradiction as follows:

First we prove that none of the sentences Si can be true. Assume to obtain a contradiction that Si is true for some i. Then it is true that “for all j>i, Sj is not true”. Thus none of the sentences Sj for j>i are true. In particular, Si+1 is not true. Si+1 is the sentence “for all j>i+1, Sj is not true”. Since this sentence is not true, there must be some k>i+1 for which Sk is true. However, this contradicts that none of the sentences Sj with j>i are true.

We have now proved that none of the sentences Si are true. Then, in particular, we have that for all j>0, Sj is not true. This is exactly what is expressed by S0, so S0 must be true. This is again a contradiction.”

    Dalej zaś następują następujące, cokolwiek zagadkowe słowa: “Yablo’s paradox demonstrates that we can have logical paradoxes without self-reference – only a certain kind of non-wellfoundedness is needed to obtain a contradiction. There are obviously structural differences between the ordinary paradoxes of self-reference and Yablo’s paradox: the ordinary paradoxes of self-reference involve a cyclic structure of reference, whereas Yablo’s paradox involve an acyclic, but non-wellfounded, structure of reference. More precisely, the referential structure in self-referential paradoxes such as the liar is a reflexive relation on a singleton set, whereas the referential structure in Yablo’s paradox is isomorphic to the usual less-than ordering on the natural numbers, which is an irreflexive relation. Even though there is this difference, Yablo’s paradox still share most properties with the ordinary paradoxes of self-reference. When solving paradoxes we might thus choose to consider them all under one, and refer to them as paradoxes of non-wellfoundedness. In the following we will however stick to the term paradoxes of self-reference, even though most of what we say will apply to Yablo’s paradox and related paradoxes of non-wellfoundedness as well.”

    Jak zatem rozumieć sprzeczność w paradoksie Yablo? Może wcale nie mamy tu paradoksu skoro to jest złe ufundowanie? Co znaczy to bliżej nieokreślone pojęcie? Najwyraźniej autor hasła w zacytowanej encyklopedii ma problemy z określeniem co ono znaczy, choć oczywiście jakaś analogia z aksjomatem ufundowania wydaje się tu narzucać. Wydaje się że nie jest to przypadek, a w poprzednim, niezbyt udanym wpisie, pojawił się przykład eksploatujący układ teorii które być może, wymagają do konstrukcji, obiektów źle ufundowanych w sensie teorii mnogości ( czy tak jest pozostaje dla mnie otwartym problemem) .

    Moim zdaniem należy patrzeć na tą kwestię w następujący sposób.

    Początkowe zdania (Y) stwierdzają pewną treść o pozostałych zdaniach systemu. W szczególności zdanie Y0, stwierdza że każde zdanie w zbiorze zdań (Y1) = {Y1,Y2,…} jest fałszywe. Co mówi zdanie Y1? Zdanie Y1 stwierdza, że każde zdanie w zbiorze (Y2) = {Y2,Y3…} jest fałszywe. Wynika z tego, że oba te zdania stwierdzają, że zdania zbioru będącego częścią wspólną zbiorów (Y0) i (Y1) są fałszywe. Jednak jednocześnie zdanie Y0 stwierdza także że zdanie Y1 jest fałszywe. Innymi słowy nie mamy tu do czynienia z samozwrotnością, jak błędnie moim zdaniem twierdzą rozmaici autorzy, ale wprost z dwoma ( nieskończoną ilością) zdań zwyczajnie sprzecznych. Aby zobaczyć to jaśniej, zapiszmy nasze zdania w następującej postaci:

Y0= ~Y1 ^ ~(U)
Y1= ~(U)

    Gdzie przez (U) rozumiemy pewien zbiór zdań ( dokładnie {Y2,Y3,Y4,…} ) zaś ~(U) należy rozumieć jako koniunkcję zaprzeczenia wszystkich zdań składowych (U). Wynika z tego że Y0 i Y1 nie moga być jednocześnie prawdziwe lub jednocześnie fałszywe. Oczywiście dla skończonej ilości zdań ( gdyby w przykładzie powyżej rozumieć (U) jako zdanie a nie zbiór zdań), stosowne wartościowanie istnieje – możemy przyjąć że zdania Y0 i Y1 są fałszywe, zaś “zdanie” (U) prawdziwe i jest to możliwe dla dowolnej skończonej ilości zdań o konstrukcji podobnej jak zdania powyżej. Jednak (U) nie jest tu zdaniem a całym zbiorem zdań. Widać wyraźnie że paradoks nie pojawia się tu na skutek samozwrotności ale w wyniku pewnych własności nieskończonego zbioru zdań.

    I w tym miejscu pojawia się pewien pomysł. Jak wiadomo w arytmetyce wyrażenia postaci 1/0 nie mają określonego sensu ( ba! są jawnie niepoprawne lub niezdefiniowane). Niemniej istnieje możliwość określenia ich wartości w pewnego rodzaju warunkach, i właściwe używanie symbolu nieskończoności wraz z definicjami uzupełniającymi reguły arytmetyki mnożenia i dodawania, pozwala pewne rachunki prowadzić w sposób konsystentny. Nasze postępowanie mogłoby zatem polegać tu na zdefiniowaniu logicznych praw operowania nieskończonym zbiorem zdań (U) w rozumowaniach jak powyżej i na wykazaniu że tak zdefiniowany element pozwala na zapisanie paradoksu Yablo.

    Załóżmy zatem że obowiązują następujące zasady:

1. nie wolno nam orzekać o prawdziwości zdania (U) – prawdziwość tego zdania jest tematem tabu;
2. wszelkie rachunki logiczne przeprowadzamy w sposób klasyczny ale z końcowego wyniku, na każdym kroku wymazujemy (U)
3. jeśli musimy w trakcie rozumowania rozpatrywać alternatywę przypadków, musimy dokonać założeń na temat zdań o największej nieokreśloności w stosunku do (U) czyli na przykład w wypadku dwu zdań t=~(U) oraz s = ~x ^ ~ (U) jeśli rozpatrujemy alternatywę t v s musimy przyjąć przypadek że s jest prawdziwe ( bo podobne założenie co do prawdziwości/fałszu t przenosiłoby się bezpośrednio na zdanie (U), w wypadku zdania s pozostaje/pozostają inne mozliwści )

    Punkt 3 stanie się jaśniejszy po rozpatrzeniu poniższych rachunków.

    Postępując w taki sposób rozpatrzmy zespół zdań:
Y0= ~Y1 ^ ~Y2 ^ ~ Y3 ^ ~(U)
Y1= ~Y2 ^ ~ Y3 ^ ~(U)
Y2= ~ Y3 ^ ~(U)
Y3 = ~(U)

    Załóżmy że zdanie Y0 jest prawdziwe, dostaniemy w ten sposób następujące rozumowanie ( każda następna linia wynika z poprzedniej):
Y0 =>
~Y1 ^ ~Y2 ^ ~ Y3 ^ ~(U) => ( wymażemy (U) – patrz reguła 2 )
~Y1 ^ ~Y2 ^ ~ Y3 => ( skoro koniunkcja to możemy wziąć jako zdanie prawdziwe ~Y1)
~Y1 =>
~( ~Y2 ^ ~ Y3 ^ ~(U) ) => (zastosujemy prawa de Morgana dla koniunkcji)
Y2 v Y3 v (U) => ( dalej wymażemy (U) – patrz reguła 2 )
Y2 v Y3 =>
sprzeczność z założeniem że Y0 jest prawdziwe.

    Czyli Y0 nie możę być prawdziwe.

    Odwrotnie załóżmy że Y0 jest fałszywe.
~Y0 =>
~(~Y1 ^ ~Y2 ^ ~ Y3 ^ ~(U)) => (stosujemy prawo de Morgana dla koniunkcji)
Y1 v Y2 v Y3 v (U) => ( wymażemy (U) – patrz reguła 2 )
Y1 v Y2 v Y3 => ( tu użyjemy reguły 3 i założymy że z tej alternatywy wynika że prawdziwe musi koniecznie być zdanie Y1 – bo w najmniej sztywny sposób określa warunki dla prawdziwości zdania (U)) ***
Y1 =>
~Y2 ^ ~ Y3 ^ ~(U) => ( dalej wymażemy (U) – patrz reguła 2 )
~Y2 ^ ~ Y3 =>
~Y2 =>
~ (~ Y3 ^ ~(U) ) => (prawa de Morgana)
Y3 v (U) => ( dalej wymażemy (U) – patrz reguła 2 )
Y3 =>
sprzeczność z linią stwierdzającą prawdziwość Y1 ( która wynikała z fałszywości Y0).

    Czyli Y0 nie może być fałszywe.

    Widać że rozumowanie powyższe od miejsca oznaczonego *** działa dokładnie tak jak pierwsza część dowodu ( dotycząca przypadku kiedy Y0 jest prawdziwe). Oczywiście rozumowanie to jest niepoprawne logicznie. nie mam także żadnej pewności że wprowadzenie reguł 1,2,3 nie prowadzi do jawnej sprzeczności w systemie “zwykła logika” + 1,2,3. Zapewne prowadzi. Celem przedstawionego rachunku nie było “udowodnienie” że paradoks Yablo jest paradoksem, bo to łatwo jest dowieść bez “sztucznych reguł”. Moim celem było zwrócenie uwagi na to, że realizacja tego paradoksu nie wymaga samozwrotności a jedyne istnienia “elementu tabu” który oczywiści imituje działanie “nieskończonego zbioru zdań” co samo w sobie pozwala na zapisanie paradoksu. Oczywiście najwięcej kontrowersji budzi skomplikowana reguła 3 która pozwala nam w dowodzie związanym z założeniem ~Y0 odtworzyć postępowanie dowodowe z części z opcją Y0. Jest to cena jaką płacimy za skończoną ilość wypisanych wyrażeń i rezygnację z użycia kwantyfikatorów. Jeśli czyta to wypracowanie zawodowy logik lub matematyk, uprzejmie proszę o zastanowienie się nad eksploatowaną tu analogią miedzy postulatami 1,2,3, a powodem wprowadzenia wartości dla symboli nieoznaczonych jak 1/0. W szczególności sensem wprowadzania 1,2,3 w moim wypadku miałoby być ich użycie w odniesieniu do predykatu prawdy Tarskiego, zwłaszcza w kontekście hierarchii języków-metajęzyków. W tym sensie 1,2,3 wypisane powyżej nalezy traktować jako hipotezę roboczą, nie twierdzę że sa one szczególnie szczęśliwie dobrane. To propozycja. Proszę podać własną!

    Czy przedstawiony powyżej rachunek jest użyteczny? Być może. Zrezygnujmy z założenia że (U) to zbiór zdań. W opisanym powyżej “dowodzie” nie używamy nigdzie tego założenia ( poza milczącym zakładaniem że wyrażenie postaci (x ^ (U)), (x v (U) ), ~(U) itp. mają sens, oraz że prawa logiki jak np. prawo de Morgana obowiązuje dla wyrażeń utworzonych z użyciem (U). W istocie (U) może być jakimkolwiek obiektem logicznym którego struktura wewnętrzna jest nam całkowicie obojętna, może być na przykład predykatem ( funkcją zdaniową) itp.

    Gdyby przyjąć że przedstawione tu podejście ma inne niż czysto heurystyczny sens, na przykład, że zasady 1,2,3 nie prowadzą do sprzeczności jeśli dodać je do klasycznego rachunku predykatów, moglibyśmy uzyskać dwie korzyści, jedną spodziewaną i pożądaną, druga zaskakująca ale niepożądaną.

    Korzyść pożądana to oczywiście wyjaśnienie pochodzenia paradoksu Yablo. Paradoks ten w myśl mojego pomysłu powstaje nie w wyniku samozwrotności ( co jest bardzo dyskusyjne, zapisanie wszystkich zdań paradoksu Yablo w jakiejś (meta)teorii jako predykat zależny od rozmaitych zmiennych, nie jest tym samym co możliwość wypisania wszystkich tych zdań jedno po drugim), ale w wyniku zwykłej sprzeczności, takiej samej jak w wypadku dwu zdań: “śnieg jest czarny”, “śnieg jest biały”. Powtórzmy – zdania Y0 i Y1 paradoksu Yablo stwierdzają coś o innych obiektach teorii – zdanie Y0 o Y1 i (U) zaś Y1 o (U) i treść tego stwierdzenia przeczą sobie wzajemnie. Wobec własności obiektu (U) ustalenie prawdziwości ich układu Y0, Y1… wymaga ustalenia prawdziwości na pewnym skończonym zbiorze zdań co jest niemożliwe bo zdania te przeczą sobie wzajemnie.

    “Korzyść niepożądana” dotyczy przykładu z poprzedniego, nieudanego wpisu na blogu. Niech Y0 będzie zdaniem pewnej teorii T, zbudowanym z użyciem predykatu prawdy dla podteorii T1 owej teorii. Wówczas obiekt (U) może być predykatem prawdy jaki teoria T’ buduje dla swoich podteorii T2 itd. W szczególności obiekt taki nie ma określonej prawdziwości ale chcąc łatać pod(pod…)teorie budowane w T możemy stosując zasady 1,2,3 ratować nasza koncepcję prawdy przed sprzecznością. Obiekt (U) może mieć postać ( w teorii T) “Teoria T1 mówi nieprawdę kiedy używa swojego predykatu prawdy w stosunku do predykatu prawdy teorii T2 kiedy ten orzeka o predykacie prawdy T3 kiedy ten orzeka o predykacie prawdy T4….” Widać wyraźnie że jest to bardzo źle zdefiniowany obiekt.

    Oczywiście z bzdur wynikają bzdury i być może status tych wszystkich rozważań jest bzdurą. Całość powyżej jest niewątpliwie szalenie wątpliwa ;-)

    Rozważmy jednak następujący, tym razem już ostatni, przykład. Weźmy bardzo rozwlekły i ogólny język programowania – nazwijmy go dla zachowania analogii Asemblerem. Rozpatrzmy w tym języku programowania rozmaite programy, niech wszystkie one mają nazwę która jest liczbą naturalną ( np. Program nr 18 a Asemblerze nazywa sie “A18″ ) a w wyniku działania niech zwraca liczbę. Niech każdy z tych programów zawsze kończy obliczenia. Inne programy ( na przykład takie które nie kończą swoich obliczeń) nas nie interesują. Załóżmy ze dysponujemy Maszyną która uruchamia programy w Asemblerze więc możemy dla każdego z rozważanych programów poznać wynik jego działania. Co więcej Maszyna owa pozwala na porównanie wyników takich programów ( czyli sprawdzenie czy A19 =?= A20 ). Kluczowa własność w tym co piszę poniżej to właśnie owo porównywanie.

    Na bazie Asemblera zdefiniujemy język wyższego poziomu. Budowa owego języka ma wyłącznie postać makr ( a więc nietwórczych definicji). Nazwijmy ów język Basemblerem. Basembler ma swoje własne programy ( które rozwijają się oczywiście do Asemblera, to kluczowa własnośc która imituje właność językowej relacji teoria-metateoria, w tym pojecie przekłądu, a pośrednio prawdy), które mają własne nazwy, na przykład B18. Maszyna która uruchamia Asembler oczywiście potrafi uruchamiać Basembler ( wystarczy w tym celu rozkodować makra). Ale w niektórych wypadkach będzie używać maszyny Basemblerowej, która nie wie jak wyliczać wyrażenia w Asemblerze. Liczenie w Basemblerze idzie jej jednak znakomicie.

    Na bazie Basemblera, zdefiniujemy Casembler, za pomocą tych samych nietwórczych konstrukcji ( a więc znowu makra) i zbudujemy Casemblerową maszynę.

    Na bazie Casemblera, Dasembler i jego maszynę itd.

    Oczywiście powstanie w ten sposób pewna hierarchia makr i maszyn możliwa do ciągnięcia w nieskończoność. Na przykład w praktycznej realizacji makra Basemblera mogą wyliczać wyłącznie liczby parzyste – czyli postaci 2n i być nazywane za pomocą liczby n. Casembler może wyliczać wyłącznie liczby 4n i być nazywany n itp.

    Programy coś muszą liczyć. Cecha jaką chcemy wyliczyć jest całkowicie obojętna, ważne by jej wyliczanie było proste, łatwe, szybkie i przyjemne, oraz by nie ulegało żadnych wątpliwości że maszyna Asemblerowa, Basemblerowa i następne potrafią stosowne obliczenia wykonać, wraz ze stosownymi porównaniami. Nie budujemy żadnego dowodu przez diagonalizację, więc zbieżność N i XN w dalszych rozważaniach jest całkowicie nieistotna. Załóżmy ze chodziło o sprawdzenie że N = BN. Chcemy wyodrębnić wszystkie programy których wynik działania – liczba N jest taka sama jak numer programu w stosownym języku BN ( na przykład kiedy program A18 daje w wyniku 18, a program D20 daje w wyniku 20). Maszyna Asemblerowa jest w stanie sprawdzać programy w Basemblerze. Stworzono w tym celu specjalny program Asemblera, który wyliczał N, a następnie badał czy wynik programu Basemblera, BN jest jej równy. Uzyskano pewne wyniki, poprawne o tyle o ile poprawne jest wyliczanie N w Asemblerze ( można by rzec że wyniki sa zrelatywizowane do poprawności Asemblera co w istocie pozostaje poza tematem dyskusji). Sprawdzono tym sposobem wszystkie programy zbudowane w Basemblerze, Casemblerze, Dasemblerze i następnych językach. Niestety wynik wzbudzał wątpliwości. Dla kontroli chciano wykonać stosowne badania dla Casemblera. Oczywiście najprościej było stworzyć stosowny program w Basemblerze, który wyliczał N a następnie CN i sprawdzał zgodność uzyskanych liczb. Konstrukcję powtórzono dla Dasemblera i następnych języków. Z powodu nawału prac prace developerskie prowadzono jednocześnie, rozpisane one były na wiele zespołów, każdy zajmował się jednym językiem programowania i zatrudniał specjalistów z tej dziedziny. Programowano w technologii zwinnego programowania kowbojskiego i szczegóły implementacji zaginęły, a programiści zostali zwolnieni po zakończeniu testów. Do porównania wyników zatrudniono konsultantów Bardzo Drogiej Firmy Konsultingowej Arbiter Arythmeticsen Polska sp. z o.o

    Konsultanci wcale sie nie zdziwili. Wiadomo od dawna że programiści pracujący w Asemblerze nie maja zbyt dobrego zdania o specjalistach z Basemblerze. Wyniki zespołu Asemblerowego całkowicie potwierdziły ta opinie. testy zespołu Asemblerowego jasno pokazały że wszystkie porównania wyliczane w Basemblerze, także i te które dotyczyły programów Casemblerowych, Daemblerowych i następnych – były błędne! Lider zespołu Asemblerowego napisał nawet na marginesie: “ten margines jest zbyt krótki by wypisać wszystkie bugi jakie znaleźliśmy w Baseblmerze!” Arbiter Arythmeticsen znało zjawisko flame wars i nie był im obcy fakt że opinie wyrażane w takiej atmosferze bywają przejaskrawione.

    Rozpoczęto więc kolejny etap integracji wyników. Tym razem zajęto się Basemblerem. Zespół Basemblerowy przyjął jako aksjomat – czyli oczywistą prawdę – że Basembler pozwala na bezbłędne wyliczanie wartości N, o ile ktoś postępuje zgodnie ze składnią języka oczywiście. Zbudowani takim założeniem bardzo dokładnie przetestowali programy w Casemblerze, Dasemblerze i następnych językach. Wyniki nie napawały optymizmem. ‘Kim sa ci co tworzą te wszystkie “języki atrapy” zamiast używać sprawdzonych – jak Basembler – narzędzi” napisał Lider Zespołu Basemblera na marginesie raportu, który stwierdzał że każde porównanie jakiego dokonywali programiści języków wyższego rzędu było nieprawdziwe.

    Specjaliści Arythmeticsen Polska sp. z o.o. sprawdzili także kolejne raporty. Każdy stwierdzał to samo co poprzednie – zakładając poprawność konstrukcji języka programowania jakiego używali, specjaliści nie zostawiali suchej nitki na wszystkich językach wyższego poziomu stworzonych na jego bazie.

    Pomóż sporządzić konsultantom Arbiter Arythmeticsen Polska sp. z o.o końcowy raport.

    Drogi czytelniku który dotarłeś az do tego miejsca. Oto treść którą chciałbym abyś zapamiętał: istnieje możliwość że koncepcja prawdy ( zdefiniowanej jako predykat, według metody Tarskiego) ma sens wyłącznie lokalnie, to znaczy nie prowadzi do sprzeczności wyłącznie dla skończonego ciągu teorii, metateorii, metametateorii, … . chciałbym byś rozważył a może zapamiętał w tym zdaniu słowo lokalnie.

Ułamki łańcuchowe – Nonstandard matrix representation of continued fractions – cz 5

Please find below likk to Sage worksheet for “Nonstandard matrix representation of continued fractions”. It contains several definitions and computations which may be usefull if You would like to check or play stuff I described in earlier essays. It is very simple, and selfexplanatory so I will not comment it content here.

If You have account on sagenb,com server – which is free and very simple to obtain – You may use it online to play with it. It is here.

The same worksheet is avialilable in google doc service for download if You have Sage at home… If You prefer that way – it is there. ( there is no view option, You have to download it!)

Stay tuned! I will continue…

UPDATE: I publish another one Sage worksheet with summary and simple comments. If You want to know what I am play with – take it rather than worksheets above. There is also .sws in Google docs ready for download.

Drzewa ułamków – cz 2.

W 1855 zmarł Carl Friedrich Gauss. Trzy lata później w roku 1858 Moritz Abraham Stern został mianowany Ordinarius Na Uniwersytecie w Getyndze, zajmując tym samym katedrę Gaussa. Stern był pierwszym pełno-miarowym profesorem matematyki żydowskiego pochodzenia w Niemczech. W roku w którym obejmował stanowisko Gaussa Stern opisał ciekawą konstrukcję na liczbach wymiernych. Był to rodzaj listy ułamków ułożonych w pewnym porządku, tak, że dało się je narysować w postaci drzewa binarnego. Każdy wierzchołek w drzewie – rodzic, miał dwie wychodzące z niego gałęzie – dzieci. Związek pomiędzy wartościami rodziców i dzieci byl prosty ale intrygujący – napiszemy o tym niżej. Stern opisał ciekawe własności tej konstrukcji – jako zawodowy matematyk zajmował się teorią liczb zaś konstrukcja przypominała i uogólniała opisane wcześniej w 1818 roku ciągi Fareya – co zapewne było samo w sobie interesujące. Zupełnie niezależnie konstrukcję tą, z powodów praktycznych, w kilka lat później powtórzył francuski zegarmistrz Achille Brocot -było to w 1861 roku. Konstrukcja ta przeszła do historii pod nazwą drzewa Sterna-Brocota. Co takiego praktycznego zainteresowało Achille Brocota – zegarmistrza, którego ojciec także był zegarmistrzem – w uporządkowaniu ułamków w drzewo?
Problemem blisko związanym z zegarmistrzostwem jest konstrukcja przekładni zębatych. Mechanizm zegarowy musi transmitować napęd dając precyzyjną i z góry zadaną liczbę obrotów – często kilka zadanych liczb obrotów. Na przykład wskazówka godzinowa musi obracać się 2 razy podczas gdy minutowa 1440 razy na dobę. Ponieważ obie napędzane są z jednej sprężyny – trzeba skonstruować przekładnię zębatą która zapewni stosowne przełożenia – 1/720. W dawnych czasach koła zębate wykonywano ręcznie – precyzyjne wykonanie koła o dużej liczbie zębów jest nie lada wyzwaniem i bardzo czasochłonną pracą. Luksusowe produkty zegarowe – nie tylko zegary liczące czas, ale i inne służące rozrywce, wskazujące fazy księżyca i może datę Wielkanocy, różne pozytywki wymagały sporej wiedzy już na etapie projektu – należało wyliczać ilości zębów w kołach by uzyskać właściwe stosunki. Jeśli chcemy wykonać przekładnię realizującą stosunek 34/55 możemy dokonać rozkładu licznika i mianownika: 17/5* 2/11 i uzyskać szukane przełożeni używając 4-rech kół zębatych – łącząc dwie przekładnie o stosunkach jak tym iloczynie. Metoda zdaje się działać, przynajmniej dla prostych stosunków. Znanym problemem zegarmistrzowskim było zadanie postawione przez Charlesa E. Camus – chodziło o projekt zegara realizującego stosunek 720 / 525,949 . Problem z tym ułamkiem jest taki, że mianownik jest liczbą pierwszą, a więc nie damy rady go rozłożyć na czynniki. Tym samym, nawet starając się wykonać przekładnie złożoną z wielu kół nie unikniemy wykonania koła o olbrzymiej ilości zębów! Powinniśmy się zatem raczej odwołać do przybliżeń. Jak znaleźć najlepsze – takie w którym ułamki mają możliwie najmniejszą liczbę zębów ale ich stosunki dobrze przybliżają poszukiwaną wartość? Odpowiedź na to pytanie była wynikiem pracy Brocota, jego metodę można znaleźć tu: http://www.ams.org/samplings/feature-column/fcarc-stern-brocot dodajmy jedynie, że

720 / 525,949 ~ 196 / 143,175 = 2/3 * 2/25 * 7/23 * 7/83

było jednym z możliwych rozwiązań. Drzewo Sterna Brocota umożliwia systematyczne wyliczanie takich przybliżeń, co więcej gwarantuje optymalność – mogę przypuszczać, że jego implementacja to także współczesne narzędzie służące do projektowania przekładni zębatych – ciekawe lu ludzi zdaje sobie współcześnie z tego sprawę ( czy jest inżynier na sali? czy wspomniano o tym?)…

Przejdźmy zatem do opisu konstrukcji Sterna-Brocota. Klasyczna szkolna konstrukcja drzewa zakłada użycie tzw. mediantów. Dla danych ułamków A = a/b i B=c/d ich mediantem nazywamy ułamek M = (a+c)/(b+d) co przypomina nieco sposób dodawania ułamków jaki błędnie wypracowują sobie dzieci. Drzewo Sterna-Brocota to drzewo ułamków, a więc liczb wymiernych. Każda liczba wymierna daje się przedstawić jako iloraz liczb naturalnych p/q gdzie q=/= 0. Jednak drzewo o którym mówimy jest konstruowane wychodząc od dwu stosunków w postaci 0/1 i 1/0 z których jeden jak widać nie jest ułamkiem. Może dać to pretekst do rozważań na temat roli punktu w nieskończoności w tej konstrukcji i a z estetycznego punktu widzenia nieco psuje konstrukcję klasyczną. Wydaje się jednak że jest ona nadal prostsza pojęciowo, zwłaszcza gdy mowa o praktycznych zastosowaniach. Poniżej wprowadzimy znacznie ładniejszą w mojej ocenie konstrukcje algebraiczną. Ale nie uprzedzajmy faktów.

Z każdego wierzchołka drzewa spuśćmy w dól linię. Drzewo SB wisi rozpięte między dwoma stosunkami 0/1 i 1/0 i linie spuszczone z tych elementów są granicami drzewa. Każdy element drzewa leży pomiędzy dwoma liniami – i jest mediantem stosunków od których te linie wychodzą. Tak więc pierwsze dwa elementy ( które nie są uważane za części drzewa i stanowią tylko jego “techniczne zawieszenie” ) to 0/1 i 1/0. Następny -pojedynczy element – to ich mediant czyli:

(-1 – zawieszenie) – 0/1 1/0

(0-wiersz ) (0+1)/(1+0) = 1/1 = 1

Liczba 1 jest wierzchołkiem drzewa – spuszczamy z niej linię w dól – wraz z granicami – liniami opuszczonymi z 0/1 i 1/0 mamy podział “przestrzeni drzewa” dwa sektory. Po lewej stronie mamy linię wychodzącą z 0/1, po środku 1/1 a po prawej 1/0. Wyliczając medianty dostajemy kolejny rząd elementów drzewa:

(1-wiersz) (0+1)/(1+1) = 1/2 ; (1+1)/(1+0) = 2

Spuścimy kolejne linie, wyliczymy kolejne medianty:

(2-wiersz) (0+1)/(1+2) = 1/3 ; (1+1)/(2+1) = 2/3 ; (1+2)/(1+1) = 3/2 ; (2+1)/(1+0) = 3

Myślę, że konstrukcja za pomocą mediantów stanie się jaśniejsza jeśli spojrzy się na rysunek ( z wikipedii):

Powstaje w ten sposób drzewo SB o bardzo ciekawych własnościach. Po pierwsze ułamki sa w nim ułożone według pewnego porządku – ułamki o mniejszych liczbach w mianowniku są wyżej niż ułamki o większych mianownikach – drzewo jest wyposażone w porządek pionowy.. Po drugie wszystkie ułamki są nieskracalne. Trzecią ciekawą własnością jest to, że w drzewie SB każda liczba występuje w unikalny sposób – tylko raz. Czwarta własność -każda liczba ma tu swoją reprezentację. Drzewo SB jest więc to tablica wszystkich liczb wymiernych w określonym porządku.

Dokładniejsza analiza pokazuje dalsze własności: na lewo są zawsze liczby mniejsze a na prawo większe – mamy zatem porządek w wierszach a więc poziomy. Przyglądając się obrazkowi z wikipedii przedstawiającemu drzewo SB można zauważyć kolejną ciekawa własność. Przepiszmy liczniki ułamków z 3-ciego rzędu drzewa wypisanego wyżej – od lewej – dostaniemy wówczas ciąg 1,2,3,3. Przepiszmy teraz ciąg mianowników od lewej 3,3,2,1 (gdzie uznaliśmy że 3=3/1) Widzimy że jest to ten sam ciąg ale w odwrotnym kierunku! nie jest to przypadek – jest to cecha która występuje w każdym wierszu drzewa SB. Przypuszczam, że podobnego rodzaju własności można wskazać cale mnóstwo, dla nas jednak następuje tu czas aby odnieść drzewo SB do ułamków łańcuchowych.

Popatrzmy na ułamki znajdujące się w n-tym rzędzie drzewa. Przedstawię tutaj ciekawe podejście opisane przez Alexandra Bogomolny na jego fantastycznej stronie Cut-The-Knot ( sekcja o ułamkach łańcuchowych zaczyna się tu: http://www.cut-the-knot.org/blue/Euclid.shtml i przynależy do artykułów o algorytmie Euklidesa – polecam!).

Po pierwsze, skoro każdy rodzić ma tu dwoje potomków, zachowując notację w której wierzchołek drzewa, zawierający tylko jeden wyraz równy 1, ma numer 0, otrzymamy wniosek (ogólnie prawdziwy dla wszystkich drzew binarnych):

( T3 ) Jeśli piętra drzewa Sterna-Brockota liczymy od zera to na n-tym poziomie drzewa mamy 2^n liczb.

Warto zauważyć, że drzewo dzieli się na dwie gałęzie, prawa i lewą, oraz, że wyrazy po lewej są odwrotnościami tych po prawej stronie – gałęzie sa swoim lustrzanym odbiciem z inwersją. Biorąc pod uwagę opisany w poprzednim eseju fakt, iż dla ułamków łańcuchowych zachodzi zależność (wzór (10) w poprzednim wpisie) :

należy się spodziewać że i w drzewie SB znajdzie ona swoje wykorzystanie – np. możemy ograniczyć się do analizy połowy drzewa – druga połowa to lustrzane odbicie.

Zajmijmy się teraz bezpośrednim wyliczeniem ułamków łańcuchowych i ich związkiem z przedstawionym drzewem. Rozpoczniemy niewinnie od ponownego napisania wzoru na pierwszy krok w rozkładzie ułamka p/q na ułamki łańcuchowe:

(12)

Idąc za pomysłem przedstawionym na stronach Bogomolnego wprowadzimy tu nieco algebry linowej. Pomysł jest taki: niech ułamek p/q będzie reprezentowany przez wektor [p,q] i niech będzie to kolumna. Spróbujmy równanie (12) przedstawić za pomocą takich wektorów, w postaci macierzowej:

(13)

Jak na razie – fajnie. Co dalej. W następnym kroku rozkładu na ułamki powinniśmy wziąć odwrotność r_1/q czyli q/r_1 i powtórzyć nasze rachunki:

(14)

Szczęśliwie w języku macierzy nie musimy martwić się o odwrotność, po prostu zapiszemy nasze równanie za pomocą odpowiednio dobranych macierzy:

(15)

Sprytnie, prawda? Następnych kroków łatwo się domyśleć: za każdym razem dokonujemy rozkładu tej ze współrzędnych wektora która jest większa ( za pierwszym razem było to p, za drugim q). Konstrukcja – nasz algorytm – sprawia, że raz jest to współrzędna górna a raz dolna. Jak widać pojawiają się tu ciekawe macierze w postaci:

(16)

oraz:

(17)

Zdefiniowaliśmy tym samym operatory macierzowe L i R. Zauważmy, że możemy (dzięki trickowi który pozwolił nam nie dokonywać operacji odwrotności) zestawić równania (13) i (15) w jedno:

(18)

jesteśmy już bardzo niedalecy od drzewa Sterna-Brocota. W poprzednim odcinku uzasadniliśmy, że rozkład jak powyżej musi się zakończyć na pewnym, skończonym etapie dla liczb wymiernych. nastąpi to oczywiście gr\dy jedna ze współrzędnych wektora będzie zerowa. Uważny i podejrzliwy czytelnik z pewnością zechce rozpoznać w literach L i R angielskie skróty od słów Right i Left i będzie miał słuszność!

Dla otarcia się o prawdziwe obliczenia, podajmy tutaj jakiś konkretny przykład – a jego waga nie sprowadza się jedynie do rachunków. Wskaże on nam pewną cechę, która z jednej strony może być nieco rozczarowująca, ale z drugiej jest nieunikniona. nie uprzedzajmy faktów. Oto przykład:

(19)

Po pierwsze zwróćmy uwagę, że otrzymaliśmy prawidłowy rozkład ułamka 4/7 = [0,1,1,3] co zresztą można odczytać z przedostatniej równości. Proszę teraz sprawdzić, gdzie mieści się 4/7 na drzewie Sterna-Brocota – stosownie duże drzewo jest tu: http://www.cut-the-knot.org/blue/stern.gif

Jak widać, chcąc dotrzeć do liczby 4/7 z wierzchołka reprezentowanego tu przez 1/1 należy wybrać się w Lewo, potem w Prawo, a potem 2-razy w Lewo – daje to zygzak postaci LRLL . A mogło być tak ładnie! Niestety w naszym rozkładzie na ostatnim miejscu jest liczba 3 a nie 2.

Okazuje się, ze na ostatnim miejscu ułamka łańcuchowego zawsze pojawia się cyfra o 1 większa niż stosowny zapis “zygzaka” od liczby 1/1 do liczby która przechodząc zygzak osiągamy. Taka własność drzewa – ot co.

Aby jednak całość rozjaśnić, to jest zagmatwać, zapisałem jeszcze jedną równość w równaniu (19). Teraz mamy poprawną ścieżkę, oraz jeden dodatkowy krok w lewo jeśli startujemy od “absolutnego zakotwiczenia drzewa” w postaci “ułamka “1/0″. Popatrzmy może na inny przykład:

(20)

I rzeczywiście, co nie powinno dziwić 2/3 = [0,1,2] ale tym razem mamy dodatkowy ruch w zygzaku ( dla 2/3 zygzak ma kształt LR) tym razem w prawo ale od 0/1. Najwyraźniej jakaś siła nie chce nam pozwolić operować na “gołych okropieństwach w postaci 1/0 i 0/1″ i wstawia stosowne R lub L w ostatnie miejsce – łamiąc miłą dla oka symetrię i cenzorując horrendum wyrażeń postaci 1/0.. Co ciekawe i oczywiste R[0,1] =L[1,0] = [1,1] = 1… Rozkład jest poprawny – a nieoczekiwane pojawienie się liczby o jeden większej nie jest przypadkiem – można się tu dopatrywać jakiejś ingerencji wielkiego cenzora, albo metafizyki, a może po prostu rzeczy są nieco złośliwe. Drzewo pamięta jak jest zawieszone ale uwzględnia to w niemiłym dla nas miejscu. Ot, taka własność.

Czas na podsumowanie naszych wyprowadzeń. Niech ciąg liter R i L reprezentuje pewną ścieżkę w drzewie SB – L oznacza wybór lewej gałęzi, R prawej oraz jeśli w takim ciągu występuje po sobie kilka jednakowych liter, np. p liter R to taki fragment ciągu zapisujemy jako ( podobnie dla liter L następujących po sobie). Rozpatrujemy tylko ciągi zaczynające się od litery R , z tym że dopuszczamy możliwość że występuje ona “0″ razy. Niech CF oznacza funkcję która dla zadanego ciągu R i L zwraca ułamek łańcuchowy leżący w stosownym miejscu drzewa Sterna-Brocota. Możemy zapisać wzór na CF:

( 21 )

gdzie oznacza R lub L razy po sobie, zaś może być równe 0 lub nie. Czytelnik podobne wyprowadzenie może znaleźć u Bogomolnego, tam jednak użyte sa mnożenia macierzowe od lewej strony i wektory jako wiersze. Proszę pamiętać o tej różnicy w notacji porównując rachunki. Należy dla porządku także nadmienić, ze zapis procedury rozkładu ułamków łańcuchowych w postaci macierzy jest pochodną macierzowej postaci algorytmu Euklidesa – czy uczą tego na informatyce? Jak ktoś dociekliwy – proszę samemu spróbować zapisać algorytm na gcd(a,b) w postaci macierzowej – podobnie jak powyżej.

Skoro w ciągu liter RLRRLL…. zawarta jest informacja o miejscu ułamka łańcuchowego w drzewie SB, a zarazem o jego czynnikach, uzyskujemy w naturalny sposób ciekawy wniosek. Aby dojść do dowolnej liczby w 3-cim rzędzie musimy wykonać 3 ruchy licząc od 0 (powiedzmy RLL dla liczby 4/3 = CF(RLL) = [1,3] ) . Stosownie w n-tym rzędzie znajdują się liczby reprezentowane przez ciągi n-literowe. Prawdziwe jest zatem następujące twierdzenie:

( T4 ) Niech ułamkiem łańcuchowym pojawiającym się w n-tym rzędzie drzewa Sterna-Brocota. Wówczas:

Rozkład liczby na sumę czynników, kiedy bierzemy pod uwagę kolejność składników nosi nazwę kompozycji Twierdzenie T4 można zatem wypowiedzieć inaczej:

Na n-tym piętrze drzewa SB mamy wszystkie takie ułamki łańcuchowe że ich czynniki są kompozycjami liczby n przy czym należy pamiętać, że dopuszczamy możliwość iż zero może występować tylko na pierwszym miejscu.

Jako proste ćwiczenie kombinatoryczne proponuję dowieść że wynik ten jest zgodny z T3 w którym napisaliśmy, ze na n-tym wierszu drzewa Sb jest 2^n liczb ( zakładając, że wiersze liczymy od zera). Podpowiem że wystarczy zmodyfikować rozumowanie opisane w artykule o kompozycjach z wikipedii aby uwzględnić występowanie liczby 0 oraz fakt, że dla ułamków łańcuchowych zachodzi zależność ( należy konsekwentnie wybrać tylko jedną reprezentację ułamków, np. zawierająca zawsze 1-dynkę na końcu).

Uznałem że w tym miejscu zrobimy przerwę. Miałem napisać o funkcji ?(x) ale to chyba byłoby za wiele na raz. Jak zwykle proszę o uwagi i ewentualne poprawki co do rachunków.

W kolejnych odcinkach jeśli autor poradzi sobie z rachunkami (co mu na razie nie idzie) powiemy coś o pasjonującej funkcji ?(x) Minkowskiego oraz o drzewie Calkina–Wilfa – co będzie niejako rozważaniami na boku tego co chciałbym opisać, ale pozwoli zadać ciekawe, w opinii autora, 2 pytania. Głównym celem cyklu jest jednak przedstawienie nieco innego podejścia do tego co opisano tutaj, w tym wpisie. I temu poświęcę następny wpis.