Jed­ną z istot­nych wła­sno­ści zbio­rów nie­skoń­czo­nych jest moż­li­wość ich upo­rząd­ko­wa­nia, czy­li ponu­me­ro­wa­nia lub usta­wie­nia w ciąg. Mate­ma­ty­cy lubią nazy­wać zbio­ry o tej wła­sno­ści zbio­ra­mi prze­li­czal­ny­mi i zaska­ki­wać mło­dych adep­tów mate­ma­ty­ki infor­ma­cją, że wszyst­kie zbio­ry prze­li­czal­ne mają dokład­nie tyle samo ele­men­tów co zbiór liczb natu­ral­nych, ale fakt szo­ku­ją­cej rów­no­licz­no­ści nie będzie istot­ny w niniej­szym tekście.

Zauważ­my, że licz­by natu­ral­ne moż­na – nomen omen – „natu­ral­nie” usta­wić w ciąg:

\[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \ldots \]

Podob­nie może­my usta­wić w ciąg licz­by parzy­ste oraz licz­by pierwsze:

\[ 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, \ldots \]

\[ 2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots \]

Przy odro­bi­nie fine­zji może­my nawet usta­wić w ciąg wszyst­kie licz­by całkowite:

\[ 0, 1, ‑1, 2, ‑2, 3, ‑3, 4, ‑4, 5, \ldots \]

A co ze zbio­rem liczb wymier­nych? Z pozo­ru sytu­acja się kom­pli­ku­je – prze­cież mię­dzy dowol­ny­mi dwie­ma licz­ba­mi wymier­ny­mi znaj­du­je się nie­skoń­cze­nie wie­le innych liczb wymier­nych1. Jak zatem może­my roz­sąd­nie ponu­me­ro­wać wszyst­kie licz­by wymierne?

Zauważ­my jed­nak, że wystar­czy wska­zać spo­sób upo­rząd­ko­wa­nia liczb wymier­nych dodat­nich, ponie­waż wszyst­kie licz­by wymier­ne moż­na będzie wów­czas usta­wić w nie­skoń­czo­ny ciąg ana­lo­gicz­nie do przed­sta­wio­ne­go wcze­śniej porząd­ku dla liczb całkowitych.

Naj­po­pu­lar­niej­szą meto­dą usta­wia­nia dodat­nich liczb wymier­nych w ciąg jest zasto­so­wa­nie nastę­pu­ją­ce­go porządku:

Naj­pierw usta­wia­my licz­by o mniej­szych sumach licz­ni­ka i mia­now­ni­ka, a jeże­li sumy są takie same, to w pierw­szej kolej­no­ści usta­wia­my licz­by o mniej­szym liczniku.

Zatem „począt­ko­we” dodat­nie licz­by wymier­ne będą usta­wio­ne następująco:

\( \underset{2}{\overset{\frac{1}{1},}{–}}{\:}\ \underset{3}{\overset{\frac{1}{2},\ \frac{2}{1},}{—}}{\:}\ \underset{4}{\overset{\frac{1}{3},\ ( \frac{2}{2} ),\ \frac{3}{1},}{——}}{\:}\ \underset{5}{\overset{\frac{1}{4},\ \frac{2}{3},\ \frac{3}{2},\ \frac{4}{1},}{———}}{\:}\ \underset{6}{\overset{\frac{1}{5},\ ( \frac{2}{4} ),\ ( \frac{3}{3} ),\ ( \frac{4}{2} ),\ \frac{5}{1},}{—————}}{\:}\ \underset{7}{\overset{\frac{1}{6},\ \frac{2}{5},\ \frac{3}{4},\ \frac{4}{3},\ \frac{5}{2},\ \frac{6}{1},}{————–}}{\:}\ \underset{8}{\overset{\frac{1}{7},\ ( \frac{2}{6} ),\ \frac{3}{5},\ ( \frac{4}{4} ),\ \frac{5}{3},\ ( \frac{6}{2} ),\ \frac{7}{1}, }{———————}}{\:}\ \underset{\:}{\overset{\frac{1}{8},{\:}\ldots }{—}}{\:}\ \)

W powyż­szym usta­wie­niu prę­dzej czy póź­niej poja­wi się każ­da licz­ba wymier­na: dla dowol­nej licz­by wymier­nej moż­na obli­czyć sumę jej licz­ni­ka i mia­now­ni­ka i dzię­ki tej sumie moż­na ją zlo­ka­li­zo­wać w tym cią­gu2. Wadą powyż­sze­go roz­wią­za­nia jest jed­nak to, że każ­da licz­ba wymier­na wystę­pu­je w cią­gu wie­lo­krot­nie3 – powtór­ki zosta­ły zapi­sa­ne mię­dzy nawia­sa­mi. Przy­kła­do­wo, zauważ­my, że licz­bę 1 widzi­my w powyż­szym cią­gu na czte­rech pozy­cjach (któ­rych?). Gdy­by­śmy kon­ty­nu­owa­li wypi­sy­wa­nie kolej­nych ele­men­tów tego cią­gu, co jakiś czas natra­fi­li­by­śmy na nią ponow­nie. Aby unik­nąć tej nie­jed­no­znacz­no­ści, wystar­czy zasto­so­wać pro­sty trik:

Usta­wia­my licz­by wymier­ne zgod­nie z powyż­szą pro­ce­du­rą, ale gdy tra­fi­my na licz­bę któ­ra już wystą­pi­ła w cią­gu, to ją pomijamy.

Tym spo­so­bem otrzy­mu­je­my nastę­pu­ją­cy ciąg liczb wymier­nych zapi­sa­nych w posta­ci ułam­ków nieskracalnych:

\( \frac{1}{1},\ \frac{1}{2},\ \frac{2}{1},\ \frac{1}{3},\ \frac{3}{1},\ \frac{1}{4},\ \frac{2}{3},\ \frac{3}{2},\ \frac{4}{1},\ \frac{1}{5},\ \frac{5}{1},\ \frac{1}{6},\ \frac{2}{5},\ \frac{3}{4},\ \frac{4}{3},\ \frac{5}{2},\frac{6}{1},\ \frac{1}{7},\ \frac{3}{5},\ \frac{5}{3},\ \frac{7}{1},\ \frac{1}{8},\ \frac{2}{7},\ \frac{4}{5},\ \frac{5}{4},\ \frac{7}{2},\ \frac{8}{1},\ \frac{1}{9},\ \ldots\ \)

Licz­ba 1 wystę­pu­je w nowym cią­gu tyl­ko na pierw­szej pozy­cji4.

Powyż­sza meto­da pozwa­la upo­rząd­ko­wać dodat­nie licz­by wymier­ne, ale wyma­ga stwo­rze­nia cią­gu pomoc­ni­cze­go i wyko­na­nia w nim nie­skoń­czo­nej licz­by wykre­śleń. Czy ist­nie­je pro­ce­du­ra, któ­ra pozwa­la od razu skon­stru­ować ciąg ułam­ków nie­skra­cal­nych, bez koniecz­no­ści usu­wa­nia powtó­rzeń? Oka­zu­je się, że tak – jed­na z pro­ce­dur reali­zu­ją­cych to zada­nie jest ści­śle zwią­za­na ze spo­so­bem two­rze­nia tzw. cią­gu Sterna-Brocota.

Przyj­mij­my, że potom­ka­mi licz­by wymier­nej \( \frac{a}{b} \) są licz­by \( \frac{a}{a+b} \) oraz \( \frac{a+b}{b} \) – licz­bę \( \frac{a}{b} \) nazy­wa­my rodzi­cem swo­ich potom­ków.
Może­my tę zależ­ność przed­sta­wić graficznie:

W ten spo­sób, zaczy­na­jąc od licz­by \( \frac{1}{1} {,}\) może­my skon­stru­ować drze­wo5 binar­ne, któ­re­go kil­ka począt­ko­wych pozio­mów moż­na przed­sta­wić następująco:

Prze­pi­su­jąc powyż­sze ułam­ki wier­sza­mi, zgod­nie z kolej­ny­mi poko­le­nia­mi potom­ków licz­by 1, w kolej­no­ści od lewej do pra­wej, otrzy­mu­je­my ciąg:

\( \frac{1}{1},\ \frac{1}{2},\ \frac{2}{1},\ \frac{1}{3},\ \frac{3}{2},\ \frac{2}{3},\ \frac{3}{1},\ \frac{1}{4},\ \frac{4}{3},\ \frac{3}{5},\ \frac{5}{2},\ \frac{2}{5},\ \frac{5}{3},\ \frac{3}{4},\ \frac{4}{1},\ \frac{1}{5},\ \frac{5}{4},\ \frac{4}{7},\ \frac{7}{3},\ \frac{3}{8},\ \frac{8}{5},\ \frac{5}{7},\ \frac{7}{2},\ \frac{2}{7},\ \frac{7}{5},\ \frac{5}{8},\ \frac{8}{3},\ \frac{3}{7},\ \frac{7}{4},\ \frac{4}{5},\ \frac{5}{1},\ \ldots\ \ \)

Powyż­szą sekwen­cję nazy­wa­my cią­giem Sterna-Brocota.

Udo­wod­ni­my, że zawie­ra on wszyst­kie dodat­nie licz­by wymier­ne oraz że każ­da taka licz­ba wystę­pu­je w nim dokład­nie raz.

Jeże­li dwie licz­by natu­ral­ne nie mają wspól­ne­go dziel­ni­ka więk­sze­go niż 1, to nazy­wa­my je względ­nie pierw­szy­mi.

Oka­zu­je się, że:

W każ­dej licz­bie w drze­wie Sterna-Brocota licz­nik i mia­now­nik są względ­nie pierwsze.

Powyż­sze zda­nie jest oczy­wi­ście praw­dzi­we dla począt­ko­we­go ele­men­tu drze­wa – licz­by \( \frac{1}{1} \) . Załóż­my nie wprost, że \( \frac{p}{q} \) jest naj­wy­żej poło­żo­ną licz­bą w drze­wie, dla któ­rej p i q nie są względ­nie pierw­sze. Zauważ­my, że \( \frac{p}{q} \) jest potom­kiem licz­by \( \frac{p}{q‑p} \) lub licz­by \( \frac{p‑q}{q}{.} \) Jed­nak sko­ro p i q nie są względ­nie pierw­sze, ozna­cza to, że w każ­dym z tych dwóch przy­pad­ków rodzic rów­nież two­rzy parę liczb, któ­re nie są względ­nie pierw­sze. Pro­wa­dzi to do sprzecz­no­ści z zało­że­niem, że \( \frac{p}{q} \) jest znaj­du­ją­cą się naj­wy­żej w drze­wie licz­bą o tej własności.

W bar­dzo podob­ny spo­sób poka­że­my teraz, że

każ­da dodat­nia licz­ba wymier­na znaj­du­je się w drze­wie Sterna-Brocota.

Ponow­nie zauważ­my, że licz­ba 1 nale­ży do drze­wa. Załóż­my nie wprost, że zbiór U dodat­nich liczb wymier­nych nie­wy­stę­pu­ją­cych w drze­wie Sterna-Brocota jest nie­pu­sty. Wśród wszyst­kich ele­men­tów zbio­ru U, któ­re mają naj­mniej­szy mia­now­nik (rów­ny q), niech \( \frac{p}{q} \) będzie tym, któ­ry ma naj­mniej­szy licz­nik. Z fak­tu, że \( \frac{p}{q} \) nale­ży do zbio­ru U wyni­ka, że rodzic tego ułam­ka rów­nież musi nale­żeć do U. Rodzi­cem \( \frac{p}{q} \) jest \( \frac{p}{q‑p} \) lub \( \frac{p‑q}{q}{.}\) W pierw­szym przy­pad­ku otrzy­mu­je­my licz­bę o mniej­szym mia­now­ni­ku, a w dru­gim – o mniej­szym licz­ni­ku. Obie sytu­acje pro­wa­dzą do sprzecz­no­ści z zało­że­niem, że q jest naj­mniej­szym mia­now­ni­kiem, a p – naj­mniej­szym licz­ni­kiem wśród ułam­ków o mia­now­ni­ku q.

Ana­lo­gicz­ną tech­ni­kę dowo­do­wą moż­na zasto­so­wać po raz trze­ci – aby wyka­zać, że

każ­da dodat­nia licz­ba wymier­na wystę­pu­je w drze­wie Sterna-Brocota dokład­nie raz.

Dowód nale­ży roz­po­cząć od licz­by 1, któ­ra wystę­pu­je w drze­wie dokład­nie jeden raz – gdy­by było ina­czej, musia­ła­by być potom­kiem pew­nej licz­by \( \frac{p}{q}{,} \) ale jej potom­ka­mi są \( \frac{p}{p+q} \) oraz \( \frac{p+q}{p} \) – żad­na z tych liczb nie może być rów­na 1.
Dokoń­cze­nie dowo­du pozo­sta­wi­my jako ćwi­cze­nie dla docie­kli­we­go Czytelnika.

War­to na koniec dodać, że oprócz upo­rząd­ko­wa­nia liczb wymier­nych drze­wo Sterna-Brocota ma rów­nież wie­le innych cie­ka­wych i zaska­ku­ją­cych wła­sno­ści, lecz sta­no­wią one mate­riał na zupeł­nie inną opowieść.

dr inż. Bar­tło­miej Pawlik

1 Wyka­zać ten fakt może­my nastę­pu­ją­co: Mię­dzy licz­ba­mi wymier­ny­mi a i b znaj­du­je się – cho­ciaż­by – ich śred­nia aryt­me­tycz­na \( a_1 = \frac{a+b}{2}{,} \) któ­ra oczy­wi­ście też jest licz­bą wymier­ną. Mię­dzy a1 i b jest ich śred­nia a2, mię­dzy a2 i b jest ich śred­nia a3, itd., więc osta­tecz­nie mię­dzy a i b znaj­du­je się nie­skoń­cze­nie wie­le liczb wymier­nych a1, a2, a3, ….

2 Przy­kła­do­wa licz­ba \( \frac{8}{5} \) ma sumę 13. Liczy o sumie 13 znaj­du­ją się na pozy­cjach 67–78. Licz­nik ułam­ka wska­zu­je na ósmą spo­śród tych pozy­cji, więc osta­tecz­nie licz­ba \( \frac{8}{5} \) w roz­pa­try­wa­nym cią­gu znaj­du­je się na pozy­cji 74. Wzór na loka­li­zo­wa­nie licz­by wymier­nej w tym cią­gu moż­na zna­leźć w arty­ku­le Wacła­wa Sier­piń­skie­go „Poję­cie odpo­wied­nio­ści w mate­ma­ty­ce”.

3 Nie­trud­no zauwa­żyć, że każ­da licz­ba wymier­na poja­wia się w tym cią­gu nie­skoń­cze­nie wie­le razy: ułam­ki \( \frac{8}{5}, \frac{16}{10}, \frac{24}{15}, \ldots \) repre­zen­tu­ją tę samą liczbę!

4 Licz­ba \( \frac{8}{5} \) jest na pozy­cji 53.

5 Nazy­wa się je drze­wem Calkina-Wilfa. Nie nale­ży go mylić z (bar­dzo podob­nym) drze­wem Sterna-Brocota! W nazew­nic­twie wystę­pu­je zamie­sza­nie – w tym tek­ście mówi­my o cią­gu Sterna-Brocota ze wzglę­du na jego okre­śle­nie w The On-Line Encyc­lo­pe­dia of Inte­ger Sequ­en­ces OEIS (A002487).