初等同値性
ウィキペディア フリーな encyclopedia
数理論理学の一分野であるモデル理論において、同じシグネチャ σ の2つの構造 M と N が同じ一階σ-文を満たすとき、M と N は初等的同値であるという。
N が M の部分構造であるとき、さらに強い条件について考える場合がある。N が M の初等部分構造 であるとは一階 σ-式 φ(a1, …, an)(ただしパラメータ a1, …, an は全て N の元)が N で真であることと M で真であることが同値であること。N が M の初等部分構造であるとき、M は N の 初等拡大 という。埋め込み h: N → M は h(N) が M の初等部分構造であるとき、N から M への 初等埋め込みと呼ぶ。
M の部分構造 N が初等的であるのは、それがタルスキ–ヴォートテストを通ることと同値である: すなわち x を未知数とする任意の1階の式 φ(x, b1, …, bn)(ただし、パラメータは全て N の元)が M に解を持つならいつでも N でも解を持つこと。また、二つの構造の初等同値性を示すにはEhrenfeucht–Fraïssé gamesを用いた判定法もある。
初等埋め込みはrank-into-rank基数を含む巨大基数研究に用いられる。