Zkouska 27. 1.

Matfyz wrote: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?

Nevím, zda jsou mé úvahy správné, pokud to někdo zkontrolujete, bude to fajn...

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 $\mathcal A \models Q$. A teď ještě potřebujeme ukázat, že každá teorie T', která má A za model, je nerozhodnutelná. Nechť tedy $\mathcal A \models T'$. Pak $T' \cup Q$ 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 $\mathcal A \models Th(A)$. Proto jednak Th(A) je nerozhodnutelná a zřejmě má i silně nerozhodnutelný model - a to A.