Výpočet Móbiových funkcí Aby bylo možno aplikovat věty o Móbiových inverzních formulích, je třeba, abychom uměli počítat Móbiovy funkce částečně uspořádaných množin P, které nás budou zajímat. Začneme jednoduchým příkladem. Buď N řetězec všech kladných celých čísel uspořádaných standardně podle velikosti. Pak pro libovolná čísla i J G N splňující / ^7 platí Skutečně, podle rekurentních formulí pro výpočet Móbiovy funkce uvedených na konci předminulého paragrafu máme /) = 1 pro všechna / G N, Mn('"3 / + 1) = — Mn(' + 1, / + 1) = —1 pro všechna / G N, Mn('"3 i + 2) = —^(i + 1, / + 2) — ^(i + 2, / + 2) = 1 — 1 = 0 pro všechna / G N, a dále, předpokládáme-li s použitím indukce, že už víme, že MnO? i + 2) = / + 3) = • • • = i + k) = 0 pro všechna / G N a pro nějaké k G N splňující k > 1, dostaneme odtud Mn(/,í) = < -1 0 jestliže / = 7, jestliže j — i = 1, jestliže j — i > 1. jL4N(; +1, / + k +1) - //N(; + 2, / + /c +1) //n(7 + 3, / + /c + 1)-----Mn(/' + /c - 1, / + /c + 1) jL4N(/ + /C, / + k + 1) - fJLN(Í + /c + 1, / + k + 1) 0+0+0h-----1-0 + 1-1 = 0. Takže opravdu ^(/, / + /c) = 0 pro všechna / G N a pro všechna k G N splňující k > 1. Poznamenejme už jen pro úplnost, že tento příklad by zůstal zcela beze změny i tehdy, pokud bychom místo řetězce N všech kladných celých čísel pracovali s řetězcem N U {0} všech nezáporných celých čísel. Dále budeme potřebovat následující obecnou techniku k výpočtu Móbiových funkcí některých částečně uspořádaných množin. Tvrzení. Nechť P a Q jsou lokálně konečné částečně uspořádané množiny a nechť P x Q je jejich přímý součin. Pak pro každá a,b 6) ^(y, c/) = ô((a, c), (b, c/)). (a,cK(x,yK(M) Ovšem opět podle zmíněných rekurentních formulí pro výpočet Móbiových funkcí máme pro Móbiovu funkci ijlpxQ rovnost MPx(?((x,y), (b, d)) = c), (b, d)). (a,c)^(x,y)^(b,c/) Tyto rovnosti, vzaté pro všechna (a, c), (b, d) E P x Q splňující (a, c) ^ (b, d), ovšem určují Móbiovu funkci /^PxQ jednoznačně. Hodnoty //pxg((x,y), (b, d)) tedy vyhovují těmto rovnostem. Ale podle předchozí rovnosti také hodnoty //p(x, b) //g(y, d) vyhovují týmž rovnostem. Vzhledem ke zmíněné jednoznačnosti odtud proto plyne, že pro každá (a, c), (b, d) £ P x Q splňující (a, c) ^ (b, d) máme rovnost ^pxq((<3, c), (b, c/)) = //p(a, b) //q(c, c/), což jsme měli ukázat. □ Budeme potřebovat ještě následující pozorování týkající se Móbiovy funkce částečně uspořádané množiny P, jestliže se při jejím výpočtu omezíme pouze na nějaký interval [a, b] uvnitř této uspořádané množiny P. Takový interval [a, b] je pak sám o sobě částečně uspořádanou množinou. Tvrzení. Buď P lokálně konečná částečně uspořádaná množina. Pak pro libovolné prvky a, b, c, d E P splňující a ^ c ^ d ^ b platí rovnost Hp{c,d) = M[a,b](c, d). Důkaz Toto tvrzení se dokáže indukcí vzhledem k velikosti intervalu [c, d] s využitím rekurentních formulí pro výpočet Móbiových funkcí uvedených na konci předminulého paragrafu. □ Buď nyní A libovolná neprázdná konečná množina a buď 2A množina všech podmnožin množiny A Tuto poslední množinu můžeme částečně uspořádat inkluzí. Dostáváme tak konečnou částečně uspořádanou množinu 2A. Směřujeme k tomu určit Móbiovu funkci fi2a této částečně uspořádané množiny 2A. Buď dále {0,1} dvouprvkový řetězec. Pak můžeme pořídit částečně uspořádanou množinu {0,1}A, to jest množinu všech funkcí f : A —>* {0,1} s uspořádáním podle hodnot na jednotlivých argumentech. Tato částečně uspořádaná množina {0,1}A je izomorfní předchozí částečně uspořádané množině 2A, příslušný izomorfismus přiřadí každé funkci f : A —>* {0,1} podmnožinu {a E A : f (a) = 1} množiny A. Takže Móbiova funkce částečně uspořádané množiny 2A koresponduje s Móbiovou funkcí částečně uspořádané množiny {0,1]A Vezměme libovolné dvě funkce f,g : A —>► {0,1} splňující f ^ g, což znamená, že f (a) ^ g (a) pro všechna a E A, a uvažujme interval [f,g] v částečně uspořádané množině {0,1}A. Podle prvního z předchozích dvou tvrzení je hodnota Móbiovy funkce i^[o,i}A na intervalu [f,g] rovna součinu hodnot Móbiových funkcí//{o,1} na jednotlivých intervalech [f(a),g(a)] přes všechna a E A. Podle druhého z předchozích dvou tvrzení a podle úvodního příkladu je ale hodnota Móbiovy funkce M{o,i} na intervalu [f(a),g(a)\ rovna 1, je-li f (a) = g(a), a je rovna —1, je-li f (a) < g(a). Hodnota Móbiovy funkce /i{o,i}A na intervalu [f,g] je tedy rovna mocnině (—1)^, kde k je počet všech těch prvků a E A, pro něž je f (a) < g(a). Přejděme nyní od částečně uspořádané množiny {0,1}A k částečně uspořádané množině 2A. Našim dvěma funkcím f,g : A —>* {0,1} splňujícím f ^ g budou odpovídat podmnožiny C = {a E A : f (a) = 1} a D = {a E A : g-(a) = 1} množiny A splňující CCD. Intervalu [f,g] v částečně uspořádané množině {0,1}A bude odpovídat interval [C, D] v částečně uspořádané množině 2A. Prvky aG A pro něž je f (a) < g(a), jsou právě prvky množiny D — C. Počet k všech těchto prvků je tedy roven číslu D — C . Takže podle předchozího zjištění je hodnota Móbiovy funkce ji2a na intervalu [C, D] rovna mocnině (—1) D-CI Buď dále 9T množina všech kladných celých čísel uspořádaná dělitelností. To znamená, že pro libovolná kladná celá čísla m, n považujeme m za menší než n anebo rovno n právě tehdy, když A7i|A7, to jest právě tehdy, když číslo m dělí číslo a?. Chystáme se určit Móbiovu funkci /x^t částečně uspořádané množiny 9T. To znamená, že pro libovolná kladná celá čísla m, n splňující ati|a7 chceme určit hodnotu iiyi(m,n). Nechť /?, k jsou libovolná kladná celá čísla taková, že h m a n k. Pak můžeme uvažovat interval [/?, k] v částečně uspořádané množině 9T, který v sobě obsahuje interval [ati, n]. Potom podle druhého z předchozích dvou tvrzení máme rovnost ^(m, n) = (^n, n). Takže potřebujeme určit hodnotu /i[/Jj/ř](A7i, n). Nechť k = p^p^2 • • • Pfs. kde pi, p2,..., ps jsou navzájem různá prvočísla a £i, £2,..., £s jsou kladná celá čísla. Poněvadž h\k, máme h = pf1 p^2 ... pfs pro nějaká nezáporná celá čísla i?23 • • •, $s splňující i?i ^ £i, $2 ^ ^2. ■ ■ ■ . $s ^ £s- Mějme nyní libovolná dvě kladná celá čísla m, n v intervalu [/?, k\. Pak rn = p^p^2 ... p™s pro nějaká celá Čísla K\, X2, . . . , Ks Splňující Ůi ^ H\ ^ £i, 1?2 ^ ^2 ^ ^2, ■ ■ ■ , $s ^ ^ a a? = p^p^2 • • • Pss pro nějaká celá čísla Ai, A2,..., As splňující ů\ ^ Ai ^ e\, $2 ^ A2 ^ £2, ■ ■ ■ , $s ^ ^ £s- Pak naše čísla m. n splňují m\n právě tehdy, když platí h\ ^ Ai, %2 ^ A2, .. . , >cs ^ As. Tato úvaha ukazuje, že interval [/?,/c] v částečně uspořádané množině 91 je izomorfní součinu intervalů [^2,^2], ■ ■ ■ , [^S5^s] v množině N U {0} všech nezáporných celých čísel uspořádané podle velikosti čísel. To znamená, že Móbiova funkce /J>[h,k] na intervalu [/?, k] koresponduje s Móbiovou funkcí na součinu intervalů x [$2, £2] x ••• x [$s,£s]. Takže pro naše čísla m, n splňující m \ n je hodnota j^[h,k](mi n) rovna hodnotě posledně jmenované Móbiovy funkce na intervalu [(xi, ^2, • • •, ^s), (Ai, A2,..., As)]. Podle prvního z předchozích dvou tvrzení je ovšem tato hodnota rovna součinu hodnot M^i^ijí^ij Ai)/i[l?2>e2](^2, A2) ••• M[tfs,ss](^s, As). Podle druhého z předchozích dvou tvrzení a podle úvodního příkladu ale pro každé / = 1, 2,..., s platí 1, jestliže h\ = A/, — 1, jestliže A/ — h\ = 1, 0, jestliže A/ — h\ > 1. Odtud plyne, že hledaná hodnota /^/^(m, n) je rovna 1, jestliže k\ = Ai, >ť2 = A2, ... , >cs — As, to jest jestliže m = n, hodnota ^[/^(ati, a?) je rovna (—l)ř, jestliže Ai — xi ^ 1, A2 — ^ 1. ■ ■ ■ , As — ks ^ 1, přičemž počet těch indexů / = 1, 2,..., s, pro něž je A/ — = 1, je roven ŕ, což nastane právě když podíl n/m je součinem ŕ různých prvočísel, a konečně hodnota /^[/,?^](/77, n) je rovna 0, jestliže pro některé / = 1, 2,..., s platí A/ — k\ > 1, což nastane právě když podíl n/m je dělitelný druhou mocninou nějakého celého čísla většího než 1. Shrnuto celkem, pro libovolná kladná celá čísla rn, n splňující ati|a7 je hodnota Móbiovy funkce jjl^x na intervalu [m, n] rovna fim{m. n) = < 1, (-l)ř 0, jestliže A77 = A7, jestliže n/m = qiq2 ... qt, kde <7i, <72,..., <7t jsou vzájemně různá prvočísla jestliže n/m = r2u pro nějaká kladná celá čísla r, splňující r > 1.