Típuselkerülési tétel

A matematikai logikában, közelebbről a modellelméletben a szaturált modellek az összes elég „kis” számosságú X részhalmazból építkező X-típust megvalósítják. A fogalom ellenpontja bizonyos szempontból, amikor egy teljes típust ki nem elégítő modelleket keresünk. Ilyen modellek létezéséről szól a típuselkerülési tétel.

Típuselkerülés és megvalósítás

Ha egy T teljes elsőrendű elmélet, és ${\mbox{ }}_{\vartheta (x_{1},...,x_{n_{m}})}$ konzisztens T-vel, akkor

$T\cup \{(\exists {\overline {x}})\vartheta ({\overline {x}})\}$

konzisztens. Ha ráadásul ${\mbox{ }}_{\vartheta (x_{1},...,x_{n})}$ generálja ${\mbox{ }}_{\Gamma (x_{1},...,x_{n})}$ formulaosztályát, azaz minden ${\mbox{ }}_{\psi (x_{1},...,x_{n})\in \Gamma (x_{1},...,x_{n})}$ formulára

$T\models (\forall {\overline {x}})\vartheta ({\overline {x}})\rightarrow \psi ({\overline {x}})$,

akkor T minden modellje megvalósítja ${\mbox{ }}_{\Gamma (x_{1},...,x_{n})}$-t. Kontraponálva, ha a ${\mbox{ }}_{\Gamma (x_{1},...,x_{n})}$-t T elkerüli, akkor lokálisan is elkerüli. Ennek a viszonylag egyszerű megállapításnak a fordítottja is igaz (ráadásul nem is kell, hogy T teljes legyen).

Típuselkerülési tétel

Legyen T elsőrendű elmélet, minden m természetes számra ${\mbox{ }}_{\Gamma _{m}(x_{1},...,x_{n_{m}})}$ formulahalmaz T nyelvén. Ha

(1) T nyelve megszámlálható,

(2) T konzisztens és

(3) minden m-re T lokálisan elkerüli a ${\mbox{ }}_{\Gamma _{m}(x_{1},...,x_{n_{m}})}$ formulahalmazt, akkor

létezik T-nek olyan megszámlálható modellje, mely minden m természetes számra elkerüli a ${\mbox{ }}_{\Gamma _{m}(x_{1},...,x_{n_{m}})}$ formulahalmazt.

Bizonyítás

A konstrukció

Ha L a T nyelve, akkor konstruálni fogunk az L-nek olyan L⁺ és a T-nek olyan L⁺ feletti T⁺ bővítését, mely elmélet kanonikus modelljének L reduktuma a kívánt tulajdonságú. Megadunk véges elméletek olyan megszámlálható

$T_{0}\subseteq T_{1}\subseteq ...\subseteq T_{i}...$

láncolatát, melynek T-vel vett uniója a T⁺-t adja:

$T^{+}=T\cup \bigcup \limits _{i=0}^{\infty }T_{i}$

T⁺-t úgy fogjuk megkonstruálni, hogy teljesítse a következő kitételeket:

1) T⁺ teljes, azaz minden az L⁺ nyelven felírt mondat vagy negáltja T⁺-beli.

2) tetszőleges φ(x) egyváltozós formulára, ha a (∃x)φ(x) formula T⁺-beli, akkor legyen megszámlálhatóan végtelen sok különböző új c_k konstansjel, hogy φ(c_k) is T⁺-beli

3) minden m-re és minden ismétlésmentes L⁺\L-beli ${\mbox{ }}_{(c_{1},...,c_{n_{m}})}$ konstanssorozatra legyen olyan ${\mbox{ }}_{\gamma (x_{1},...,x_{n_{m}})\in \Gamma _{m}}$ formula, hogy

$\neg \gamma (c_{1},...,c_{n_{m}})\in T^{+}$

Fő gondolat

Ha T ezeket mutatja, akkor készen vagyunk. Legyen ugyanis ${\mbox{ }}_{\mathfrak {A}}$ a T⁺ kanonikus modellje. Ismert, hogy egy teljes elmélet a kanonikus modellje valóban modellje az elméletnek, ha minden egyváltozós, levezethető egzisztenciális (∃x)φ(x) formula esetén létezik a nyelvnek olyan t zárt termje, mellyel a φ(t) mondat levezethető. Ezt T⁺ tudja, mert 1) miatt teljes és 2) pont az előző kitételt állítja. Így ${\mbox{ }}_{\mathfrak {A}}$ a részelméletnek is modellje, ill. ${\mbox{ }}_{\mathfrak {A}}$ L reduktuma is modellje T-nek.

Belátjuk T elkerülési tulajdonságot. A modell univerzumának elemei (lényegében) zárt termek. De minden zárt t term esetén a (∃x)(x=t) egzisztenciális kijelentés márcsak logikai okokból is levezethető, így 2) miatt lesz végtelen sok c_k új konstans, amire c_k=t is T⁺-beli. Legyen m tetszőleges természetes szám. Az kell, hogy akárhogy is vegyünk ${\mbox{ }}_{(a_{1},...,a_{n_{m}})}$ véges sorozatot ${\mbox{ }}_{\mathfrak {A}}$ univerzumából, legyen olyan Γ_m-beli formula, mely hamis az ${\mbox{ }}_{(a_{1},...,a_{n_{m}})}$ értékelés szerint. Az előbbi, zárt termekre vonatkozó megjegyzés miatt ${\mbox{ }}_{(a_{1},...,a_{n_{m}})}$-t megnevezi egy ismétlésmentes konstanssorozat, ${\mbox{ }}_{(c_{1},...,c_{n_{m}})}$. Ehhez 3) miatt van ${\mbox{ }}_{\gamma (x_{1},...,x_{n_{m}})\in \Gamma _{m}}$ formula, hogy ${\mbox{ }}_{\neg \gamma (c_{1},...,c_{n_{m}})\in T^{+}}$. Világos, hogy akkor

$\gamma (x_{1},...,x_{n_{m}})$

nem lehet konzisztens T-vel, mert ${\mbox{ }}_{(a_{1},...,a_{n_{m}})}$ mutatja, hogy ${\mbox{ }}_{\mathfrak {A}}$-ban igaz a

$\neg (\exists (x_{1},...,x_{n_{m}}))\gamma (x_{1},...,x_{n_{m}})$

formula.

A „szakértős” konstrukció

Azt, hogy létezik T⁺, mely teljesíti 1), 2), 3)-at a W. Hodeges által papírra vetett, de a modellelmélészek körében közismert módszerrel látjuk be.

Kapcsolódó szócikkek

• Modellelmélet
• Típus (modellelmélet)
• Matematikai struktúra