1 ÚLOHY Z PREDIKÁTOVÉ LOGIKY Instance, varianty. UF.1.1. Substituovatelnost. 1. Buď ϕ formule (∃z)(x = z) & y < x a dále x, y, z různé proměnné, F unární funkční symbol, c konstantní symbol. Uveďte, zda je term t substituovatelný do ϕ za proměnnou v v následujících případech: Řešení: Ne. a) t je F (z), v je x. Řešení: Ano. b) t je F (z), v je y. Řešení: Ano. c) t je F (x), v je x. Řešení: Ano. d) t je F (c), v je y. 2. Buď ϕ formule (∀x)((∃z)(z < x & y = z) ∨ z 6= x) a dále x, y, z různé proměnné, G binární funkční symbol, c konstantní symbol. Uveďte, zda je term t substituovatelný do ϕ za proměnnou v v následujících případech: Řešení: Ne. a) t je G(c, x), v je y Řešení: Ano. b) t je G(c, y), v je y Řešení: Ano. c) t je G(c, c), v je z Řešení: Ne. d) t je G(z, x), v je z UF.1.2. Instance. Varianty. 1. Nechť y není volná ve ϕ a je substituovatelná za x do ϕ, ϕ0 je ϕ(x/y). Zjistěte, zda ϕ0 (y/x) je ϕ. Zdůvodněte odpověď. Řešení: Oba předpoklady dohromady zaručují, že volný výskyt y ve ϕ0 je právě tam, kde je volný výskyt x v ϕ. Tedy x je substituovatelné za y do ϕ0 a také rovnost obou uvažovaných formulí platí. 2. Buďte x, y, z, u různé proměnné, Q kvantifikátor. Odpovězte a zdůvodněte, zda v následujících případech platí: ψ je varianta ϕ. a) ϕ je (Qx)(x < y ∨ (∃z)(z = y & z 6= x)) ψ je (Qz)(z < y ∨ (∃z)(z = y & z 6= z)) Řešení: Ne. z není substituovatelné za x do x < y ∨ (∃z)(z = y & z 6= x). b) ϕ je (Qx)(x < y ∨ (∀z)(z = y & z 6= x)) ψ je (Qy)(y < y ∨ (∀z)(z = y & z 6= y)) Řešení: Ne. y je volná ve ϕ. c) ϕ je (Qx)(x < y ∨ (∃z)(z = y & z 6= x)) ψ je (Qu)(u < y ∨ (∃z)(z = y & z 6= u)) Řešení: Ano. u není volná ve ϕ a je substituovatelná za x do x < y ∨ (∃z)(z = y & z 6= x). 3. Buď P unární predikátový symbol, ϕ formule (∃y)(y = x) & P (x), ϕ0 formule (∃y)(y = y) & P (y). a) b) c) d)
Je (∀x)ϕ0 varianta (∀x)ϕ? Řešení: Ne. Je x substituovatelné do ϕ0 za y? Řešení: Ano. Je ϕ rovno ϕ0 (y/x)? Řešení: Ne. ϕ0 (y/x) je (∃y)(y = y) & P (x). Je ` ϕ ↔ ϕ0 (y/x)? Řešení: Ano. Je ` (∃y)(y = x) ↔ (∃y)(y = y), protože obě formule z ekvivalence jsou dokazatelné. Odtud ` (∃y)(y = x) & P (x) ↔ (∃y)(y = y) & P (x).
2 Pojem modelu a splňování. Axiomatizovatelnost. UF.1.3. Platnost formule v modelu. 1. Buď ϕ formule P (x) → (∀x)P (x), kde P je unární relační symbol. V právě kterých strukturách hA, P A i neplatí ϕ ani ¬ϕ? Řešení: Právě když ∅ 6= P A 6= A. 2. Buď ϕ formule x = c, kde c je konstantní symbol. V právě kterých strukturách hA, cA i neplatí ϕ ani ¬ϕ? Řešení: Právě když |A| ≥ 2. 3. Buď ϕ formule P (x) → (∀x)R(x), kde P, R jsou různé unární predikátové symboly. V právě kterých strukturách A = hA, P A , RA i neplatí ϕ ani ¬ϕ? Řešení: Právě když ∅ 6= P A 6= A 6= RA . Zřejmě totiž: A 6|= ϕ ⇔ P A 6= ∅ a RA 6= A, A 6|= ¬ϕ ⇔ P A 6= A nebo RA = A. UF.1.4. Korektnost substituce. Buď ϕ formule (∃y)(x 6= y) s různými proměnnými x, y. Buď ϕ0 výsledek „nekorektní substituceÿ y do ϕ za volný výskyt x. Buď A struktura. Uvažujme tvrzení: Pro každé e : Var → A je A |= ϕ0 [e] ⇔ A |= ϕ[e(x/y[e])]. (∗) a) Uveďte, zda (∗) platí pro A = hN, +i, kde + je sčítání přirozených čísel. Řešení: Ne. b) Uveďte, zda (∗) platí pro A = h{0}, Ri, kde R = {h0, 0i}. Řešení: Ano. c) Právě pro které modely A = hAi (teorie čisté rovnosti) platí (∗)? Řešení: Právě pro A s A jednoprvkovým. UF.1.5. Axiomatizovatelnost. 1. Buď K = {hAi; velikost A je sudá nebo nekonečná} třída modelů jazyka L čisté rovnosti. Zjistěte, zda je K axiomatizovatelná, případně najděte její axiomatiku. Řešení: T = {¬„existuje právě 2k + 1 prvkůÿ; k ∈ N} axiomatizuje K. 2. Nechť T je teorie v jazyce L s rovností taková, že T má model a každý její model je nekonečný. Buď 0 < n ∈ N. Najděte L-teorii T 0 tak, aby M∞ (T 0 ) = M∞ (T ) a T 0 měla nějaké konečné modely, a to všechny: a) právě n-prvkové, b) právě n-prvkové nebo 2n-prvkové. Řešení: Buď T 0 = {ϕ ∨ ψ; ϕ ∈ T } s vhodným ψ. 3. Buď 0 < n ∈ N. Najděte teorii T v nějakém jazyce s rovností, která má nekonečné modely, nemá spočetný model, má konečné modely, všechny kardinality nejvýše n. Řešení: Buď L = hci ; i ∈ Ri s konstantními symboly ci a T0 buď L-teorie {ci 6= cj ; i, j ∈ R, i 6= j}; hledaná T je L-teorie {ϕ ∨ „existuje nejvýše n prvkůÿ; ϕ ∈ T0 }. 4. Buď L = hU i s rovností, přičemž U je unární relační symbol, 0 < n ∈ N a K = {hA, U A i; U A je nekonečná nebo nejvýše n-prvková} je třída L-struktur. Zjistěte, zda je K axiomatizovatelná, případně najděte její axiomatiku. Řešení: Nechť T0 je teorie V V L-teorie {(∃x0 , . . . , xm−1 )( i<j<m xi 6= xj & i<m U (xi )); 0 < m ∈ N}. Pro L-strukturu A platí: A |= T0 ⇔ |U A | ≥ ω. Buď χ sentence „existuje nejvýše n prvků x s U (x)ÿ. Pak T = {ϕ ∨ χ; ϕ ∈ T0 }, axiomatizuje K.
3 Izomorfní spektra. UF.1.6. Izomorfní spektra v jazyce hU, ci. Buď L = hU, ci, kde U je unární relační a c konstantní symbol. 1. Popište izomorfní spektrum L-teorie T = {U (c)}. Řešení: I(κ, T ) = |Cn ∩ κ|. Modely hκ, U 0 , c0 i, hκ, U 00 , c00 i teorie T jsou izomorfní, právě když h|U 0 |, |κ − U 0 |i = h|U 00 |, |κ − U 00 |i, přičemž |U 0 | ≥ 1. Všech různých dvojic h|U 0 |, |κ − U 0 |i s |U 0 | ≥ 1, U 0 ⊆ κ je právě |Cn ∩ κ|. Pro κ < ω je totiž |Cn ∩ κ| = κ. Pro κ ≥ ω je buď |U 0 | jakékoli kardinality < κ, nebo |U 0 | = κ a pak může být |κ − U 0 | jakékoli kardinality ≤ κ; takových možností je |Cn ∩ κ| + |Cn ∩ κ| = |Cn ∩ κ|. 2. Popište izomorfní spektrum L-teorie T = {(∃!x)U (x)}. Řešení: I(κ, T ) = 1 pro κ = 1 a 2 pro κ > 1. UF.1.7. Izomorfní spektrum jazyka spočetně konstant. Buď L = hci ii<ω , kde ci jsou konstantní symboly. 1. Pro L-strukturu A definujeme ekvivalenci E A na ω: A i E A j ⇔ cA i = cj . Buďte A, B dvě L-struktury téže velikosti. a) Platí: B A∼ (1) = B ⇔ E A = E B a |A − {cA i ; i < ω}| = |B − {ci ; i < ω}|. Speciálně je nejvýše kontinuum neizomorfních L-struktur dané kardinality. b) Jsou-li A, B konečné nebo nespočetné, platí: A∼ (2) = B ⇔ EA = EB . c) Najděte spočetné A, B, pro které (2) neplatí. 2. Pro κ ≥ 2 je I(κ, L) = 2ω . Návod: Užijte toho, že na ω je kontinuum různých ekvivalencí s λ třídami, když 2 ≤ λ ≤ ω. Řešení: Buď E ekvivalence na ω, λ(E) počet tříd E. Pro κ ≥ λ(E) deE E finujme L-strukturu κE = hκ, cE i ii<ω tak, aby platilo: ci = cj ⇔ i E j. Pak: 0 Jsou-li E, E 0 ekvivalence na ω tak κE ∼ = κE ⇔ E = E 0 . Tedy: jelikož je na ω kontinuum různých ekvivalencí s λ třídami, jakmile 2 ≤ λ ≤ ω, existuje alespoň kontinuum neizomorfních L-struktur kardinality κ (≥ 2) a dle (1) jich není více. UF.1.8. Teorie DiLO diskrétního lineárního uspořádání má pro každé κ ≥ ω právě 2κ neizomorfních modelů kardinality κ. Návod: Užijte toho, že pro každé κ ≥ ω je právě 2κ neizomorfních lineárních uspořádání s univerzem kardinality κ. Řešení: Pro ostré lineární uspořádání A = hA,
4 Základy dedukce. UF.1.9. Syntaktický důkaz bezespornosti teorie rovnosti v L. Nechť T je teorie rovnosti v L, tj. L-teorie s rovností bez mimologických axiomů. Buď d nový konstantní symbol. Pro L-formuli ϕ buď ϕ∗ formule, která se získá z ϕ odstraněním všech kvantifikací a nahrazením každého termu konstantním symbolem d. Pak ϕ∗ je výrok nad prvovýroky d = d, R(d, . . . , d), kde R je relační symbol z L. a) Je-li ϕ logický axiom nebo axiom rovnosti, kromě axiomu x = x, je ϕ∗ tautologie. Řešení: Pro logický axiom ϕ, který není axiomem rovnosti, to je jasné. Axiomy rovnosti ϕ kromě x = x přejdou na ϕ∗ tvaru d = d → d = d → · · · → (R(d, . . . , d) → R(d, . . . , d)) nebo d = d → d = d → ··· → d = d a pak ovšem v(ϕ∗ ) = 1. b) T ` ϕ ⇒ v(ϕ∗ ) = 1, jakmile v je ohodnocení uvedených prvovýroků takové, že platí v(d = d) = 1. Speciálně je T bezesporná. Návod: Užijte indukci na teorémech T . Řešení: Indukcí na teorémech T . Pro axiom ϕ to platí, neboť (x = x)∗ je d = d. Buď v(d = d) = 1. Nechť pro ψ, ψ → ϕ to platí. Pak 1 = v((ψ → ϕ)∗ ) = v(ψ ∗ → ϕ∗ ) a v(ψ ∗ ) = 1, tedy v(ϕ∗ ) = 1. Platí-li to pro ϕ, tak v(((∀x)ϕ)∗ ) = v(ϕ∗ ) = 1. UF.1.10. Dokazatelné, vyvratitelné, nezávislé a bezesporné formule. 1. Buďte P , R různé unární predikátové symboly. Zdůvodněte, zda formule ϕ je dokazatelná, vyvratitelná či nezávislá v logice, kde ϕ je a) P (x) c) (∀x, y)(P (x) → (R(x) → P (x)))
b) P (x) → R(x) d) (∃x)P (x)
Řešení: a) Nezávislá. h1, ∅i |= ¬ϕ, h1, 1i |= ϕ. b) Nezávislá. h2, ∅, 2i |= ϕ, h2, 2, ∅i |= ¬ϕ. c) Dokazatelná, neboť P (x) → (R(x) → P (x)) je tautologie. d) Nezávislá. h1, ∅i |= ¬ϕ, h1, 1i |= ϕ. 2. Najděte nějaké nezávislé sentence teorie čisté rovnosti, teorie lineárního uspořádání, teorie grup, teorie těles. 3. Nechť T ` (∃x)ϕ(x). Co lze říci o dokazatelnosti, vyvratitelnosti, nezávislosti, konzistenci ϕ, ¬ϕ vzhledem k T ? UF.1.11. Vlastnosti kvantifikátorů. 1. ` (∀x)(ϕ → ψ) → ((Qx)ϕ → (Qx)ψ), kde Q značí kvantifikátor. Návod: Užijte větu o konstantách. Řešení: Buďte T logické axiomy v jazyce rozšířeném o nové konstantní symboly ci ; ϕ(x, x1 /c1 , · · · ) resp. ψ(x, x1 /c1 , · · · ) označme ϕ0 (x) resp. ψ 0 (x) (konstanty substituujeme za všechny volné proměnné, kromě x). Pak T, (∀x)(ϕ0 → ψ 0 ) ` ϕ0 → ψ 0 , dle pravidla distribuce kvantifikátoru i T, (∀x)(ϕ0 → ψ 0 ) ` (Qx)ϕ0 → (Qx)ψ 0 a zbytek dá věta o dedukci a konstantách. 2. a) ` (∀x)ϕ → (∃x)ϕ. Řešení: Je ` (∀x)ϕ → ϕ, ` ϕ(x) → (∃x)ϕ; odtud pomocí pravidla tranzitivity implikace plyne dokazované. b) ` ϕ → (∀x)ϕ ⇔ ` (∃x)ϕ → (∀x)ϕ ⇔ ` (∀x)¬ϕ ∨ (∀x)ϕ. Řešení: Prvá ekvivalence. Implikace ⇒: ` ϕ → (∀x)ϕ ⇔ ` (∀x)(ϕ → (∀x)ϕ) ⇒ ` (∃x)ϕ → (∀x)ϕ. Implikace ⇐: ` (∃x)ϕ → (∀x)ϕ ⇒ ` (∀x)(ϕ → (∀x)ϕ) ⇒ ` ϕ → (∀x)ϕ. Užitím de Morganových vztahů plyne druhá ekvivalence.
5 3. a) ` (∀x)(∀x)ϕ ↔ (∀x)ϕ. Řešení: i) ` (∀x)(∀x)ϕ → (∀x)ϕ dává axiom substituce. ii) ` (∀x)ϕ → (∀x)(∀x)ϕ plyne z ` (∀x)ϕ → (∀x)ϕ pravidlem ∀-zavedení. Z i), ii) plyne ihned dokazované. b) ` (∃x)(∀x)ϕ ↔ (∀x)ϕ. Řešení: i) (∃x)(∀x)ϕ → (∀x)ϕ dává pravidlo ∃-zavedení. ii) (∀x)ϕ → (∃x)(∀x)ϕ plyne z platného vztahu ` ψ → (∃x)ψ. Z i), ii) plyne ihned dokazované. UF.1.12. Vytýkání kvantifikátorů - protipříklady. 1. 6` (∀x)(ϕ → ψ) → (ϕ → (∀x)ψ). Řešení: Buď A = hA, P A , RA i, kde P, R jsou unární predikátové symboly, a ∈ P A ⊆ RA ( A. Pak A |= (∀x)(P (x) → R(x)), A 6|= (P (x) → (∀x)R(x))[a]. Tedy A 6|= (∀x)(P (x) → R(x)) → (P (x) → (∀x)R(x)). 2. 6` (ϕ → (∀x)ψ) → (∀x)(ϕ → ψ). Řešení: Buď A = hA, P A , RA i, kde P, R jsou unární predikátové symboly, a ∈ A − P A , ∅ 6= P A 6⊆ RA . Pak A |= (P (x) → (∀x)R(x))[a], A 6|= (∀x)(P (x) → R(x)). Tedy A 6|= (P (x) → (∀x)R(x)) → (∀x)(P (x) → R(x)). 3. 6` (∃x)(ϕ → ψ) → (ϕ → (∃x)ψ). Řešení: Buď A = hA, P A , RA i, kde P, R jsou unární predikátové symboly, a ∈ P A ( A, RA = ∅. Pak A |= (∃x)(P (x) → R(x)) (protože existuje b ∈ A − P A ), A 6|= (P (x) → (∃x)R(x))[a] (protože je a ∈ P A ). Tedy A 6|= (∃x)(P (x) → R(x)) → (P (x) → (∃x)R(x)).
