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

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

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

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

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

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

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

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

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

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

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

N ${\displaystyle \models }$ φ(а₁, …, а_п) iff M ${\displaystyle \models }$ φ(а₁, …, а_п).

Следует, что N является подструктурой M.

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

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

Нисходящий Теорема Левенгейма – Сколема дает счетную элементарную подструктуру для любой бесконечной структуры первого порядка в не более чем счетной сигнатуре; восходящая теорема Левенгейма – Сколема дает элементарные расширения любой бесконечной структуры первого порядка сколь угодно большой мощности.

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

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

Позволять M быть структурой подписи σ и N подструктура M. потом N является элементарной подструктурой M тогда и только тогда, когда для каждой формулы первого порядка φ(Икс, y₁, …, y_п) над σ и все элементы б₁, …, б_п из N, если M ${\displaystyle \models }$ ${\displaystyle \exists }$Икс φ(Икс, б₁, …, б_п), то есть элемент а в N такой, что M ${\displaystyle \models }$ φ(а, б₁, …, б_п).

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

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

N ${\displaystyle \models }$ φ(а₁, …, а_п) если и только если M ${\displaystyle \models }$ φ(час(а₁), …, час(а_п)).

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

Элементарные вложения - самые важные карты в теории моделей. В теория множеств, элементарные вложения, область определения которых 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