Языки и исчисления

Ультрафильтры и компактность


В этом разделе мы дадим прямое доказательство теоремы о компактности (теорема 50).

Пусть — непустое множество, а — непустое семейство подмножеств множества . Семейство называется фильтром на , если выполнены следующие три свойства (для наглядности множества из мы называем далее большими):

  • (пустое множество не является большим);
  • (пересечение двух больших множеств — снова большое множество); отсюда следует, что пересечение конечного числа больших множеств — большое множество и что любые два больших множества пересекаются;

  • (любое надмножество большого множества является большим); отсюда следует, что все множество является большим.

Дополнения к большим множествам естественно назвать малыми. (Отметим, что множество может не быть ни большим, ни малым; это отличает фильтры от ультрафильтров, которые мы вскоре определим.)

Тривиальным примером фильтра является семейство, состоящее из единственного множества . Другой пример — семейство всех подмножеств , содержащих некоторый выделенный элемент . Такой фильтр называется главным. Третий пример: пусть бесконечно, тогда фильтром будет множество всех коконечных подмножеств , то есть подмножеств, дополнение которых конечно. (Другими словами, малыми будут конечные множества.) Последний пример — из анализа: фильтром на является семейство всех окрестностей некоторой фиксированной точки , то есть всех множеств, для которых является внутренней точкой.

156. Переформулируйте определение фильтра в терминах малых множеств.

Заметим, что одно и то же множество не может быть одновременно и большим, и малым, поскольку любые два больших множества пересекаются (по большому, и потому непустому, множеству). Но, как мы уже говорили, множество может не быть ни большим, ни малым. Если таких "промежуточных" множеств нет, фильтр называют ультрафильтром.

Иными словами, ультрафильтром называется фильтр на с таким свойством: или для любого множества .

Очевидно, любой главный фильтр является ультрафильтром. Фильтры остальных наших примеров не были ультрафильтрами.


157. Докажите, что на конечном множестве любой ультрафильтр является главным.

158. Докажите, что любой неглавный ультрафильтр содержит все коконечные множества.

159. Докажите, что если ультрафильтр не является главным, то вместе с каждым множеством он содержит и все множества , для которых симметрическая разность конечна.

Определение ультрафильтра можно переформулировать следующим образом: ультрафильтры — это фильтры, не имеющие собственных расширений (максимальные по включению). Докажем это. Если фильтр не максимален, то найдется больший фильтр . Тогда множество и его дополнение до не принадлежит (иначе и , и его дополнение принадлежали бы фильтру ). Следовательно, не является ультрафильтром.

Обратно, пусть фильтр не является ультрафильтром, и ни множество , ни его дополнение не принадлежат . Добавим к все множества вида (для всех ) и все их надмножества. Получится фильтр. В самом деле, пустое множество ему не принадлежит, так как иначе бы не пересекалось с некоторым множеством из и содержало бы некоторое множество из потому лежало бы в . Остальные свойства фильтра очевидны; новый фильтр (в отличие от исходного) содержит и потому расширяет .

Теорема 75. Всякий фильтр на множестве можно расширить до ультрафильтра .

Доказательство этой теоремы неконструктивно: мы не предъявляем такого фильтра, а устанавливаем его существование с помощью леммы Цорна (см. [6]). Нужно только заметить, что объединение любой цепи фильтров является фильтром (что непосредственно следует из определения).

Другими словами, пока фильтр не станет ультрафильтром, мы берем "промежуточное" множество и расширяем фильтр, объявляя его большим, повторяя этот процесс по трансфинитной индукции.

160. Докажите, что на любом бесконечном множестве есть неглавный ультрафильтр. (Указание: расширим фильтр коконечных множеств до ультрафильтра.)

Можно представлять себе элементы множества как голосующих (которые никогда не воздерживаются от голосования). При этом фильтр на определяет регламент: решение принимается, если множество проголосовавших "за" является большим.


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

Свойство ультрафильтра также имеет ясный смысл: по любому вопросу можно принять решение (одно из двух противоположных мнений набирает большинство). Главные ультрафильтры соответствуют диктатуре (существенно мнение лишь одного голосующего); задача 150 показывает, что для конечного числа голосующих любые другие способы не позволяют принять решения по некоторым вопросам.

Ультрафильтры можно использовать для построения любопытных примеров. Вот один из них. Рассмотрим игру двух участников, в которой они по очереди объявляют некоторые натуральные числа " своими". На первом шаге начинающий игру объявляет своими числа от нуля до некоторого числа , на втором шаге его противник присваивает числа от (не включая его) до некоторого большего числа (включая его), затем первый игрок присваивает числа от до и так далее. Партия продолжается неограниченно и делит натуральный ряд между первым и вторым (на два взаимно дополнительных множества). Выигрывает тот, чье множество большое (принадлежит некоторому фильтру).

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

Теорема 76. Если ультрафильтр неглавный, то ни один из игроков не имеет выигрышной стратегии. (Стратегия — это функция, предписывающая следующий ход в зависимости от истории игры. Стратегия считается выигрышной, если ее использование гарантирует выигрыш при любой игре противника.)

Прежде всего отметим, что оба игрока не могут одновременно иметь выигрышные стратегии. (Что будет, если они оба ими воспользуются?) Покажем теперь, что если выигрышную стратегию имеет один, то ее имеет и второй.


Совсем просто понять, что если у ходящего вторым есть выигрышная стратегия, то и первый может ей воспользоваться (он должен представить себя вторым, считая, что первый на первом ходу ничего не взял).

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

161. Проведите это рассуждение подробно.

Сейчас мы докажем теорему компактности с помощью ультрафильтров. Для этого нам понадобится понятие произведения интерпретаций.

Пусть — семейство интерпретаций некоторой (одной и той же) сигнатуры , индексированное множеством (для каждого имеется своя интерпретация ). Определим произведение интерпретаций Элементами носителя будут отображения, сопоставляющие c каждым индексом некоторый элемент интерпретации . Иными словами, носитель строимой интерпретации будет декартовым произведением всех .

Функциональные символы интерпретировать легко: они применяются отдельно в каждой компоненте. Именно так определяется произведение групп или колец в алгебре. Остается определить предикатные символы. В алгебре два элемента в произведении колец или групп считаются равными, если все их компоненты равны. По аналогии будем считать, что два элемента и делают истинным двуместный предикат , если истинно в интерпретации для всех . (Мы взяли двуместный символ для примера, то же самое можно сделать и для символов любой валентности.)

Для произведения двух упорядоченных множеств (индексное множество равно , сигнатура есть ) возникает покомпонентный порядок на парах: , если и . Заметим, что такой порядок на произведении двух линейно упорядоченных множеств уже не будет линейным (если сомножители состоят более чем из одного элемента).





Нам это не нравится: мы хотим, чтобы произведение интерпретаций обладало бы всеми свойствами, которыми обладают сомножители. Введем понятие фильтрованного произведения (по модулю данного фильтра). Пусть на множестве индексов задан фильтр . Изменим определение истинности предикатов и будем считать, что элементы делают истинным предикат , если истинно "для большинства ", то есть если множество принадлежит фильтру . В остальном (носитель, функциональные символы) определение остается прежним.

Что будет равенством в фильтрованном произведении нормальных интерпретаций? Два элемента произведения (то есть функции на множестве индексов) равны, если они "совпадают почти всюду", то есть множество индексов, где они совпадают, принадлежит фильтру. При этом полученная интерпретация не будет нормальной. Чтобы перейти к нормальной, нужно рассмотреть классы равных элементов — как это делается, скажем, для пространства интегрируемых с квадратом функций, где элементами являются не сами функции, а их классы с точностью до совпадения почти всюду.

162. Что можно сказать про фильтрованное произведение по главному фильтру?

Вернемся к нашему примеру: произведению линейно упорядоченных множеств. Будет ли оно линейно упорядоченным? Это зависит от фильтра. Например, если фильтр состоит только из множества , то фильтрованное произведение совпадает с определенным ранее, и линейного порядка не получится. Но если фильтр является ультрафильтром, то будет. В самом деле, рассмотрим два элемента и в произведении и два множества и . В объединении они покрывают все , и потому (если у нас ультрафильтр) одно из них должно быть большим (если оно не большое, так малое, его дополнение большое и содержится во втором множестве).

163. Докажите, что в фильтрованном произведении нормальных интерпретаций функции и предикаты корректны относительно равенства (то есть совпадения почти всюду): при замене аргументов на равные значение функции совпадает с прежним почти всюду, а значение предиката не меняется.



Это утверждение можно сформулировать так: аксиомы равенства истинны в фильтрованном произведении нормальных интерпретаций. Для ультрафильтров верно и более общее свойство: любая формула, истинная во всех интерпретациях, истинна в фильтрованном произведении по модулю ультрафильтра. Поэтому именно такие ультрапроизведения (фильтрованные по модулю ультрафильтра) представляют основной интерес для логики.

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

Теорема 77 (Лося об ультрапроизведениях).

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

Наглядно утверждение теоремы можно сформулировать так: голосование можно проводить не только по атомарным вопросам, а для любых формул. Для замкнутых формул про параметры можно ничего не говорить, и мы получаем, что формула истинна в ультрапроизведении, если и только если она истинна в большинстве (с точки зрения ультрафильтра) сомножителей. В частности, если формула истинна во всех сомножителях, то она истинна и в ультрапроизведении. Это важное утверждение заслуживает особого упоминания:

Следствие. Ультрапроизведение семейства моделей некоторой теории является моделью той же теории.

Докажем теорему Лося индукцией по построению формулы. Для атомарных формул оно непосредственно следует из определения истинности предикатов.

Пусть формула является конъюнкцией двух других формул , для которых утверждение уже верно. Тогда множество тех индексов, для которых истинно, является пересечение множеств тех индексов, где истинны

и . Тем самым нам нужно такое свойство ультрафильтра: пересечение двух множеств является большим тогда и только тогда, когда оба они большие. Оно непосредственно следует из определения фильтра (здесь неважно, что это ультрафильтр), поскольку пересечение содержится в обоих множествах.



Для объединения соответствующее свойство звучит так: объединение двух множеств большое тогда и только тогда, когда хотя бы одно из множеств и большое. В одну сторону (если одно из множеств большое, то и объединение таково) это вытекает из определения фильтра. В обратную сторону надо воспользоваться свойствами ультрафильтра: если большое, а оба множества и — нет, то они малые, их дополнения большие, пересечение дополнений большое, и не пересекается с , что невозможно.

Пусть формула имеет вид . Тогда имеет место такая цепочка: ( истинна в ультрапроизведении ложна в неммножество индексов тех сомножителей, где истинна, не является большимэто множество является малымего дополнение большоемножество номеров тех сомножителей, где ложна (то есть истинна), большое).

Импликация сводится к уже рассмотренным случаям (

эквивалентна ); можно также сразу заменить формулу на эквивалентную без импликации.

Наиболее интересен случай кванторов. Можно ограничиться квантором существования (квантор всеобщности сводится к нему и к отрицаниям). Он разбирается так (мы используем не вполне корректные обозначения — надеемся, они не вызовут путаницы). Пусть формула

истинна в ультрапроизведении. Это значит, что существует функция , для которой

истинно в ультрапроизведении. По предположению индукции это означает, что для большинства формула

истинна в . Но тогда для этих индексов и формула

истинна в , что и требовалось. Обратное рассуждение аналогично: если для большинства найдется соответствующее значение , то эти можно собрать в функцию (доопределив ее как угодно на малом множестве остальных ), и эта функция будет искомым значением в ультрапроизведении.

Теорема Лося доказана.

Мы уже говорили, что произведение нормальных интерпретаций может не быть нормальным. Но теорема Лося гарантирует, что в ультрапроизведении нормальных интерпретаций выполнены аксиомы равенства (поскольку они выполнены в каждом сомножителе), и потому равенство является отношением эквивалентности, и классы эквивалентности уже дают нормальную интерпретацию (с теми же истинными формулами).



Теорема Лося позволяет дать прямое доказательство теоремы компактности (теорема 50). Она утверждает, что если всякое конечное подмножество данного множества замкнутых формул совместно (имеет модель), то и все множество совместно.

Модель для всего множества строится как ультрапроизведение. Индексами будут конечные подмножества множества . Для каждого из них сомножителем будет существующая по условию модель. Теперь надо правильно подобрать фильтр на семействе конечных подмножеств множества . Нам нужно, чтобы для каждого семейство всех конечных подмножеств, содержащих , было бы большим. (В этом случае теорема Лося гарантирует, что будет истинно в ультрапроизведении.)

Как построить такой фильтр? Для каждого конечного рассмотрим семейство всех конечных подмножеств, содержащих . Очевидно, пересечение таких семейств снова будет семейством такого вида (), так что после добавления всех надмножеств всех таких множеств получится фильтр. Остается расширить этот фильтр до ультрафильтра по теореме 75. Теорема компактности доказана.

Поучительно проследить до конца, что дает такого рода построение для какого-нибудь конкретного примера. Вспомним построение нестандартного натурального ряда. Оно использовало теорему компактности. Сочетая его с приведенным только что доказательством теоремы компактности (и кое-что упростив), получаем такую конструкцию.

Рассмотрим натуральные числа как интерпретацию сигнатуры . Рассмотрим ультрапроизведение счетного числа таких интерпретаций по модулю какого-либо неглавного ультрафильтра. Теорема Лося говорит, что в этой интерпретации будут истинны те же формулы, что в натуральном ряду, то есть что элементарно эквивалентна стандартной интерпретации .

Покажем, что не изоморфна . В самом деле, при таком изоморфизме нуль обязан переходить в элемент (точнее, в класс этого элемента относительно равенства), поскольку такой класс обладает свойствами нуля, однозначно его определяющими (в , а потому и в ). По аналогичным причинам единица переходит в класс и вообще число соответствует классу .А класс отличается от любого класса (они совпадают в единственном сомножителе, а одноэлементное множество является малым, так как ультрафильтр неглавный). Таким образом, построенная нами модель

не является стандартной.

Аналогичное рассуждение позволяет построить и нестандартные модели действительных чисел (о которых мы будем говорить в следующем разделе).


Содержание раздела