В теории моделей , разделе математической логики , две структуры M и N одинаковой сигнатуры σ называются элементарно эквивалентными , если они удовлетворяют одним и тем же σ -предложениям первого порядка .
Если N является подструктурой M , часто требуется более сильное условие. В этом случае N называется элементарной подструктурой M , если каждая σ -формула первого порядка φ ( a 1 , …, an ) с параметрами a 1 , …, an из N истинна в N тогда и только тогда, когда она истинна в M. Если N является элементарной подструктурой M , то M называется элементарным расширением N. Вложение h : N → M называется элементарным вложением N в M , если h ( N ) является элементарной подструктурой M.
Подструктура N структуры M является элементарной тогда и только тогда, когда она проходит тест Тарского–Воота : каждая формула первого порядка φ ( x , b 1 , …, b n ) с параметрами в N , имеющая решение в M , также имеет решение в N при вычислении в M . Можно доказать, что две структуры элементарно эквивалентны с играми Эренфойхта–Фрессе .
Элементарные вложения используются при изучении больших кардиналов , включая ранг-в-ранг .
Две структуры M и N одной и той же сигнатуры σ элементарно эквивалентны , если каждое предложение первого порядка (формула без свободных переменных) над σ истинно в M тогда и только тогда, когда оно истинно в N , т.е. если M и N имеют одну и ту же полную теорию первого порядка. Если M и N элементарно эквивалентны, то записывается M ≡ N .
Теория первого порядка является полной тогда и только тогда, когда любые две ее модели элементарно эквивалентны.
Например, рассмотрим язык с одним бинарным символом отношения '<'. Модель R действительных чисел с ее обычным порядком и модель Q рациональных чисел с ее обычным порядком элементарно эквивалентны, поскольку они обе интерпретируют '<' как неограниченный плотный линейный порядок . Этого достаточно для обеспечения элементарной эквивалентности, поскольку теория неограниченных плотных линейных порядков является полной, как может быть показано тестом Лоса–Вогта .
В более общем смысле, любая теория первого порядка с бесконечной моделью имеет неизоморфные, элементарно эквивалентные модели, которые могут быть получены с помощью теоремы Лёвенгейма–Скулема . Так, например, существуют нестандартные модели арифметики Пеано , которые содержат другие объекты, а не только числа 0, 1, 2 и т. д., и при этом элементарно эквивалентны стандартной модели.
N является элементарной подструктурой или элементарной подмоделью M , если N и M являются структурами одной и той же сигнатуры σ, такими что для всех σ -формул первого порядка φ ( x 1 , …, x n ) со свободными переменными x 1 , …, x n и всеми элементами a 1 , …, a n из N , φ ( a 1 , …, a n ) выполняется в N тогда и только тогда, когда она выполняется в M :
Это определение впервые появляется в работе Тарского, Воота (1957). [1] Из этого следует , что N является подструктурой M.
Если N является подструктурой M , то и N, и M можно интерпретировать как структуры в сигнатуре σ N , состоящие из σ вместе с новым постоянным символом для каждого элемента N . Тогда N является элементарной подструктурой M тогда и только тогда, когда N является подструктурой M , а N и M элементарно эквивалентны как σ N -структуры.
Если N является элементарной подструктурой M , то пишут N M и говорят, что M является элементарным расширением N : M N .
Нисходящая теорема Лёвенгейма–Скулема дает счетную элементарную подструктуру для любой бесконечной структуры первого порядка в не более чем счетной сигнатуре; восходящая теорема Лёвенгейма–Скулема дает элементарные расширения любой бесконечной структуры первого порядка произвольно большой мощности.
Тест Тарского–Воота (или критерий Тарского–Воота ) является необходимым и достаточным условием для того, чтобы подструктура N структуры M была элементарной подструктурой. Он может быть полезен для построения элементарной подструктуры большой структуры.
Пусть M — структура сигнатуры σ , а N — подструктура M. Тогда N является элементарной подструктурой M тогда и только тогда, когда для каждой формулы первого порядка φ ( x , y 1 , …, y n ) над σ и всех элементов b 1 , …, b n из N , если M x φ ( x , b 1 , …, b n ), то существует элемент a в N такой, что M φ ( a , b 1 , …, b n ).
Элементарное вложение структуры N в структуру M той же сигнатуры σ — это отображение h : N → M такое, что для каждой σ -формулы первого порядка φ ( x 1 , …, x n ) и всех элементов a 1 , …, a n из N ,
Каждое элементарное вложение является сильным гомоморфизмом , а его образ — элементарной подструктурой.
Элементарные вложения являются наиболее важными картами в теории моделей. В теории множеств элементарные вложения, областью определения которых является V (вселенная теории множеств), играют важную роль в теории больших кардиналов (см. также Критическая точка ).
