Матлогика · Часть II — Мощности множеств (11–17)

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

Часть II · Мощности множеств (билеты 11–17)

11

Эквивалентные множества и их свойства.

определение Множества X, Y равномощны (эквивалентны), X∼Y, если существует биекция f:X↔Y (взаимно однозначное соответствие).

Свойства. Отношение ∼ — отношение эквивалентности:

  • рефлексивность: X∼X (тождественное отображение);
  • симметричность: X∼Y ⇒ Y∼X (обратная биекция f−1);
  • транзитивность: X∼Y, Y∼Z ⇒ X∼Z (композиция g∘f).

Кроме того согласовано с операциями: если X∼X′, Y∼Y′, то X×Y ∼ X′×Y′ и XY∼X′Y′; при непересекающихся частях — X⊔Y ∼ X′⊔Y′.

на пальцах Равномощность = «можно идеально разбить на пары, без остатка с обеих сторон». Это и есть определение «одинакового количества», работающее и для бесконечных множеств. Классы эквивалентности по ∼ и называются мощностями (кардинальными числами, б.22).
12

Теорема Кантора – Шрёдера – Бернштейна.

формулировка Если есть инъекция f:X↪Y и инъекция g:Y↪X, то существует биекция X↔Y. Кратко: |X|≤|Y| и |Y|≤|X| ⇒ |X|=|Y|. (Аксиома выбора не нужна.)
идея доказательства (цепи / неподвижная точка) Назовём элемент x∈X «X-нет-прообраза», если x∉g(Y). Запустим из таких элементов «цепочки», чередуя f и g. Формально положим
C0=X∖g(Y),   Cn+1=g(f(Cn)),   C=⋃nCn.
Определим
h(x)= f(x), если x∈C;   h(x)=g−1(x), если x∉C.
Проверяется, что h корректна (вне C прообраз g−1 существует и единствен) и является биекцией. ∎
на пальцах Если X целиком «помещается» внутрь Y, и одновременно Y помещается внутрь X (оба раза без склеек), то на самом деле они одного размера — хотя явную биекцию «увидеть» бывает трудно. Теорема гарантирует её существование. Пример: [0,1]∼(0,1) — вложения в обе стороны очевидны, биекция «на глаз» — нет.
13

Счётные множества и их свойства.

определение Множество счётно, если оно равномощно ℕ (его элементы можно занумеровать в бесконечную последовательность x0,x1,… без повторов). Мощность обозначают ℵ0.

Свойства.

  • Любое бесконечное подмножество счётного множества счётно.
  • ℕ×ℕ счётно (нумерация Кантора «по диагоналям»); поэтому ℤ, ℚ и любое конечное произведение счётных множеств счётны.
  • Счётное объединение счётных множеств счётно (нужна счётная аксиома выбора).
  • Множество всех конечных слов/последовательностей над счётным алфавитом счётно.
  • ℵ0 — наименьшая бесконечная мощность: всякое бесконечное множество содержит счётное подмножество (нужна AC).
на пальцах «Счётно» = «можно составить бесконечный список, в котором каждый элемент рано или поздно встретится на конечном месте». Удивительно: дробей столько же, сколько целых чисел — их можно выстроить в один ряд. А вот вещественных чисел уже нельзя (б.15) — это «большая» бесконечность.
14

Множества мощности континуума и их свойства.

определение Множество имеет мощность континуума 𝔠, если оно равномощно ℝ. Эквивалентно: равномощно {0,1}ℕ (всем последовательностям из нулей и единиц) или 𝒫(ℕ) (всем подмножествам ℕ). Поэтому 𝔠 = 2ℵ0.

Свойства.

  • ℝ ∼ (0,1) ∼ [0,1] ∼ ℝn ∼ ℝℕ.
  • 𝔠+𝔠=𝔠,   𝔠·𝔠=𝔠 (значит ℝ²∼ℝ — у плоскости столько же точек, сколько у прямой!),   𝔠ℵ0=𝔠.
  • ℵ0+𝔠=𝔠,   ℵ0·𝔠=𝔠.
  • Множество иррациональных чисел, канторово множество — мощности 𝔠.
на пальцах «Континуум» = «столько, сколько точек на отрезке». Парадоксально, но в квадрате точек ровно столько же, сколько на стороне (𝔠·𝔠=𝔠): размерность на «количество точек» не влияет. И эта бесконечность строго больше счётной (б.16).
15

Связь между счётными множествами и множествами мощности континуума.

главные факты
  • ℵ0 < 𝔠 — континуум строго больше счётного: биекции ℕ↔ℝ нет.
  • 𝔠 = 2ℵ0 — континуум есть мощность множества подмножеств счётного.
  • Добавление или выбрасывание счётного множества не меняет континуум: |A|=𝔠, B счётно ⇒ |A∪B|=|A∖B|=𝔠 (так, иррациональных — 𝔠).
  • ℵ0·𝔠=𝔠: счётное объединение множеств мощности 𝔠 снова имеет мощность 𝔠.
диагональный аргумент Кантора (𝔠 > ℵ₀) Пусть, от противного, все числа из (0,1) выписаны в список r1,r2,… в виде десятичных дробей. Построим число r, у которого n-я цифра отлична от n-й цифры числа rn (и не 0/9 во избежание двусмысленности). Тогда r∈(0,1), но r≠rn для всех n — противоречие со «списком всех». Значит (0,1) несчётно. ∎
на пальцах + про CH Счётное — «маленькая» бесконечность, континуум — «большая»: список всех вещественных чисел невозможен, диагональ всегда «убегает» из любого предложенного списка. Гипотеза континуума (CH): есть ли мощность строго между ℵ0 и 𝔠? Ответ не зависит от обычных аксиом (Гёдель + Коэн) — недоказуемо и неопровержимо.
16

Теорема Кантора о мощности множества всех подмножеств.

формулировка Для любого множества X верно |X| < |𝒫(X)|: множество всех подмножеств строго больше самого множества. (Вложение x↦{x} даёт |X|≤|𝒫(X)|; биекции нет.)
доказательство (диагональ) Пусть f:X→𝒫(X) — любое отображение. Рассмотрим «диагональное» множество
D = { x∈X : x∉f(x) } ⊆ X.
Если бы f было сюръекцией, нашёлся бы x0 с f(x0)=D. Тогда
x0∈D ⟺ x0∉f(x0)=D —
противоречие. Значит сюръекции X→𝒫(X) нет, и |X|<|𝒫(X)|. ∎
на пальцах Это тот же трюк, что у парадокса лжеца/брадобрея. «Список всех подмножеств» нельзя поставить во взаимно однозначное соответствие с самим множеством — диагональное множество D (те x, что «не содержатся в своём образе») всегда выпадает из любого предложенного соответствия. Следствие: наибольшей мощности нет — башня ℵ0 < 2ℵ0 < 22ℵ0 < … бесконечна. В частности |ℕ|<|𝒫(ℕ)|=𝔠.
17

Эквивалентность множеств (XY)Z и XY×Z (каррирование).

обозначение и утверждение XY — множество всех функций Y→X. Требуется построить биекцию
(XY)Z ∼ XY×Z
На языке кардиналов это закон степеней (ab)c = ab·c с a=|X|, b=|Y|, c=|Z|.
построение биекции Элемент левой части — функция F:Z→(Y→X): каждому z она сопоставляет функцию F(z):Y→X. Сопоставим ей функцию двух аргументов
Φ(F):Y×Z→X,   Φ(F)(y,z) = F(z)(y).
Обратно: по функции G:Y×Z→X строим z ↦ ( y ↦ G(y,z) ). Эти два отображения взаимно обратны, значит Φ — биекция. ∎
на пальцах «Функция, которая по z выдаёт функцию от y» хранит ровно ту же информацию, что «функция от пары (y,z)». Это каррирование (приём из программирования: функция двух аргументов ⟷ функция, возвращающая функцию). Проверка на конечных множествах: слева (|X||Y|)|Z|, справа |X||Y|·|Z| — совпадает по закону степеней.