Матлогика · Часть I — Исчисление высказываний (1–10)

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

⏱ как пройти за 1 день (≈6–8 часов)
  • 0:00–0:20. Прочитать шпаргалку-минимум — это тот каркас, на который всё навешивается. Без этих 10 определений теорию не сдать.
  • 0:20–2:00. Часть I (ИВ). Главные теоремы курса: непротиворечивость (5), Линденбаум (6), полнота (8). Их любят спрашивать «докажите».
  • 2:00–3:30. Части II–III (множества, мощности, ординалы). Много коротких, но строгих фактов. Диагональный метод Кантора (16) и КШБ (12) — обязательно уметь.
  • 3:30–4:30. Часть V (модели). Связка «фильтр → ультрафильтр → ультрапроизведение → Лось → компактность» (31–35) — это один сюжет, учить цепочкой.
  • 4:30–6:00. Часть VI (алгоритмы). Цепочка «универсальная функция → диагональ → неразрешимое перечислимое → остановка» (40–42) — тоже один сюжет.
  • Последний час. Закрыть ответ и вслух проговорить формулировку + идею каждой теоремы. Если можете объяснить «на пальцах» — вы её знаете.
★

Шпаргалка-минимум: 10 определений, без которых не сдать теорию

Это «несгораемый запас» из important.txt. Каждое определение здесь дано кратко и точно; подробный разбор — в соответствующем билете (ссылки рядом).

1. Формулы и их значения. → б.1, 27, 4, 28
ИВ: формула строится из пропозициональных переменных p,q,… связками ¬,∧,∨,→ по индукции. Предикаты: к этому добавляются термы, предикатные символы и кванторы ∀x, ∃x. Значение формулы ИВ — это И/Л, вычисляемое по таблицам истинности на наборе значений переменных; значение формулы предикатов — это И/Л на модели при фиксированной оценке свободных переменных (определение Тарского).
2. Сигнатура. → б.27
Набор символов: константы, функциональные символы (с указанием местности) и предикатные символы (с местностью). Это «словарь» языка — какие операции и отношения вообще можно упоминать.
3. Модель. → б.27
M = ⟨A; …⟩: непустое множество-носитель A плюс интерпретация каждого символа сигнатуры — константам сопоставлены элементы A, n-местным функциям — отображения An→A, n-местным предикатам — отношения ⊆ An.
4. Множества: ∪, ∩, ×.
A∪B = элементы хотя бы одного; A∩B = элементы обоих; декартово произведение A×B = { ⟨a,b⟩ : a∈A, b∈B } — множество упорядоченных пар.
5. Функции, вложения, наложения, биекции. → б.11
Функция f:A→B — каждому a ровно один f(a). Вложение (инъекция): f(a)=f(a′) ⇒ a=a′ (разные в разные). Наложение (сюръекция): каждый b∈B чем-то достигается. Взаимно однозначное (биекция) = инъекция + сюръекция (идеальное «спаривание»).
6. Мощности и их сравнение. → б.11,12,22
|A|=|B| (равномощны) — есть биекция A↔B. |A|≤|B| — есть инъекция A↪B. Теорема Кантора–Шрёдера–Бернштейна: |A|≤|B| и |B|≤|A| ⇒ |A|=|B|.
7. Счётные множества. → б.13
Равномощные ℕ, т.е. элементы можно занумеровать в бесконечный список x0,x1,x2,… без пропусков и так, что каждый встретится. Мощность ℵ0 — наименьшая бесконечная.
8. Вполне упорядоченные множества и ординалы. → б.18,21
Вполне упорядоченное — линейный порядок, в котором у любого непустого подмножества есть наименьший элемент. Ординал — «тип» такого порядка (по фон Нейману: транзитивное множество, вполне упорядоченное отношением ∈; каждый ординал = множество всех меньших).
9. Алгоритмы, машины Тьюринга. → б.36
Алгоритм — конечная механическая пошаговая процедура. Машина Тьюринга формализует это: конечное управление (состояния) + бесконечная лента из ячеек + головка, читающая/пишущая символ и сдвигающаяся влево/вправо по правилу перехода δ.
10. Вычислимые функции, разрешимые множества. → б.36,39
Функция вычислима, если её считает какая-то МТ (останавливается с ответом). Множество A разрешимо, если вычислима его характеристическая функция χA — то есть алгоритм всегда отвечает «да/нет» на вопрос «x∈A?».

Часть I · Исчисление высказываний (билеты 1–10)

оговорка про аппарат Конкретный список аксиом и правил ИВ у разных лекторов различается. Ниже — самая распространённая система (гильбертовская: 3 схемы аксиом + modus ponens) и эквивалентный взгляд через натуральный вывод. Идеи доказательств от выбора системы не зависят. Если ваш конспект задаёт другие аксиомы — сверьте именно билеты 1–3.
1

Исчисление высказываний. Формулы. Теорема о единственности представления формулы ИВ.

определение Формула ИВ определяется индуктивно:
  1. каждая пропозициональная переменная p, q, r, … — формула (атом);
  2. если A — формула, то (¬A) — формула;
  3. если A, B — формулы и □ ∈ {∧, ∨, →}, то (A □ B) — формула;
  4. других формул нет.

Теорема о единственности представления (об однозначности разбора). Каждая формула принадлежит ровно одному из видов и притом единственным образом: она либо переменная, либо имеет вид (¬A) с однозначно определённой A, либо вид (A □ B) с однозначно определёнными главной связкой □ и подформулами A, B.

идея доказательства Вводим баланс скобок: читая слово слева направо, считаем +1 на «(» и −1 на «)». Ключевая лемма: у любого собственного начального отрезка формулы баланс строго положителен (скобки «не успели закрыться»). Значит, никакой собственный начальный отрезок формулы сам формулой не является. Отсюда главная связка ищется однозначно: это та связка верхнего уровня, на которой баланс впервые становится нулевым после открывающей скобки. Дальше — индукция по длине.
на пальцах Полные скобки играют роль «обязательной разметки»: запись ((p∧q)∨r) невозможно прочитать как (p∧(q∨r)). Это как правильная скобочная последовательность — у неё ровно одно дерево вложенности. Теорема говорит, что формула — это не просто строка символов, а дерево разбора, и это дерево восстанавливается однозначно. Без этого нельзя было бы корректно определять «значение формулы» рекурсией по построению (б.4).
2

Правила вывода. Секвенции. Доказательства. Допустимые правила.

определения Секвенция Γ ⊢ A: Γ — конечное множество формул (гипотезы, посылки), A — формула (заключение). Читается «из Γ выводимо A».
Правило вывода — переход от посылок (уже доказанных секвенций/формул) к заключению. В гильбертовской системе: схемы аксиом плюс одно правило modus ponens (MP): из A и A→B получаем B.
Доказательство (вывод) формулы A из Γ — конечная последовательность формул A1,…,An=A, в которой каждая Ai есть аксиома, либо элемент Γ, либо получена из предыдущих по правилу.
типичные схемы аксиом (гильберт) A1: A→(B→A)  ·  A2: (A→(B→C))→((A→B)→(A→C))  ·  A3 — про отрицание (классически, напр. (¬B→¬A)→((¬B→A)→B)). Плюс схемы для ∧, ∨.

Выводимое vs допустимое правило. Правило «из посылок P получить заключение Q» называется:

  • выводимым (производным), если Q можно получить из P фиксированной цепочкой шагов исходной системы (есть «макрос»);
  • допустимым, если добавление этого правила не меняет множество выводимых секвенций: как только посылки выводимы, заключение тоже выводимо.
ключевой факт Всякое выводимое правило допустимо; обратное в общем случае неверно. Главный пример полезного производного/допустимого правила — теорема о дедукции: Γ, A ⊢ B  ⇒  Γ ⊢ A→B. Она радикально сокращает выводы (см. б.3).
на пальцах Аксиомы и правила — это «детали Lego и инструкция сборки». Допустимое правило — это безопасный短cut: пользуясь им, вы никогда не соберёте то, чего нельзя было собрать длинным путём. Поэтому такими правилами можно свободно пользоваться, не расширяя силу системы.
3

Доказательство секвенций φ∧¬φ ⊢ и ⊢ φ∨¬φ.

что требуется доказать Две конкретные секвенции из билета:
• φ∧¬φ ⊢ — «противоречие φ∧¬φ ни с чем не совместимо»: из него выводится ⊥, а значит и любая формула.
• ⊢ φ∨¬φ — закон исключённого третьего: φ∨¬φ доказуемо без всяких гипотез (теорема классического ИВ).
1) вывод φ∧¬φ ⊢ Три шага натурального вывода:
1. φ ∧ ¬φ — гипотеза 2. φ — выкинули второй член (∧-удаление из 1) 3. ¬φ — выкинули первый член (∧-удаление из 1) 4. ⊥ — φ и ¬φ вместе дают противоречие
Итак φ∧¬φ ⊢ ⊥. По правилу «из лжи следует что угодно» отсюда φ∧¬φ ⊢ ψ для любой формулы ψ. ∎
2) вывод ⊢ φ∨¬φ (от противного) Предположим противное — что ¬(φ∨¬φ) — и придём к противоречию:
• Допустим φ. Тогда φ∨¬φ (∨-введение) — противоречит ¬(φ∨¬φ). Значит φ невозможно, то есть доказано ¬φ. • Но из ¬φ снова φ∨¬φ (∨-введение) — опять противоречие с ¬(φ∨¬φ).
Допущение ¬(φ∨¬φ) привело к противоречию, то есть доказано ¬¬(φ∨¬φ). Снятие двойного отрицания (классическая аксиома) даёт ⊢ φ∨¬φ. ∎
тонкость про интуиционизм Первая секвенция выводится и в интуиционистском ИВ (там доказуем закон непротиворечия ⊢ ¬(φ∧¬φ) — без классических средств). А вторая, ⊢ φ∨¬φ, существенно опирается на снятие двойного отрицания и в интуиционистском ИВ не выводима (см. б.10).
на пальцах φ∧¬φ ⊢: утверждать сразу φ и не φ — это уже катастрофа, из неё формально следует всё что угодно. ⊢ φ∨¬φ: «либо φ, либо нет» — в классической логике всегда верно, потому что третьего не дано; доказываем это, показав, что отрицать такую дизъюнкцию невозможно.
4

Интерпретация ИВ. Истинность формул и секвенций на наборе переменных. Тождественная истинность.

определение Интерпретация (оценка) — функция v, сопоставляющая каждой переменной значение И или Л (1 или 0). Она однозначно (по б.1!) продолжается на все формулы таблицами истинности связок:
AB¬AA∧BA∨BA→B
ИИЛИИИ
ИЛЛЛИЛ
ЛИИЛИИ
ЛЛИЛЛИ
истинность секвенции и тавтология Секвенция Γ ⊢ A истинна на v (семантически: Γ ⊨ A), если всякий раз, когда все формулы Γ истинны на v, истинна и A.
Формула тождественно истинна (тавтология), ⊨ A, если она истинна на любой интерпретации.
на пальцах Интерпретация — это «один конкретный сценарий»: каким переменным мы приписали правду. Тавтология истинна во всех сценариях сразу (напр. A∨¬A, A→A). Семантическое следствие Γ⊨A — это «гарантия»: при любом сценарии, где верны посылки, верно и заключение. Внимание: ⊢ (синтаксис, «можно вывести по правилам») и ⊨ (семантика, «истинно в моделях») — пока это разные вещи; их совпадение — содержание теорем 5 и 8.
5

Теорема о непротиворечивости ИВ (корректность).

формулировка ИВ непротиворечиво: не существует формулы A, для которой одновременно ⊢A и ⊢¬A. Равносильно: выводимо не всё (например, ⊬ p для переменной p).
доказательство (через корректность) Лемма о корректности: всё выводимое тождественно истинно, ⊢A ⇒ ⊨A. Доказывается индукцией по длине вывода: (база) каждая аксиома — тавтология (проверка по таблице); (шаг) правило MP сохраняет истинность: если на любой v истинны A и A→B, то истинна и B.
Теперь, если бы ⊢A и ⊢¬A, то были бы тавтологиями обе — A и ¬A, что невозможно (на любой v ровно одна из них ложна). ∎
на пальцах Это «лёгкая половина». Правила вывода устроены так, что из истины делают только истину — они «не врут». Поэтому из них в принципе нельзя «вывести ложь», а значит и противоречие. Сложная половина (что выводимого достаточно много) — это полнота, б.8.
6

Вложение непротиворечивого множества формул в максимальное (лемма Линденбаума).

определения Множество формул Γ непротиворечиво, если из него нельзя вывести противоречие (нет A с Γ⊢A и Γ⊢¬A).
Γ максимально непротиворечиво, если оно непротиворечиво и добавление любой формулы вне Γ делает его противоречивым (для каждой A: либо A∈Γ, либо Γ∪{A} противоречиво).

Лемма (Линденбаум). Всякое непротиворечивое множество формул содержится в некотором максимальном непротиворечивом множестве.

доказательство (счётный язык) Занумеруем все формулы A1, A2, … Строим цепочку:
Γ0=Γ;   Γn+1 = Γn∪{An+1}, если это непротиворечиво, иначе Γn+1=Γn.
Положим Γ*=⋃nΓn. Непротиворечивость Γ*: любой вывод противоречия использует конечно много формул, значит целиком лежит в некотором Γn — но все Γn непротиворечивы. Максимальность: каждую формулу An+1 мы пытались добавить; если её нет в Γ*, то на шаге n+1 добавление давало противоречие. ∎
на пальцах Идём по списку всех утверждений и жадно добавляем каждое, если оно не ссорится с уже принятым. В итоге получаем «полное непротиворечивое мировоззрение», которое про каждую формулу определилось — принять её или нет. (Для несчётного языка вместо нумерации нужна лемма Цорна, б.20.)
7

Свойства максимального непротиворечивого множества формул.

Пусть Γ максимально непротиворечиво. Тогда:

  • Дедуктивная замкнутость: Γ⊢A ⇒ A∈Γ (всё выводимое уже внутри; иначе добавление A не портило бы непротиворечивость, противореча максимальности).
  • Полнота по отрицанию: для каждой A ровно одно из A∈Γ, ¬A∈Γ.
  • A∧B∈Γ ⟺ A∈Γ и B∈Γ.
  • A∨B∈Γ ⟺ A∈Γ или B∈Γ.
  • A→B∈Γ ⟺ (A∉Γ или B∈Γ).
  • содержит все теоремы (все A с ⊢A).
зачем это нужно Эти свойства означают, что Γ ведёт себя как интерпретация: положив v(p)=И ⟺ p∈Γ, получаем (индукцией по формуле), что v(A)=И ⟺ A∈Γ для всех A. То есть из максимального непротиворечивого множества «считывается» модель. Это мост к полноте (б.8).
на пальцах «Полное непротиворечивое мнение» по каждому вопросу говорит ровно «да» или «нет» (полнота по отрицанию) и согласовано со связками так же, как таблицы истинности. Поэтому такое множество и есть замаскированная строка таблицы истинности — конкретный сценарий v.
8

Теорема о полноте классического ИВ.

формулировка Всякая тавтология выводима: ⊨A ⇒ ⊢A. В общей форме: Γ⊨A ⇒ Γ⊢A. Вместе с корректностью (б.5) это даёт ⊢A ⟺ ⊨A — синтаксис и семантика совпадают.
доказательство (Хенкин–Линденбаум, от противного) Пусть Γ⊬A. Тогда Γ∪{¬A} непротиворечиво (иначе Γ⊢A). По лемме Линденбаума (б.6) расширим его до максимального непротиворечивого Δ. Зададим оценку v(p)=И ⟺ p∈Δ. По свойствам из б.7: v(B)=И ⟺ B∈Δ для всех B. Значит все формулы Γ⊆Δ истинны на v, а ¬A∈Δ истинна, то есть A ложна. Получили интерпретацию, где Γ верны, а A нет: Γ⊭A. Контрапозиция даёт Γ⊨A ⇒ Γ⊢A. ∎
на пальцах Полнота = «система достаточно сильна»: что всегда истинно — то и доказуемо по правилам, ничего не упущено. Логика этого доказательства: «если не доказать A, то отрицание A можно мирно достроить до целого мировоззрения — а это и есть контрпример-модель». Так несуществование вывода превращается в существование модели.
9

Понятие об интуиционизме и конструктивизме в математике.

суть Интуиционизм (Брауэр): математические объекты — это мысленные конструкции, а «истинно» значит «построено/доказано», а не «соответствует платоновской реальности». Завершённая (актуальная) бесконечность отвергается; отвергается и безусловный закон исключённого третьего и доказательство существования «от противного».
Конструктивизм: чтобы утверждать ∃x P(x), нужно предъявить конкретный x; чтобы утверждать A∨B, нужно знать, какой именно из дизъюнктов верен.
интерпретация БХК (Брауэр–Гейтинг–Колмогоров) Доказательство A∧B = пара (доказ. A, доказ. B);   A∨B = указание дизъюнкта + его доказательство;   A→B = метод, перерабатывающий доказательства A в доказательства B;   ∃x A = свидетель + доказательство;   ∀x A = метод по x;   ¬A := A→⊥.
на пальцах Девиз — «покажи». Фраза «либо гипотеза верна, либо нет» неинформативна, пока вы не умеете выяснить, что именно. Поэтому A∨¬A не принимается как универсальный принцип. Заметьте: A→¬¬A интуиционисты принимают, а вот ¬¬A→A — нет (из «нельзя опровергнуть» не следует «есть конструкция»).
10

Интуиционистское ИВ. Недоказуемость закона исключённого третьего.

что такое ИИВ Интуиционистское ИВ — тот же язык, но без аксиомы/правила, дающего классическое снятие двойного отрицания (¬¬A→A) / закон A∨¬A. Берут ⊥ и «из лжи — всё» (⊥→A), остальные интро/элим-правила, но без классического A3.

Утверждение. A∨¬A в ИИВ не выводимо.

доказательство 1 — топологическая модель (алгебра Гейтинга) Интерпретируем формулы открытыми множествами на прямой ℝ: ∧=∩, ∨=∪, ¬U=int(ℝ∖U) (внутренность дополнения). ИИВ корректно для такой семантики: выводимое получает значение «всё ℝ». Возьмём ⟦p⟧=ℝ∖{0} (открыто). Тогда
¬p = int(ℝ∖(ℝ∖{0})) = int({0}) = ∅,   p∨¬p = (ℝ∖{0})∪∅ = ℝ∖{0} ≠ ℝ.
Значение не «всё ℝ», значит p∨¬p не теорема ИИВ. ∎
доказательство 2 — модель Крипке Модель Крипке — частично упорядоченное множество «миров» (состояний знания) с монотонным форсингом (⊩ сохраняется вверх по порядку). Возьмём два мира w0 ≤ w1, где p не форсится в w0, но форсится в w1. В w0: p не форсится; ¬p значит «во всех будущих мирах p ложно», но в w1 оно истинно — значит и ¬p не форсится. Поэтому p∨¬p не форсится в w0. По корректности — не теорема. ∎
на пальцах Смысл моделей — «знание растёт со временем». В состоянии, где про p ещё ничего не решено, нет ни доказательства p, ни доказательства ¬p (вдруг в будущем p подтвердится) — поэтому дизъюнкция p∨¬p «провисает». Классически она верна, потому что классика смотрит только на финальные «истинно/ложно», игнорируя процесс узнавания.