初等同値性

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

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

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

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

初等同値な構造

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

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

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

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

初等部分構造と初等拡大

N が M の初等部分構造や初等部分モデル であるとは、N と M が同じシグネチャ σ についての構造であって、全ての一階 σ-式 φ(x₁, …, x_n) （ただし、x₁, …, x_n は自由変数）について a₁, …, a_n が N の元であるのならば、φ(a₁, …, a_n) が N で成り立つときかつその時に限り M でも成り立つことをいう: $${\displaystyle N\models \varphi (a_{1},\dots ,a_{n}){\text{ if and only if }}M\models \varphi (a_{1},\dots ,a_{n}).}$$

この定義はTarski, Vaught (1957) で初めて提唱された。^[1] この定義は N が M の部分構造になることを含意する。

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

N が M の初等部分構造（M が N の初等拡大）であるとき、N ${\displaystyle \preceq }$ M か M ${\displaystyle \succeq }$ N で表すことがある。

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

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

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

M をシグネチャ σ の構造、N を M の部分構造とする。このとき、N が M の初等部分構造であるという条件は、「任意の σ 上の一階の式 φ(x, y₁, …, y_n) と任意の N の要素 b₁, …, b_n について、M ${\displaystyle \models }$ ${\displaystyle \exists }$ x φ(x, b₁, …, b_n) が成立するときは必ずある N の元 a について M ${\displaystyle \models }$ φ(a, b₁, …, b_n) が成立する。」という条件と同値である。

初等埋め込み

同じシグネチャ σ についての構造 N から構造 M への初等埋め込みとは写像 h: N → M であって、任意の一階 σ-式 φ(x₁, …, x_n) と N の要素 a₁, …, a_n について,

N ${\displaystyle \models }$ φ(a₁, …, a_n) if and only if M ${\displaystyle \models }$ φ(h(a₁), …, h(a_n)).

となるものである。

初等埋め込みはstrong homomorphismであり、その像は埋め込み先の初等部分構造になる。

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