Zkouška 17.2.2010

Tak dneska jsem měl štěstí!

Moje otázky, vybral jsem lehkou:

1. počet nezávislých výroků v teorii T

2. počet vyvratitelných výroků v teorii T

3. výrok a, spočtěte počet výroků b: v T není dokazatelné a -> b a v T není dokazatelné b -> -a (to se převede na a -> -b) a pak se počítá počet nezávislých teorií v T,a

Pak se mě zeptal na pár definic a vpohodě (trapas byl, když jsem se zamotal v definici dokazatelnosti)

Lehka otazka-
Prazdna teorie v jazyce <c> kde c je konstantni symbol
a) je kompletni
b) je omega-kategoricka (omega je takove to kulate W, doufam)
c) je rozhodnutelna?

reseni: a) neni, dokazeme existenci 1prvkoveho a dvouprvkoveho modelu a formuli pro vsechna x( x=c)
b) je, model <N,c> je isomorfni se vsemi modely velikosti omega
c) je, protoze ma nejakou komletaci, tohle jsem nevedel uplne presne, spis jsem tak tusil, takze mi nakonec rekl, "Moc jste to teda neumel, budte rad za trojku" a poslal me na 3denni prazdniny:D

Jinak GL pri tahu otazky. Co jsem slysel, tak jeden kolega dostal podobnou otazku jako ja, ale byla pro 3 ruzne teorie, tedy je to opravdu docela loterie.

Též lehká otázka. Dostal sem uspořádání racionálních čísel, $\langle\mathbb{Q}, \le\rangle$; otázky byly: 1) Jaké všechny jednoprvkové podmnožiny $\mathbb{Q}$ lze definovat v $\langle\mathbb{Q}, \le\rangle$ bez parametrů? 2) Jaké všechny podmnožiny $\mathbb{Q}^2$ lze definovat v $\langle\mathbb{Q}, \le\rangle$ bez parametrů?

Přičemž množina je definovaná bez parametrů v $\mathcal{A}$ s jazykem L, když je to množina $\left\{ \langle a_1, a_2, \ldots, a_n \rangle \;:\; \mathcal{A} \models \varphi[a_1, a_2, \ldots, a_n] \right\}$ pro nějakou $\varphi \in \mathrm{Fm}_L$.

Po definici definované množiny už nebyly moje znalosti tak úžasné. Vypsal sem mu nějaké množiny, co se daly definovat z nějakých formulí jako $a \le b$, $a < b$, $a e b$, atd., ale neměl sem důkaz -- ani mě žádný nenapadal --, že to jsou množiny všechny. Při pokecu s Mlčkem sem se dozvěděl, že na to du „překvapivě správně“, neboť $\langle\mathbb{Q}, \le\rangle$ je model DeLO, která má eliminaci kvantifikátorů -- tedy by zřejmě stačilo vzít všechny booleovské kombinace atomických formulí a z nich definovat množiny, pak by to měly být množiny všechny. (Pokud sem Mlčka pochopil správně.)

Pak se mě tedy zeptal, jak bych dokázal, že DeLO má eliminaci kvantifikátorů -- to sem nevěděl, tak se mě zeptal, co je eliminace kvantifikátorů -- na to sem mu taky nedal moc přesnou definici. To ho zřejmě nepotěšilo, tak se mě zeptal na větu o úplnosti, od tý pokračoval otázkou, „Co znamená $T \models \varphi$“ a „Co znamená $T \vdash \varphi$“. To sem mu odpověděl bez problémů. Od posledně zmíněného se přehoupl k definici důkazu, kterou sem mu též řekl -- od důkazu sme se dostali k logickým axiomům, kde sem mu špatně řekl axiom substituce (dal sem kvantifikátor, kam nepatří).

To už se mu opravdu nelíbilo, po řečnické otázce „Eliminaci kvantifikátorů neumíte, definice neumíte, logické axiomy neumíte, co vy teda umíte?“ mě nechal přeškrtat ten špatnej kvantifikátor v axiomu substituce a dal mi otázku z výrokové logiky (potom, co sem se musel zatvářit, že ji umim). Řekl mi, že $|\mathbb{P}| = l \in \mathbb{N}$ a teorie T má k dokazatelných výroků -- otázka tedy byla, kolik má modelů. Použil sem vzoreček $k = 2^{2^l - |M(T)|}$ a pak sem se procvičil v počítání s logaritmy. (Úspěšně.) Dodatečná otázka byla, „Co když ta teorie bude kompletní?“ -- zprávně zodpověděv, dostal sem trojku a byl propuštěn.

Je to sranda. Připadá mi, že doc. Mlček je poněkud agresivnější ve snaze vypáčit ze studenta aspoň něco, aby mu mohl dát trojku, než P. Pajas, který mě vyrazil minule. (A taky o poznání cyničtější.)

Hodně štěstí těm, co dou příští týden.