Элементарная эквивалентность - Elementary equivalence

В теории моделей , ветви математической логики , две структуры M и N одной и той же сигнатуры σ называются элементарно эквивалентными, если они удовлетворяют одним и тем же σ- предложениям первого порядка .

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

Подструктура N структуры M является элементарной тогда и только тогда, когда она проходит тест Тарского – Воота : каждая формула первого порядка φ ( x ,  b ₁ ,…,  b _n ) с параметрами в N, которая имеет решение в M, также имеет решение в  N , когда оценивали в  М . Можно доказать, что две структуры элементарно эквивалентны играм Эренфойхта – Фрассе .

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

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

Теория первого порядка является полной тогда и только тогда, когда любые две ее модели элементарно эквивалентны.

Например, рассмотрим язык с одним символом двоичного отношения «<». Модель R из действительных чисел с обычным порядком и модель Q из рациональных чисел с обычным порядком элементарно эквивалентны, так как оба они интерпретируют «<» в неограниченном плотной линейном порядке . Этого достаточно, чтобы гарантировать элементарную эквивалентность, потому что теория неограниченных плотных линейных порядков завершена, что может быть показано тестом Лоша – Воота .

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

Элементарные подструктуры и элементарные расширения

N представляет собой элементарную подструктуру из М , если N и М являются структурами одного и те же подписи   σ , что для всех первого порядка σ -формулы φ ( х ₁ , ...,  х _п ) со свободными переменными х ₁ , ...,  х _п , и все элементы a ₁ ,…,  a _n из  N , φ ( a ₁ ,…,  a _n ) выполняется в N тогда и только тогда, когда оно выполняется в M :

N φ ( a ₁ ,…,  a _n ) тогда и только тогда, когда M φ ( a ₁ ,…,  a _n ). ${\ displaystyle \ models}$ ${\ displaystyle \ models}$

Отсюда следует , что Н является подструктура М .

Если N является подструктура М , то оба N и М могут быть интерпретированы как структуры в подписи сг _N , состоящее из сг вместе с новым символом постоянной для каждого элемента  N . Тогда N является элементарной подструктурой M тогда и только тогда, когда N является подструктурой M, а N и M элементарно эквивалентны как σ _N -структуры.

Если N элементарная подструктура М , один пишет N M и говорит , что М является элементарным расширением из N : M N . ${\ displaystyle \ prevq}$ ${\ displaystyle \ successq}$

Вниз Löwenheim-Skolem теорема дает счетную элементарную подструктуру для любой бесконечной структуры первого порядка в не более чем счетной подписи; восходящая теорема Левенгейма – Сколема дает элементарные расширения любой бесконечной структуры первого порядка сколь угодно большой мощности.

Тест Тарского – Воота

Тест Тарского – Воота (или критерий Тарского – Воота ) является необходимым и достаточным условием для того, чтобы подструктура N структуры M была элементарной подструктурой. Это может быть полезно для создания элементарной подструктуры большой конструкции.

Пусть М представляет собой структуру сигнатуры сг и N подструктура М . Тогда N является элементарной подструктурой M тогда и только тогда, когда для любой формулы первого порядка φ ( x ,  y ₁ ,…,  y _n ) над σ и всех элементов b ₁ ,…,  b _n из N , если M x φ ( x ,  b ₁ ,…,  b _n ), то существует элемент a в N такой, что M φ ( a ,  b ₁ ,…,  b _n ). ${\ displaystyle \ models}$ ${\ Displaystyle \ существует}$  ${\ displaystyle \ models}$

Элементарные вложения

Элементарное вложение структуры N в структуру M той же сигнатуры сг является отображение ч :  N  →  М такое , что для каждого первого порядка σ -формула φ ( х ₁ , ...,  х _п ) и все элементы ₁ , ...,  _п из  N ,

N φ ( a ₁ ,…,  a _n ) тогда и только тогда, когда M φ ( h ( a ₁ ),…,  h ( a _n )). ${\ displaystyle \ models}$ ${\ displaystyle \ models}$

Каждое элементарное вложение является сильным гомоморфизмом , а его образ - элементарной подструктурой.

Элементарные вложения - самые важные карты в теории моделей. В теории множеств элементарные вложения, область определения которых - V (универсум теории множеств), играют важную роль в теории больших кардиналов (см. Также Критический момент ).

Рекомендации

• Чанг, Чен Чунг ; Кейслер, Х. Джером (1990) [1973], Теория моделей , Исследования в области логики и основ математики (3-е изд.), Elsevier, ISBN   978-0-444-88054-3 .
• Ходжес, Уилфрид (1997), более короткая теория модели , Кембридж: Cambridge University Press , ISBN   978-0-521-58713-6 .
• Монк, Дж. Дональд (1976), Математическая логика , Тексты для выпускников по математике, Нью-Йорк • Гейдельберг • Берлин: Springer Verlag, ISBN   0-387-90170-1