# Zkouška 4.1.2013 (předtermín)

<{ForumPost(poster="LordG", timestamp=2013-01-04 20:36:51)}>
Zadání:  
  
1. (VL)  
A) P = {p, q, r} P-teorie T má axiomatiku {p, q->r}.  
a) Napište formuli v DNF axiomatizující T  
b) Napište JKE teorie T  
  
B) P je nekonečná množina prvovýroků. T je teorie s axiomy {not(p) nebo not(q); p, q jsou různé prvovýroky }  
a) Jak vypadají modely?  
b) Je T konečně axiomatizovatelná?  
c) Je množina K P-modelů, v nichž alespoň dva výroky mají pravdivé ohodnocení, konečně axiomatizovatelná?  
  
2. (PL)  
A) Jazyk L = <F>.  
     Struktura A = <{0, 1, 2, 3}, +>; + je sčítání modullo 4. T je L-teorie s axiomem (existuje y)(pro každé x)(F(x, y) =/= x)  
a) Platí A |= T?  
b) Počet různých automorfismů na A  
c) Lze bezparametricky definovat množinu {2}?  
d) Velikost množiny Df1(0, A)  
e)   
  
B)  
a) je T otevřeně axiomatizovatelná?  
b) Jazyk L' = L u {c}, T* je L'-teorie s axiomatikou {F(x,c) =/= c}. Je T* otevřená konzervativní extenze T?  
c) Možná, že jsem do b) omylem napsal zadání b) a c). Nepamatuji se.  
  
3. (PL)  
A)  
T teorie ostrého lineárního uspořádání, navíc s rozšířením jazyka o konstanty c<sub>0</sub> a c<sub>1</sub> a axiomy  
chi<sub>0</sub>: c<sub>0</sub> =/= c<sub>1</sub>  
chi<sub>1</sub>: c<sub>0</sub> <= x <= c<sub>1</sub>  
a) I(n, T) pro 2 <= n € N  
b)  
i) má T algebraický prvomodel?  
ii) má T prvomodel?  
c) Je T kompletní?  
d) Je T otevřeně axiomatizovatelná  
e) \[NESOUVISÍ S PŘEDCHOZÍM] interval \[-2, 2], na něm {1 +- (1/(2^n)), n€N} u {-1 +- (1/(2^n)), n€N} (polopaticky, vezme se 1 / 2^n, a to se přičte a odečte od 1 a -1 a vzniknou dvě množiny bodů, které zleva a zprava konvergují k 1 a -1).  
Má se rozhodnout, jestli je {0} množina definovatelná bezparametrickou formulí ve struktuře A = <\[VÝŠE POPSANÁ MNOŽINA], <= >, kde <= je obvyklé uspořádání čísel.  
  
B)  
a) Je T rozhodnutelná?  
b) Kolik má T rozhodnutelných jednoduchých extenzí?  
  
-- možná se někde pletu, 2 A e a 2 B c si nepamatuji --  
Řešení:  
1 A   
a) (p & non q & non r) nebo (p & non q & r) nebo (p & q & r); plyne bezprostředně z množiny modelů, obecně v je model T, jestliže v(p) = 1 a v(q) <= v(r)  
b) Teorie jsou ty, které mají jako axiomatiku jednoprvkovou množinu jednoho z disjunktů formule z a). To je proto, že extenze T musí být její podmnožina a kompletní teorie má jediný model.  
  
1B  
a) Modely mají nejvýše jeden prvovýrok ohodnocen pravdou. To se dokáže snadno: má-li nějaké v pro p =/= q v(p) = v(q) = 1, potom neplatí axiom (not p nebo not q) a tudíž takové v není modelem T.  
b) NE. Dokazatelné sporem: pokud je konečně axiomatizovatelné, pak se v konečné axiomatice vyskytuje konečně mnoho prvovýroků. Tedy tam jistě některé nebudou a taková axiomatika o jejich hodnocení nebude nic říkat.  
c) NE. Množina K je komplement M(T). Kritérium říká, že K i -K jsou axiomatizovatelné <=> K je konečně axiomatizovatelné. V b) je dokázáno, že M(T) není. Takže vezmeme K := M(T), -K := naše množina K a hotovo.  
  
2A  
a) ANO. Stačí uspokojit ten jediný axiom. Stačí za x dosadit cokoliv kromě 0 a vyjde to (.. a pokud nevyjde, tak jsem tu axiomatiku napsal špatně  :D )  
b) 2. Jde o to, že 1 a 3 se chovají "stejně" (1+0 = 1, 3+0 = 3, 1+2 = 3, 3+2 = 1, 1+3 = 3+1 = 0, 1+1 = 2, 3+3 = 2), takže izomorfismy buď prohodí nebo neprohodí 1 a 3  
c) ANO. Formule x+x = 0 a (pro každé y) y+x =/= y. (První konjunkt dá {0, 2}, druhý vyloučí nulu).  
d) 8 (=2<sup>3</sup>). Mohu definovat "atomické" množiny {0}, {2}, {1,3} (jak, to naznačuje c) ). Booleovskými úpravami pak i kombinace těchto tří.  
  
2B  
a) NE. Podle kritéria T je ot. axiomatizovalná <=> (A podmnožina B |= T => A |= T). Stačí za B vzít naše A a za A vzít strukturu < {0}, +>. Ta není modelem teorie T.  
b) ANO. Jde o Skolemovu variantu toho jediného axiomu. Ta je s ním podle nějaké věty ekvivalentní. A je otevřená, tzn ta T* je otevřená.  
  
3A  
a) 1. Mezi c<sub>0</sub> a c<sub>1</sub> je v modelu o n prvcích vždy n-2 prvků, což máme zařízeno axiomy, a o uspořádání ostatních prvků axiomy nic jiného neříkají. Takže jsou modely stejné velikosti izomorfní.  
b), c), d) Řešil jsem trochu jiné zadání, což mi bylo u zkoušky odpuštěno, ale řešení proto nevím.  
e) NE. Poslouží to slavné kritérium o definovatelnosti množiny.  
  
3B  
a) ANO. Má rekurzivní kompletaci.  
b) omega. Že jich je alespoň omega dokazuje to, že každá teorie T<sub>n</sub>, rozšiřující T axiomem "existuje právě n prvků", spolu navíc s T<sub>nekonečno</sub> ("existuje nekonečno prvků") je kompletní a má rekurzivní axiomatiku, tedy je rozhodnutelná. Že jich není víc, to nechám na chytřejších, aby vysvětlili.
<{/ForumPost}>

<{ForumPost(poster="LordG", timestamp=2013-01-04 20:38:31)}>
..dále k průběhu: tato písemka byla na hodinu, potom se doc. Mlček s panem Glivickým vrhli na nás a postupně to s námi s jedním za druhým konzultovali. Dlužno podotknout, že p. Glivický byl velice shovívavý, jak je z mého výše popsaného řešení patrné :) . Celá zkouška zabrala necelou hodinu a půl.
<{/ForumPost}>

<{ForumPost(poster="Locky", timestamp=2013-01-12 19:29:56)}>
Koukám, že test už má i na stránkách:  
[http://ktiml.mff.cuni.cz/~mlcek/ET-1_12.pdf](http://ktiml.mff.cuni.cz/~mlcek/ET-1_12.pdf)

*Attachments:*

- *[ET-1_12.pdf](/Forum%20archiv/Attachments/5489_03b5143f999bb60defe4744c8c071e62)*

<{/ForumPost}>