初等同値性のソースを表示

[[数理論理学]]の一分野である[[モデル理論]]において、同じ[[シグネチャ(数理論理学)|シグネチャ]] ''σ'' の2つの[[構造(数理論理学)|構造]] ''M'' と ''N'' が同じ[[一階述語論理|一階]][[文(数理論理学)|''σ''-文]]を満たすとき、''M'' と ''N'' は'''初等的同値'''であるという。

''N'' が ''M'' の部分構造であるとき、さらに強い条件について考える場合がある。''N'' が ''M'' の'''初等部分構造''' であるとは一階 ''σ''-式 ''φ''(''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>''n''</sub>)（ただしパラメータ ''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>''n''</sub> は全て ''N'' の元）が ''N'' で真であることと ''M'' で真であることが同値であること。''N'' が ''M'' の初等部分構造であるとき、''M'' は ''N'' の '''初等拡大''' という。[[埋め込み (数学)|埋め込み]] ''h'':&nbsp;''N''&nbsp;→&nbsp;''M'' は  ''h''(''N'') が ''M'' の初等部分構造であるとき、''N'' から ''M'' への '''初等埋め込み'''と呼ぶ。

''M'' の部分構造 ''N'' が初等的であるのは、それが'''タルスキ–ヴォートテスト'''を通ることと同値である: すなわち ''x'' を未知数とする任意の1階の式 ''φ''(''x'',&nbsp;''b''<sub>1</sub>,&nbsp;…,&nbsp;''b''<sub>''n''</sub>)（ただし、パラメータは全て ''N'' の元）が ''M'' に解を持つならいつでも ''N'' でも解を持つこと。また、二つの構造の初等同値性を示すには[[Ehrenfeucht–Fraïssé games]]を用いた判定法もある。

初等埋め込みは[[rank-into-rank]]基数を含む[[巨大基数]]研究に用いられる。

==初等同値な構造==

同じシグネチャ ''σ'' の構造 ''M'' と ''N'' が'''初等的同値'''であるとは、自由変数を持たない ''σ'' 上の一階文が ''M'' で真であることと ''N'' で真であることが同値であることである。すなわち、''M'' と ''N'' が同じ[[complete theory|完全]]な一階理論を持つことである。''M'' と ''N'' が初等的同値であることを ''M''&nbsp;≡&nbsp;''N'' で表すことがある。

一階の[[理論 (数理論理学)|理論]]が完全であることは、その理論のいかなる二つのモデルも初等的同値であることと、同値である。

例えば、一つの二項関係記号 '<' のみを持つ言語を考える。通常の順序を入れた[[実数]]全体の集合 '''R''' と [[有理数]]全体の集合 '''Q''' は初等的同値である。というのも、両方とも '<' は非有界の稠密[[線型順序]]であるからである。それで初等同値性が分かるのは、[[ウォッシュ-ヴォートテスト]]で示されるように、[[稠密順序|非有界稠密線型順序]]の理論が完全であるためである。

より一般に、無限モデルを持ついかなる一階理論にも、同型でない初等同値なモデルが存在する。このことは[[レーヴェンハイム-スコーレムの定理]]から得られる。例えば、[[ペアノ算術]]の[[算術の超準モデル|超準モデル]]は通常の 0, 1, 2, etc. 以外のオブジェクトを持つが、標準モデルと初等的同値である。

==初等部分構造と初等拡大==

''N'' が ''M'' の'''初等部分構造'''や'''初等部分モデル''' であるとは、''N'' と ''M'' が同じ[[シグネチャ (数理論理学)|シグネチャ]] ''σ'' についての構造であって、全ての一階 ''σ''-式 ''φ''(''x''<sub>1</sub>,&nbsp;…,&nbsp;''x''<sub>''n''</sub>) （ただし、''x''<sub>1</sub>,&nbsp;…,&nbsp;''x''<sub>''n''</sub> は自由変数）について ''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>n</sub> が ''N'' の元であるのならば、''φ''(''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>n</sub>) が ''N'' で成り立つときかつその時に限り ''M'' でも成り立つことをいう:
<math display="block">N \models \varphi(a_1, \dots, a_n) \text{ if and only if } M \models \varphi(a_1, \dots, a_n).</math>

この定義はTarski, Vaught (1957) で初めて提唱された。<ref>E. C. Milner, [https://www.sciencedirect.com/science/article/pii/0012365X9590789N The use of elementary substructures in combinatorics] (1993). Appearing in ''Discrete Mathematics'', vol. 136, issues 1--3, 1994, pp.243--252.</ref> この定義は ''N'' が ''M'' の部分構造になることを含意する。

''N'' が ''M'' の部分構造であるとき、''N'' と ''M'' はともに ''σ'' に ''N'' の全ての要素の定数記号を付け加えたシグネチャ ''σ''<sub>''N''</sub> についての構造で解釈することができる。このため、''N'' が ''M'' の初等部分モデルであるのは、''N'' が ''M'' の部分構造であり、かつ ''N'' と ''M'' が ''σ''<sub>''N''</sub>-構造として初等的同値であるとき、かつその時に限る。

''N'' が ''M'' の初等部分構造（''M'' が ''N'' の'''初等拡大'''）であるとき、''N'' <math>\preceq</math> ''M'' か ''M'' <math>\succeq</math> ''N'' で表すことがある。

下向き[[レーヴェンハイム-スコーレムの定理]]はいかなる高々可算なシグネチャの無限一階構造にもその可算初等部分構造を与える; そして、上向きレーヴェンハイム-スコーレムの定理はいかなる無限一階構造にも、その初等拡大をいくらでも大きな濃度のもので与える。

==タルスキ-ヴォートテスト==

'''タルスキ-ヴォートテスト'''（または'''タルスキ-ヴォートの判定法'''）とは構造 ''M'' の部分構造 ''N'' が初等部分構造であるための必要十分条件である。大きい構造の初等部分構造を構成するのに有用である。

''M'' をシグネチャ ''σ'' の構造、''N'' を ''M'' の部分構造とする。このとき、''N'' が ''M'' の初等部分構造であるという条件は、「任意の ''σ'' 上の一階の式 ''φ''(''x'',&nbsp;''y''<sub>1</sub>,&nbsp;…,&nbsp;''y''<sub>''n''</sub>) と任意の ''N'' の要素 ''b''<sub>1</sub>,&nbsp;…,&nbsp;''b''<sub>''n''</sub> について、''M'' <math>\models</math> <math>\exists</math> ''x''&nbsp;''φ''(''x'',&nbsp;''b''<sub>1</sub>,&nbsp;…,&nbsp;''b''<sub>''n''</sub>) が成立するときは必ずある ''N'' の元 ''a'' について ''M'' <math>\models</math> ''φ''(''a'',&nbsp;''b''<sub>1</sub>,&nbsp;…,&nbsp;''b''<sub>''n''</sub>) が成立する。」という条件と同値である。

==初等埋め込み==

同じシグネチャ ''σ'' についての構造 ''N'' から構造 ''M'' への'''初等埋め込み'''とは写像 ''h'':&nbsp;''N''&nbsp;→&nbsp;''M'' であって、任意の一階 ''σ''-式 ''φ''(''x''<sub>1</sub>,&nbsp;…,&nbsp;''x''<sub>''n''</sub>) と ''N'' の要素 ''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>n</sub> について, 
:''N'' <math>\models</math> ''φ''(''a''<sub>1</sub>,&nbsp;…,&nbsp;''a''<sub>''n''</sub>) if and only if ''M'' <math>\models</math> ''φ''(''h''(''a''<sub>1</sub>),&nbsp;…,&nbsp;''h''(''a''<sub>''n''</sub>)).
となるものである。

初等埋め込みは[[Structure (mathematical logic)#Homomorphisms|strong homomorphism]]であり、その像は埋め込み先の初等部分構造になる。

初等埋め込みはモデル理論で最も重要な写像である。[[集合論]]において、''V'' (集合論の宇宙) を定義域とする初等埋め込みは[[巨大基数]]の理論で重要な役割を持っている ([[Critical point (set theory)|Critical point]]も参照)。

==参考文献==

{{reflist}}

* {{Citation| last1=Chang | first1=Chen Chung | last2=Keisler | first2=H. Jerome | author1-link=Chen Chung Chang | author2-link=Howard Jerome Keisler | title=Model Theory | orig-year=1973 | publisher=Elsevier | edition=3rd | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-88054-3 | year=1990}}.
* {{Citation| last1=Hodges | first1=Wilfrid | author1-link=Wilfrid Hodges | title=A shorter model theory | publisher= [[Cambridge University Press]]| location=Cambridge | isbn=978-0-521-58713-6 | year=1997}}.
* {{Citation|last=Monk |first=J. Donald |title=Mathematical Logic |series=Graduate Texts in Mathematics |publisher=Springer Verlag |location=New York • Heidelberg • Berlin |year=1976 |isbn=0-387-90170-1 |url-access=registration |url=https://archive.org/details/mathematicallogi00jdon}}

{{Mathematical logic}}
{{DEFAULTSORT:しよとうとうちせい}}
[[Category:同値 (数学)]]
[[Category:数理論理学]]
[[Category:モデル理論]]
[[Category:数学に関する記事]]