Матлогика · Части III–IV — Порядки, выбор, числа (18–26)

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

Часть III · Порядки, выбор, числа (билеты 18–24)

18

Вполне упорядоченные множества. Трансфинитная индукция.

определения Линейный (полный) порядок — рефлексивный, антисимметричный, транзитивный и сравнимый (любые два элемента сравнимы). Вполне упорядоченное множество (в.у.м.) — линейный порядок, в котором у каждого непустого подмножества есть наименьший элемент.
∀S⊆W (S≠∅ ⟹ ∃ min S)
трансфинитная индукция Чтобы доказать ∀x∈W: P(x), достаточно показать: если P верно для всех y<x, то P(x). (Нет отдельной «базы»: для наименьшего элемента множество меньших пусто, посылка выполнена тривиально.) Почему работает: если бы P где-то нарушалось, у множества контрпримеров был бы наименьший элемент x₀ — но тогда для всех y<x₀ верно P, значит верно и P(x₀), противоречие.
ключевое свойство В в.у.м. нет бесконечно убывающих цепочек x₀>x₁>x₂>… (иначе у их множества не было бы минимума). Это эквивалентная характеристика фундированности.
на пальцах Обычная индукция по ℕ — частный случай: ℕ вполне упорядочено. «Вполне» = можно всегда «начать с самого левого» в любом куске. Пример в.у.м.: ℕ, или 0<1<2<…<ω<ω+1<…. А вот ℤ и [0,1]⊆ℝ не вполне упорядочены обычным порядком (у ℤ нет минимума, у (0,1] нет).
19

Аксиома выбора. Теорема Цермело о полном упорядочении.

аксиома выбора (AC) Для любого семейства непустых множеств {Ai}i∈I существует функция выбора f с f(i)∈Ai для всех i. Эквивалентно: произведение непустых множеств непусто, ∏Ai≠∅.

Теорема Цермело. Любое множество можно вполне упорядочить (на любом X существует отношение, делающее его в.у.м.). Это эквивалентно AC.

идея (AC ⟹ полное упорядочение) Берём функцию выбора f на всех непустых подмножествах X. Трансфинитно строим элементы: x₀=f(X), x₁=f(X∖{x₀}), …, xα=f(X∖{xβ:β<α}) — «выбираем по одному» из ещё не использованных, пока они не кончатся. Порядок xα<xβ ⟺ α<β — вполне упорядочивает X. ∎
осторожно AC неконструктивна: она утверждает существование выбора/упорядочения, не предъявляя его. Знаменитое следствие: вполне упорядочить ℝ можно, но явную формулу для такого порядка выписать нельзя.
на пальцах AC — «можно одновременно выбрать по носку из бесконечного числа пар носков, даже если пары неразличимы». Для ботинок выбор явный («бери левый»), для носков — нужна AC. Теорема Цермело удивительна тем, что любое множество, даже ℝ, в принципе можно расставить в в.у.-цепочку.
20

Лемма Цорна и её применения.

формулировка Пусть (P,≤) — частично упорядоченное множество, в котором у каждой цепи (линейно упорядоченного подмножества) есть верхняя грань в P. Тогда в P есть максимальный элемент. ⟺ AC ⟺ т. Цермело
типовая схема применения Чтобы построить «максимальный объект» (базис, идеал, ультрафильтр, полное упорядочение): (1) берём P = все «частичные» объекты, упорядоченные включением; (2) проверяем, что объединение цепи частичных объектов снова частичный объект (верхняя грань); (3) Цорн даёт максимальный; (4) показываем, что максимальный — искомый «полный».
классические применения У любого векторного пространства есть базис (базис Гамеля); у любого кольца с 1 есть максимальный идеал; любой фильтр содержится в ультрафильтре (б.31); лемма Линденбаума для несчётного языка (б.6).
на пальцах «Если можно бесконечно наращивать объект, не упираясь (любую растущую башню можно увенчать), то есть и предельно большой объект, дальше которого расти некуда». Цорн, AC и Цермело — три лица одного принципа; на экзамене достаточно уметь применять Цорн по схеме выше.
21

Ординалы. Арифметика ординалов.

ординал (фон Нейман) Ординал — транзитивное множество (x∈α ⟹ x⊆α), вполне упорядоченное отношением ∈. Идея: каждый ординал есть множество всех меньших ординалов.
0=∅, 1={0}, 2={0,1}, …, ω={0,1,2,…}, ω+1=ω∪{ω}, …
Любое в.у.м. изоморфно ровно одному ординалу (его «порядковый тип»).
арифметика (через типы порядков) α+β — тип «копия α, за ней копия β». α·β — тип β копий α подряд (лексикографически на β×α). Определяются и трансфинитной рекурсией: α+0=α, α+(β+1)=(α+β)+1, на пределе — объединение.
сложение и умножение НЕкоммутативны
1+ω = ω ≠ ω+1,   2·ω = ω ≠ ω·2 = ω+ω.
1+ω: один элемент, потом ℕ — это снова просто ℕ-порядок =ω. ω+1: вся ℕ, потом ещё один элемент «на самом верху» — есть наибольший элемент, тип другой. 2·ω = ω пар = ω; ω·2 = две копии ω подряд.
нормальная форма Кантора (НФК) Любой ординал единственным образом записывается как сумма убывающих степеней ω с натуральными коэффициентами:
α = ωβ1·c1 + ωβ2·c2 + … + ωβk·ck,   β1>β2>…>βk≥0.
Это «запись по разрядам», как у обычных чисел. Правила упрощения: поглощение — при α<β: ωα·a + ωβ·b = ωβ·b (младшая степень слева от старшей исчезает); сбор подобных — ωα·a + ωα·b = ωα·(a+b); ω0=1. Пример: ω·2 + 2·ω² = ω·2 + ω² = ω² (слева 2·ω²=(2·ω)·ω=ω², затем младшее ω·2 поглощается старшим ω²). Обратный порядок не упрощается: ω² + ω·2 — уже НФК.
на пальцах Ординал — это «номер в очень длинной очереди», где после всех натуральных идёт ещё ω-й, потом ω+1-й и т.д. Складывать надо «приклеивая справа», и порядок приклеивания важен: добавить один элемент в начало бесконечной очереди — ничего не меняет, а в конец — создаёт новый «последний» тип.
22

Кардиналы. Арифметика кардиналов.

кардинал Кардинал — ординал, не равномощный никакому меньшему ординалу (начальный ординал). Каждому множеству по т. Цермело отвечает кардинал |X| — наименьший ординал, равномощный X. Бесконечные кардиналы нумеруются ординалами: ℵ₀<ℵ₁<ℵ₂<…<ℵω<…
арифметика 𝔪+𝔫=|A⊔B| (дизъюнктное объединение), 𝔪·𝔫=|A×B|, 𝔪𝔫=|AB|. Главная теорема для бесконечных: если 𝔪≤𝔫 и 𝔫 бесконечен, то
𝔪 + 𝔫 = 𝔪 · 𝔫 = 𝔫 = max(𝔪,𝔫).
(Сложение и умножение бесконечных кардиналов тривиальны — берут максимум. Вся нетривиальность — в возведении в степень: 2ℵ₀ уже больше ℵ₀, б.16.)
почему 𝔫·𝔫=𝔫 Ключевая лемма (требует AC): для любого бесконечного 𝔫 верно 𝔫·𝔫=𝔫. Доказывается трансфинитной индукцией по кардиналу с «канторовым» (диагональным) вполне упорядочением пар на κ×κ. Отсюда уже 𝔪·𝔫≤max·max=max и 𝔪+𝔫≤𝔪·𝔫 (для 𝔫≥2).
на пальцах Для бесконечностей «сложить» и «перемножить» — всё равно что взять большую из двух: ℕ×ℕ счётно, ℝ×ℝ равномощно ℝ. Никакого «роста» от + и · нет. Единственный способ получить строго большую бесконечность — взять множество всех подмножеств, т.е. 2𝔫 (степень).
23

Равенство 𝔪+𝔪=𝔪 для бесконечного кардинала.

утверждение Для любого бесконечного кардинала 𝔪:  𝔪 + 𝔪 = 𝔪.  Равносильно: 2·𝔪 = 𝔪, то есть две непересекающиеся копии множества мощности 𝔪 вместе дают ту же мощность 𝔪.
доказательство Способ через 𝔪·𝔪=𝔪 (б.22): 𝔪 ≤ 𝔪+𝔪 ≤ 𝔪·𝔪 = 𝔪 (среднее: 𝔪+𝔪=2·𝔪≤𝔪·𝔪 при 𝔪≥2), и по Кантору–Шрёдеру–Бернштейну (б.12) 𝔪+𝔪=𝔪.
Прямой образец на ℵ₀: ℕ = (чётные) ⊔ (нечётные), биекции n↦2n и n↦2n+1 показывают ℵ₀+ℵ₀=ℵ₀. Для общего бесконечного 𝔪 нужное разбиение на две равномощные части даёт AC / вполне упорядочение. ∎
следствия «Добавление ещё одной такой же копии» бесконечность не увеличивает: ℝ ⊔ ℝ ∼ ℝ; прямая и плоскость без одной точки — той же мощности; |ℝ∖ℚ|=𝔠 (выкинуть счётное из континуума — мощность не меняется).
на пальцах «Гостиница Гильберта»: в полностью занятый бесконечный отель приезжает ещё целый бесконечный автобус — всех расселяем (старых в чётные номера, новых в нечётные). Бесконечность «проглатывает» собственную копию. Для конечных множеств это, конечно, неверно (5+5≠5) — свойство чисто бесконечное.
24

Мощность множества A×A.

утверждение Для бесконечного множества A декартов квадрат равномощен самому множеству:
|A×A| = |A|.
(Для конечного A, разумеется, |A×A|=|A|². Интересен именно бесконечный случай.)
доказательство «≥» очевидно: вложение a ↦ (a, a₀) при фиксированном a₀ даёт |A| ≤ |A×A|.
«≤», образец на ℕ: пары (m,n) нумеруются без пропусков и повторов «канторовой диагональю»
⟨m,n⟩ = (m+n)(m+n+1)/2 + m,
это биекция ℕ×ℕ → ℕ, то есть |ℕ×ℕ|=ℕ₀=|ℕ|.
Общий бесконечный случай. Вполне упорядочим A (б.19) и рассмотрим максимальное по включению частичное взаимно однозначное соответствие f:B×B↔B с B⊆A (существует по лемме Цорна, б.20). Если бы |B|<|A|, то оставшаяся часть A∖B была бы не меньше B, и соответствие можно было бы расширить — противоречие с максимальностью. Значит |B|=|A| и |A×A|=|A|. ∎
следствия Плоскость равномощна прямой: |ℝ×ℝ|=|ℝ|=𝔠; вообще 𝔪·𝔪=𝔪 для любого бесконечного кардинала 𝔪 (это и есть содержание билета — «арифметика мощностей», ср. б.22). Отсюда же 𝔪+𝔪=𝔪 (б.23).
на пальцах Кажется, что пар «вдвое больше измерений», чем точек, — но для бесконечности это не так. Точки квадрата можно занумеровать той же «длины» списком, что и точки одной стороны: бесконечность не замечает удвоения размерности. На конечных множествах это, конечно, неверно (|A×A|=n²>n).

Часть IV · Аксиоматики чисел (билеты 25–26)

25

Аксиомы Пеано. Коммутативность сложения.

аксиомы Пеано (PA) Сигнатура ⟨0, S⟩ (ноль и «следующий»). Аксиомы:
  1. 0 не является значением S: ∀x  S(x)≠0;
  2. S инъективна: ∀x∀y  S(x)=S(y)→x=y;
  3. схема индукции: [φ(0) ∧ ∀x(φ(x)→φ(S(x)))] → ∀x φ(x).
Сложение задаётся рекурсивно: x+0=x,  x+S(y)=S(x+y). (Аналогично x·0=0, x·S(y)=x·y+x.)

Теорема. Сложение коммутативно: ∀x∀y  x+y=y+x. Доказывается индукцией с двумя вспомогательными леммами.

доказательство Лемма A (0+n=n): индукция по n. База 0+0=0 по определению. Шаг: 0+S(n)=S(0+n)=S(n).
Лемма B (S(m)+n=S(m+n)): индукция по n. База: S(m)+0=S(m)=S(m+0). Шаг: S(m)+S(n)=S(S(m)+n)=S(S(m+n))=S(m+S(n)).
Итог (m+n=n+m): индукция по n. База m+0=m=0+m (лемма A). Шаг: m+S(n)=S(m+n)=S(n+m)=S(n)+m (последнее — лемма B). ∎
почему «в лоб» не выходит Определение + рекурсивно по второму аргументу. Поэтому x+0=x — по определению, а 0+x=x приходится доказывать индукцией (лемма A). Симметрия не «дана», она — теорема. Это типичная ловушка: нельзя ссылаться на коммутативность, пока она не доказана.
на пальцах Индукция — единственный «двигатель» PA: любое утверждение про все числа доказывается «эффектом домино». Коммутативность не очевидна формально именно потому, что + определено несимметрично (наращиваем правый аргумент). Сначала учим складывать слева (леммы A, B), потом склеиваем.
26

Аксиоматика действительных чисел.

ℝ — полное упорядоченное поле ℝ аксиоматизируется тремя группами:
  1. Поле: +, ·, 0, 1 с обычными законами (ассоц., коммут., дистрибутивность, обратные по + и по · для ненулевых).
  2. Линейный порядок, согласованный с операциями: x≤y⟹x+z≤y+z; x,y≥0⟹xy≥0.
  3. Аксиома полноты (супремума): всякое непустое ограниченное сверху множество имеет точную верхнюю грань sup.
категоричность Эти аксиомы категоричны: любые две модели изоморфны — ℝ определено однозначно с точностью до изоморфизма. Аксиома полноты — то, что отличает ℝ от ℚ (в ℚ множество {x:x²<2} ограничено, но sup=√2∉ℚ).
эквиваленты полноты Аксиому супремума можно заменить любым из: принцип вложенных отрезков + аксиома Архимеда; сходимость всех фундаментальных последовательностей (полнота по Коши) + Архимед; существование inf у ограниченных снизу; теорема о точной грани. Все они над упорядоченным полем эквивалентны.
тонкость: второй порядок Аксиома полноты квантифицирует по множествам (подмножествам ℝ) — это логика второго порядка. Именно поэтому достижима категоричность. В первопорядковой теории ℝ категоричности нет: по теореме компактности (б.35) есть неархимедовы модели с бесконечно малыми (нестандартный анализ).
на пальцах Поле + порядок — это «арифметика и сравнение, как в ℚ». Полнота — «на прямой нет дырок»: где последовательность хочет сойтись, там и есть число. Аксиома супремума формализует именно «непрерывность» вещественной прямой и отделяет ℝ от ℚ, у которой дырки есть (в точке √2 и т.п.).