od mifeet » 2. 2. 2010 16:31
Ahoj,
na dnešní zkoušce byla jako obvykle na výběr lehká a těžká otázka. Pokud vím, tak jsme tam byli dva ze šesti, kdo si vybral těžkou.
Vypadá to, že těžká otázka je obvykla analýza nějaké teorie. Na (možná řečnickou) otázku pana doc. Mlčka, jakou teorii bych měl dostat, jsem odpověděl, že nějakou pěknou jednoduchou - a dostal jsem skutečně tu nejjednodušší, tedy PE (teorie prázdného jazyka s rovností bez axiomů).
Pana Mlčka zajímala
- kompletnost - PE není kompletní, kompletace jsou právě extenze o axiomy "existuje právě n prvků" a "existuje nekonečně prvků"
- rozhodnutelnost - je rozhodnutelná, protože podle předchozího má
kompletaci
- modelová kompletnost - není modelově kompletní (to mi trochu napověděl), snadno se najde protipříklad - pro struktury A={0}, B={0,1} plati, že obě jsou modelem PE, A je podstruktura B, ale formule
v B platí, ale v A ne, tedy A není elementární podstruktura B
- eliminace kvantifikátorů - nemá (plyne z předchozího)
- izomorfní spektrum - I(k, PE) = 1 pro každé k
Potom se ještě ptal jakými axiomy vyjádřím "existuje nekonečně prvků" (pro každné n přidám
), jaká je definice 1-koexistence, co se změní, když se do PE přidá jeden konstantní symbol (nic, je to konzervativní extenze) a jestli je f-homogenita silnější než 1-koexistence (tipnul jsem si, že jo, snažil se tvářit dostatečně sebevědomě, aby se neptal proč a vyšlo to
).
Tohle stačilo na jedničku. U ostatních lidí byla myslím jedna dvojka, jedna čtyřka, zbytek trojky a jeden dělal zkoušku ještě po mně, takže nevím, jak dopadl.
Pokud trochu rozumíte tomu textu o analýze teorií, možná se vyplatí zkusit těžkou otázku. Některé "lehké" otázky mi připadaly těžší. Na druhou stranu jeden kamarád si na rovinu řekl o nějakou jednoduchou otázku z výrokové logiky, opravdu dostal jednoduchý příklad na počet pravdivých a nezávislých formulí dané teorie a stačilo to na trojku.
Tak hodně štěstí u dalších termínů
Ahoj,
na dnešní zkoušce byla jako obvykle na výběr lehká a těžká otázka. Pokud vím, tak jsme tam byli dva ze šesti, kdo si vybral těžkou.
Vypadá to, že těžká otázka je obvykla analýza nějaké teorie. Na (možná řečnickou) otázku pana doc. Mlčka, jakou teorii bych měl dostat, jsem odpověděl, že nějakou pěknou jednoduchou - a dostal jsem skutečně tu nejjednodušší, tedy PE (teorie prázdného jazyka s rovností bez axiomů).
Pana Mlčka zajímala
- kompletnost - PE není kompletní, kompletace jsou právě extenze o axiomy "existuje právě n prvků" a "existuje nekonečně prvků"
- rozhodnutelnost - je rozhodnutelná, protože podle předchozího má [latex]\Sigma_1[/latex] kompletaci
- modelová kompletnost - není modelově kompletní (to mi trochu napověděl), snadno se najde protipříklad - pro struktury A={0}, B={0,1} plati, že obě jsou modelem PE, A je podstruktura B, ale formule [latex](\exists x, y) x
eq y[/latex] v B platí, ale v A ne, tedy A není elementární podstruktura B
- eliminace kvantifikátorů - nemá (plyne z předchozího)
- izomorfní spektrum - I(k, PE) = 1 pro každé k
Potom se ještě ptal jakými axiomy vyjádřím "existuje nekonečně prvků" (pro každné n přidám [latex]\exists x_1,\ldots, x_n (\textstyle{\bigwedge_{0<i<j\leq n}} x_i
eq x_j)[/latex]), jaká je definice 1-koexistence, co se změní, když se do PE přidá jeden konstantní symbol (nic, je to konzervativní extenze) a jestli je f-homogenita silnější než 1-koexistence (tipnul jsem si, že jo, snažil se tvářit dostatečně sebevědomě, aby se neptal proč a vyšlo to :) ).
Tohle stačilo na jedničku. U ostatních lidí byla myslím jedna dvojka, jedna čtyřka, zbytek trojky a jeden dělal zkoušku ještě po mně, takže nevím, jak dopadl.
Pokud trochu rozumíte tomu textu o analýze teorií, možná se vyplatí zkusit těžkou otázku. Některé "lehké" otázky mi připadaly těžší. Na druhou stranu jeden kamarád si na rovinu řekl o nějakou jednoduchou otázku z výrokové logiky, opravdu dostal jednoduchý příklad na počet pravdivých a nezávislých formulí dané teorie a stačilo to na trojku.
Tak hodně štěstí u dalších termínů ;)