Теорема Лося

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

История

Теорема была опубликована Ежи Лосем в 1955 году в статье «Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres» (с фр. — «Некоторые замечания, теоремы и проблемы об определимых классах алгебр»). Лось, работавший в то время в Польской академии наук, обобщил более ранние результаты Альфреда Тарского и Абрахама Робинсона о прямых произведениях и гомоморфизмах. Первоначально теорема формулировалась для алгебраических систем, но позже была распространена на любые структуры логики первого порядка.

В 1960-х годах теорема Лося стала краеугольным камнем нестандартного анализа, разработанного Абрахамом Робинсоном. С её помощью Робинсон построил нестандартные модели вещественных чисел, содержащие бесконечно малые и бесконечно большие величины. В 1970-х годах теорема активно применялась в теории ультрапроизведений, развитой Полом Коэном и другими математиками.

Формулировка

Основные понятия

Для понимания теоремы необходимо определить несколько ключевых понятий:

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

• Ультрапроизведение — это фактор-множество декартова произведения семейства структур \( \{A_i\}_{i \in I} \) по отношению эквивалентности, задаваемому ультрафильтром \( U \): две последовательности \( (a_i) \) и \( (b_i) \) эквивалентны, если множество индексов, на которых они совпадают, принадлежит \( U \). Ультрапроизведение обозначается \( \prod_{i \in I} A_i / U \). Если все сомножители одинаковы, то говорят об ультрастепени.

Утверждение теоремы

Пусть \( \{A_i\}_{i \in I} \) — семейство структур языка логики первого порядка \( \mathcal{L} \), \( U \) — ультрафильтр на множестве индексов \( I \), и \( \varphi(x_1, \dots, x_n) \) — формула языка \( \mathcal{L} \). Тогда для любой последовательности элементов \( (a_1, \dots, a_n) \) из ультрапроизведения \( \prod A_i / U \) выполняется:

\[ \prod A_i / U \models \varphi([a_1], \dots, [a_n]) \iff \{ i \in I \mid A_i \models \varphi(a_1(i), \dots, a_n(i)) \} \in U, \]

где \( [a_k] \) — класс эквивалентности последовательности \( a_k \), а \( a_k(i) \) — значение на \( i \)-м сомножителе.

В упрощённой форме: формула истинна в ультрапроизведении тогда и только тогда, когда она истинна «почти всюду» (относительно ультрафильтра) среди сомножителей.

Доказательство

Доказательство теоремы Лося проводится индукцией по сложности формулы \( \varphi \). Для атомарных формул (равенств и отношений) утверждение следует из определения ультрапроизведения. Индукционные шаги для логических связок (\( \land \), \( \lor \), \( \neg \)) и кванторов (\( \forall \), \( \exists \)) опираются на свойства ультрафильтров:

• Для конъюнкции: истинность \( \varphi \land \psi \) в ультрапроизведении означает, что множество индексов, где истинны обе формулы, принадлежит \( U \), что следует из замкнутости ультрафильтра относительно пересечений.
• Для отрицания: истинность \( \neg \varphi \) эквивалентна тому, что множество индексов, где \( \varphi \) ложна, принадлежит \( U \), что следует из свойства дополнения.
• Для квантора существования: если \( \exists x \varphi(x) \) истинно в ультрапроизведении, то существует элемент \( [a] \), такой что \( \varphi([a]) \) истинно, и по индукции множество индексов, где \( \varphi(a(i)) \) истинно, принадлежит \( U \). Обратное утверждение требует аксиомы выбора для выбора подходящих элементов.

Следствия и применения

Компактность логики первого порядка

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

Нестандартные модели

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

Теория ультрапроизведений

Теорема Лося является основой для изучения ультрапроизведений как инструмента классификации структур. Например, с её помощью доказывается, что элементарная эквивалентность двух структур (то есть совпадение всех истинных в них формул первого порядка) эквивалентна существованию изоморфизма между их ультрастепенями (теорема Кейслера — Шелаха).

Применения в алгебре

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

Критика и ограничения

Теорема Лося справедлива только для формул логики первого порядка. Для формул высших порядков (например, второго порядка) она не выполняется, так как ультрапроизведения не сохраняют свойства, выражаемые кванторами по множествам. Кроме того, доказательство теоремы существенно опирается на аксиому выбора (через существование ультрафильтров), что делает её неконструктивной в рамках теории множеств Цермело — Френкеля без аксиомы выбора.

Интересные факты

• Теорема Лося иногда называется «фундаментальной теоремой теории ультрапроизведений».
• Ежи Лось был также известен работами по теории вероятностей и математической экономике, но именно теорема Лося принесла ему наибольшую известность в математической логике.
• В 1960-х годах теорема Лося была независимо переоткрыта некоторыми математиками, что привело к её популяризации в западной литературе.

Источники

• Los, J. «Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres». — Mathematical Interpretation of Formal Systems, 1955.
• Chang, C. C.; Keisler, H. J. «Model Theory». — 3rd ed., North-Holland, 1990.
• Барвайс, Дж. (ред.). «Справочная книга по математической логике». — Часть 1: Теория моделей, Наука, 1982.
• Robinson, A. «Non-standard Analysis». — Princeton University Press, 1966.