Читайте также:
|
|
Если отношение S является расширением отношения R,, то элементарность этого расширения R, означает, что любой кортеж элементов из носителя отношения R, ("меньшее" отношение) удовлетворяет одним и тем же формулам в R, и в S; это свойство выражается следующей очень полезной теоремой, где, заметим, выполнимость подразумевается относительно "большего" отношения
Если S - расширение R. то это расширение элементарно тогда и только тогда, когда для любого а из носителя отношения R и любой формулы , то существует b из носителя R, такой, что
Необходимость очевидна. Достаточность докажем индукцией по кванторному рангу р формулы : если из носителя R, тогда Это очевидно для р = 0, поскольку по определению самого понятия расширения удовлетворяет одним и тем же формулам в R и S. Предположим, что имеет вид , где кванторный ранг формулы g меньше р. Если , то по предположению существует b из носителя R, такой, что и по индукционному предположению , следовательно, . Если , то для всех b из носителя S и, в частности, для всех b из носителя R, имеем . По предположению индукции , значит, Это завершает доказательство, поскольку формула кванторного ранга р является булевой комбинацией формул рассмотренного вида
□
Теорема 2.5 (теорема Левенгейма.) Каждое отношение R, имеет конечное или счетное элементарное ограничение; более точно, если А - бесконечное подмножество носителя R,. то существует элементарное ограничение R,. носитель которого содержит А и равномощен А.
Доказательство. Пересчитаем все формулы с параметрами в А: существует счётное множество формул ; в каждой нужно заменить n -кой из А, и так как А бесконечно, то существует card(A) таких п-ок (поскольку, если А бесконечно, то множество конечных подмножеств А имеет ту же мощность, что и А); значит, существует формул с параметрами из А (позднее мы уточним эту арифметику кардиналов). Для каждой формулы такой, что , добавляем к А элемент b из носителя R, такой, что ; Так как нужно самое большее добавить card(A) элементов, то получим в итоге множество A1, содержащее А и имеющее ту же мощность, что и А. Повторим эту операцию, заменив А на , получим множество и т.д. Пусть В - объединение множеств это - множество мощности , и ограничение R на В удовлетворяет условиям теста Тарского.
□
Мы видим, в частности, что каждая совместная теория языка m -арного отношения имеет конечную или счетную модель. Пусть I - носитель линейного порядка <; цепью расширений, индексированной множеством I, называется семейство отношений Ri с базой такое что расширение Ri для любых i < j. Пределом (индуктивным!) цепи расширений называется единственное отношение R с базой являющееся расширением всех Ri: удовлетворяет R, если для достаточно большого i (на самом деле, как только попадает в ) удовлетворяет Очень часто на практике < полный порядок (например, порядок натуральных чисел , как в доказательстве теоремы 2.5), так как расширение строятся одно за другим; но это предположение не нужно для доказательства следующей теоремы.
Теорема 2.6 Если - це,пь элементарных расширений (т.е.
для i < j), то её предел R будет элементарным расширением каждого
Доказательство. Покажем индукцией по кванторному рангу р формулы , что если Это очевидно для р = 0. Пусть и g имеет кванторный ранг р. Если то существует b из E, такой, что Этот b принадлежит Ej для некоторого , и по гипотезе индукции . Значит, и, поскольку есть элементарное расширение , имеем Если , то для любого b из E и, в частности, для любого b из , следовательно, по предположению индукции , что влечёт
октября 2014
Дата добавления: 2014-12-15; просмотров: 22 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
Элементарные отношения: тест Тарского, теорема Левенгейма | | | Принципы Школы |