Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 46
Текст из файла (страница 46)
Что можно сказать про фильтрованное произведение по главномуфильтру?Вернёмся к нашему примеру: произведению линейно упорядочен-206Теории и модели[гл. 5]ных множеств. Будет ли оно линейно упорядоченным? Это зависитот фильтра. Например, если фильтр состоит только из множестваS, то фильтрованное произведение совпадает с определённым ранее, и линейного порядка не получится. Но если фильтр являетсяультрафильтром, то будет. В самом деле, рассмотрим два элементаs 7→ as и s 7→ bs в произведении и два множества {s | as 6 bs } и{s | as > bs }. В объединении они покрывают всё S, и потому (еслиу нас ультрафильтр) одно из них должно быть большим (если ононе большое, то оно малое, его дополнение большое и содержится вовтором множестве).163.
Докажите, что в фильтрованном произведении нормальных интерпретаций функции и предикаты корректны относительно равенства (тоесть совпадения почти всюду): при замене аргументов на равные значение функции совпадает с прежним почти всюду, а значение предиката неменяется.Это утверждение можно сформулировать так: аксиомы равенстваистинны в фильтрованном произведении нормальных интерпретаций.
Для ультрафильтров верно и более общее свойство: любая формула, истинная во всех интерпретациях, истинна в фильтрованномпроизведении по модулю ультрафильтра. Поэтому именно такие ультрапроизведения (фильтрованные по модулю ультрафильтра) представляют основной интерес для логики.Мы сейчас докажем это свойство по индукции. Как обычно, надопредварительно распространить его на формулы с параметрами.Теорема 78 (Лося об ультрапроизведениях).
Пусть параметрамиформулы ϕ являютсяQ переменные a, b, . . . Она будет истинной в ультрапроизведении s∈S Ms при значениях параметров α, β, . . . тогдаи только тогда, когда множество тех s, при которых ϕ истинна в Msпри значениях параметров αs , βs , . . . , принадлежит ультрафильтру.Наглядно утверждение теоремы можно сформулировать так: голосование можно проводить не только по атомарным вопросам, а длялюбых формул. Для замкнутых формул про параметры можно ничего не говорить, и мы получаем, что формула истинна в ультрапроизведении, если и только если она истинна в большинстве (с точкизрения ультрафильтра) сомножителей. В частности, если формулаистинна во всех сомножителях, то она истинна и в ультрапроизведении. Это важное утверждение заслуживает особого упоминания:Следствие.
Ультрапроизведение семейства моделей некоторой теории является моделью той же теории. Докажем теорему Лося индукцией по построению формулы.[п. 6]Ультрафильтры и компактность207Для атомарных формул оно непосредственно следует из определенияистинности предикатов.Пусть формула ϕ является конъюнкцией двух других формулψ ∧ η, для которых утверждение уже верно. Тогда множество тех индексов, для которых ϕ истинно, является пересечение множеств техиндексов, где истинны ψ и η.
Тем самым нам нужно такое свойствоультрафильтра: пересечение двух множеств является большим тогдаи только тогда, когда оба они большие. Оно непосредственно следует из определения фильтра (здесь неважно, что это ультрафильтр),поскольку пересечение содержится в обоих множествах.Для объединения соответствующее свойство звучит так: объединение S ∪ T двух множеств большое тогда и только тогда, когда хотябы одно из множеств S и T большое.
В одну сторону (если одно измножеств большое, то и объединение таково) это вытекает из определения фильтра. В обратную сторону надо воспользоваться свойствами ультрафильтра: если S ∪T большое, а оба множества S и T —нет, то они малые, их дополнения большие, пересечение дополненийбольшое, и не пересекается с S ∪ T , что невозможно.Пусть формула ϕ имеет вид ¬ψ. Тогда имеет место такая цепочка: (ϕ истинна в ультрапроизведении) ⇔ (ψ ложна в нём) ⇔⇔ (множество индексов тех сомножителей, где ψ истинна, не является большим) ⇔ (это множество является малым) ⇔ (его дополнениебольшое) ⇔ (множество номеров тех сомножителей, где ψ ложна (тоесть ϕ истинна), большое).Импликация сводится к уже рассмотренным случаям (ψ → η эквивалентна ¬ψ ∨ η); можно также сразу заменить формулу на эквивалентную без импликации.Наиболее интересен случай кванторов. При этом можно ограничиться квантором существования (квантор всеобщности сводится кнему и к отрицаниям).
Он разбирается так (мы используем не вполнекорректные обозначения — надеемся, они не вызовут путаницы).Пусть формула ∃x ϕ(x, y, z, . . . ) истинна в ультрапроизведении. Этозначит, что существует функция x : s 7→ xs , для которой ϕ(x, y, z, . . . )истинно в ультрапроизведении. По предположению индукции этоозначает, что для большинства s формула ϕ(xs , ys , zs , . . . ) истиннав Ms . Но тогда для этих индексов s и формула ∃x ϕ(x, y, z, . . . ) истинна в Ms , что и требовалось. Обратное рассуждение аналогично:если для большинства s найдётся соответствующее значение xs , тоэти xs можно собрать в функцию (доопределив её как угодно намалом множестве остальных s), и эта функция будет искомым зна-208Теории и модели[гл.
5]чением x в ультрапроизведении.Теорема Лося доказана. Мы уже говорили, что произведение нормальных интерпретацийможет не быть нормальным. Но теорема Лося гарантирует, что вультрапроизведении нормальных интерпретаций выполнены аксиомы равенства (поскольку они выполнены в каждом сомножителе), ипотому равенство является отношением эквивалентности, и классыэквивалентности уже дают нормальную интерпретацию (с теми жеистинными формулами), как мы видели в разделе 5.1.Теорема Лося позволяет дать прямое доказательство теоремыкомпактности (теорема 50, с.
153). Она утверждает, что если всякое конечное подмножество данного множества замкнутых формулT совместно (имеет модель), то и всё множество T совместно.Модель для всего множества T строится как ультрапроизведение.Индексами будут конечные подмножества множества T . Для каждого из них сомножителем будет существующая по условию модель.Теперь надо правильно подобрать фильтр на семействе конечныхподмножеств множества T .
Нам нужно, чтобы для каждого t ∈ Tсемейство всех конечных подмножеств, содержащих t, было бы большим. (В этом случае теорема Лося гарантирует, что t будет истиннов ультрапроизведении.)Как построить такой фильтр? Для каждого конечного T 0 ⊂ Tрассмотрим семейство S(T 0 ) всех конечных подмножеств, содержащих T 0 . Очевидно, пересечение таких семейств снова будет семейством такого вида (S(T 0 ) ∩ S(T 00 ) = S(T 0 ∪ T 00 )), так что после добавления всех надмножеств всех таких множеств получится фильтр.Остаётся расширить этот фильтр до ультрафильтра по теореме 76.Теорема компактности доказана.Поучительно проследить до конца, что даёт такого рода построение для какого-нибудь конкретного примера. Вспомним построениенестандартного натурального ряда на с. 193.
Оно использовало теорему компактности. Сочетая его с приведённым только что доказательством теоремы компактности (и кое-что упростив), получаемтакую конструкцию.Рассмотрим натуральные числа как интерпретацию сигнатуры(=, +, ×). Рассмотрим ультрапроизведение ∗N счётного числа такихинтерпретаций по модулю какого-либо неглавного ультрафильтра.Теорема Лося говорит, что в этой интерпретации будут истинны теже формулы, что в натуральном ряду, то есть что ∗N элементарноэквивалентна стандартной интерпретации N.[п. 7]Нестандартный анализ209Покажем, что N не изоморфна ∗N.
В самом деле, при таком изоморфизме нуль обязан переходить в элемент (0, 0, 0, . . . ) (точнее,в класс этого элемента относительно равенства), поскольку такойкласс обладает свойствами нуля, однозначно его определяющими(в N, а потому и в ∗N). По аналогичным причинам единица переходит в класс (1, 1, 1, . . . ) и вообще число k соответствует классу(k, k, k, .
. . ). А класс (0, 1, 2, 3, 4, . . . ) отличается от любого класса(k, k, k, . . . ) (они совпадают в единственном сомножителе, а одноэлементное множество является малым, так как ультрафильтр неглавный). Таким образом, построенная нами модель ∗N не является стандартной.Аналогичное рассуждение позволяет построить и нестандартныемодели действительных чисел (о которых мы будем говорить в следующем разделе).5.7.
Нестандартный анализОдин из создателей теории моделей, А. Робинсон, заметил, чтос её помощью можно придать точный смысл понятиям «бесконечномалых» и «бесконечно больших» величин, с которыми оперировалиещё Ньютон и Лейбниц и которые затем были изгнаны и замененырассуждениями с эпсилонами и дельтами.Это направление получило название нестандартного анализа.Целей тут две: во-первых, упростить доказательства известных теорем, во-вторых, использовать методы нестандартного анализа дляполучения новых результатов. Насколько эти цели достигнуты затридцать с лишним лет, прошедших с возникновения нестандартного анализа?Простота доказательств — дело вкуса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
