Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 45
Текст из файла (страница 45)
Покажите, что две интерпретации одной сигнатуры элементарноэквивалентны тогда и только тогда, когда они имеют изоморфные элементарные расширения.5.6. Ультрафильтры и компактностьВ этом разделе мы дадим прямое доказательство теоремы о компактности (теорема 50, с. 153).Пусть S — непустое множество, а F — непустое семейство подмножеств множества S. Семейство F называется фильтром на S, есливыполнены следующие три свойства (для наглядности множества изF мы называем далее большими):• ∅ 6∈ F (пустое множество не является большим);• A ∈ F, B ∈ F ⇒ A ∩ B ∈ F (пересечение двух больших множеств — снова большое множество); отсюда следует, что пересечение конечного числа больших множеств — большое множество и что любые два больших множества пересекаются;• A ∈ F, A ⊂ B ⇒ B ∈ F (любое надмножество большого множества является большим); отсюда следует, что всё множествоS является большим.Дополнения к большим множествам естественно назвать малыми.
(Отметим, что множество может не быть ни большим, ни малым202Теории и модели[гл. 5]с точки зрения фильтра; это отличает фильтры от ультрафильтров,которые мы вскоре определим.)Тривиальным примером фильтра является семейство, состоящееиз единственного множества S. Другой пример — семейство всех подмножеств S, содержащих некоторый выделенный элемент s ∈ S. Такой фильтр называется главным. Третий пример: пусть S бесконечно, тогда фильтром будет множество всех коконечных подмножествS, то есть подмножеств, дополнение которых конечно.
(Другими словами, малыми будут конечные множества.) Последний пример — изанализа: фильтром на R является семейство всех окрестностей некоторой фиксированной точки a, то есть всех множеств, для которых aявляется внутренней точкой.156. Переформулируйте определение фильтра в терминах свойств малых множеств.Заметим, что одно и то же множество не может быть одновременно и большим, и малым, поскольку любые два больших множествапересекаются (по большому, и потому непустому, множеству). Но,как мы уже говорили, множество может не быть ни большим, нималым. Если таких «промежуточных» множеств нет, фильтр называют ультрафильтром.Иными словами, ультрафильтром называется фильтр на S с таким свойством: A ∈ F или S \ A ∈ F для любого множества A ⊂ S.Очевидно, любой главный фильтр является ультрафильтром.
Востальных наших примерах фильтры не были ультрафильтрами.157. Докажите, что на конечном множестве любой ультрафильтр является главным.158. Докажите, что любой неглавный ультрафильтр содержит все коконечные множества.159. Докажите, что если ультрафильтр не является главным, то вместес каждым множеством A он содержит и все множества B, для которыхсимметрическая разность A 4 B конечна.Определение ультрафильтра можно переформулировать следующим образом: ультрафильтры — это фильтры, не имеющие собственных расширений (максимальные по включению).
Докажем это. Если фильтр F не максимален, то найдётся больший фильтр F 0 . Тогдамножество A ∈ F 0 \ F и его дополнение до S не принадлежит F(иначе и A, и его дополнение принадлежали бы фильтру F 0 ). Следовательно, F не является ультрафильтром.Обратно, пусть фильтр F не является ультрафильтром, и ни множество A, ни его дополнение S \ A не принадлежат F . Добавим к F[п. 6]Ультрафильтры и компактность203все множества вида A ∩ B (для всех B ∈ F ) и все их надмножества.Получится фильтр.
В самом деле, пустое множество ему не принадлежит, так как иначе бы A не пересекалось с некоторым множествомиз F и S \ A содержало бы некоторое множество из F потому лежало бы в F . Остальные свойства фильтра очевидны; новый фильтр (вотличие от исходного) содержит A и потому расширяет F .Теорема 76. Всякий фильтр F на множестве S можно расширитьдо ультрафильтра F 0 ⊃ F . Доказательство этой теоремы неконструктивно: мы не предъявляем такого фильтра, а устанавливаем его существование с помощью леммы Цорна (см. [6]).
Нужно только заметить, что объединение любой цепи фильтров является фильтром (что непосредственноследует из определения).Другими словами, пока фильтр не станет ультрафильтром, мыберём «промежуточное» множество и расширяем фильтр, объявляяего большим, повторяя этот процесс по трансфинитной индукции. 160. Докажите, что на любом бесконечном множестве есть неглавный ультрафильтр.
(Указание: расширим фильтр коконечных множествдо ультрафильтра.)Можно представлять себе элементы множества S как голосующих (которые никогда не воздерживаются от голосования). При этомфильтр на S определяет регламент: решение принимается, если множество проголосовавших «за» — большое. Аксиомы фильтра тогдазвучат так: решение, против которого все, принято быть не может;если каждое из двух решений принимается, то они принимаются и всовокупности; наконец, принятое решение не может быть отвергнуто, если некоторые из голосовавших против него передумали.Свойство ультрафильтра также имеет ясный смысл: по любомувопросу можно принять решение (одно из двух противоположныхмнений набирает большинство).
Главные ультрафильтры соответствуют диктатуре (существенно мнение лишь одного голосующего);задача 157 показывает, что для конечного числа голосующих любые другие способы не позволяют принять решения по некоторымвопросам.Ультрафильтры можно использовать для построения любопытных примеров. Вот один из них. Рассмотрим игру двух участников,в которой они по очереди объявляют некоторые натуральные числа«своими». На первом шаге начинающий игру объявляет своими числа от нуля до некоторого числа n1 , на втором шаге его противникприсваивает числа от n1 (не включая его) до некоторого больше-204Теории и модели[гл.
5]го числа n2 (включая его), затем первый игрок присваивает числаот n2 до n3 и так далее. Партия продолжается неограниченно и делит натуральный ряд между первым и вторым (на два взаимно дополнительных множества). Выигрывает тот, чьё множество большое(принадлежит некоторому фильтру).Если этот фильтр является ультрафильтром, то в этой игре неможет быть ничьей.
Если ультрафильтр главный, то игра тривиальна — побеждает тот, кто захватит решающее число, и потому первыйможет гарантировать выигрыш на первом же ходу.Теорема 77. Если ультрафильтр неглавный, то ни один из игроков не имеет выигрышной стратегии. (Стратегия — это функция,предписывающая следующий ход в зависимости от истории игры.Стратегия считается выигрышной, если её использование гарантирует выигрыш при любой игре противника.) Прежде всего отметим, что оба игрока не могут одновременноиметь выигрышные стратегии.
(Что будет, если они оба ими воспользуются?) Покажем теперь, что если выигрышную стратегию имеетодин, то её имеет и второй. Совсем просто понять, что если у ходящего вторым есть выигрышная стратегия, то и первый может ейвоспользоваться (он должен представить себя вторым, считая, чтопервый на первом ходу ничего не взял).Не столь ясно, что выигрышная стратегия первого может бытьиспользована вторым, но и это верно — поскольку конечные множества не влияют на принадлежность ультрафильтру (задача 159),второй может забыть про ход, с которого началась игра, и вообразить себя первым. (Это сделает его первый ход бессмысленным, еслиэтот ход окажется меньше хода противника.
В этом случае можносделать сразу второй ход первого игрока, и далее следовать стратегии.) 161. Проведите это рассуждение подробно.Сейчас мы докажем теорему компактности с помощью ультрафильтров. Для этого нам понадобится понятие произведения интерпретаций.Пусть Ms — семейство интерпретаций некоторой (одной и тойже) сигнатуры σ, индексированное множеством S (для каждого s ∈∈ S имеется своя интерпретация Ms ).
Определим произведение интерпретаций этого семейства, обозначаемоеYMs .s∈S[п. 6]Ультрафильтры и компактность205Элементами носителя будут отображения, сопоставляющие c каждым индексом s ∈ S некоторый элемент интерпретации Ms . Инымисловами, носитель строимой интерпретации будет декартовым произведением всех Ms .Функциональные символы интерпретировать легко: они применяются отдельно в каждой компоненте. Именно так определяетсяпроизведение групп или колец в алгебре.
Остаётся определить предикатные символы. В алгебре два элемента в произведении колецили групп считаются равными, если все их компоненты равны. Поаналогии будем считать, что два элемента s 7→ as и s 7→ bs делаютистинным двуместный предикат P , если P (as , bs ) истинно в интерпретации Ms для всех s. (Мы взяли двуместный символ для примера,то же самое можно сделать и для символов любой валентности.)Таким способом в произведении двух упорядоченных множеств(индексное множество S равно {1, 2}, сигнатура есть (=, 6)) возникает покомпонентный порядок на парах: ha1 , a2 i 6 hb1 , b2 i, если a1 6 a2и b1 6 b2 . Заметим, что такой порядок на произведении двух линейноупорядоченных множеств уже не будет линейным (если сомножители состоят более чем из одного элемента).Нам это не нравится: мы хотим, чтобы произведение интерпретаций обладало бы всеми свойствами, которыми обладают сомножители.
Введём понятие фильтрованного произведения (по модулюданного фильтра). Пусть на множестве индексов S задан фильтр F .Изменим определение истинности предикатов и будем считать, чтоэлементы s 7→ as , s 7→ bs , . . . делают истинным предикат P , еслиP (as , bs , . . . ) истинно «для большинства s», то есть если множество{s | P (as , bs , .
. . )} принадлежит фильтру F . В остальном (носитель,функциональные символы) определение остаётся прежним.Что будет равенством в фильтрованном произведении нормальных интерпретаций? Два элемента произведения (то есть функциина множестве индексов) равны, если они «совпадают почти всюду»,то есть множество индексов, где они совпадают, принадлежит фильтру. При этом полученная интерпретация не будет нормальной. Чтобы перейти к нормальной, нужно рассмотреть классы равных элементов — как это делается, скажем, для пространства L2 интегрируемых с квадратом функций, где элементами являются не сами функции, а их классы с точностью до совпадения почти всюду.162.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
