Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Matematika IV – 9. týden
Systémy polynomiálních rovnic (dokončení),
Booleovské algebry
Jan Slovák
Masarykova univerzita
Fakulta informatiky
15. 4. – 19. 4. 2013
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Obsah přednášky
1 Gröbnerovy báze a eliminace proměnných
2 Množinová algebra a logika
3 Posety a svazy
4 Normální tvary a morfismy
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Plán přednášky
1 Gröbnerovy báze a eliminace proměnných
2 Množinová algebra a logika
3 Posety a svazy
4 Normální tvary a morfismy
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Theorem (Dělení se zbytkem)
Nechť < je monomiální a F = (f1, . . . , fs) s-tice polynomů
v K[x1, . . . , xn]. Pak každý f ∈ K[x1, . . . , xn] lze vyjádřit jako
f = a1f1+· · ·+asfs+r kde ai , r ∈ K[x1, . . . , xn] pro i = 1, 2, . . . , s
a navíc r = 0 nebo r je lineární kombinací monomů, z nichž žádný
není dělitelný kterýmkoli z LT f1, . . . , LT fs a pokud ai fi = 0 pak
multideg f ≥ multideg ai fi pro každé i.
Polynom r nazýváme zbytkem po dělení f /F.
Věta neříká nic o jednoznačnosti výsledku. Následující algoritmus
dává jedno možné řešení. Nadále budeme výsledkem dělení se
zbytkem chápat právě tento výstup pevně zvoleného algoritmu.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
1 a1 := 0, . . . , as := 0, r := 0, p := f
2 while p = 0
1 i := 1
2 d := false
3 while i ≤ s ∧ not d
1 if LT fi |LT p
ai := ai + LT p/LT fi
p := p − (LT p/LT fi ) · fi
d := true
2 else i := i + 1
4 if not d
1 r := r + LT p
2 p := p − LT p
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
V K[x1, . . . , xn] platí pouze implikace
f = a1f1 + · · · + asfs + 0 =⇒ f ∈ f1, . . . , fs
Obrácení obecně neplatí, uvažujme f = xy2 − x, f1 = xy + 1,
f2 = y2 − 1. Potom algoritmus dělení dá
f = y(xy + 1) + 0(y2
− 1) + (−x − y)
ale přitom evidentně f = x(y2 − 1), a tedy f ∈ f1, f2 .
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Ideál I ⊆ k[x1, . . . , xn] nazýváme monomiální, existuje-li množina
A ⊆ Nn taková, že I se sestává právě ze všech polynomů tvaru
α∈A hαxα, kde hα ∈ k[x1, . . . , xn]. Potom píšeme
I = xα, α ∈ A .
Zřejmě pro monomiální ideál I platí
xβ
∈ I ⇐⇒ ∃α ∈ A: xα
|xβ
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Lemma
Nechť I ⊆ k[x1, . . . , xn] je monomiální ideál, f ∈ k[x1, . . . , xn]
polynom. Pak následující tvrzení jsou ekvivalentní
1 f ∈ I
2 Každý člen polynomu f je prvkem I.
3 Polynom f je lineární kombinací monomů z I s koeficienty z k.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Lemma
Nechť I ⊆ k[x1, . . . , xn] je monomiální ideál, f ∈ k[x1, . . . , xn]
polynom. Pak následující tvrzení jsou ekvivalentní
1 f ∈ I
2 Každý člen polynomu f je prvkem I.
3 Polynom f je lineární kombinací monomů z I s koeficienty z k.
Corollary
Dva monomiální ideály splývají právě tehdy, když obsahují stejné
monomy.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Lemma
Nechť I ⊆ k[x1, . . . , xn] je monomiální ideál, f ∈ k[x1, . . . , xn]
polynom. Pak následující tvrzení jsou ekvivalentní
1 f ∈ I
2 Každý člen polynomu f je prvkem I.
3 Polynom f je lineární kombinací monomů z I s koeficienty z k.
Corollary
Dva monomiální ideály splývají právě tehdy, když obsahují stejné
monomy.
Theorem (Dicksonovo lemma)
Každý monomiální ideál I = xα, α ∈ A ⊆ k[x1, . . . , xn] lze psát
ve tvaru I = xα1 , . . . , xαs , kde α1, . . . , αs ∈ A.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Je-li I ⊆ K[x1, . . . , xn] nenulový, označme
LT I := {axα
, ∃f ∈ I : LT f = axα
}
Zřejmě LT I je monomiální, a tedy podle Dicksonova lemmatu
lze psát LT I = LT g1, . . . , LT gs pro nějaká vhodná
g1, . . . , gs ∈ I.
Theorem (Hilbertova věta)
Každý ideál I ∈ K[x1, . . . , xn] je konečně generovaný.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Důkaz.
Pokud by I = {0}, je tvrzení triviální. Uvažujme tedy I ⊃ {0}.
Podle Dicksonova lematu a předchozí poznámky existují taková
g1, . . . , gs ∈ I, že LT I = LT g1, . . . , LT gs Zřejmě
g1, . . . , gs ⊆ I. Vezměme libovolné f ∈ I a proveďme dělení se
zbytkem s-ticí g1, . . . , gs. Dostáváme
f = a1g1 + · · · + asgs + r
kde žádný člen r není dělitelný LT g1, . . . , LT gs.
Protože r = f − a1g1 − · · · − asgs, platí r ∈ I, a tedy LT r ∈ LT I.
Zřejmě tedy LT r ∈ LT I . Připusťme, že r = 0. Protože LT I je
monomiální, musí být LT r dělitelný některým z jeho generátorů, tj.
LT g1, . . . , LT gs. To je ovšem spor s výsledkem algoritmu dělení.
Proto r = 0 a I je tedy generovaný g1, . . . , gs.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Konečná báze g1, . . . , gs ideálu I ⊆ k[x1, . . . , xn] se nazývá
Gröbnerova, jestliže platí LT I = LT g1, . . . , LT gs .
Báze použitá v důkazu Hilbertovy věty byla Gröbnerova.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Corollary
Každý ideál I ⊆ K[x1, . . . , xn] má Gröbnerovu bázi. Naopak každá
množina polynomů g1, . . . , gs ∈ I splňující
LT I = LT g1, . . . , LT gs je Gröbnerovou bází ideálu I.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Jednoduchý případ s uspořádáním <lex:
Označme generátory fi = j ai,j xj + ai,0. Uvažujme matici
A = (ai,j ), kde i = 1, . . . , s a j = 0, . . . , n a aplikujme na ni
Gausovu eliminaci. Získláme B = (bi,j ) ve schodovitém tvaru, z ní
navíc vypustíme nulové řádky. Máme novou bázi g1, . . . , gt, kde
t ≤ s.
Vzhledem k provedeným úpravám je každé fi vyjádřitelné jako
lineární kombinace g1, . . . , gt, a tedy
f1, . . . , fs = g1, . . . , gt
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
získaná g1, . . . , gt je Gröbnerova báze:
Bez újmy na obecnosti předpokládejme, že proměnné jsou značeny
tak, že LM gi = xi pro i = 1, . . . , t. Libovolný f ∈ I lze psát
f = h1f1 + · · · + hsfs = h1g1 + · · · + htgt
Chceme, aby LT f ∈ LT g1, . . . , LT gt , tj. LT f má být dělitelný
některým z x1, . . . , xt. Předpokládejme, že f je pouze
v proměnných xt+1, . . . , xn. Pak ale h1 = 0, protože x1 je vzhedem
ke schodovitosti B pouze v g1. Analogickým postupem získáme
h2 = · · · = ht = 0, a tedy f = 0.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Theorem
Nechť G = {g1, . . . , gt} je Gröbnerova báze ideálu
I ⊆ K[x1, . . . , xn] a f je polynom v K[x1, . . . , xn]. Pak existuje
právě jedno r = α aαxα ∈ K[x1, . . . , xn] s těmito vlastnostmi
1 Žádný člen r není dělitelný žádným z LT g1, . . . , LT gt, tj.
∀α∀i : LT gi | aαxα.
2 ∃g ∈ I : f = g + r
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Theorem
Nechť G = {g1, . . . , gt} je Gröbnerova báze ideálu
I ⊆ K[x1, . . . , xn] a f je polynom v K[x1, . . . , xn]. Pak existuje
právě jedno r = α aαxα ∈ K[x1, . . . , xn] s těmito vlastnostmi
1 Žádný člen r není dělitelný žádným z LT g1, . . . , LT gt, tj.
∀α∀i : LT gi | aαxα.
2 ∃g ∈ I : f = g + r
Corollary
Nechť G = {g1, . . . , gt} je Gröbnerova báze ideálu
I ⊆ K[x1, . . . , xn] a f je polynom v K[x1, . . . , xn]. Pak platí
f ∈ I ⇐⇒ zbytek po dělení f /G je nulový
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Pro α = multideg f a β = multideg g uvažme
γ := (γ1, . . . , γn) kde γi = max{αi , βi }
Monom xγ nazýváme nejmenším společným násobkem (least
common multiple) monomů LM f a LM g a zavádíme označení
LCM(LM f , LM g) := xγ. Výraz
S(f , g) :=
xγ
LT f
· f −
xγ
LT g
· g
nazýváme S-polynomem (nebo také syzygy, neboli spřežení)
polynomů f , g.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Pro α = multideg f a β = multideg g uvažme
γ := (γ1, . . . , γn) kde γi = max{αi , βi }
Monom xγ nazýváme nejmenším společným násobkem (least
common multiple) monomů LM f a LM g a zavádíme označení
LCM(LM f , LM g) := xγ. Výraz
S(f , g) :=
xγ
LT f
· f −
xγ
LT g
· g
nazýváme S-polynomem (nebo také syzygy, neboli spřežení)
polynomů f , g.
Jedná se o nástroj k eliminaci vedoucích členů, Gaussova eliminace
je speciálním případem tohoto postupu pro stupeň 1. Narozdíl od ní
ale může dojít ke zvýšení stupně, i když původní vedoucí členy
odstraní.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Theorem
Nechť I ⊆ K[x1, . . . , xn] je ideál. Pak jeho báze G = {gj , . . . , gt} je
Gröbnerova právě tehdy, když pro každé i = j je zbytek po dělení
S(gi , gj )/G nulový.
Důkaz.
Nebudeme na přednášce uvádět – hodně technické (ale napíšu
časem do textů).
Věta poskytuje účinný prostředek pro zjištění, zda nějaká báze je
Gröbnerova. Uvažujme například I = x + y, y − z . Jediný
S-polynom, který připadá v úvahu je
S(x + y, y − z) =
xy
x
(x + y) −
xy
y
(y − z) = xz + y2
Dělením získáme xz + y2 = z(x + y) + y(y − z), a tedy daná báze
je Gröbnerova.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Naivní algoritmus pro Gröbnerovy báze
1 G := F, G := ∅
2 while G = G
1 G := G
2 ∀p, q ∈ G : p = q do
1 s := S(p, q)
G
2 if s = 0
G := G ∪ {s}
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Naivní algoritmus pro Gröbnerovy báze
1 G := F, G := ∅
2 while G = G
1 G := G
2 ∀p, q ∈ G : p = q do
1 s := S(p, q)
G
2 if s = 0
G := G ∪ {s}
Tento algoritmus ovšem není zdaleka ideální. Lze vymyslet velmi
jednoduše vypadající vstupy, pro něž vrací divoké výsledky. Dále
výstupní báze se přímo odvíjí od vstupní, a tedy pro tentýž ideál
zadaný různými bázemi dá také různé výsledky.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Lemma
Nechť G je Gröbnerova báze ideálu I a p ∈ G takový, že
LT p ∈ LT(G − {p}) . Pak G − {p} je také Gröbnerova báze I.
Důkaz.
Z definice Gröbnerovy báze platí LT I = LT G . Protože
LT p ∈ LT(G − {p}) , platí LT(G − {p}) = LT G . Odsud již
plyne tvrzení.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Minimální Gröbnerovou bází ideálu I je taková Gröbnerova báze G,
že pro všechna p ∈ G platí LC p = 1 a zároveň
LT p /∈ LT(G − {p})
Například mějme k[x, y] a <grlex,
I = f1, f2 = x3 − 2xy, x2y − 2y2 + x . Zmíněný algoritmus dá
(f1, . . . , f5) = (x3
− 2xy, x2
y − 2y2
+ x, −x2
, −2xy, −2y2
+ x)
Přitom platí LT f1 = x3 = −x LT f3 a LT f2 = −1
2 x LT f4 a tedy
f1 a f2 jsou zbytečné.
Všimněme si: pro každé a je {x2 + axy, xy, y2 − 1/2x} minimální
Gröbnerovou bází uvedeného ideálu.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Polynom g ∈ G nazveme redukovaný pro bázi G pokud žádný
z jeho monomů neleží v LT(G − {g}) . Redukovanou Gröbnerovou
bází ideálu I potom nazveme takovou Gröbnerovu bázi G, že pro
všechna p ∈ G platí LC p = 1 a zároveň p je redukovaný pro G.
Zjevně je každá redukovaná Gröbnerova báze je minimální a navíc
platí:
Lemma
Je-li polynom g redukovaný pro nějakou minimální Gröbnerovu bázi
G ideálu I, pak je také redukovaný pro každou minimální
Gröbnerovu bázi G téhož ideálu, která jej obsahuje.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Důkaz.
Tvrzení dokážeme sporem. Uvažme G = {g1, . . . , gs},
G = {g1, . . . , gt} a g = · · · + m + · · · kde m ∈ LT(G − {g})
(tj. g není redukovaný pro G ). Potom
m = a1 LT g1 + · · · + at LT gt pro nějaké vhodné polynomy
a1, . . . , at. Protože G i G jsou Gröbnerovy báze téhož ideálu, platí
LT G = LT G , a tedy každé LT gi lze vyjádřit jako kombinaci
LT g1, . . . , LT gs. Odtud už plyne m ∈ LT G a protože je G
minimální, je m ∈ LT(G \ {g}) , což je spor s předpokládanou
redukovaností g pro G.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Theorem
Nechť I ⊆ k[x1, . . . , xn] je nenulový. Pak pro každé monomiální
uspořádání existuje právě jedna redukovaná Gröbnerova báze ideálu
I. Navíc každou Gröbnerovu bázi lze algoritmicky redukovat.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Budeme považovat okruh K[xp+1, . . . , xn] za podokruh
K[x1, . . . , xn]. Jedná se o polynomy, v nichž se nevyskytují
proměnné x1, . . . , xp. Je to skutečně podokruh, ale už ne ideál.
Definition
Nechť I = f1, . . . , fs ⊆ k[x1, . . . , xn]. Pro p = 1, . . . , n definujeme
Ip := I ∩ K[xp+1, . . . , xn]
Tuto množinu nazveme p-tým eliminačním ideálem.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Budeme považovat okruh K[xp+1, . . . , xn] za podokruh
K[x1, . . . , xn]. Jedná se o polynomy, v nichž se nevyskytují
proměnné x1, . . . , xp. Je to skutečně podokruh, ale už ne ideál.
Definition
Nechť I = f1, . . . , fs ⊆ k[x1, . . . , xn]. Pro p = 1, . . . , n definujeme
Ip := I ∩ K[xp+1, . . . , xn]
Tuto množinu nazveme p-tým eliminačním ideálem.
Samozřejmě Ip je ideálem pouze v k[xp+1, . . . , xn].
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Na úrovni polynomiálních rovnic Ip obsahuje všechny rovnice, které
jsou důsledky systému f1 = 0, . . . , fs = 0 a v kterých vystupují
pouze proměnné xp+1, . . . , xn.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Na úrovni polynomiálních rovnic Ip obsahuje všechny rovnice, které
jsou důsledky systému f1 = 0, . . . , fs = 0 a v kterých vystupují
pouze proměnné xp+1, . . . , xn.
Theorem (Eliminační věta)
Nechť I ⊆ K[x1, . . . , xn] je ideál, G = {g1, . . . , gm} jeho
Gröbnerova báze vzhledem k <lex. Proměnné nechť jsou
uspořádány x1 >lex x2 >lex · · · . Potom pro každé p = 0, . . . , n je
Gp := G ∩ K[xp+1, . . . , xn] Gröbnerovou bází ideálu Ip.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Plán přednášky
1 Gröbnerovy báze a eliminace proměnných
2 Množinová algebra a logika
3 Posety a svazy
4 Normální tvary a morfismy
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
S každou množinou M máme také množinu K = 2M všech jejích
podmnožin a na ní operace ∨ : K × K → K sjednocení množin a
∧ : K × K → K průniku množin.
To jsou dvě binární operace, které se častěji značí ∪ a ∩.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
S každou množinou M máme také množinu K = 2M všech jejích
podmnožin a na ní operace ∨ : K × K → K sjednocení množin a
∧ : K × K → K průniku množin.
To jsou dvě binární operace, které se častěji značí ∪ a ∩.
Dále máme ke každé množině A ∈ K také její množinu doplňkovou
A , což je další unární operace. Konečně máme „největší objekt“, tj.
celou množinu M, který je neutrální vůči operaci ∧ a který proto
budeme v této souvislosti označovat jako 1, a obdobně se chová
prázdná množina ∅ ∈ K vůči operaci ∧. Tu budeme v této
souvislosti značit jako 0.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Na množině K všech podmnožin v M přitom platí pro všechny
prvky A, B, C následující vlastnosti:
A ∧ (B ∧ C) = (A ∧ B) ∧ C, A ∨ (B ∨ C) = (A ∨ B) ∨ C (1)
A ∧ B = B ∧ A, A ∨ B = B ∨ A (2)
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
(3)
existuje 0 tak, že A ∨ 0 = A (4)
existuje 1 tak, že A ∧ 1 = A (5)
A ∧ A = 0, A ∨ A = 1. (6)
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Na množině K všech podmnožin v M přitom platí pro všechny
prvky A, B, C následující vlastnosti:
A ∧ (B ∧ C) = (A ∧ B) ∧ C, A ∨ (B ∨ C) = (A ∨ B) ∨ C (1)
A ∧ B = B ∧ A, A ∨ B = B ∨ A (2)
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
(3)
existuje 0 tak, že A ∨ 0 = A (4)
existuje 1 tak, že A ∧ 1 = A (5)
A ∧ A = 0, A ∨ A = 1. (6)
Vlastnost (1) je asociativní zákon pro obě operace, (2) je
komutativita, (3) je distributivita obou operací. Poslední vlastnost
(6) vystihuje vlastnosti komplementu.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Množině K spolu s dvěmi binárními operacemi ∧ a ∨ a jednou
unární operací splňující vlastnosti (1)–(7) říkáme Booleovská
algebra. Operaci ∧ budeme říkat infimum (případně průnik,
anglicky často také meet), operaci ∨ budeme říkat supremum
(případně sjednocení, anglicky také join). Prvku A se říká
doplněk k prvku A.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Množině K spolu s dvěmi binárními operacemi ∧ a ∨ a jednou
unární operací splňující vlastnosti (1)–(7) říkáme Booleovská
algebra. Operaci ∧ budeme říkat infimum (případně průnik,
anglicky často také meet), operaci ∨ budeme říkat supremum
(případně sjednocení, anglicky také join). Prvku A se říká
doplněk k prvku A.
Všimněme si, že axiomy Booleovské algebry jsou zcela symetrické
vůči záměně operací ∧ a ∨, společně se záměnou prvků 0 a 1.
Důsledkem tohoto faktu je, že jakékoliv tvrzení, které odvodíme z
axiomů, má také platné duální tvrzení, které vznikne z prvého
právě záměnou všech výskytů ∧ za ∨ a naopak a stejně tak všech
výskytů 0 a 1. Hovoříme o principu duality.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Stejně jako u speciálního případu Booleovské algebry všech
podmnožin v dané množině M je doplněk k A ∈ K určen
jednoznačně (tj. máme-li dáno (K, ∧, ∨), může existovat nejvýše
jedna unární operace, se kterou dostaneme Booleovskou algebru).
Skutečně, pokud B a C ∈ K splňují vlastnosti A , platí
B = B ∨0 = B ∨(A∧C) = (B ∨A)∧(B ∨C) = 1∧(B ∨C) = B ∨C
a podobně také C = C ∨ B. Je tedy nutně B = C.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
V následujícím výčtu se vlastnostem (2) říká absorpční zákony,
vlastnosti (3) popisují idempotentnost operací a (4) jsou tzv. De
Morganova pravidla.
Theorem
V každé Booleovské algebře (K, ∧, ∨, ) platí pro všechny prvky v K
1 A ∧ 0 = 0, A ∨ 1 = 1
2 A ∧ (A ∨ B) = A, A ∨ (A ∧ B) = A
3 A ∧ A = A, A ∨ A = A
4 (A ∧ B) = A ∨ B , (A ∨ B) = A ∧ B
5 (A ) = A.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Naši symboliku interpretujeme tak, že z prvků A, B, · · · ∈ K
tvoříme „slova“ pomocí operací ∨, ∧, a závorek vyjasňujících v
jakém pořadí a na jaké argumenty jsou operace aplikovány.
Samotné axiomy a jejich důsledky pak říkají, že velice často různá
slova dávají stejnou hodnotu výsledku v K.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Naši symboliku interpretujeme tak, že z prvků A, B, · · · ∈ K
tvoříme „slova“ pomocí operací ∨, ∧, a závorek vyjasňujících v
jakém pořadí a na jaké argumenty jsou operace aplikovány.
Samotné axiomy a jejich důsledky pak říkají, že velice často různá
slova dávají stejnou hodnotu výsledku v K.
V případě množiny všech podmnožin K = 2M je to zřejmé – prostě
jde o rovnost podmnožin.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Nyní budeme pracovat opět se slovy jako výše, interpretujeme je ale
jako tvrzení složené z elementárních výroků A, B, . . . a logických
operací AND (binární operace ∧), OR (binární operace ∨) a negace
NOT (unární operace ). Taková slova nazýváme výroky a
přiřazujeme jim pravdivostní hodnotu v závislosti na pravdivostní
hodnotě jednotlivých elementárních argumentů. Pravdivostní
hodnotu přitom bereme jako prvek z triviální Booleovy algebry Z2,
tedy buď 0 nebo 1. Pravdivostní hodnota výroku je plně určena
přiřazením hodnot pro nejjednoduší výroky A ∧ B, A ∨ B a A , tj.
A ∧ B je pravdivé pouze, když jsou oba výroky A a B pravdivé,
A ∨ B je nepravdivé pouze. když jsou oba výroky nepravdivé a A
má opačnou hodnotu než A.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Výrok obsahující k elementárních výroků tedy představuje funkci
(Z2)k → Z2 a dva výroky nazýváme logicky ekvivalentní, jestliže
zadávají stejnou funkci. Snadno se nyní přímo ověří, že na množině
tříd logicky ekvivalentních výroků jsme takto zadefinovali strukturu
Booleovy algebry (je pouze třeba projít naše axiomy a ověřit je).
Nutně tedy pro výrokovou logiku bude v tomto smyslu platné vše,
co dokážeme pro obecné Booleovy algebry.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Výrok obsahující k elementárních výroků tedy představuje funkci
(Z2)k → Z2 a dva výroky nazýváme logicky ekvivalentní, jestliže
zadávají stejnou funkci. Snadno se nyní přímo ověří, že na množině
tříd logicky ekvivalentních výroků jsme takto zadefinovali strukturu
Booleovy algebry (je pouze třeba projít naše axiomy a ověřit je).
Nutně tedy pro výrokovou logiku bude v tomto smyslu platné vše,
co dokážeme pro obecné Booleovy algebry.
Stručně si proberme, jak vypadají obvyklé další jednoduché výroky
ve výrokové logice jakožto prvky Booleovy algebry (tj.
reprezentujeme vždy naším výrazem třídu výroků ekvivalentních):
Implikaci A ⇒ B dostaneme jako A ∨ B, ekvivalenci A ⇔ B
odpovídá (A ∧ B) ∨ (A ∧ B ). Dále vylučovací OR, neboli XOR, je
dáno jako (A ∧ B ) ∨ (A ∧ B), negace NOR operace OR je
vyjádřena jako A ∧ B a negace NAND operace AND je dána jako
A ∨ B . Všimněme si také, že XOR odpovídá v množinové algebře
symetrickému rozdílu množin.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Přepínač je pro nás černá skříňka, která má jen dva stavy, buď je
zapnut (a signál prochází) nebo naopak vypnut (a signál
neprochází).
Jeden nebo více přepínačů zapojujeme do sítě sériově nebo
paralelně. Sériové zapojení je popsáno pomocí binární operace ∧,
paralelní je naopak ∨. Unární operace A zadává přepínač, který je
vždy v opačné poloze než A.
B
A B
A
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Každé konečné slovo vytvořené pomocí přepínačů A, B, . . . a
operací ∧, ∨ a umíme převést na obrázek, který bude
představovat systém přepínačů propojených dráty a zcela obdobně
jako v minulém odstavci nám každá volba poloh jednotlivých
přepínačů zadá hodnotu „zapnuto/vypnuto“ pro celý systém.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Každé konečné slovo vytvořené pomocí přepínačů A, B, . . . a
operací ∧, ∨ a umíme převést na obrázek, který bude
představovat systém přepínačů propojených dráty a zcela obdobně
jako v minulém odstavci nám každá volba poloh jednotlivých
přepínačů zadá hodnotu „zapnuto/vypnuto“ pro celý systém.
Opět se snadno krok po kroku ověří platnost základních axiomů
Booleových algeber pro náš systém. Na obrázku je ilustrován jeden
z axiomů distributivity. Propojení bez přepínače odpovídá prvku 1,
koncové body bez propojení (nebo sériové zapojení A a A ) dává
prvek 0.
=A
A
A
B
C
B
C
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Dalším přirozeným příkladem Booleovské algebry je systém dělitelů
přirozeného čísla nebo polynomu.
Zvolme pevně takové číslo p ∈ N nebo polynom p ∈ K[x1, . . . , xs]
nad oborem integrity K s jednoznačným rozkladem. Za nosnou
množinu Dp bereme množinu všech dělitelů q našeho p. Pro dva
takové dělitele definujeme q ∧ r jako největší společný dělitel prvků
q a r, q ∨ r je nejmenší společný násobek. Dále klademe
p = 1 ∈ Dp a neutrálním prvkem vůči supremu je jednička v Z,
resp. 1 ∈ K ⊂ K[x1, . . . , xs]. Unární operaci dostáváme pomocí
dělení: q = p/q.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Lemma
Množina Dp spolu s výše uvedenými operacemi ∧, ∨ a je
Booleova algebra právě, když rozklad p neobsahuje kvadráty (tj. v
jednoznačném rozkladu p = q1 . . . qn na nerozložitelné faktory jsou
všechna qi po dvou různá).
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Plán přednášky
1 Gröbnerovy báze a eliminace proměnných
2 Množinová algebra a logika
3 Posety a svazy
4 Normální tvary a morfismy
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Vzpomeňme na definici uspořádání jakožto reflexivní, antisymetrické
a tranzitivní relace ≤ na množině K. Taková relace obecně neříká o
každé dvojici a, b ∈ K jestli je a ≤ b nebo b ≤ a (takové
uspořádání se nazývá úplné uspořádání nebo dobré uspořádání).
Často v našem případě obecného uspořádání hovoříme také o
částečném uspořádání a množina (K, ≤) vybavená částečným
uspořádáním se nazývá poset (z anglického „partial ordered set“).
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Vzpomeňme na definici uspořádání jakožto reflexivní, antisymetrické
a tranzitivní relace ≤ na množině K. Taková relace obecně neříká o
každé dvojici a, b ∈ K jestli je a ≤ b nebo b ≤ a (takové
uspořádání se nazývá úplné uspořádání nebo dobré uspořádání).
Často v našem případě obecného uspořádání hovoříme také o
částečném uspořádání a množina (K, ≤) vybavená částečným
uspořádáním se nazývá poset (z anglického „partial ordered set“).
Takové uspořádání je zejména vždy na množině K = 2M všech
podmnožin množiny M prostřednictvím inkluze podmnožin. Pomocí
naší relace infima na K je můžeme definovat jako A ⊂ B právě,
když A ∧ B = A. Ekvivalentně, A ⊂ B právě, když A ∨ B = B.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Lemma
Je-li (K, ∧, ∨, ) Booleova algebra, pak relace ≤ definovaná
vytahem A ≤ B právě, když A ∧ B = A, je částečné uspořádání.
Navíc platí
1 A ∧ B ≤ A
2 A ≤ A ∨ B
3 jestliže A ≤ C a zároveň B ≤ C, pak také A ∨ B ≤ C
4 A ≤ B právě, když A ∧ B = 0
5 0 ≤ A a A ≤ 1 pro všechny A ∈ K.
Všimněme si, že stejně jako v případě algebry podmnožin je v
Booleovských algebrách A ∧ B = A právě, když je A ∨ B = B.
Skutečně, je-li A ∧ B = A, pak z absorpčních zákonů plyne
A ∨ B = (A ∧ B) ∨ B = B, a naopak.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Viděli jsme, že každá Booleova algebra zadává poset (K, ≤).
Zdaleka ne každý poset ovšem vzniká takovýmto způsobem. Např.
triviální částečné uspořádání, kdy A ≤ A pro všechny A a všechny
dvojice různých prvků jsou nesrovnatelné, samozřejmě z Booleovy
algebry vzniknout nemůže, pokud je v K více než jeden prvek
(viděli jsme, že největší a nejmenší prvek v Booleově algebře je totiž
srovnatelný s každým prvkem). Zkusme se zamyslet, do jaké míry
lze z uspořádání budovat operace ∧ a ∨.
Pracujme s pevně zvoleným posetem (K, ≤). O prvku C ∈ K
řekneme, že je dolní závorou pro nějakou množinu prvků L ⊂ K,
je-li C ≤ A pro všechny A ∈ L. Prvek C ∈ K je infimem množiny
L ⊂ K, jestliže je dolní závorou a pro každou jinou dolní závoru D
téže množiny platí D ≤ C.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Obdobně definujeme horní závory a supremum podmnožiny L
záměnou ≤ za ≥ v posledním odstavci.
Konečné posety se přehledně zobrazují pomocí orientovaných grafů.
Prvky K jsou představovány uzly a hranou jsou spojeny právě prvky
v relaci s orientací od většího k menšímu. Hasseho diagram
posetu je zakreslení takového grafu v rovině tak, že větší prvky jsou
zobrazeny vždy výš než menší (a orientace hran je tedy dána takto
implicitně).
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Obdobně definujeme horní závory a supremum podmnožiny L
záměnou ≤ za ≥ v posledním odstavci.
Konečné posety se přehledně zobrazují pomocí orientovaných grafů.
Prvky K jsou představovány uzly a hranou jsou spojeny právě prvky
v relaci s orientací od většího k menšímu. Hasseho diagram
posetu je zakreslení takového grafu v rovině tak, že větší prvky jsou
zobrazeny vždy výš než menší (a orientace hran je tedy dána takto
implicitně).
Definition
Svaz je poset (K, ≤), ve kterém každá dvouprvková množina
{A, B} má supremum A ∨ B a infimum A ∧ B v K.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Na svazu (K, ≤) tedy máme definovány binární operace ∧ a ∨ a
přímo z definice je zjevná asociativita a komutativita těchto operací.
Snadno lze ale nakreslit Hasseho diagram svazu, který není
distributivní.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Na svazu (K, ≤) tedy máme definovány binární operace ∧ a ∨ a
přímo z definice je zjevná asociativita a komutativita těchto operací.
Snadno lze ale nakreslit Hasseho diagram svazu, který není
distributivní.
Nyní můžeme snadno definovat Booleovskou algebru v jazyce
svazů: Booleovská algebra je distributivní svaz s největším prvkem 1
a nejmenším prvkem 0 takový, že v něm existují ke všem prvkům
komplementy.
Ověřili jsme již, že v takovém případě komplementy jsou definovány
jednoznačně, takže je naše alternativní definice Booleovské algebry
korektní.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Na svazu (K, ≤) tedy máme definovány binární operace ∧ a ∨ a
přímo z definice je zjevná asociativita a komutativita těchto operací.
Snadno lze ale nakreslit Hasseho diagram svazu, který není
distributivní.
Nyní můžeme snadno definovat Booleovskou algebru v jazyce
svazů: Booleovská algebra je distributivní svaz s největším prvkem 1
a nejmenším prvkem 0 takový, že v něm existují ke všem prvkům
komplementy.
Ověřili jsme již, že v takovém případě komplementy jsou definovány
jednoznačně, takže je naše alternativní definice Booleovské algebry
korektní.
Všimněme si také, při diskusi dělitelů daného čísla nebo polynomu p
jsme narazili na svazy Dp, které jsou Booleovskou algebrou právě
tehdy, když rozklad p neobsahuje kvadráty.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Plán přednášky
1 Gröbnerovy báze a eliminace proměnných
2 Množinová algebra a logika
3 Posety a svazy
4 Normální tvary a morfismy
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Při diskusi výrokové logiky jsme se potýkali s problémem, co vlastně
jsou prvky příslušné Booleovy algebry. Formálně vzato jsme je
definovali jako třídy ekvivalentních výroků. Jinak řečeno, pracovali
jsme s hodnotovými funkcemi pro výroky s daným počtem
argumentů. Vůbec jsme přitom neřešili obtížný problém, jak
rozpoznat stejné výroky v tomto smyslu. Také jsme neřešili, jestli
všechny formálně možné hodnotové funkce (Z2)n → Z2 lze zadat
pomocí základních logických operací.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Při diskusi výrokové logiky jsme se potýkali s problémem, co vlastně
jsou prvky příslušné Booleovy algebry. Formálně vzato jsme je
definovali jako třídy ekvivalentních výroků. Jinak řečeno, pracovali
jsme s hodnotovými funkcemi pro výroky s daným počtem
argumentů. Vůbec jsme přitom neřešili obtížný problém, jak
rozpoznat stejné výroky v tomto smyslu. Také jsme neřešili, jestli
všechny formálně možné hodnotové funkce (Z2)n → Z2 lze zadat
pomocí základních logických operací.
Zcela obdobně se můžeme tázat, jak poznat, zda dva systémy
přepínačů mají stejnou funkci. Obdobně jako u výroků zde pro
systém s n přepínači pracujeme s funkcemi (Z2)n → Z2 a zjevně
existuje právě 22n
různých takových přepínacích funkcí. Na těchto
funkcích umíme přirozeným způsobem zadat strukturu Booleovy
algebry (využíváme, že hodnoty, tj. Z2 jsou Booleovou algebrou).
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Při diskusi výrokové logiky jsme se potýkali s problémem, co vlastně
jsou prvky příslušné Booleovy algebry. Formálně vzato jsme je
definovali jako třídy ekvivalentních výroků. Jinak řečeno, pracovali
jsme s hodnotovými funkcemi pro výroky s daným počtem
argumentů. Vůbec jsme přitom neřešili obtížný problém, jak
rozpoznat stejné výroky v tomto smyslu. Také jsme neřešili, jestli
všechny formálně možné hodnotové funkce (Z2)n → Z2 lze zadat
pomocí základních logických operací.
Zcela obdobně se můžeme tázat, jak poznat, zda dva systémy
přepínačů mají stejnou funkci. Obdobně jako u výroků zde pro
systém s n přepínači pracujeme s funkcemi (Z2)n → Z2 a zjevně
existuje právě 22n
různých takových přepínacích funkcí. Na těchto
funkcích umíme přirozeným způsobem zadat strukturu Booleovy
algebry (využíváme, že hodnoty, tj. Z2 jsou Booleovou algebrou).
Odpovíme nyní na výše uvedené otázky tak, že pro libovolný prvek
obecné Booleovy algebry sestrojíme jeho tzv. normální
disjunktivní tvar, tj. napíšeme jej pomocí vybrané skupiny
nejjednodušších prvků a operace ∨.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Prvek A ∈ K nazveme atom v Booleově algebře K, jestliže pro
všechny B ∈ K platí A ∧ B = A nebo A ∧ B = 0.
Jinak řečeno, A je atom, když pro všechny ostatní prvky B ≤ A
implikuje B = 0 nebo B = A.
Lemma
Booleova algebra funkcí přepínačového systému s n přepínači
A1, . . . , An má 2n atomů, které jsou tvaru Aσ1
1 ∧ · · · ∧ Aσn
n , kde buď
Aσ
i = Ai nebo Aσi
i = Ai .
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Theorem
Každý prvek B v konečné Booleově algebře (K, ∧, ∨, ) lze zapsat
jako supremum atomů
B = A1 ∨ · · · ∨ Ak.
Tato formule je navíc jednoznačná až na pořadí atomů.
Pro důkaz budeme potřebovat tři jednoduchá tvrzení:
Theorem
1 Jestliže jsou Y , X1, . . . , X atomy v K, pak Y ≤ X1 ∨ · · · ∨ X
tehdy a jen tehdy, když Y = Xi pro nějaké i = 1, . . . , .
2 Pro každý prvek Y = 0 v K existuje atom X, pro který je
X ≤ Y .
3 Jestliže jsou X1, . . . , Xr všechny atomy v K, pak Y = 0 právě,
když Y ∧ Xi = 0 pro všechny i = 1, . . . , r.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Jak jsme již viděli u mnoha matematických struktur, o objektech se
dozvídáme informace pomocí tzv. homomorfismů, tj. zobrazení,
které zachovávají příslušné operace. V případě Booleovských
algeber definujeme podobně jako u okruhů:
Definition
Zobrazení f : (K, ∧, ∨, ) → (L, ∧, ∨, ) se nazývá homomorfismus
Booleovských algeber, jestliže pro všechny A, B ∈ K platí
1 f (A ∧ B) = f (A) ∧ f (B)
2 f (A ∨ B) = f (A) ∨ f (B)
3 f (A ) = f (A) .
Homomorfismus f je izomorfismus Booleovských algeber, jestliže je
f bijektivní.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Snadno se ověří, že bijektivnost f již zaručí, že f −1 je opět
homomorfismem.
Z definice uspořádání na Booleových algebrách je zřejmé, že každý
homomorfismus f : K → L bude také splňovat f (A) ≤ f (B) pro
všechny prvky A ≤ B v K. To je definiční vlastnost pro tzv.
izotonní zobrazení neboli homomorfismy posetů.
Jakkoliv umíme rekonstruovat operace suprema a infima z
uspořádání, pokud toto vzniklo z Booleovy algebry, není pravda, že
by každý homomorfismus posetů byl automaticky homomorfismem
příslušných algeber. Zkuste si najít příklad (stačí vkládat algebru se
dvěma atomy do algebry s alespoň čtyřmi atomy)!
Theorem
Každá konečná Booleova algebra je izomorfní Booleově algebře
K = 2M, kde M je množina atomů v K.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Definition
Homomorfismem posetů (K, ≤K ) a (L, ≤L) rozumíme takové
zobrazení f : K → L, že z A ≤K B vždy vyplývá také
f (A) ≤L f (B). Hovoříme přitom také o izotonních zobrazeních.
Snadno se ověří, že bijektivnost f již zaručí, že f −1 je opět
homomorfismem.
Z definice uspořádání na Booleových algebrách nebo svazech je
zřejmé, že každý homomorfismus f : K → L bude také splňovat
f (A) ≤ f (B) pro všechny prvky A ≤ B v K, půjde tedy vždy o
izotonní zobrazení.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
Mnoho praktických úloh spočívá v diskusi pevných bodů zobrazení
f : K → K na nějaké množině K, tj. prvků x ∈ K s vlastností
f (x) = x. Naše úvahy o infimech a supremech umožňují překvapivě
snadno odvodit velice silná tvrzení tohoto typu. Dokážeme si jednu
takovou klasickou větu, kterou odvodili Knaster a Tarski (ve
speciálním případě Booleovské algebry podmnožin dané množiny již
koncem dvacátých let 20. století, obecné tvrzení pak publikoval
Tarski v r. 1955):
Theorem (Tarského věta)
Uvažujme libovolný úplný svaz (K, ∧, ∨) a libovolné isotonní
zobrazení f : K → K. Pak f má pevný bod a množina všech
pevných bodů f je (s uspořádáním zděděným z K) opět úplný svaz.
Gröbnerovy báze a eliminace proměnných Množinová algebra a logika Posety a svazy Normální tvary a morfismy
V literatuře lze najít mnoho variant vět o pevných bodech v
různých souvislostech. Jednou z velmi užitečných je tzv. Kleeneho
věta, jejíž tvrzení můžeme vyčíst z právě dokázané věty
následujícím způsobem.
Jestliže (ve značení Tarského věty) uvážíme spočetnou podmnožinu
v K tvořenou tzv. Kleeneho řetězcem
0 ≤ f (0) ≤ f (f (0)) ≤ . . . ,
pak supremum z této podmnožiny zjevně nemůže být větší, než
kterýkoliv pevný bod zobrazení f . Skutečně, pokud je y pevný bod
zobrazení f pak ze vztahu 0 ≤ y dostaneme f (0) ≤ f (y) = y atd.
Pokud má f navíc vlastnost, že „dostatečně“ zachovává suprema,
můžeme dovodit že f (z) bude opět supremem téhož řetězce a tedy
pevný bod. Musí to proto být nejmenší pevný bod. Toto tvrzení se
nazývá Kleeneho věta o pevném bodě a má četná použití v
teorii rekurzí, při diskusi zastavení algoritmů atd.