Matematyka dyskretna - wykład - część 3
10. Funkcja M�biusa
Definicja 10.1
Niech (P, ) będzie zbiorem uporządkowanym. Mówimy, że zbiór uporządko-
wany P jest lokalnie skończony, jeśli każdy podział [a, b] ą" P jest skończony,
a, b " P
Uwaga 10.1
Zbiór liczb rzeczywistych i zbiór liczb wymiernych nie są zbiorami lokalnie
skończonymi. Natomiast zbiór liczb naturalnych i zbiór liczb całkowitych są
zbiorami lokalnie skończonymi.
Rozważmy, zbiór
ńł �ł
�ł żł

A(P ) = f: P �P R: <" (a b) �! f(a, b) = 0
ół �ł
a,b"P
Zauważmy, że w zbiorze A(P ) można zdefiniować dodawanie funkcji i mnoże-
nie funkcji przez skalar (jako zwykłe operacje dodawania funkcji i mnożenie
funkcji przez skalar). Zdefiniujemy trzecie działanie:
Definicja 10.2
Niech f, g " A(P ). Funkcję f g: P �P R określoną wzorem

f g(a, b) = 0, gdy <"(a b) i f g(a, b) = f(a, c)g(c, b), gdy a b
c"[a,b]
nazywamy splotem Dirichleta.
Uwaga 10.2
Każdej funkcji ze zbioru A(P ) można przyporządkować macierz reprezentu-
jącą tą funkcję. Wówczas dodawaniu funkcji odpowiada dodawanie macierzy.
Mnożeniu funkcji przez skalar odpowiada mnożenie macierzy przez skalar.
Gdy zbiór P jest zbiorem skończonym to splot Dirichleta odpowiada mnoże-
niu macierzy odpowiadającym funkcjom f i g.
Definicja 10.3
Zbiór A(P ) wraz ze zdefiniowanymi w nim trzema działaniami: dodawaniem,
mnożeniem przez skalar i splotem Dirichleta nazywamy algebrą incydencji
zbioru P .
Uwaga 10.3
W definicji splotu Dirichleta od zbioru P oczekujemy, aby był lokalnie skoń-
czony, gdyż w przeciwnym wypadku występująca w definicji suma mogłaby
być nieskończona.
Twierdzenie 10.1
Funkcja �: P �P R określona wzorem

0, gdy a = b

�(a, b) =
1, gdy a = b
jest elementem neutralnym splotu Dirichleta.
Dowód:
Niech f " A(P ) i niech a b. Wtedy:

f �(a, b) = f(a, c)�(c, b) = f(a, b)
c"[a,b]
gdyż �(c, b) = 0 tylko, gdy c = b.

Dla � f dowód jest analogiczny.
Definicja 10.4
Funkcja ś: P �P R określona wzorem:

0, gdy <"(a b)
ś(a, b) =
1, gdy a b
jest funkcją charakterystyczną relacji porządku w zbiorze P .
Definicja 10.5
Funkcja � " A(P ), taka że ś � = � ś = � jest nazywana funkcją M�biusa
zbioru P .
Twierdzenie 10.2
W zbiorze A(P ) istnieje dokładnie jedna funkcja �: P � P R, taka że
ś � = � oraz � ś = �
Dowód (konstrukcja funkcji):
�(a, b) = 0, gdy <" (a b). Załóżmy, że a b. Zastosujemy indukcję wzglę-
dem |[a, b]| = n. Jeśli n = 1, to:
ś �(a, a) = �(a, a) = 1
oraz

ś �(a, a) = ś(a, a)�(a, a) = �(a, a)
c"[a,a]
A więc �(a, a) = 1. Załóżmy, że znana jest wartość funkcji � dla wszystkich
a, b " P , takich że |[a, b]| < n. Niech więc |[a, b]| = n > 1. Wtedy:
ś �(a, b) = �(a, b) = 0
oraz

ś �(a, b) = ś(a, c)�(c, b) = ś(a, a)�(a, b) + ś(a, c)�(c, b) =
c"[a,b] c"(a,b]

= �(a, b) + �(c, b), gdyż a c �! ś(a, c) = 1
c"(a,b] c"(a,b] c"(a,b]
Ostatecznie otrzymujemy (przyrównując ostatnią równość do zera), że:

�(a, b) = - �(c, b)
c"(a,b]
Ponieważ [c, b] �" [a, b] oraz |[c, b]| < |[a, b]| = n to wartość funkcji � jest
określona na podstawie założenia indukcyjnego.
Uwaga 10.4
Prawdziwe są następujące równości:

1ć% �(a, c) = �(a, b), gdy a b
c"[a,b]

2ć% �(c, b) = �(a, b), gdy a b
c"[a,b]

3ć% �(a, b) = - �(c, b)
c"(a,b]

4ć% �(a, b) = - �(a, c)
c"[a,b)
Twierdzenie 10.3
Niech (P, ) będzie zbiorem uporządkowanym liniowo. Wówczas:
ńł
�ł 1 , gdy a = b
�ł
�(a, b) = -1 , gdy |[a, b]| = 2
�ł
ół
0 , gdy |[a, b]| > 2
Twierdzenie 10.4
Niech X będzie zbiorem skończonym i niech P = P (X) będzie rodziną
wszystkich podzbiorów zbioru X. Wówczas: �(�, X) = (-1)|X|
Dowód:
Indukcja względem |X| = n. Jeśli n = 0, to X = �, a więc �(�, �) = 1 =
(-1)0. Jeśli n = 1, to X = {x} i �(�, X) = -1 = (-1)1.
Załóżmy, że wzór jest prawdziwy dla |Y | < n. Niech |X| = n. Wtedy:

n-1 n-1

n
�(�, X) = - �(�, Y ) = - �(�, Y ) = - (-1)i =
i
i=0 i=0
Y "[�,X) Y "P i(X)
n-1

n n n
= - (-1)i + (-1)n - (-1)n =
i n n
i=0

n

n n
= - (-1)i -(-1)n = -((1 - 1)n - (-1)n) = (-1)n = (-1)|X|
i n
i=0
Uwaga 10.5
Jeśli A, B " P (X) oraz A ą" B, to �(A, B) = (-1)|B|-|A|
Dowód:
Niech Y " [A, B]. Zbiorowi Y przyporządkujemy zbiór Y \ A " [�, B \ A].
A ą" Y ą" B. Odwrotnie, jeśli Z " [�, B \ A], to zbiorowi Z przyporządkuje-
my zbiór Z *"A " [A, B]. A więc przedziały [A, B] i [�, B \A] są izomorficzne,
więc zachowany jest porządek, zatem funkcja ś ma takie same wartości w obu
przedziały, więc także funkcja � ma takie same wartości w obu przedziałach.
Stąd:
�(A, B) = �(�, B \ A) = (-1)|B\A| = (-1)|B|-|A|, gdyż A ą" B
Uwaga 10.6
Rozpatrzmy zbiór uporządkowany i lokalnie skończony (N, |). Niech a, b " N.
Wtedy
ńł
�ł 1 gdy a = b
�ł
�(a, b) = (-1)s gdy a|b i a/b rozkłada się na s różnych liczb pierwszych
�ł
ół
0 w pozostałych przypadkach
Definicja 10.6
Niech (P, ) będzie zbiorem uporządkowanym, lokalnie skończonym. Mówi-
my, że funkcja F : P R jest sumowalna w dół, jeśli zbiór supp F )" (�!, x]
jest skończony dla każdego x " P , gdzie supp F = {x " P : F (x) = 0}.

Zbiór supp F nazywamy nośnikiem funkcji F .
Lemat 10.1
Jeśli F : P R jest sumowalna w dół, to funkcja G: P R zdefiniowana
wzorem:

G(x) = F (y)
y"(�!,x]
jest dobrze określona dla każdego x " P (dla każdego x suma jest skończona)
i sumowalna w dół.
Dowód:
Funkcja G jest dobrze określona bo funkcja F jest dobrze określona (co wyni-
ka z definicji funkcji F ). Należy pokazać, że G jest sumowalna w dół. Załóżmy,
że y " supp G )" (�!, x]. Zauważmy, że supp F )" (�!, x] = {y1, . . . , yn}, bo
zbiór ten jest skończony, G(y) = 0, bo y " supp G oraz y x. Więc


0 = G(y) = F (z) �! F (z) = 0

z"(�!,y] z"(�!,y]
z " (�!, y] ą" (�!, x] = {y1, . . . , yn}
Niech więc z = yi dla pewnego i " {1, . . . , n}. Mamy: yi y x. Zatem
n

y " [yi, x]
i=1
i suma ta jest zbiorem skończonym. Ostatecznie wobec dowolności wyboru y
n

y " supp G )" (�!, x] ą" [yi, x]
i=1
co pozwala wnioskować, że supp G )" (�!, x] jest zbiorem skończonym, zatem
funkcja G jest sumowalna w dół.
Twierdzenie 10.5 (twierdzenie inwersyjne M�biusa)
Niech (P, ) będzie zbiorem uporządkowanym, lokalnie skończonym, i niech
F=: P R będzie funkcją sumowalną w dół. Niech F : P R będzie funkcją
określoną następująco:

F (x) = F=(y)
y"(�!,x]
Wtedy

F=(x) = F (y)�(y, x)
y"(�!,x]
Dowód:


F (y)�(y, x) = F=(z) �(y, x) =
y"(�!,x] y"(�!,x] z"(�!,y]
Ponieważ z y x, można zmienić zakresy sumowania:

= F=(z)�(y, x) = F=(z) �(y, x) =
z"(�!,x] y"[z,x] z"(�!,x] y"[z,x]

= F=(x) + F=(z) �(y, x) = F=(x)
z"(�!,x) y"[z,x]
gdyż ostatnia suma jest na mocy uwagi 10.4 jest równa 0, gdy z = x.

Definicja 10.7
Niech (P, ) będzie zb. uporządkowanym, lokalnie skończonym. Mówimy, że
funkcja F : P R jest sumowalna w górę, jeśli zbiór supp F )" [x, ) jest
skończony dla każdego x " P .
Lemat 10.2
Jeśli F : P R jest sumowalna w górę, to funkcja G: P R, taka że:

G(x) = F (y)
y"[x,)
jest dobrze określona dla każdego x " P i sumowalna w górę.
Twierdzenie 10.6 (twierdzenie inwersyjne M�biusa II)
Niech (P, ) będzie zb. uporządkowanym, lokalnie skończonym, F=: P R
będzie funkcją sumowalną w dół oraz F : P R będzie funkcją, taką że:

F (x) = F=(y)
y"[x,)
Wtedy

F=(x) = F (y)�(x, y)
y"[x,)
11. Zasada włączania - wyłączania.
Niech X będzie dowolnym zbiorem niepustym, niech {A1, . . . , At} będzie ro-
dziną podzbiorów zbioru X i niech T = {1, . . . , t}.
Określmy funkcję �: X P (T ) wzorem: �(x) = {i " T : x " Ai}
Przyjmijmy dla każdego podzbioru S " P (T ) następujące oznaczenia:

AS = Ai oraz A(S) = {x " X: �(x) = S}
i"S
Lemat 11.1
Prawdziwe są następujące zdania:
1ć% x " AS �! S ą" �(x)
2ć% S1 = S2 �! A(S1) )" A(S2) = �


3ć% AS = A(R)
R"[S,)
Dowód: 1ć% ( �! )

x " AS = Ai �! x " Ai �! S ą" �(x) = {i " T : x " Ai}
i"S i"S
( �! ) Niech S ą" �(x) = {i " T : x " Ai}. Wtedy

x " Ai �! x " Ai = AS
i"S i"S
2ć%
Niech S1, S2 ą" T, S1 = S2. Załóżmy, że A(S1) )" A(S2) = �, więc


z " A(S1) )" A(S2) �! z " A(S1) '" z " A(S2) �!
z"X
�! z " {x " X: �(x) = S1} '" z " {x " X: �(x) = S2} �!
�! �(z) = S1 '" �(z) = S2 �! S1 = S2
i otrzymujemy sprzeczność.
3ć%
Zauważmy, że jeśli S ą" R, to AR ą" AS oraz A(R) ą" A(S). Ponadto dla
każdego R " [S, ) mamy: S ą" R. A więc

x " A(R) �! x " A(R) �! x " Ai �! x " Ai ą" Ai = AS
i"R i"R i"S
R"[S,) R"[S,)

x " AS �! x " A(R) ą" A(R)
R"[S,) R"[S,)
Implikacja wynika z następującego faktu. Niech S = {1, . . . , n}. Do przekroju
n zbiorów A1, . . . , An może należeć element x, taki że x " Ai, i " {1, . . . , n}
i x " An+1. Wtedy �(x) = {1, . . . , n + 1} = R, więc x " A(R) i S " [R, ).
Definicja 11.1
Niech X = �. Funkcję �: X (0, ") ą" R nazywamy funkcją wagową zbioru

X. Jeśli A ą" X, to

�(A) = �(x)
x"A
Ponadto �(�) = 0
Twierdzenie 11.1 (twierdzenie Sylwestera)
Niech A1, . . . , At będą podzbiorami zbioru skończonego X i �: X (0, ")
będzie funkcją wagową. Wtedy

t t

� An = (-1)n+1 � An
n=1 n=1 n"S
S"Pn(T )
Dowód:
Określmy funkcje F=, F : P (T ) R wzorami: F=(S) = �(A(S)) oraz
�ł �ł

�ł
F (S) = F=(R) = �(A(R)) = � A(R)łł = �(AS)
R"[S,) R"[S,) R"[S,)
Przedstatnia równość wynika z faktu, iż sumowanie przebiega po zbiorach
parami rozłącznych (lemat 11.1), ostatnia wprost z lematu 11.1. Ponadto

F=(S) = F (R)�(S, R) = �(AR)�(S, R)
R"[S,) R"[S,)
Załóżmy, że S = �. Zauważmy, że
t

A(�) = {x " X: �(x) = �} �! <" x " At �! A(�) = X \ Ai
t"T i=1

t t

F=(�) = �(A(�)) = � X \ Ai = �(X) - � Ai
i=1 i=1
Z drugiej strony
t

F=(�) = �(AR)�(�, R) = �(AR)�(�, R) =
n=0
R"P (T ) R"Pn(T )
t t

= (-1)n�(AR) = (-1)0�(AR) + (-1)n �(AR) =
n=0 n=1
R"Pn(T ) R"P0(T ) R"Pn(T )

t t

= �(A�) + (-1)n �(AR) = �(X) + (-1)n � An
n=1 n=1 n"R
R"Pn(T ) R"Pn(T )
gdyż A� = X. Porównując stronami obie wartości F=(�) i mnożąc je przez
-1 otrzymujemy dowodzoną równość.
Twierdzenie 11.2 (zasada włączania - wyłączania)
Niech A1, . . . , At będą podzbiorami zbioru skończonego X. Wtedy

t t



An = (-1)n+1 An


n=1 n=1 n"S
S"Pn(T )
W dowodzie należy skorzystać z twierdzenia Sylwestera z funkcją wagową
�(x) = 1 dla każdego x " X
12. Problemy mini-maksowe
Definicja 12.1
Niech (P, ) będzie skończonym zbiorem uporządkowanym. Podzbiór L �" P
nazywamy łańcuchem, jeśli L jest uporządkowany liniowo. Podzbiór A �" P
nazywamy antyłańcuchem, jeśli A jest uporządkowany antyliniowo.
Długość łańcucha L jest równa |L| - 1.
Definicja 12.2
Niech dana będzie rodzina C1, . . . , Cn podzbiorów zbioru P . Taką rodzinę
nazywamy pokryciem zbioru P , jeśli
n

P = Ci
i=1
Pokrycie nazywamy zupełnym, jeśli Ci )" Cj = �, gdy i = j

Twierdzenie 12.1 (Twierdzenie Dilwortha)
Jeśli (P, ) jest skończonym zbiorem uporządkowanym, to maksymalna licz-
ność antyłańcucha w zbiorze P jest równa minimalnej liczbie łańcuchów po-
trzebnych do pokrycia zbioru P .
Dowód:
Niech m oznacza maksymalną liczność łańcucha w zbiorze P , a n - minimal-
ną liczbą łańcuchów potrzebnych do pokrycia zbioru P .
Oczywiście m n, gdyż aby pokryć zbiór P każdy element antyłańcucha
musi należeć do innego łańcucha. Pokażemy,że n m. Indunkcja względem
k = |P |. Załóżmy, że każdy zbiór uporządkowany, który ma mniej niż k ele-
mentów spełnia twierdzenie Dilwortha.
Niech L �" P będzie łańcuchem maksymalnym. Wez
my pod uwagę zbiór P \L
(który jest uporządkowany) i rozpatrzmy dwa przypadki:
1ć%
Każdy antyłańcuch w zbiorze P \ L zawiera co najwyżej m - 1 elemen-
tów, a więc istnieje antyłańcuch zawierający dokładnie m - 1 elementów.
Do zbioru P \ L stosujemy założenie indukcyjne: istnieje rodzina łańcuchów
L1, . . . , Lm-1 pokrywająca zbiór P \ L. Stąd P = L *" L1 *" . . . *" Lm-1. Istnieje
zatem pokrycie zbioru P rodziną złożoną z m łańcuchów, czyli n m
2ć%
W zbiorze P \ L istnieje antyłańcuch A mający m elementów. Zdefiniujmy
dwa zbiory:


D = x " P : x a '" G = x " P : x a
a"A a"A
Zbiory D i G mają następujące (istotne dla dowodu twierdzenia) własności:
(a) P = D *" G
Załóżmy, że x " P . A *" {x} nie jest antyłańcuchem, gdy x " A. Wtedy x
/
jest porównywalny z jednym z elementów antyłańcucha a " A. Jeśli x a,
to x " D. Jeśli a x, to x " G. Ostatecznie x " D *" G.
(b) D )" G = A
Oczywiście A ą" D )" G. Jeśli zaś x " D )" G, to x " D i x " G. Wobec
tego istnieje a " A takie, że x a oraz istnieje b " A takie, że b x. A
więc b x a, skąd wynika, że b a. Ponieważ jednak a, b są elementami
antyłańcucha, to a = b = x.
(c) Element maksymalny łańcucha L nie należy do zbioru D
Ponieważ A �" P \ L, to A )" L = �. Niech b " L będzie elementem maksy-
malnym łańcucha L. A więc b " A. Przypuśćmy niewprost, że b " D. Wobec
/
tego istnieje a " A takie, że b a. Ale ponieważ b " A, to b < a. Wynika
/
stąd, że L *" {a} jest łańcuchem - sprzeczność z maksymalnością łańcucha L.
(d) Element minimalny łańcucha L nie należy do zbioru G
Dowód analogiczny jak w punkcie (c).
Z powyższych rozważań wynika, że zbiory D i G są niepuste, są właściwymi
podzbiorami zbioru P oraz |D| < k i |G| < k. Z założenia indukcyjnego
wynika, że istnieją pokrycia D1, . . . , Dm oraz G1, . . . , Gm zbiorów D i G.
Niech A = (a1, . . . , am). Wtedy każdy element ai należy tylko do jedne-
go z łańcuchów Di i tylko jednego z łańcuchów Gi. Zdefiniujmy łańcuchy
L1 = D1 *" G1, . . . , Lm = Dm *" Gm. Tak określona rodzina m łańcuchów jest
pokryciem zbioru P . A więc n m
Twierdzenie 12.2 (II twierdzenie Dilwortha)
Jeśli (P, ) jest skończonym zbiorem uporządkowanym, to maksymalna licz-
ność antyłańcucha w zbiorze P jest równa minimalnej liczbie rozłącznych
łańcuchów potrzebnych do pokrycia zbioru P .
Dowód:
Niech m oznacza maksymalną liczność antyłańcucha i niech L1, . . . , Lm bę-
dzie pokryciem zbioru P . Skonstruujemy nową rodzinę łańcuchów.
i m-1

S1 = L1 S2 = L2 \ L1 . . . Si+1 = Li+1 \ Lk . . . Sm = Lm \ Lk
k=0 k=0
Oczywiście każdy ze zbiorów Si jest zbiorem niepustym. Gdyby Si+1 = �, to
musiałoby być Li+1 �" (L1 *" . . . *" Li). Wobec tego łańcuch Li+1 byłby zbędny
do pokrycia zbioru P , co jest sprzeczne z wyborem liczby m.
Zatem rodzina S1, . . . , Sm łańcuchów jest rozłącznym pokryciem zbioru P .
Twierdzenie 12.3 (Twierdzenie dualne Dilwortha)
Jeśli (P, ) jest skończonym zbiorem uporządkowanym, to maksymalna licz-
ność łańcucha w zbiorze P jest równa minimalnej liczbie rozłącznych anty-
łańcuchów potrzebnych do pokrycia zbioru P .
Dowód:
Niech m oznacza maksymalną liczność łańcucha, zaś k - minimalną liczbę
antyłańcuchów potrzebnych do pokrycia zbioru P .
Utwórzmy rodzinę zbiorów Ai = {x " P : ranga(x) = i}. Zauważmy, że każ-
dy ze zbiorów Ai jest antyłańcuchem oraz Ai )" Aj = �, gdy i = j. Zbiory

A0, . . . , Am-1 tworzą m-elementowe pokrycie zbioru P .
Niech x1, . . . , xm będzie maksymalnym łańcuchem. Zauważmy, że każdy ele-
ment xi musi należeć do innego antyłańcucha, a więc tych antyłańcuchów
musi być co najmniej m. Zatem m k. Ponieważ wcześniej zbudowaliśmy
pokrycie zbioru P dokładnie m antyłańcuchami, to m = k