WikiDer > Элементарная эквивалентность

Elementary equivalence

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

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

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

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

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

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

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

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

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

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

N φ(а1, …, ап) iff M φ(а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 тогда и только тогда, когда для каждой формулы первого порядка φ(Иксy1, …, yп) над σ и все элементы б1, …, бп из N, если M Икс φ(Иксб1, …, бп), то есть элемент а в N такой, что M φ(аб1, …, бп).

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

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

N φ(а1, …, ап) если и только если M φ(час(а1), …, час(ап)).

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

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