Перейти к содержимому
Topos Uranos
Русский

Язык: итоги и задачи повышенной трудности

Краткое содержание

Этот урок завершает раздел, посвящённый языку логики высказываний. Он восстанавливает дедуктивную цепь, которая ведёт от различения правильности и истинности и от анализа парадоксов к однозначности разбора формул и к формализации высказываний и рассуждений, и указывает в каждом звене, какой принцип используется и в каком уроке он доказывается; соотносит достигнутое с планом курса и объясняет, почему уже построенный язык ставит вопрос следующего раздела, посвящённого выводу. В итоговой проверке он повторяет навыки входной проверки и заканчивается шестью задачами повышенной трудности, более сложными, чем задачи уроков, которые требуют соединять средства нескольких из них.

Цели обучения

  1. Восстановить логический порядок результатов раздела, указывая принцип, на который опирается каждый из них, и урок, в котором он доказывается.
  2. Объяснить, как сцепляются принцип замыкания, разложение на слова, лемма о весе и однозначность разбора и почему от последней зависят определения по рекурсии и сравнение формализаций.
  3. Отличать то, что раздел доказал, от того, что он принял как допущение (двузначность, схема истинности, принцип индукции и прочтение стрелки Пирса), и от того, что он оставил следующим разделам.
  4. Решать задачи, в которых сочетаются диагональная лемма, подсчёт цепочек, индукция по формулам, рассуждение о весе и развёртывание сокращений.

Чего достиг раздел

Раздел ставил целью построить, исходя из алфавита из двух символов, язык, в котором каждая формула читается единственным образом, строго доказать свойства этого языка и перекинуть мост между ним и языком, на котором мы рассуждаем. Цель достигнута с немногими оговорками, каждая из которых сделана на своём месте: двузначность и схема истинности, которые первый урок принял не как истины, а как явные допущения, чтобы исследовать, что происходит, когда они соблюдаются одновременно; принцип индукции по натуральным числам, который принимается как пятая аксиома Пеано; неформальное прочтение стрелки Пирса, которое постулируется и которое раздел о семантике превратит в определение; и необходимый минимум теории множеств (принадлежность, включение и объединение), изложенный там, где он понадобился. С этими оговорками пройденный путь можно прочесть как одну дедуктивную цепь из четырёх участков.

Рассуждать и говорить о языке

Урок о том, что такое математическая логика, определил предмет курса: не истинность высказываний, которая есть дело каждой науки, а её передачу. Рассуждение правильно, когда его форма не допускает ни одного частного случая с истинными посылками и ложным заключением, и из этого определения выведено единственное, что гарантирует правильность: если посылки истинны, то истинно и заключение; откуда у правильного рассуждения с ложным заключением есть ложная посылка, а форма неправильна в точности тогда, когда у неё есть контрпример. Тот же результат превратил анализ парадоксов в процедуру: если шаги рассуждения, которое приводит к противоречию, правильны, то какое-то допущение ложно, и разрешить парадокс значит найти, какое именно. Так был разобран лжец, в котором двузначность и схема истинности не могут одновременно соблюдаться для предложения, объявляющего себя ложным, и так были разобраны парадокс Берри и прилагательное «гетерологический». Из брадобрея извлечена общая лемма, диагональная лемма, которая доказывает, что брадобрея не существует и что неограниченный принцип свёртывания противоречив. Наконец, урок установил различие между языком-объектом и метаязыком и между употреблением выражения и его упоминанием, которое управляет всем дальнейшим: результаты раздела о формулах суть не формулы, а метатеоремы.

Язык кружков и дисков

Урок о языке логики высказываний ввёл множества и цепочки, подсчитал цепочки каждой длины (их 2n2^{n} длины nn и 2N+1−22^{N + 1} - 2 длин от 11 до NN) и построил базовый язык: переменные vn=∘n∙v_n = \sigO^{n}\sigI и единственное правило, которое из двух формул φ\varphi и ψ\psi образует ∙φψ\sigI\varphi\psi. Пункт «ничто другое не есть формула» был уточнён определением формул как цепочек, принадлежащих всем замкнутым множествам, и из этого определения выведен принцип замыкания, с помощью которого доказано, что всякая формула есть переменная или имеет вид ∙φψ\sigI\varphi\psi, но не то и другое вместе, что всякая формула кончается диском и что она содержит нечётное число дисков. Наблюдение, что переменные и отдельный диск образуют префиксный код, дало однозначное разложение на слова, а с ним и понятие веса. Урок построил также метаязык, с которым мы работаем в дальнейшем: метапеременные, стрелку Пирса, записываемую (φ↓ψ)(\varphi \downarrow \psi), и шесть официальных сокращений, каждое из которых определено один раз через предыдущие, так что всякое сокращённое выражение обозначает ровно одну цепочку.

Индукция и однозначность разбора

Урок об индукции по натуральным числам и по формулам обосновал подсчёты, которые предыдущий урок проводил «и так далее», вывел сильную индукцию из простой и, применив её к длине, получил структурную индукцию, которая оказывается той же индукцией по натуральным числам, перенесённой на формулы. С помощью этого средства он доказал лемму о весе: всякая формула весит +1+1, а всякий собственный непустой префикс по словам весит не более 00. Отсюда следуют, в этом порядке, что никакая формула не является собственным префиксом другой и что всякая составная формула читается единственным образом. Однозначность разбора есть звено, на котором держится весь остальной раздел: она обосновывает разрешающую процедуру, которую урок о языке описал как погашение долга, и узаконивает определения по рекурсии (длина, число переменных и дисков-связок, подформулы, глубина и подстановка), которые без неё могли бы приписать формуле два разных значения.

От русского языка к формулам

Урок о формализации естественного языка перекинул мост к языку, на котором мы говорим. Он зафиксировал соглашение о буквах pp, qq, rr, ss и tt как именах пяти определённых переменных, потребовал, чтобы всякая формализация объявляла свой словарь, и вывел из одного лишь постулированного прочтения стрелки Пирса прочтение каждого сокращения. С помощью однозначности разбора он доказал, что две разные группировки одних и тех же связок суть разные формулы, а с помощью рекурсивного определения длины вычислил, сколько символов содержат развёрнутые сокращения, что даёт быстрый критерий для различения формализаций. Он показал, что материальная импликация ложна лишь тогда, когда антецедент истинен, а консеквент ложен, и что это единственное прочтение, зависящее лишь от истинности частей, при котором истинны условные теоремы математики; указал, что теряет формализация (кванторы, время, причинность, модальность), и закончил формализацией целых рассуждений как множества посылок Γ\Gamma и заключения.

Следующий рисунок соединяет четыре участка в одну цепь. Каждый узел столбца есть определение или результат, пронумерованный в логическом порядке и соединённый дугой с предыдущими звеньями, которые использует его доказательство; вокруг расположены опоры, то есть принципы, к которым цепь обращается снова и снова, и каждая соединена сплошной линией со звеньями, которые на неё опираются, и пунктирной со звеном, где она устанавливается, кроме тех, что принимаются без доказательства: они изображены кольцами. Нажатие на опору выделяет все звенья, которые её используют, а каждое звено ведёт к уроку, где оно доказывается. Заметим, что разрешающая процедура, хотя и излагается в уроке о языке, занимает своё логическое место после однозначности разбора, на которую она опирается.

Опоры цепи

  • AДвузначность. Всякое высказывание истинно или ложно, и не то и другое вместе; быть ложным равносильно тому, чтобы не быть истинным. Принимается как явное допущение при анализе парадоксов. В этом модуле принимается без доказательства.
  • BСхема истинности. Предложение истинно тогда и только тогда, когда то, что оно говорит, имеет место. Принимается как явное допущение; решение Тарского сохраняет её, но лишь для предложений языка, не содержащего собственного предиката истинности. В этом модуле принимается без доказательства.
  • CПринцип индукции. Если свойство выполняется для 11 и всякий раз, когда оно выполняется для натурального числа kk, выполняется и для k+1k + 1, то оно выполняется для всех натуральных чисел. Это пятая аксиома Пеано, и она принимается. В этом модуле принимается без доказательства.
  • DДиагональная лемма. Никакой объект bb совокупности не удовлетворяет условию R(b,x)⇔¬R(x,x)R(b, x) \Leftrightarrow \neg R(x, x) для всех xx этой совокупности. Устанавливается в: 3. Диагональная лемма.
  • EПринцип замыкания. Свойством, которым обладают все переменные и которое переходит от φ\varphi и ψ\psi к ∙φψ\sigI\varphi\psi, обладают все формулы. Устанавливается в: 5. Принцип замыкания.
  • FСтруктурная индукция. Индукция по сложности формул, выведенная из сильной индукции по длине: её базу составляют переменные, а шаг индукции есть единственное правило образования. Устанавливается в: 9. Структурная индукция.
  • GОднозначность разбора. Если ∙φψ=∙φ′ψ′\sigI\varphi\psi = \sigI\varphi'\psi', где все четыре цепочки суть формулы, то φ=φ′\varphi = \varphi' и ψ=ψ′\psi = \psi'. Устанавливается в: 11. Однозначность разбора.
  • HПрочтение стрелки Пирса. Формула (φ↓ψ)(\varphi \downarrow \psi) истинна в точности тогда, когда φ\varphi и ψ\psi обе ложны. Это единственное постулируемое прочтение; остальные выводятся из него, а раздел о семантике его уточнит. В этом модуле принимается без доказательства.

  1. Участок 1 Рассуждать и говорить о языке

    • Отличать правильность от истинности и опровергать неправильную форму контрпримером.
    • Распознавать неоднозначности естественного языка и разделять прочтения высказывания.
    • Отличать язык-объект от метаязыка, а употребление выражения от его упоминания.
    • Анализировать парадокс, выделяя его допущения и решая, от какого следует отказаться.

    1. Что гарантирует правильность. Если рассуждение правильно и все его посылки истинны, то его заключение истинно; откуда у правильного рассуждения с ложным заключением есть ложная посылка, а форма неправильна в точности тогда, когда у неё есть контрпример.

      Доказывается в уроке: Что такое математическая логика.

    2. Парадокс лжеца. В применении к предложению mm, «предложение mm ложно», двузначность и схема истинности дают V(m)⇔¬V(m)V(m) \Leftrightarrow \neg V(m); для языка, содержащего mm, от одного из двух допущений приходится отказаться, и выход Тарского состоит в том, чтобы никакой язык не содержал собственного предиката истинности, так что mm нельзя образовать.

      Использует: 1. Что гарантирует правильность. Опирается на: A (Двузначность), B (Схема истинности). Доказывается в уроке: Что такое математическая логика.

    3. Диагональная лемма. Если RR есть отношение между объектами совокупности DD, такое что каждое R(x,y)R(x, y) истинно или ложно, то никакое bb из DD не удовлетворяет условию R(b,x)⇔¬R(x,x)R(b, x) \Leftrightarrow \neg R(x, x) для всех xx из DD.

      Опирается на: A (Двузначность). Доказывается в уроке: Что такое математическая логика.

    4. Брадобрей и Рассел. Не существует мужчины из деревни, который брил бы в точности тех мужчин деревни, что не бреются сами; а неограниченный принцип свёртывания противоречив, потому что утверждает существование множества Z={x:x∉x}Z = \{ x : x \notin x \}.

      Опирается на: D (Диагональная лемма). Доказывается в уроке: Что такое математическая логика.

  2. Участок 2 Язык кружков и дисков

    • Описывать множества цепочек и подсчитывать цепочки каждой длины.
    • Определять формулы как наименьшее замкнутое множество и выводить отсюда принцип замыкания.
    • Доказывать свойства всех формул и пользоваться ими, чтобы отбрасывать цепочки.
    • Разлагать цепочку на слова и развёртывать сокращения до базового языка.

    1. Принцип замыкания. Множество F\mathcal{F} формул есть наименьшее множество цепочек, которое содержит переменные vn=∘n∙v_n = \sigO^{n}\sigI и вместе с φ\varphi и ψ\psi содержит ∙φψ\sigI\varphi\psi; следовательно, свойством, которым обладают переменные и которое переходит от φ\varphi и ψ\psi к ∙φψ\sigI\varphi\psi, обладают все формулы.

      Доказывается в уроке: Язык логики высказываний.

    2. Вид формул. Всякая формула есть переменная или имеет вид ∙φψ\sigI\varphi\psi, где φ\varphi и ψ\psi суть формулы, но не то и другое вместе: всякая переменная начинается с ∘\sigO, а всякая составная формула с ∙\sigI.

      Опирается на: E (Принцип замыкания). Доказывается в уроке: Язык логики высказываний.

    3. Последний символ и число дисков. Всякая формула кончается диском и содержит нечётное число дисков; откуда ни конкатенация двух формул, ни цепочка ∙φ\sigI\varphi не являются формулами.

      Опирается на: E (Принцип замыкания). Доказывается в уроке: Язык логики высказываний.

    4. Разложение на слова. Всякая цепочка, оканчивающаяся диском, единственным образом разлагается на слова, то есть на переменные ∘n∙\sigO^{n}\sigI и отдельные диски, потому что каждое слово кончается своим единственным диском и никакое слово не является собственным префиксом другого.

      Доказывается в уроке: Язык логики высказываний.

  3. Участок 3 Индукция и однозначность разбора

    • Доказывать простой и сильной индукцией и выводить из них индукцию по сложности формул.
    • Доказывать лемму о весе и выводить из неё однозначность разбора.
    • Решать, является ли цепочка формулой, и восстанавливать её построение.
    • Определять функции на формулах по рекурсии и доказывать соотношения между ними.

    1. Структурная индукция. Сильная индукция выводится из простой; применённая к длине, она даёт принцип индукции по сложности: если переменные обладают свойством и оно переходит от φ\varphi и ψ\psi к ∙φψ\sigI\varphi\psi, то им обладают все формулы.

      Использует: 6. Вид формул. Опирается на: C (Принцип индукции). Доказывается в уроке: Индукция по натуральным числам и по формулам.

    2. Лемма о весе. Если каждое вхождение переменной весит +1+1, а каждый диск-связка −1-1, то всякая формула весит +1+1, а всякий собственный непустой префикс по словам формулы весит не более 00; в частности, во всякой формуле вхождений переменных на одно больше, чем дисков-связок.

      Использует: 8. Разложение на слова. Опирается на: F (Структурная индукция). Доказывается в уроке: Индукция по натуральным числам и по формулам.

    3. Однозначность разбора. Никакая формула не является собственным префиксом другой; откуда, если ∙φψ=∙φ′ψ′\sigI\varphi\psi = \sigI\varphi'\psi', где все четыре цепочки суть формулы, то φ=φ′\varphi = \varphi' и ψ=ψ′\psi = \psi'.

      Использует: 7. Последний символ и число дисков, 8. Разложение на слова, 10. Лемма о весе. Доказывается в уроке: Индукция по натуральным числам и по формулам.

    4. Разрешающая процедура. Цепочка, оканчивающаяся на ∘\sigO, не есть формула; если она оканчивается на ∙\sigI, её разлагают на слова. Если первое слово является переменной, цепочка есть формула тогда и только тогда, когда эта переменная является её единственным словом. Если это диск, после него ведут счёт долга: если долг ни разу не обращается в нуль, цепочка не есть формула; если обращается, разрез между φ\varphi и ψ\psi находится там, где это происходит впервые, и каждый кусок исследуется тем же способом, с учётом того, что пустая цепочка не есть формула.

      Использует: 6. Вид формул, 7. Последний символ и число дисков, 8. Разложение на слова. Опирается на: G (Однозначность разбора). Доказывается в уроке: Язык логики высказываний.

    5. Определение по рекурсии. Если даны значение для каждой переменной и правило, вычисляющее значение для ∙φψ\sigI\varphi\psi по φ\varphi, по ψ\psi и по их значениям, то существует ровно одна функция на формулах, которая их соблюдает; так определяются длина, подформулы, глубина и подстановка, которая всегда даёт формулы.

      Использует: 6. Вид формул. Опирается на: C (Принцип индукции), F (Структурная индукция), G (Однозначность разбора). Доказывается в уроке: Индукция по натуральным числам и по формулам.

  4. Участок 4 От русского языка к формулам

    • Формализовать высказывания с явным словарём, решая, какова область действия каждой связки.
    • Развёртывать сокращения, чтобы решить, являются ли две формализации одной и той же формулой.
    • Отличать материальную импликацию от «если… то» естественного языка и указывать, что теряет формализация.
    • Формализовать целые рассуждения как множество посылок и заключение.

    1. Длина сокращений. Если L(φ)=aL(\varphi) = a и L(ψ)=bL(\psi) = b, то цепочки ¬φ\neg\varphi, (φ∨ψ)(\varphi \vee \psi), (φ→ψ)(\varphi \rightarrow \psi) и (φ∧ψ)(\varphi \wedge \psi) имеют длины 2a+12a + 1, 2a+2b+32a + 2b + 3, 4a+2b+54a + 2b + 5 и 8a+8b+158a + 8b + 15; две формализации разной длины суть разные формулы.

      Использует: 13. Определение по рекурсии. Доказывается в уроке: Формализация естественного языка.

    2. Область действия и разные формулы. Группировки ((p∧q)∨r)((p \wedge q) \vee r) и (p∧(q∨r))(p \wedge (q \vee r)) суть разные цепочки: если бы они совпадали, однозначность разбора, применённая дважды, заставила бы переменную rr совпасть с составной формулой (p∧q)(p \wedge q).

      Использует: 6. Вид формул. Опирается на: G (Однозначность разбора). Доказывается в уроке: Формализация естественного языка.

    3. Материальная импликация. Импликация (φ→ψ)(\varphi \rightarrow \psi), сокращающая (¬φ∨ψ)(\neg\varphi \vee \psi), ложна лишь тогда, когда φ\varphi истинна, а ψ\psi ложна; это единственное прочтение, зависящее лишь от истинности частей, при котором истинны условные теоремы математики.

      Опирается на: H (Прочтение стрелки Пирса). Доказывается в уроке: Формализация естественного языка.

К выводу. Цепь останавливается там, где язык построен, а рассуждения формализованы как множество посылок и заключение. Остаётся решить, когда формула следует из других: сначала оперируя знаками по правилам, в следующем разделе, а затем принимая во внимание их истинность.