MA007 — 4. sada domácích úloh
Příklad 1 [2 body]
Je dán jazyk L = {P, f} s rovností, kde P je unární predikátový symbol a f je unární funkční symbol. Dále
je dána jeho teorie T = {ϕ1, ϕ2, ϕ3, ϕ4}, kde
ϕ1 ≡ ∃x1∃x2∃x3∃x4∃x5∀y


5
i=1
5
j=i+1
xi = xj ∧
5
i=1
y = xi

 ,
ϕ2 ≡ ∃x∃y∀z(x = y ∧ P(x) ∧ P(y) ∧ (P(z) → (z = x ∨ z = y))),
ϕ3 ≡ ∀x(P(f(x))),
ϕ4 ≡ ∀x(P(x) → f(x) = x).
Zadání. Rozhodněte a dokažte, zda je teorie T bezesporná a zda je úplná.
Řešení. Nejprve si rozebereme význam jednotlivých formulí teorie T: Uvažme libovolnou realizaci M =
(M, PM, fM) jazyka L. Pro jednodušší vyjadřování a v souladu s níže uvedenými obrázky budeme individua
x ∈ PM označovat jako červená, ostatní pak jako černá.
Zřejmě M |= ϕ1, právě když M je pětiprvková. Podobně M |= ϕ2, právě když právě dvě individua jsou
červená. Dále M |= ϕ3, právě když je obraz každého individua v fM červený. A konečně M |= ϕ4, právě když
všechna červená individua jsou pevnými body fM.
Uvažme následující modely M, M teorie T (formálně M = M = {a, b, c, d, e}, PM = PM = {a, b},
fM = {(a, a), (b, b), (c, a), (d, a), (e, a)}, fM = {(a, a), (b, b), (c, a), (d, a), (e, b)}):
a
b
c
d
e
model M
a
b
c
d
e
model M
Tyto modely zřejmě nejsou izomorfní (a jsou to — až na izomorfizmus — jediné modely naší teorie; to ale
k vyřešení zadání vědět nepotřebujeme), a jsou dokonce rozlišitelné v naší predikátové logice: uvažme (uzavřenou)
formuli ϕ ≡ ∀x(P(x) → ∃y(¬P(y) ∧ f(y) = x)) — intuitivně: každé červené individuum má nějaký černý
vzor. Zřejmě M |= ϕ a M |= ϕ, takže M |= ¬ϕ. Z toho dostáváme, že T |= ϕ ani T |= ¬ϕ. Podle věty o
korektnosti tak T ϕ ani T ¬ϕ.
Teorie T je tedy bezesporná (našli jsme formuli, která v T není dokazatelná), ale není úplná (našli jsme
uzavřenou formuli takovou, že v T není dokazatelná ani ona, ani její negace).
Příklad 2 [5 bodů]
Je dán jazyk L = {P} s rovností, kde P je binární predikátový symbol. Pro libovolné n ∈ N uvažme formule
ϕn ≡ ∀y∃x1∃x2 · · · ∃xn


n
i=1
n
j=i+1
(xi = xj ∧ P(y, xi))

 ,
ψn ≡ ∃x1∃x2 · · · ∃xn


n
i=1
n
j=i+1
(xi = xj ∧ P(xi, xj))

 .
Nyní ještě zadefinujme formuli θ ≡ ∀x∀y(P(x, x) ∧ (P(x, y) → P(y, x))) a teorie R = {θ} ∪ {ϕn | n ∈ N},
S = {θ} ∪ {ψn | n ∈ N}. Uvažme libovolnou realizaci M jazyka L s nosičem M a binární relací PM ⊆ M × M
1
pro symbol P. Řekneme, že podsoubor S ⊆ M je povolený, právě když pro každá jeho dvě individua x, y ∈ S
platí (x, y) ∈ PM.
Zadání.
a) [1 bod] Rozhodněte a dokažte, zda každý model teorie R obsahuje nekonečný povolený podsoubor
individuí.
b) [1 bod] Rozhodněte a dokažte, zda každý model teorie S obsahuje nekonečný povolený podsoubor
individuí.
c) [2 body] Zadejte nějakou teorii T jazyka L = {P, f} s rovností, kde P je binární predikátový symbol
a f unární funkční symbol, takovou, že pro každý soubor individuí M a každou binární relaci PM ⊆ M × M
platí: M obsahuje nekonečný povolený podsoubor individuí, právě když existuje zobrazení fM: M → M takové,
že realizace M = (M, PM, fM) jazyka L je modelem teorie T.
Pokud nejste schopni podúlohu c) vyřešit, můžete místo ní vyřešit jednodušší verzi (pak ale z této podúlohy
získáte nejvýš 1 bod): Zadejte nějakou teorii T jazyka L = {P, Q} s rovností, kde P je binární predikátový
symbol a Q unární predikátový symbol, takovou, že pro každý soubor individuí M a každou binární relaci
PM ⊆ M × M platí: M obsahuje nekonečný povolený podsoubor individuí, právě když existuje podsoubor
QM ⊆ M takový, že realizace M = (M, PM, QM) jazyka L je modelem teorie T.
d) [1 bod] Uvažme ještě pro libovolné n ∈ N formuli
ξn ≡ ∀y∃x1∃x2 · · · ∃xn


n
i=1
n
j=i+1
(xi = xj ∧ P(y, xi) ∧ P(xi, xj))


a zadefinujme teorii U = {θ}∪{ξn |n ∈ N}. Rozhodněte a dokažte, zda každý model teorie U obsahuje nekonečný
povolený podsoubor individuí.
Poznámky. Symbol ≡ za formulí značí (meta)rovnítko. a = b je syntaktická zkratka pro ¬(a = b). Slovo
soubor je zde používáno jako synonymum pro (meta)množinu.
Řešení. Opět si nejprve zkusíme udělat o úloze názornou představu. Realizaci M = (M, PM) jazyka L si
můžeme představit jako graf na M, kde individua x, y jsou spojená hranou, právě když (x, y) ∈ PM. Zřejmě
M |= θ, právě když PM je reflexivní a symetrická; náš graf tedy můžeme považovat za neorientovaný (smyčky
ovšem do něj pro jednoduchost zařazovat nebudeme). Povolený podsoubor individuí pak odpovídá klice v grafu.
a) Platí M |= ϕn, právě když stupeň každého vrcholu je aspoň n. Dohromady tedy M |= R, právě když
stupeň každého vrcholu je nekonečný; to však nekonečnou kliku nevynucuje, jak můžeme vidět na modelu
s nosičem N a PM = {(a, b) ∈ N × N | a = b nebo 2 a + b}. Odpovídající graf je zřejmě bipartitní, a tak
neobsahuje ani kliku o velikosti 3.
0 2 4 6 8 · · ·
1 3 5 7 9 · · ·
b) Platí M |= ψn, právě když graf obsahuje kliku o velikosti n. Dohromady tedy M |= S, právě když graf
obsahuje kliku libovolné (konečné) velikosti; to však opět nekonečnou kliku nevynucuje, jak můžeme vidět na
modelu s nosičem N a PM = {(a, b) ∈ N×N |
√
a =
√
b }. Každý vrchol má totiž zřejmě jen konečný stupeň.
0
1
23
4
5
67
8
9
10
11
1213
14
15
· · ·
2
c) Nejprve se podívejme na zjednodušenou variantu úlohy. Uvažme formuli
η ≡ ∀x∀y((Q(x) ∧ Q(y)) → P(x, y))
a dále pro libovolné n ∈ N definujme formuli
ζn ≡ ∃x1∃x2 · · · ∃xn


n
i=1
n
j=i+1
(xi = xj ∧ Q(xi))

 .
Teď můžeme uvážit teorii T = {η} ∪ {ζn | n ∈ N}.
Vezměme nejprve libovolný model M = (M, PM, QM) teorie T. Formule ζn vynucují, že predikát Q platí pro
nekonečně mnoho individuí. Formule η pak vynucuje, že individua, pro něž je Q pravdivý, tvoří v odpovídajícím
grafu kliku.
Nyní naopak předpokládejme, že na souboru individuí M máme binární relaci PM ⊆ M × M takovou, že
odpovídající graf obsahuje nekonečnou kliku. Pak můžeme do QM zařadit právě individua (nějaké) takové kliky
a realizace M = (M, PM, QM) pak jistě bude modelem teorie T.
A nyní k původní variantě: Jednou z možností je „vytvořit si z funkčního symbolu predikátový a vyřešit
úlohu stejně jako výše (např. místo Q(x) bychom psali f(x) = x). Není těžké si rozmyslet, že na aspoň
dvouprvkovém nosiči máme naprostou volnost v tom, která individua budou tuto rovnost splňovat.
Funkční symbol nám ale dává možnost zadat dokonce konečnou teorii s požadovanou vlastností: Definujme
formule
ρ ≡ ∀x∀y(f(x) = f(y) → x = y),
σ ≡ ∃x∀y(f(y) = x),
τ ≡ ∀x∀y((f(x) = x ∧ f(y) = y) → P(x, y)).
Nyní položíme T = {ρ, σ, τ}.
Vezměme nejprve libovolný model M = (M, PM, fM) teorie T. Formule σ vynucuje, že fM není surjektivní,
tj. že existuje individuum x, které nemá v fM žádný vzor. Formule ρ pak vynucuje, že fM je injektivní. Individua
x, fM(x), fM(fM(x)), . . . jsou tedy po dvou různá, takže žádné z nich není pevným bodem fM, a tak podle τ
každá dvojice z nich náleží do PM. Tvoří tedy nekonečnou kliku.
Nyní naopak předpokládejme, že na souboru individuí M máme binární relaci PM ⊆ M × M takovou, že
odpovídající graf obsahuje nekonečnou kliku. To tedy1
znamená, že existuje injektivní posloupnost g: N → M
taková, že (g(i), g(j)) ∈ PM pro libovolná i, j ∈ N. Definujeme zobrazení fM: M → M následovně:
• fM(g(i)) = g(i + 1) pro každé i ∈ N;
• fM(a) = a pro všechna individua a, která v g nejsou obrazem žádného přirozeného čísla.
Je nasnadě, že realizace M = (M, PM, fM) je skutečně modelem teorie T.
d) Nyní M |= ξn, právě když každý vrchol grafu je obsažen v klice o velikosti n. Dohromady tedy M |= U,
právě když každý vrchol grafu je obsažen v klice libovolné (konečné) velikosti; ani takto silná vlastnost ale stále
nevynucuje nekonečnou kliku. Jako protipříklad nyní můžeme zvolit „sjednocení modelů z podpříkladů a), b),
tj. nosičem je stále N a položíme PM = {(a, b) ∈ N × N |
√
a =
√
b nebo 2 a + b}.
Pro každé individuum (číslo) pak najdeme libovolně mnoho čísel opačné parity, s nimiž tvoří kliku. Každé
číslo je ovšem spojeno hranou jen s konečně mnoha čísly stejné parity, takže každá klika může od obou parit
obsahovat jen konečně mnoho čísel, a tak žádná nekonečná klika neexistuje.
1Pro znalce teorie množin: zde se ve skutečnosti odvoláváme na (velmi slabou formu) axiomu výběru.
3