Ahoj,
byla na vyber lehka a tezka otazka. Vzal jsem si tu lehkou:
T je jednoducha bezesporna extense Peanovy aritmetiky. Zduvodnete, jestli plati nasledujici tvrzeni:
1 - T ma silne nerozhodnutelny model.
2 - nepamatuju se
3 - A je modelem T. Potom Th(A) ma silne nerozhodnutelny model.
Doufam, ze jsem to napsal spravne. Myslim, ze todle byla jedna z mala veci, ktere jsem nevedel. Kolega mel priklad na teorii naslednika a dostal trojku. To bych nejspis taky dal. Dalsi kolega mel priklad na teorii grafu a ten mel ctyrku.
Zkouska 27. 1.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 22
- Registrován: 7. 2. 2008 21:33
- Typ studia: Informatika Bc.
Re: Zkouska 27. 1.
K bodu 3 jsem vycetl z textu "Teorie a jejich analyza" (1.7.2), ze libovolny model A teorie T je silne nerozhodnutelna struktura a ze to plyne z vety o nerozhodnutelnosti. Nevite nekdo, jak to z vety o nerozhodnutelnosti plyne?
-
- Matfyz(ák|ačka) level I
- Příspěvky: 20
- Registrován: 26. 1. 2010 14:28
- Typ studia: Informatika Mgr.
- Bydliště: Praha
Re: Zkouska 27. 1.
Nevím, zda jsou mé úvahy správné, pokud to někdo zkontrolujete, bude to fajn...Matfyz píše:K bodu 3 jsem vycetl z textu "Teorie a jejich analyza" (1.7.2), ze libovolny model A teorie T je silne nerozhodnutelna struktura a ze to plyne z vety o nerozhodnutelnosti. Nevite nekdo, jak to z vety o nerozhodnutelnosti plyne?
Pokud T je bezesporná extenze Robinsonovy aritmetiky Q (což jednoduchá bezesporná extenze Peanovy aritmetiky je), tak platí dle věty 4.3.4 (O nerozhodnutelnosti), že je T nerozhodnutelná. Také platí, že . A teď ještě potřebujeme ukázat, že každá teorie T', která má A za model, je nerozhodnutelná. Nechť tedy . Pak je jednoduché rozšíření T' o konečně axiomů. Tedy dle věty 4.3.6 je i T' nerozhodnutelná. Proto A je silně nerozhodnutelná.
A k příkladu ze zkoušky: Již víme, že A je silně nerozhodnutelná struktura. Dále platí, že . Proto jednak Th(A) je nerozhodnutelná a zřejmě má i silně nerozhodnutelný model - a to A.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 22
- Registrován: 7. 2. 2008 21:33
- Typ studia: Informatika Bc.
Re: Zkouska 27. 1.
Ahoj, myslím, že je to správně. Moc díky !Nevím, zda jsou mé úvahy správné, pokud to někdo zkontrolujete, bude to fajn...