MA007 — zadání páté sady
Příklad 1 [2 body]
Zadání Uvažme jazyk C — {R} s rovností, kde i? je binární predikátový symbol. Dále uvažme následující teorii T s jazykem C:
T    =    {VxVy(R(x,y) -^\/z(R(x,z)     z = y))}.
Nyní uvažme jazyk Ľ! — C U {/} s rovností, kde / je unární funkční symbol, a teorii T' s tímto jazykem zadanou následovně:
T'    = {\fx\fy(R(x,y)^f(y)^x),\fx\fy(x^y^f(x)^f(y))}.
Rozhodněte a dokažte, zda:
a) T' je rozšířením teorie T,
b) T' je konzervativním rozšířením teorie T.
Řešení Teorie T' je rozšíření teorie T, které ovšem není konzervativní.
Nejprve ukážeme, že T' je rozšířením teorie T. Zřejmě jazyk teorie T' obsahuje jazyk teorie T, stačí tedy ukázat, že T' h \/x\/y (R(x, y) —> \/z(R(x, z) —> z — y)). Označme tuto formuli (jediný axiom teorie T) jako p. Dle věty o úplnosti stačí ukázat, že T' \= p.
Sporem předpokládejme, že existuje model M. teorie T' takový, že M. ^ p. Z Tarského definice pravdivosti plyne, že musí existovat trojice individuí a, b, c v nosiči M. takových, že (a, b) g Rm, («, c) g Rm & b ^ c. Protože M. |= T', musí platit /mÍP) — cl a /mÍ0) — a (vynucuje to první axiom teorie T"). To ovšem není možné, neboť v každém modelu teorie T' se / realizuje jako injektivní funkce (vynucuje to druhý axiom teorie T"), spor.
Nyní ukážeme, že T' není konzervativním rozšířením teorie T. Dle definice musíme najít formuli ip jazyka C takovou, že T Y- ip a T' h ip. Uvažme formuli ijj — VxVyVz ((iž(x, z) A R(y, z)) —> x — y). Neformálně řečeno, formule ip říká, že R se má realizovat jako relace, jejíž inverze je parciální funkce. Dle vět o korektnosti, resp. o úplnosti, stačí ukázat, že T ^ tp, resp. T' \= tp.
Nejprve ukážeme, že T ^ tp. Uvažme realizaci Ad\ jazyka C danou následovně:
• jejím nosičem je soubor M — {0,1},
. RMl ={(0,0), (1,0)}.
Pak zřejmě Ad\ \= T (neformálně řečeno, ip říká, že R se musí realizovat jakožto parciální funkce) avšak M.1 ^ tp (neboť RJ^ — {(0, 0), (0,1)} není parciální funkce). Tedy T ^ ip.
Nyní ukážeme, že T' |= ip. Sporem předpokládejme, že existuje model M.2 teorie T' takový,1 že A42 ^ i/1- Z Tarského definice pravdivosti plyne, že existují prvky a, b, c v nosiči realizace M.2 takové, že (a, c) g Rm2i (b, c) g Rm2 a zároveň a ^ b. Pak ale musí platit Jm2 (c) — a a m2 (c) — & (vynucuje to první axiom teorie T"), což není možné, neboť Jm2 je funkce, spor. Tím je důkaz hotov.
1Tj. M.2 je realizace jazyka C'
1
Příklad 2 [3 body]
Zadání Uvažme jazyk L — {P1, P2, P3,... } s rovností, kde pro libovolné i > 1 je P1 unární predikátový symbol. (Zejména tedy jazyk C obsahuje nekonečně mnoho predikátových symbolů.)
a) Zadejte splnitelnou teorii T s jazykem C takovou, že pro každý model M. teorie T platí
oo
f^l Pm Je nekonečný soubor individuí.
i=l
b) Dokažte, že neexistuje žádná teorie T s jazykem C taková, že pro libovolnou realizaci M. jazyka Ĺ, platí
oo
Á4 |= T    •<=>        PlM je nekonečný soubor individuí.
i=l
Řešení     a) Uvažme například teorii
T={v?„,Vn |neN}, kde pro libovolné n e N máme
Ifin — 3x1 . . . 3xn       f\      Xi ^ Xj
l<i<j<n
Tjjn=VxPn(x).
Neformálně řečeno, formule pn vynucuje alespoň n-prvkový nosič a formule ij}n vynucuje, aby se predikátový symbol Pn realizoval jako soubor všech prvků v nosiči. Pak každý model M. teorie T má nekonečný nosič a všechny unární predikátové symboly jazyka C se v tomto modelu realizují jako soubory rovné tomuto nekonečnému nosiči. V takové realizaci je průnik Hi^i Pm °pět roven celému nosiči, obsahuje tedy nekonečně mnoho individuí.
b) Mějme libovolnou teorii T takovou, že každá realizace M. jazyka C, v níž je P%m nekonečným souborem individuí, je modelem teorie T. Ukážeme, že pak níže uvedená realizace M1 jazyka C, v níž je        Pjví' prázdným souborem, je rovněž modelem teorie T. Tím bude vyloučena existence teorie T uvedené v zadání.
Realizace M1 je dána následovně:
• jejím nosičem je soubor všech přirozených čísel N,
• pro libovolné n g N je PM, — {n, n + 1,.. . } — {m E N | m > n}.
Zřejmě vskutku Hi^i P%m' Je prázdný soubor individuí.
Nechť ip g T je libovolná formule. Protože ip je konečné slovo, vyskytuje se v ní pouze konečně mnoho predikátových symbolů jazyka C Existuje tedy k e N takové, že ve p se nevyskytuje symbol Pn pro žádné n > k. Dále realizace symbolů, které se ve formuli nevyskytují, zřejmě nemají žádný vliv na to, zda je formule v dané realizaci jazyka C pravdivá, či nikoliv. Máme tedy následující:
2
Tvrzení Nechť Ad" je libovolná realizace jazyka C taková, že M' — M" a PJ^, — P]^„ pro všechna n < k. Pak Ad' |= p právě když Ad" |= y>.
Uvažme nyní realizaci Af" jazyka £ s nosičem N takovou, že
• Pjh„ — {n, n + 1, ... } — {to € N \ m > n}, jestliže n < k;
• Pj^„ = {k, k + 1,... } — {to e N | m > k}, jestliže n> k.
Pak platí Hi^i Pm" — {^j k + !;■■■}; coz je nekonečný soubor a tedy dle předpokladu Af" |= p. Ovšem v Ad" se všechny predikátové symboly s indexem < k realizují stejným způsobem, jako v Ad'. Z výše uvedeného tvrzení tedy dostáváme Ad' \= p>. Protože ip g T byla zvolena libovolně, dostáváme Ad' |= T, což jsme chtěli ukázat.
3