Введение

Концепция в теории моделей

В теории моделей, ветви математической логики, две структуры M и N с одинаковой сигнатурой σ называются элементарно эквивалентными, если они удовлетворяют одним и тем же формулам первого порядка σ. Если N является подструктурой M, часто требуется более сильное условие. В этом случае N называется элементарной подструктурой M, если для любой формулы σ первого порядка φ(a1, ..., an) с параметрами a1, ..., an из N она истинна в N тогда и только тогда, когда она истинна в M. Если N является элементарной подструктурой M, то M называется элементарным расширением N. Вложение h: N → M называется элементарным вложением N в M, если h(N) является элементарной подструктурой M.

Подструктура N структуры M является элементарной тогда и только тогда, когда она проходит тест Тарского — Вохта: любая формула первого порядка φ(x, b1, ..., bn) с параметрами из N, имеющая решение в M, также имеет решение в N при вычислении в M. Можно доказать, что две структуры элементарно эквивалентны с помощью игр Эренфейхта — Фраиссе. Элементарные вложения используются при изучении больших кардиналов, включая переход от ранга к рангу.

Элементарно эквивалентные структуры

Две структуры M и N с одинаковой сигнатурой σ являются элементарно эквивалентными, если каждое предложение первого порядка (формула без свободных переменных) над σ истинно в M тогда и только тогда, когда оно истинно в N, то есть если M и N имеют одну и ту же полную теорию первого порядка. Если M и N элементарно эквивалентны, то пишут M ≡ N.

Теория первого порядка является полной, если и только если любые две ее модели элементарно эквивалентны. Например, рассмотрим язык с одним символом бинарного отношения '<'. Модель R действительных чисел с их обычным порядком и модель Q рациональных чисел с их обычным порядком являются элементарно эквивалентными, поскольку они оба интерпретируют '<' как неограниченное плотное линейное упорядочение. Этого достаточно для обеспечения элементарной эквивалентности, потому что теория неограниченных плотных линейных упорядочений является полной, что можно показать с помощью теста Лоша–Вотта. В более общем случае, любая теория первого порядка с бесконечной моделью имеет неизоморфные, элементарно эквивалентные модели, которые можно получить с помощью теоремы Лёвенхайма–Сколема. Таким образом, например, существуют нестандартные модели арифметики Пеано, которые содержат объекты, отличные от чисел 0, 1, 2 и т.д., и тем не менее являются элементарно эквивалентными стандартной модели.

Испытание Тарски-Ваута

Испытание Тарски–Ваута (или критерий Тарски–Ваута) является необходимым и достаточным условием для того, чтобы подструктура N структуры M была элементарной подструктурой. Оно может быть полезно при построении элементарной подструктуры большой структуры. Пусть M – структура сигнатуры σ, а N – подструктура M. Тогда N является элементарной подструктурой M тогда и только тогда, когда для каждой формулы первого порядка φ(x, y1, …, yn) над σ и для всех элементов b1, …, bn из N, если M ⊧ x φ(x, b1, …, bn), то существует элемент a в N такой, что M ⊧ φ(a, b1, …, bn).