Матлогика · Часть V — Логика предикатов и модели (27–35)

Строгое определение → идея доказательства → объяснение «на пальцах» → типичные ловушки. Слева — оглавление по всем 5 файлам: текущий файл листается мгновенно, билеты других файлов (со стрелкой ↗) открываются в своём файле. Файлы держите в одной папке.

Часть V · Логика предикатов и модели (билеты 27–35)

Логика предикатов: сигнатура, термы, формулы, модель.

сигнатура и термы Сигнатура σ — набор символов: константы, функциональные символы (каждый со своей местностью) и предикатные символы (со местностью). Термы строятся индуктивно: переменные x,y,… и константы — термы; если f n-местный и t₁,…,t_n — термы, то f(t₁,…,t_n) — терм. Термы обозначают элементы.

формулы Атомарные: P(t₁,…,t_n) и t₁=t₂. Составные: замыкание по связкам ¬,∧,∨,→ и кванторам ∀x φ, ∃x φ. Переменная связана, если под своим квантором, иначе свободна; формула без свободных переменных — предложение.

модель (структура) M=⟨A; σ^M⟩: непустой носитель A и интерпретация — константам элементы A, n-местным функц. символам отображения Aⁿ→A, n-местным предикатам отношения ⊆Aⁿ.

на пальцах Сигнатура — это «словарь» (какие операции и отношения вообще есть). Термы — «существительные» (указывают на объекты), формулы — «утверждения» (бывают И/Л). Модель — конкретный мир, где словарь наполнен смыслом: например σ={+,·,0,1,<} можно интерпретировать на ℕ, ℤ, ℝ — это разные модели одного языка.

Истинность формулы на модели (определение Тарского).

значение терма Фиксируем оценку s переменных (s(x)∈A). Значение терма: x^M[s]=s(x), c^M[s]=c^M, f(t₁,…,t_n)^M[s] = f^M(t₁^M[s],…,t_n^M[s]).

отношение истинности M⊨φ[s] Индукция по формуле:

M⊨P(t₁,…,t_n)[s] ⟺ (t₁^M[s],…,t_n^M[s])∈P^M; M⊨(t₁=t₂)[s] ⟺ значения равны;
связки ¬,∧,∨,→ — по таблицам истинности;
M⊨∀x φ[s] ⟺ для всех a∈A: M⊨φ[s(x:=a)];
M⊨∃x φ[s] ⟺ существует a∈A: M⊨φ[s(x:=a)].

Для предложения истинность не зависит от s; пишем M⊨φ.

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

на пальцах Определение Тарского — это аккуратное «раскрытие смысла слоями»: смысл сложной формулы сводится к смыслу подформул, а кванторы заставляют пробежать весь носитель. Тонкость кванторов: ∀ и ∃ «смотрят» на размер и устройство модели — одно и то же предложение может быть истинно на ℝ и ложно на ℚ.

Элиминация кванторов. Пример: плотный линейный порядок.

определение Теория T допускает элиминацию кванторов (QE), если для каждой формулы φ(x) найдётся бескванторная ψ(x) с T⊨φ↔ψ. Достаточно уметь убирать один ∃x из конъюнкции литералов.

пример: DLO (плотный линейный порядок без концов) Аксиомы: линейный порядок, плотность ∀x∀y(x<y→∃z\,x<z<y), нет наименьшего и наибольшего. Ключевой шаг элиминации:

∃x (a₁<x ∧ … ∧ x<b₁ ∧ …) ⟺ (все a_i < все b_j)

частный случай ∃x(a<x<b) ⟺ a<b. Так любой ∃ сводится к сравнениям параметров без x ⟹ QE.

следствия QE DLO полна и разрешима; (ℚ,<) и (ℝ,<) элементарно эквивалентны. Определимые (с параметрами) подмножества ℚ — это в точности конечные объединения точек и интервалов с концами среди параметров.

на пальцах «Кванторы можно вычистить» — значит теория прозрачна: любое сложное свойство переписывается через простые сравнения. Если параметров между a и b «есть место», точка вставляется (плотность), поэтому ∃x эквивалентен простому условию на концы.

Выразимость (определимость). Метод автоморфизмов.

определимость Множество D⊆Aⁿ определимо (формулой φ(x), возможно с параметрами p), если D={a: M⊨φ[a,p]}. Так же определимы элементы (как D из одной точки) и функции (через графики).

метод автоморфизмов Ключевой факт: любой автоморфизм π модели M сохраняет всякое определимое без параметров множество; если есть параметры p, то — всякий автоморфизм, неподвижный на p. Доказательство неопределимости: предъявить автоморфизм, который двигает точку, обязанную лежать в D (или меняет местами элементы, которые формула «не имеет права» различать).

образцы В (ℝ,<) ни одна константа не определима (порядковые автоморфизмы действуют транзитивно). В (ℂ,+,·) число i неопределимо: комплексное сопряжение — автоморфизм, меняющий i↔−i. В (ℚ,<) определимы только интервалы/точки с концами-параметрами (б.29).

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

Фильтры и ультрафильтры. Вложение фильтра в ультрафильтр.

определения Фильтр на множестве I — семейство F⊆P(I) с: I∈F, ∅∉F, замкнутость вверх (X∈F, X⊆Y ⟹ Y∈F) и по конечным пересечениям (X,Y∈F ⟹ X∩Y∈F).
Ультрафильтр — максимальный фильтр; эквивалентно: для каждого X⊆I ровно одно из X∈F, I∖X∈F.

примеры и характеризация Главный ультрафильтр: {X: i₀∈X}. Фильтр Фреше (дополнения конечных множеств) на бесконечном I — не ультрафильтр; любой содержащий его ультрафильтр неглавный. Эквивалентная характеризация ультрафильтра: «решает» про каждое X — большое оно (∈F) или малое.

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

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

Центрированные системы множеств и вложение в фильтр.

определение (FIP) Система S⊆P(I) центрирована (обладает свойством конечных пересечений, FIP), если любое конечное пересечение её членов непусто: S₁∩…∩S_k≠∅.

теорема Всякая центрированная система порождает фильтр, а значит вкладывается в ультрафильтр. Построение: берём

F = { X⊆I : X ⊇ S₁∩…∩S_k для некоторых S_i∈S }.

Это фильтр: ∅∉F ровно из-за FIP (конечные пересечения непусты), замкнутость вверх и по пересечениям очевидна. Дальше — вложение в ультрафильтр (б.31). ∎

зачем это нужно Это «рабочий инструмент» для теоремы компактности (б.35): из набора попарно/конечно совместимых условий собираем единый ультрафильтр-свидетель. Родственно топологической характеризации компактности через центрированные системы замкнутых множеств.

на пальцах «Если куски конечно не противоречат друг другу (любая горстка имеет общую точку), то существует общий фильтр, делающий их все большими». Локальная совместимость поднимается до глобального согласия.

Ультрапроизведение моделей.

конструкция Дан набор моделей {M_i}_i∈I одной сигнатуры и ультрафильтр U на I. На декартовом произведении ∏A_i вводим отношение

f ∼_U g ⟺ { i : f(i)=g(i) } ∈ U.

Ультрапроизведение ∏M_i/U — фактор-множество ∏A_i /∼_U; операции и предикаты определяются покомпонентно «почти всюду»: P([f₁],…,[f_n]) ⟺ { i : M_i⊨P(f₁(i),…,f_n(i)) }∈U. Если все M_i=M — это ультрастепень M^I/U.

корректность ∼_U — отношение эквивалентности (рефлексивность: I∈U; транзитивность: пересечение двух U-множеств в U). Операции и предикаты не зависят от представителей классов — снова потому, что согласие «на U-большом множестве» устойчиво к пересечениям.

на пальцах Ультрапроизведение — это «голосование по ультрафильтру»: элемент — это последовательность (f(i))_i, а две последовательности считаются равными, если совпадают на «большом» (по U) множестве индексов. Значение любого утверждения определяется тем, что выполнено у почти всех сомножителей.

Теорема Лося (Łoś).

формулировка Пусть M=∏M_i/U. Тогда для любой формулы φ и элементов [f₁],…,[f_n]:

M ⊨ φ([f₁],…,[f_n]) ⟺ { i : M_i ⊨ φ(f₁(i),…,f_n(i)) } ∈ U.

«Истина в ультрапроизведении = истина почти всюду (по U)».

идея доказательства (индукция по φ) Атомарные — по определению конструкции. ∧: пересечение двух U-множеств снова в U. ¬: тут нужна ультра-свойство — ровно одно из X, I∖X лежит в U (для произвольного фильтра не прошло бы). ∃: если на U-большом множестве индексов свидетель есть, аксиомой выбора собираем функцию-свидетеля g; обратно очевидно.

следствие Диагональное вложение a↦[const_a] модели в свою ультрастепень — элементарно: M ≡ M^I/U (элементарно эквивалентны). Это даёт нестандартные модели (напр. с бесконечно большими/малыми элементами).

на пальцах Теорема Лося — «мотор» всей теории: она переносит истинность с сомножителей на произведение по правилу большинства (по U). Именно роль ¬ объясняет, почему нужен ультрафильтр, а не просто фильтр: судья обязан выносить ровно один вердикт.

Теорема Гёделя–Мальцева (компактность) через ультрапроизведения.

формулировка (компактность) Множество предложений Σ имеет модель тогда и только тогда, когда модель есть у каждого его конечного подмножества.

идея в одной фразе Сторона «⟸» нетривиальна. У каждого конечного куска Σ модель есть — нужно «склеить» все эти частичные модели в одну модель всего Σ. Склейку делает ультрапроизведение.

доказательство «⟸» по шагам Пусть каждое конечное подмножество Σ выполнимо.

Обозначим через I набор всех конечных подмножеств Σ. Для каждого i∈I возьмём модель M_i, в которой истинны все предложения из i (она есть по условию).
Для каждого предложения φ∈Σ соберём те куски, что содержат φ: J_φ = { i∈I : φ∈i }. Любое конечное пересечение J_φ₁∩…∩J_φₙ непусто — в нём лежит сам кусок {φ₁,…,φₙ}. Значит семейство всех J_φ центрировано и вкладывается в некоторый ультрафильтр U на I (б.31–32).
Возьмём ультрапроизведение M* = ∏ M_i / U. По теореме Лося (б.34) предложение истинно в M* в точности тогда, когда оно истинно «почти во всех» M_i — то есть на множестве индексов из U.
Берём любое φ∈Σ. Оно истинно во всех M_i, у которых φ∈i, поэтому множество «где φ истинно» содержит J_φ, а J_φ∈U. Значит M* делает φ истинным.

Это верно для каждого φ∈Σ, поэтому M* — модель всего Σ. ∎

следствия Если Σ⊨φ, то уже какое-то конечное Σ₀⊆Σ даёт Σ₀⊨φ (следование «финитно»). Отсюда же — существование нестандартных моделей арифметики и анализа, а также теоремы Лёвенгейма–Сколема.

на пальцах «Локально совместимо ⟹ совместимо целиком»: если ни один конечный кусок теории не противоречив (у каждого есть модель), то модель есть и у всей теории. Ультрафильтр U — это способ честно «проголосовать» среди бесконечного числа частичных моделей и собрать из них одну общую.