Elementární ekvivalence - Elementary equivalence

v teorie modelů, pobočka matematická logika, dva struktur M a N stejné podpis σ se nazývají elementárně ekvivalentní pokud uspokojí to samé první objednávka σ- věty.

Li N je spodní konstrukce z M, člověk často potřebuje silnější kondici. V tomto případě N se nazývá základní konstrukce z M pokud každá první objednávka σ-vzorec φ(A₁, …, A_n) s parametry A₁, …, A_n z N je pravda v N právě když je to pravda vM.Li N je základní substruktura M, pak M se nazývá elementární rozšíření zN. An vkládání h: N → M se nazývá základní vložení z N do M -li h(N) je základní substrukturaM.

Spodní konstrukce N z M je základní právě tehdy, když prochází Tarski – Vaughtův test: každý vzorec prvního řádu φ(X, b₁, …, b_n) s parametry v N který má řešení v M také má řešení vN při hodnocení vM. Lze dokázat, že dvě struktury jsou elementárně ekvivalentní s Hry Ehrenfeucht – Fraïssé.

Elementárně ekvivalentní struktury

Dvě struktury M a N stejného podpisuσ jsou elementárně ekvivalentní pokud každá věta prvního řádu (vzorec bez volných proměnných) skončilaσ je pravda v M právě když je to pravda v N, tj. pokud M a N mít stejné kompletní teorie prvního řádu M a N jsou elementárně ekvivalentní, píše se M ≡ N.

První objednávka teorie je kompletní tehdy a jen tehdy, jsou-li jakékoli dva jeho modely elementárně ekvivalentní.

Zvažte například jazyk s jedním binárním relačním symbolem '<'. Model R z reálná čísla s obvyklým pořadím a modelem Q z racionální čísla se svým obvyklým řádem jsou elementárně ekvivalentní, protože oba interpretují '<' jako neomezenou hustotu lineární řazení. To je dostatečné k zajištění elementární ekvivalence, protože teorie neomezených hustých lineárních uspořádání je úplná, jak ukazuje Łoś – Vaughtův test.

Obecněji řečeno, každá teorie prvního řádu s nekonečným modelem má neizomorfní, elementárně ekvivalentní modely, které lze získat pomocí Löwenheim – Skolemova věta. Tak například existují nestandardní modely z Peano aritmetika, které obsahují jiné objekty než jen čísla 0, 1, 2 atd., a přesto jsou elementárně ekvivalentní standardnímu modelu.

Elementární substruktury a elementární rozšíření

N je základní konstrukce z M -li N a M jsou stejné struktury podpis  σ takové, že pro všechny prvního řádu σ-formule φ(X₁, …, X_n) s volnými proměnnými X₁, …, X_na všechny prvky A₁, …, A_n zN, φ(A₁, …, A_n) drží se N jen když to drží M:

N ${ displaystyle models}$ φ(A₁, …, A_n) iff M ${ displaystyle models}$ φ(A₁, …, A_n).

Z toho vyplývá, že N je spodní konstrukce z M.

Li N je spodní konstrukce z M, pak oba N a M lze v podpisu interpretovat jako struktury σ_N skládající se z σ společně s novým konstantním symbolem pro každý prvekN. Pak N je základní substruktura M kdyby a jen kdyby N je spodní konstrukce z M a N a M jsou elementárně ekvivalentní jako σ_N-struktury.

Li N je základní substruktura M, píše jeden N ${ displaystyle preceq}$ M a říká to M je elementární rozšíření z N: M ${ displaystyle succeq}$ N.

Dolů Löwenheim – Skolemova věta dává spočítatelnou základní strukturu pro jakoukoli nekonečnou strukturu prvního řádu v maximálně spočitatelném podpisu; vzestupná Löwenheim – Skolemova věta dává elementární rozšíření jakékoli nekonečné struktury prvního řádu libovolně velké mohutnosti.

Tarski – Vaughtův test

The Tarski – Vaughtův test (nebo Kritérium Tarski – Vaught) je nezbytnou a dostatečnou podmínkou pro spodní stavbu N struktury M být základní substrukturou. Může to být užitečné pro konstrukci základní substruktury velké struktury.

Nechat M být strukturou podpisu σ a N spodní stavba M. Pak N je základní substruktura M právě když pro každý vzorec prvního řádu φ(X, y₁, …, y_n) přes σ a všechny prvky b₁, …, b_n z N, pokud M ${ displaystyle models}$ ${ displaystyle existuje}$X φ(X, b₁, …, b_n), pak existuje prvek A v N takhle M ${ displaystyle models}$ φ(A, b₁, …, b_n).

Základní vložení

An základní vložení struktury N do struktury M stejného podpisu σ je mapa h: N → M takové, že pro každou první objednávku σ-vzorec φ(X₁, …, X_n) a všechny prvky A₁, …, A_n zN,

N ${ displaystyle models}$ φ(A₁, …, A_n) právě tehdy M ${ displaystyle models}$ φ(h(A₁), …, h(A_n)).

Každé základní vložení je a silný homomorfismus a jeho obraz je základní podstrukturou.

Elementární vložení jsou nejdůležitější mapy v teorii modelů. v teorie množin, elementární vložení, jejichž doménou je PROTI (vesmír teorie množin) hraje důležitou roli v teorii velcí kardinálové (viz také Kritický bod ).

Reference

• Chang, Chen Chung; Keisler, H. Jerome (1990) [1973], Teorie modelu„Studies in Logic and the Foundations of Mathematics (3. vyd.), Elsevier, ISBN  978-0-444-88054-3.
• Hodges, Wilfrid (1997), Kratší teorie modelů, Cambridge: Cambridge University Press, ISBN  978-0-521-58713-6.
• Monk, J. Donald (1976), Matematická logika, Maturitní texty z matematiky, New York • Heidelberg • Berlín: Springer Verlag, ISBN  0-387-90170-1