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

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

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

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

Элементарные вложения используются при исследовании больших кардиналов , в том числе ранговых .

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

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

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

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

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

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

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

N\models \varphi (a_{1},\dots ,a_{n}){\text{ if and only if }}M\models \varphi (a_{1},\dots ,a_{n}).

Это определение впервые появляется у Тарского, Воота (1957). ^[1] Отсюда следует, что N является подструктурой M .

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

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

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

Тест Тарского-Вота [ править ]

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

Пусть M — структура сигнатуры σ , а N подструктура M. — Тогда N является элементарной подструктурой M и только тогда, когда для каждой формулы первого порядка φ ( x , y ₁ , …, y _n ) над σ и всех элементов b ₁ , …, bn _N из тогда , если M $\models$ $\exists$ x φ ( x , b ₁ , …, bn _что ), то существует элемент a из N такой, M $\models$ φ ( а , б ₁ , ..., б _п ).

Элементарные вложения [ править ]

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

Н

\models

φ ( a ₁ , …, an _{) тогда и} только тогда, когда M

\models

φ ( час ( а ₁ ), …, час ( а _п )).

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

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

Ссылки [ править ]

^ EC Милнер, Использование элементарных подструктур в комбинаторике (1993). В журнале «Дискретная математика» , вып. 136, выпуски 1–3, 1994, стр. 243–252.

Чанг, Чен Чунг ; Кейслер, Х. Джером (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

[1] EC Милнер, Использование элементарных подструктур в комбинаторике (1993). В журнале «Дискретная математика» , вып. 136, выпуски 1–3, 1994, стр. 243–252.

[1]