В теории моделей , ветви математической логики , две структуры M и N одной и той же сигнатуры σ называются элементарно эквивалентными, если они удовлетворяют одним и тем же σ- предложениям первого порядка .
Если N является подструктура из М , часто требуется более сильное условие. В этом случае N называется элементарная подструктурой из М , если каждый первый порядок σ -формула φ ( 1 , ..., п ) с параметрами 1 , ..., п из N истинно в N тогда и только тогда , когда это правда , в М . Если N - элементарная подструктура M , то M называетсяэлементарное расширение из N . Вложение ч : N → M называется элементарное вложение из N в М , если ч ( Н ) является элементарной подструктурой М .
Подструктура N структуры M является элементарной тогда и только тогда, когда она проходит тест Тарского – Воота : каждая формула первого порядка φ ( x , b 1 ,…, b n ) с параметрами в N, которая имеет решение в M, также имеет решение в N , когда оценивали в М . Можно доказать, что две структуры элементарно эквивалентны играм Эренфойхта – Фраисе .
Элементарно эквивалентные конструкции
Две структуры M и N той же сигнатуры σ являются элементарно эквивалентными , если каждый первого порядка предложения (формула без свободных переменных) над σ истинно в M тогда и только тогда , когда оно истинно в N , то есть , если M и N имеют одинаковую COMPLETE теория первого порядка. Если M и N элементарно эквивалентны, один пишет M ≡ N .
Теория первого порядка является полной тогда и только тогда, когда любые две ее модели элементарно эквивалентны.
Например, рассмотрим язык с одним символом двоичного отношения «<». Модель R из действительных чисел с обычным порядком и модель Q из рациональных чисел с обычным порядком элементарно эквивалентны, так как оба они интерпретируют «<» в неограниченном плотной линейном порядке . Этого достаточно, чтобы гарантировать элементарную эквивалентность, потому что теория неограниченных плотных линейных порядков завершена, как показывает тест Лоша – Воота .
В более общем смысле, любая теория первого порядка с бесконечной моделью имеет неизоморфные, элементарно эквивалентные модели, которые могут быть получены с помощью теоремы Лёвенгейма – Сколема . Так, например, существуют нестандартные модели из арифметики Пеано , которые содержат другие объекты , чем просто числами 0, 1, 2, и т.д., и в то же элементарно эквивалентны стандартной модели.
Элементарные подструктуры и элементарные расширения
N представляет собой элементарную подструктуру из М , если N и М являются структурами одного и те же подписи σ , что для всех первого порядка σ -формулы φ ( х 1 , ..., х п ) со свободными переменными х 1 , ..., х п , и все элементы a 1 ,…, a n из N , φ ( a 1 ,…, a n ) выполняется в N тогда и только тогда, когда оно выполняется в M :
- Nφ ( a 1 ,…, a n ) тогда и только тогда, когда Mφ ( a 1 ,…, a n ).
Отсюда следует , что Н является подструктура М .
Если N является подструктура М , то оба N и М могут быть интерпретированы как структуры в подписи сг N , состоящее из сг вместе с новым символом постоянной для каждого элемента N . Тогда N является элементарной подструктурой M тогда и только тогда, когда N является подструктурой M, а N и M элементарно эквивалентны как σ N -структуры.
Если N - элементарная подструктура M , пишут N M и говорит , что М является элементарным расширением из N : M N .
Вниз Löwenheim-Skolem теорема дает счетную элементарную подструктуру для любой бесконечной структуры первого порядка в не более чем счетной подписи; восходящая теорема Левенгейма – Сколема дает элементарные расширения любой бесконечной структуры первого порядка сколь угодно большой мощности.
Тест Тарского – Воота
Тест Тарского – Воота (или критерий Тарского – Воота ) является необходимым и достаточным условием для того, чтобы подструктура N структуры M была элементарной подструктурой. Это может быть полезно для создания элементарной подструктуры большой конструкции.
Пусть М представляет собой структуру сигнатуры сг и N подструктура М . Тогда 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 той же сигнатуры сг является отображение ч : N → М такое , что для каждого первого порядка σ -формула φ ( х 1 , ..., х п ) и все элементы 1 , ..., п из N ,
- Nφ ( a 1 ,…, a n ) тогда и только тогда, когда Mφ ( h ( a 1 ),…, h ( a n )).
Каждое элементарное вложение является сильным гомоморфизмом , а его образ - элементарной подструктурой.
Элементарные вложения - самые важные карты в теории моделей. В теории множеств элементарные вложения, область определения которых - V (универсум теории множеств), играют важную роль в теории больших кардиналов (см. Также Критический момент ).
Рекомендации
- Чанг, Чен Чунг ; Кейслер, Х. Джером (1990) [1973], Теория моделей , Исследования в области логики и основ математики (3-е изд.), Elsevier, ISBN 978-0-444-88054-3.
- Ходжес, Уилфрид (1997), Более короткая теория модели , Кембридж: Издательство Кембриджского университета , ISBN 978-0-521-58713-6.
- Монк, Дж. Дональд (1976), Математическая логика , Тексты для выпускников по математике, Нью-Йорк • Гейдельберг • Берлин: Springer Verlag, ISBN 0-387-90170-1