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   ϑ ( x 1 , . . . , x n m ) {\displaystyle {\mbox{ }}_{\vartheta (x_{1},...,x_{n_{m}})}} konzisztens T-vel, akkor

T ∪ { ( ∃ x ¯ ) ϑ ( x ¯ ) } {\displaystyle T\cup \{(\exists {\overline {x}})\vartheta ({\overline {x}})\}}

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

T ⊨ ( ∀ x ¯ ) ϑ ( x ¯ ) → ψ ( x ¯ ) {\displaystyle T\models (\forall {\overline {x}})\vartheta ({\overline {x}})\rightarrow \psi ({\overline {x}})} ,

akkor T minden modellje megvalósítja   Γ ( x 1 , . . . , x n ) {\displaystyle {\mbox{ }}_{\Gamma (x_{1},...,x_{n})}} -t. Kontraponálva, ha a   Γ ( x 1 , . . . , x n ) {\displaystyle {\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   Γ m ( x 1 , . . . , x n m ) {\displaystyle {\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   Γ m ( x 1 , . . . , x n m ) {\displaystyle {\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   Γ m ( x 1 , . . . , x n m ) {\displaystyle {\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 ⊆ T 1 ⊆ . . . ⊆ T i . . . {\displaystyle T_{0}\subseteq T_{1}\subseteq ...\subseteq T_{i}...}

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

T + = T ∪ ⋃ i = 0 ∞ T i {\displaystyle 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 ck konstansjel, hogy φ(ck) is T+-beli

3) minden m-re és minden ismétlésmentes L+\L-beli   ( c 1 , . . . , c n m ) {\displaystyle {\mbox{ }}_{(c_{1},...,c_{n_{m}})}} konstanssorozatra legyen olyan   γ ( x 1 , . . . , x n m ) ∈ Γ m {\displaystyle {\mbox{ }}_{\gamma (x_{1},...,x_{n_{m}})\in \Gamma _{m}}} formula, hogy

¬ γ ( c 1 , . . . , c n m ) ∈ T + {\displaystyle \neg \gamma (c_{1},...,c_{n_{m}})\in T^{+}}

Fő gondolat

Ha T ezeket mutatja, akkor készen vagyunk. Legyen ugyanis   A {\displaystyle {\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   A {\displaystyle {\mbox{ }}_{\mathfrak {A}}} a részelméletnek is modellje, ill.   A {\displaystyle {\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 ck új konstans, amire ck=t is T+-beli. Legyen m tetszőleges természetes szám. Az kell, hogy akárhogy is vegyünk   ( a 1 , . . . , a n m ) {\displaystyle {\mbox{ }}_{(a_{1},...,a_{n_{m}})}} véges sorozatot   A {\displaystyle {\mbox{ }}_{\mathfrak {A}}} univerzumából, legyen olyan Γm-beli formula, mely hamis az   ( a 1 , . . . , a n m ) {\displaystyle {\mbox{ }}_{(a_{1},...,a_{n_{m}})}} értékelés szerint. Az előbbi, zárt termekre vonatkozó megjegyzés miatt   ( a 1 , . . . , a n m ) {\displaystyle {\mbox{ }}_{(a_{1},...,a_{n_{m}})}} -t megnevezi egy ismétlésmentes konstanssorozat,   ( c 1 , . . . , c n m ) {\displaystyle {\mbox{ }}_{(c_{1},...,c_{n_{m}})}} . Ehhez 3) miatt van   γ ( x 1 , . . . , x n m ) ∈ Γ m {\displaystyle {\mbox{ }}_{\gamma (x_{1},...,x_{n_{m}})\in \Gamma _{m}}} formula, hogy   ¬ γ ( c 1 , . . . , c n m ) ∈ T + {\displaystyle {\mbox{ }}_{\neg \gamma (c_{1},...,c_{n_{m}})\in T^{+}}} . Világos, hogy akkor

γ ( x 1 , . . . , x n m ) {\displaystyle \gamma (x_{1},...,x_{n_{m}})}

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

¬ ( ∃ ( x 1 , . . . , x n m ) ) γ ( x 1 , . . . , x n m ) {\displaystyle \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

  • Matematika Matematikaportál • összefoglaló, színes tartalomajánló lap