Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Октября 2014

Читайте также:
  1. А. И. Солженицын Выступление в Государственной Думе 28 октября 1994 г.
  2. Альтернативы октября 1917 года.
  3. До 05 октября 2012 года
  4. Добрый день. Сегодня 25 октября и выпуск « Правового Часа» на радио Института прокуратуры.
  5. Если 2 октября или 2 апреля приходятся на нерабочий день, то сессия открывается в первый следующий за ним рабочий день.
  6. Лекция 5. 1 октября 2012 года
  7. На период с 15 октября 2014 года по 28 октября 2014 года
  8. На период с 15 октября 2014 года по 28 октября 2014 года
  9. Настоящее Положение утверждено Постановлением Минтруда РФ от 24 октября 2002г N73 с учетом статей 227-231 Трудового РФ
  10. Октября (вторник).

Если отношение 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 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Элементарные отношения: тест Тарского, теорема Левенгейма| Принципы Школы

lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав