Парадокс Рассела простыми словами и пределы логики
От таблиц истинности до теорем Гёделя и до того, чего они не утверждают
Парадокс Рассела (1901) простыми словами: множество всех множеств, не содержащих себя, содержит себя тогда и только тогда, когда себя не содержит. Он обрушил принцип неограниченной свёртки, на котором стоял логицизм Фреге. Урок разбирает и другие пределы логики, в том числе что на самом деле следует из теоремы Гёделя о неполноте: ни существование абсолютно недоказуемых истин, ни превосходство ума над машиной из неё не следуют.
Oxford «Introduction to Logic» · Cambridge Part IA Paper 5 «Formal Methods» · 45 мин · обновлено 01.10.2026
После урока вы сможете
- После урока вы сможете проверять валидность пропозиционального аргумента таблицей истинности и объяснять, почему такая проверка механическая.
- Объяснять парадоксы материальной импликации и знать три стратегии ответа на них.
- Называть, что именно предикатная логика умеет, а силлогистика нет, и приводить контрпример де Моргана.
- Восстанавливать парадокс Расселла посылками и говорить, какое допущение он убивает.
- Формулировать первую и вторую теоремы Гёделя с точными условиями и перечислять выводы, которые из них не следуют.
Пропозициональная логика берёт целые утверждения как неразложимые атомы и изучает только то, как из них собираются составные утверждения. Инструментов пять: отрицание ¬, конъюнкция ∧, дизъюнкция ∨, условное →, эквивалентность ↔. Семантика истинностно-функциональна: значение составного утверждения полностью определено значениями частей. Из этого следует всё остальное. Тавтология: формула, истинная при любом распределении значений. Противоречие: формула, ложная при любом. Выполнимая: формула, истинная хотя бы при одном.
Отсюда механическая проверка валидности. Постройте таблицу на всех распределениях значений атомов (их 2ⁿ для n атомов) и найдите строку, где все посылки истинны, а вывод ложен. Если такой строки нет, аргумент валиден. Если есть, эта строка и есть контрпример, и её можно предъявить. Тут стоит развести два обозначения, которые дальше понадобятся. Запись Γ ⊨ φ означает «при всяком распределении, делающем истинным Γ, истинно и φ» (семантическое следование). Запись Γ ⊢ φ означает «φ выводится из Γ по правилам данного исчисления» (выводимость). Корректность исчисления означает, что из ⊢ следует ⊨, а полнота, что из ⊨ следует ⊢.
Историческая справка полезна, потому что имена этих результатов постоянно путают. Метод таблиц истинности опубликован в 1921 году дважды независимо: Людвигом Витгенштейном в «Логико-философском трактате» и Эмилем Постом, который вдобавок доказал полноту и разрешимость пропозиционального исчисления. Матрицы истинности были у Чарльза Пирса в неопубликованных рукописях с 1880-х по 1902 год и неявно у Фреге в «Исчислении понятий» (1879). Полноту предикатной логики первого порядка доказал Гёдель (диссертация 1929, публикация 1930).
Здесь же стоит предупреждение, к которому мы вернёмся в конце урока. Теорема о полноте логики первого порядка (Гёдель, 1930) и теоремы о неполноте арифметики (Гёдель, 1931) не одно и то же, и вторая не отменяет первую. Пропозициональная логика разрешима: таблица истинности есть конечная механическая процедура. Логика первого порядка полна, но неразрешима: общего алгоритма проверки нет (Чёрч и Тьюринг, независимо, 1936).
Материальная импликация и её парадоксы
Условное в классической логике определяется так: p → q ложно ровно в одном случае, когда p истинно, а q ложно. Во всех остальных случаях оно истинно. Это единственный способ сделать условное истинностно-функциональным, и он даёт странные следствия. Истинное следствие делает условное истинным при любом антецеденте: ⊨ q → (p → q). Ложный антецедент тоже делает его истинным: ⊨ ¬p → (p → q). Из противоречия следует что угодно: p, ¬p ⊨ q.
Для естественного языка ломается больше. Усиление антецедента: «если чиркнуть спичкой, она загорится» звучит верно, но «если чиркнуть спичкой под водой, она загорится» ложно. Материальная импликация такого перехода не блокирует, хотя должна бы. Переход «или ⟹ если»: из «Джон в Лондоне или в Париже» получается «если Джон не в Лондоне, он в Париже». Формально безупречно, содержательно подозрительно, если основание первого утверждения было иным.
Дальше начинается техника. Эрнест Адамс («The Logic of Conditionals», 1965) предложил мерить приемлемость индикативного условного условной вероятностью P(q|p). Это формализация так называемого теста Рамсея: временно добавьте p к своим убеждениям и посмотрите, насколько уверены в q. Дэвид Льюис (1976) доказал результаты о тривиальности: не существует пропозиционального условного, для которого P(p → q) = P(q|p) выполнялось бы в общем случае. Это не философское возражение, а теорема, и она ограничивает всю вероятностную семантику условных.
Три стратегии ответа делят поле до сих пор. Грайсовская защита: семантика верна, а странности объясняются прагматикой, то есть импликатурами разговора (Пол Грайс, лекции 1967, публикация 1975). Семантика возможных миров для контрфактуалов: Роберт Столнейкер («A Theory of Conditionals», 1968) и Дэвид Льюис (Counterfactuals, 1973) опираются на близость миров. Усиление антецедента с транзитивностью там невалидны, что и правильно. Релевантная логика: Алан Андерсон и Нюэл Белнап (Entailment I, 1975) требуют разделения переменных и отказываются от «взрыва». Параконсистентные логики идут дальше. Для контрфактуалов вопрос закрыт: материальная импликация не годится. Для индикативных условных он остаётся одним из самых незакрытых вопросов философской логики.
(1) Индикативное «если p, то q» логически эквивалентно ¬p ∨ q (гипотеза материальной импликации). (2) «Луна сделана из сыра» ложно. (3) Из 1 и 2: «Если Луна сделана из сыра, то 2 + 2 = 5» истинно. (4) Но компетентный носитель языка отвергает 3. Следовательно, (5) либо ложна посылка 1 и нужна неистинностно-функциональная семантика, либо интуиция 4 объясняется прагматически (Грайс), либо интуиция 4 просто ошибочна. Обратите внимание на структуру: это антиномия по классификации Куайна (урок 2), а не загадка. Все три ветви вывода 5 имеют защитников, и выбор ветви есть выбор теории, а не разгадка. Именно поэтому мы говорим «спор открыт», а не «логика ошибается».
Кванторы: что даёт предикатная логика
Пропозициональная логика не видит внутренней структуры утверждений и потому не может обосновать даже простейший силлогизм. Предикатная логика разбирает утверждение на предикаты, термы и кванторы: ∀ («для всякого») и ∃ («существует»). Аппарат создан Готлобом Фреге в «Исчислении понятий» (1879), где впервые появились переменные, кванторы и вложенность области действия. Почти одновременно и независимо к тому же пришёл Чарльз Пирс («On the Algebra of Logic», 1885).
Три приобретения решают три разные задачи. Первое, многократная общность: ∀x∃y R(x, y) и ∃y∀x R(x, y) выражают разные утверждения («у каждого есть какой-то начальник» и «есть кто-то, кто начальник всем»). Различие это выражается только порядком кванторов. Второе, отношения: предикаты с двумя и более местами, «x больше y», «x между y и z». Третье, область действия: фраза «каждый мальчик любит какую-то девочку» имеет два разных прочтения, и формализация делает выбор явным вместо того, чтобы оставлять его контексту.
Сюда же относится анализ определённых дескрипций у Бертрана Расселла («On Denoting», 1905): «тот F есть G» разворачивается в «существует ровно один x такой, что Fx, и этот x есть G». Выгода двойная: осмысленными оказываются утверждения о том, чего нет («нынешний король Франции лысый» просто ложно, а не бессмысленно), и снимается двусмысленность области действия отрицания. Подробно этим займётся урок 23.
Силлогистика Аристотеля и её пределы
Первую формальную логику в истории дала «Первая аналитика» Аристотеля (около 350 года до н. э.). Она работает с четырьмя типами суждений. A: всякое S есть P. E: никакое S не есть P. I: некоторое S есть P. O: некоторое S не есть P. У Аристотеля три фигуры, четвёртую добавила позднейшая традиция. При четырёх фигурах формальных комбинаций 256, из них в традиционной трактовке валидными признаются 24 модуса, а в современной логике 15. Разница ровно в одном допущении: традиция предполагала, что термины непусты (существенная импортация).
Именно это допущение и создаёт первый предел. «Все единороги рогаты» в традиционной трактовке влечёт «некоторые единороги рогаты». В современной логике первое истинно вакуумно, а второе ложно, поскольку единорогов нет. Квадрат противоположностей при пустых терминах частично разрушается.
Второй и главный предел: только одноместные предикаты. Отношения невыразимы, а вместе с ними невыразима огромная часть обычных рассуждений. Третий: нет многократной общности, поэтому утверждения вида «у каждого числа есть больший делитель» вне охвата. Четвёртый: нет пропозициональной структуры, так что modus ponens и рассуждения со связками силлогистика не покрывает (этот пробел заполнили стоики, а систематически Фреге).
Правильная формулировка итога такая: силлогистика есть корректный, но собственный фрагмент логики первого порядка, а именно монадический, и он разрешим. Она не «неверна», она недостаточна. Различие важно методически: устаревшая теория не то же самое, что ложная, и на экзамене это надо различать.
«Все лошади суть животные, следовательно, все головы лошадей суть головы животных». Вывод очевидно валиден: любой носитель языка это видит, и в предикатной логике он получается в три строки, поскольку «голова x» это отношение. Средствами силлогистики он недоказуем вообще: там нет двухместных предикатов, а значит нет способа связать «голову чего-то» с «чем-то». Это не придирка к деталям, а демонстрация того, что целый класс валидных выводов лежал за пределами формальной логики двадцать три века. Решение появилось только у Фреге (1879) и независимо у Пирса (1885), и именно поэтому логика считается математической дисциплиной с 1879 года, а не с античности.
Множества и парадокс Расселла
Программа логицизма Фреге состояла в том, чтобы вывести арифметику из логики. Её техническим сердцем был принцип неограниченной свёртки: любому условию соответствует множество объектов, ему удовлетворяющих (у Фреге это Основной закон V из «Grundgesetze der Arithmetik», том I, 1893). Принцип выглядел самоочевидным. Бертран Расселл обнаружил в 1901 году, что он противоречив, и сообщил об этом Фреге письмом 16 июня 1902 года. Опубликован результат в «The Principles of Mathematics» (1903, приложение А). Ответ Фреге вышел приложением ко второму тому «Grundgesetze» (1903). Независимо похожее противоречие заметил Эрнст Цермело около 1899-1902 годов, но не опубликовал. Вывод занимает шесть строк.
(1) Для любого условия φ(x) существует множество R = {x : φ(x)}.
(2) Возьмём φ(x) := x ∉ x, тогда существует R = {x : x ∉ x}.
(3) По определению R для любого a верно: a ∈ R ↔ a ∉ a.
(4) Подставим a := R и получим R ∈ R ↔ R ∉ R.
(5) Это противоречие.
(6) Следовательно, посылка 1 ложна.
Обратите внимание на форму: это reductio в чистом виде и антиномия по Куайну. Посылка казалась самоочевидной, а вывод противоречив, значит ревизии подлежит принцип. Дальнейшая работа была работой по выбору ревизии. Теория типов (Уайтхед и Расселл, «Principia Mathematica», 1910-1913) распределяет переменные по типам, так что «x ∈ x» перестаёт быть синтаксически допустимым. Теория ZF (аксиома выделения, Цермело 1908) разрешает образовывать множества лишь как подмножества уже данных. Есть и другие подходы: NF Куайна (1937), параконсистентные системы, где противоречие принимается, но «взрыв» блокируется.
Технически проблема закрыта: ZFC работает, и это редкий случай подлинного, окончательного опровержения математической программы. Открытым остаётся другой вопрос: какое из решений объясняет, почему неограниченная свёртка неверна, то есть что такое множество. И полезная поправка против упрощения: логицизм не умер целиком. Теорема Фреге, вывод аксиом Дедекинда-Пеано из принципа Юма, существенно не использует Основной закон V, и на этом стоит неологицизм.
Теоремы Гёделя: что именно они утверждают
Источник один: Курт Гёдель, «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I», Monatshefte für Mathematik und Physik 38 (1931). Формулировки надо давать с условиями, иначе получается не теорема, а лозунг.
Первая теорема. Любая непротиворечивая формальная система F, в которой можно провести некоторое количество элементарной арифметики, неполна: в языке F есть предложения, которые в F нельзя ни доказать, ни опровергнуть. Условия точные: (i) F рекурсивно аксиоматизируема, то есть множество её аксиом эффективно перечислимо. (ii) F содержит как минимум арифметику Робинсона Q. (iii) F непротиворечива. В оригинальной версии Гёделя требовалась ω-непротиворечивость: условие сильнее обычной непротиворечивости. Улучшение Джона Барклая Россера (1936) позволило обойтись простой непротиворечивостью. Скелет доказательства стоит знать, потому что он объясняет, почему условия именно такие.
(1) Синтаксис F арифметизируется: формулам и доказательствам сопоставляются числа (гёделева нумерация).
(2) Отношение «d есть доказательство в F формулы с номером n» рекурсивно, а значит представимо формулой Prf(d, n) в языке самой F.
(3) Диагональная лемма: для любой формулы ψ(x) существует предложение G такое, что F ⊢ G ↔ ψ(⌜G⌝).
(4) Возьмём ψ(x) := ¬∃d Prf(d, x), получим G.
(5) Если F непротиворечива и F ⊢ G, то доказательство G существует, значит F ⊢ ¬G, а это противоречие. Следовательно, F ⊬ G.
(6) Если F ⊢ ¬G, то F доказывает существование доказательства G, которого по шагу 5 нет. При ω-непротиворечивости (или в конструкции Россера при простой) это тоже противоречие, значит F ⊬ ¬G.
(7) Следовательно, G в F неразрешимо, и при непротиворечивости F оно истинно в стандартной модели.
Вторая теорема. Для любой такой (чуть более сильной) непротиворечивой F утверждение о непротиворечивости F недоказуемо средствами самой F. Здесь тоже есть условия: требуются условия выводимости Лёба и «интенсиональная» адекватность предиката доказуемости, а именно формула Cons(F) должна действительно выражать непротиворечивость F, а не просто быть с ней эквивалентной.
Чего теоремы Гёделя НЕ утверждают
Первое: не «существуют истины, которые нельзя доказать». Речь о выводимости внутри конкретной системы. Гёделево предложение G для F доказуемо в более сильной системе, например, в F плюс утверждение о непротиворечивости F. Тезис «существуют абсолютно недоказуемые истины» из теорем не следует. Второе: не «непротиворечивость арифметики недоказуема». Доказал её Герхард Генцен (1936) с помощью трансфинитной индукции до ε₀, просто не средствами арифметики Пеано, что вторая теорема как раз и предсказывает.
Третье: не «математика ненадёжна или противоречива». Четвёртое, самое частое в популярных пересказах: не «человеческий разум превосходит машину». Разбор смотрите во врезке. Пятое: не аргумент за релятивизм, мистику или «границы человеческого познания» вообще. Теоремы говорят о формальной выводимости в системах, содержащих арифметику. К этике, праву и языку они напрямую не применимы, а любое такое расширение требует дополнительных посылок.
Шестое: не «всякая система неполна». Полные системы существуют и хорошо известны: пропозициональная логика (Пост, 1921), логика первого порядка как логика (Гёдель, 1930), арифметика Пресбургера (сложение без умножения) разрешима и полна. Ключ в достаточной арифметической силе: слабые системы полны, а сильные неполны, и теорема указывает именно эту границу.
На деле теоремы похоронили финитную часть программы Гильберта: замысел доказать непротиворечивость формализованной математики элементарным рассуждением о конкретных знаках. Это подлинное опровержение исследовательской программы. Уцелевшее оказалось продуктивным: релятивизованные программы Гильберта стали центральными для теории доказательств (ординальный анализ Генцена, теоретико-доказательственные редукции, обратная математика).
Аргумент Джона Лукаса («Minds, Machines and Gödel», 1961) и Роджера Пенроуза (The Emperor's New Mind, 1989 и Shadows of the Mind, 1994): для любой непротиворечивой машины-системы F есть формула, которую F не выдаст, а мы «видим» её истинность, значит, ум не машина. Возражение решающее и простое: теорема даёт лишь условное, а именно «если F непротиворечива, то G истинно». Чтобы «увидеть» истинность G, надо знать непротиворечивость F, а антимеханист должен утверждать, что человеческий ум способен установить непротиворечивость произвольной формализованной теории. Это крайне неправдоподобно. Линия критики: Патнэм (1960), Бенасерраф («God, the Devil, and Gödel», 1967), Булос, Феферман, Шапиро. Сам Гёдель в Гиббсовской лекции (1951) утверждал только дизъюнкцию: либо человеческий разум бесконечно превосходит конечную машину, либо существуют абсолютно неразрешимые диофантовы задачи, и обе ветви совместимы с теоремами. По оценке SEP, существует широкий консенсус, что антимеханистические аргументы из теорем несостоятельны.
Что из этого следует для философии
Логика в её современном виде не набор правил спора, а математическая теория со своими теоремами о собственных границах. Именно это и есть её философский результат: формализация оказалась способна точно сказать, чего она не может. Пропозициональная логика разрешима, логика первого порядка полна и неразрешима, достаточно сильная арифметика неполна, непротиворечивость такой системы недоказуема внутри неё. Каждое из этих утверждений есть теорема с условиями, и каждое было бы невозможно даже сформулировать до 1879 года.
Из наличия точных пределов не следует ни бесполезность формального метода, ни его всесилие. Ошибка в обе стороны одна: результат о конкретных системах переносится на «познание вообще» без посылок, оправдывающих перенос.
Что остаётся открытым внутри самой логики: семантика индикативных условных, статус релевантных и параконсистентных систем, логический плюрализм против монизма и, наконец, природа самого логического следования. Плюрализм здесь означает тезис, что «валидно» имеет несколько равно законных уточнений (Джей Билл и Грег Ресталл, Logical Pluralism, 2006). Распределение мнений для ориентировки: в PhilPapers 2020 на вопрос «Logic» классическую логику выбрали 53,6 %, неклассическую 26,4 % (N = 1415). Как всегда, это карта позиций, а не доказательство.
Программа Венского кружка, в популярной версии Альфреда Айера (Language, Truth and Logic, 1936, 2-е изд. 1946): осмысленно только то, что аналитически истинно или эмпирически проверяемо, а метафизика, этика и теология не ложны, а бессмысленны. Аргумент самоподрыва: (1) осмысленно только аналитическое или эмпирически проверяемое. (2) Сам критерий 1 не аналитичен и не проверяем эмпирически. Следовательно, (3) по собственному критерию он бессмыслен. Оговорка, которую надо делать честно: Карнап трактовал критерий как предложение о рациональной реконструкции языка науки, а не как эмпирическое утверждение, и против его версии этот довод прямо не работает. Зато работают технические результаты: Чёрч (рецензия, 1949) построил конструкцию, делающую верифицируемым почти любое утверждение, а Гемпель (1950) показал, что строгие версии критерия выбрасывают законы науки, а слабые пропускают метафизику, и к 1950 году заключил, что поиск адекватного критерия в терминах дедуктивных отношений к наблюдательным предложениям бесполезен. Не приписывайте Карнапу тезисы Айера.
Машина контрпримеров
Аргумент невалиден тогда и только тогда, когда есть строка, где все посылки истинны, а вывод ложен. Такая строка и называется контрпримером. Ваша задача найти её или обоснованно заявить, что её нет.
Ключевые работы и аргументы
| Фреге | 1879 | «Исчисление понятий»: кванторы, переменные, вложенная область действия знаменуют рождение предикатной логики |
| Расселл | 1902 | Письмо Фреге от 16 июня: неограниченная свёртка противоречива, Основной закон V ложен |
| Пост | 1921 | Таблицы истинности в опубликованном виде плюс доказательство полноты и разрешимости пропозиционального исчисления |
| Гёдель | 1931 | Первая теорема о неполноте и вторая о недоказуемости непротиворечивости средствами самой системы |
| Россер | 1936 | Усиление первой теоремы: достаточно простой непротиворечивости вместо ω-непротиворечивости |
| Генцен | 1936 | Непротиворечивость арифметики Пеано доказана через трансфинитную индукцию до ε₀, средствами вне PA |
| Льюис | 1976 | Результаты о тривиальности: нет пропозиционального условного, для которого P(p → q) = P(q|p) в общем случае |
Что выдержало критику, а что нет
Материальная импликация даёт парадоксы верума и фальсума, «взрыв», а также пропускает усиление антецедента и транзитивность, которые в языке невалидны. Адамс (1965) предложил мерить приемлемость условной вероятностью, но Льюис (1976) доказал результаты о тривиальности: пропозиционального условного с P(p → q) = P(q|p) в общем случае не существует. Три стратегии, прагматическая (Грайс, 1975), возможных миров (Столнейкер 1968, Льюис 1973) и релевантная (Андерсон и Белнап, 1975), делят поле до сих пор. Для контрфактуалов вопрос решён: материальная импликация не годится, стандартом служит семантика близости миров. Для индикативных условных консенсуса нет.
Аргумент Лукаса (1961) и Пенроуза (1989, 1994) требует, чтобы человек мог «увидеть» истинность гёделева предложения для произвольной системы. Но теорема условна: G истинно, если F непротиворечива. Значит, антимеханист должен утверждать, что человеческий ум способен установить непротиворечивость любой формализованной теории, а такое допущение критики (Патнэм 1960, Бенасерраф 1967, Булос, Феферман, Шапиро) считают несостоятельным. По оценке SEP, консенсус против аргумента широкий. Пенроуз не согласен, но это позиция меньшинства. Сам Гёдель в 1951 году утверждал только дизъюнкцию: либо ум превосходит конечную машину, либо существуют абсолютно неразрешимые диофантовы задачи. Отдельно: непротиворечивость арифметики Пеано доказана Генценом в 1936 году, просто не средствами PA.
Критерий верификации ни в одной точной формулировке не делает того, что от него требовалось: Чёрч (1949) построил конструкцию, делающую верифицируемым почти любое утверждение, а Гемпель (1950) показал, что строгие версии исключают универсальные обобщения, то есть законы науки, а слабые пропускают метафизику. Вдобавок нарушается требование, чтобы отрицание осмысленного было осмысленным. Сам критерий не проходит собственную проверку, хотя против карнаповской версии, где он есть предложение о реконструкции языка науки, этот довод прямо не работает. Итог развести надо на две части: сам критерий в любой точной формулировке отвергнут, а программа логического эмпиризма не «опровергнута», а сильно ослаблена. Она разложилась изнутри и дала потомство: формальную эпистемологию и байесовскую теорию подтверждения.
Доказательство занимает шесть строк и воспроизводится читателем: Расселл нашёл противоречие в 1901 году и сообщил Фреге письмом 16 июня 1902-го, независимо то же заметил Цермело около 1899-1902 годов, а Фреге признал провал в приложении ко второму тому «Grundgesetze» (1903). Редкий случай окончательного опровержения программы, и техническая сторона закрыта: теория типов и ZF дают непротиворечивые ревизии. Уцелело опровержение принципа. Не уцелели два вывода из него: какая ревизия объясняет, что такое множество, остаётся открытым, а формулировка «логицизм опровергнут» неверна, ведь теорема Фреге выводит аксиомы Дедекинда-Пеано из принципа Юма, не используя Основной закон V.
Термины
- истинностно-функциональная связкаtruth-functional connective
- Связка, значение составного утверждения при которой полностью определено значениями частей.
- тавтологияtautology
- Формула, истинная при любом распределении значений входящих атомов.
- логическое следствиеlogical consequence
- Γ ⊨ φ: при всяком распределении, делающем истинными все формулы Γ, истинна и φ. Отличать от выводимости Γ ⊢ φ.
- материальная импликацияmaterial implication
- Условное, ложное ровно тогда, когда антецедент истинен, а консеквент ложен.
- кванторquantifier
- Оператор ∀ или ∃, связывающий переменную. Порядок кванторов меняет смысл утверждения.
- многократная общностьmultiple generality
- Вложенность кванторов: ∀x∃y R(x,y) и ∃y∀x R(x,y) выражают разные утверждения. В силлогистике она невыразима.
- существенная импортацияexistential import
- Допущение непустоты терминов. Именно из-за него традиция признаёт 24 валидных модуса, а современная логика 15.
- неограниченная свёрткаunrestricted comprehension
- Принцип «любому условию соответствует множество его выполнителей». Его убил парадокс Расселла.
- гёделева нумерацияGödel numbering
- Сопоставление чисел формулам и доказательствам, позволяющее системе говорить о собственном синтаксисе.
- рекурсивная аксиоматизируемостьrecursive axiomatizability
- Условие эффективной перечислимости аксиом системы. Без него первая теорема о неполноте не работает.
Практикум · Проверка валидности таблицей истинности
Задача состоит в том, чтобы убедиться руками, что валидность проверяема механически, и получить контрпример не догадкой, а вычислением. Понадобится лист бумаги. Калькулятор и компьютер не нужны. На всё уходит 25-40 минут.
- Постройте таблицу на 4 строки для двух атомов p и q со столбцами p, q, p → q. Убедитесь, что ложь стоит ровно в одной строке.
- Проверьте modus ponens: столбцы p → q, p, q. Найдите все строки, где обе посылки истинны, и посмотрите на вывод. Запишите вердикт.
- Проверьте утверждение консеквента: посылки p → q и q, вывод p. Найдите строку, где посылки истинны, а вывод ложен, и выпишите её отдельно: это и есть контрпример. Тем же способом проверьте отрицание антецедента: посылки p → q и ¬p, вывод ¬q.
- Проверьте формулу ¬p → (p → q) на тавтологичность. Если она тавтология, объясните одной фразой, почему это выглядит парадоксально и какое допущение о значении «если» вызывает дискомфорт.
- Возьмите аргумент из трёх атомов (например: «если бюджет вырос, налоги подняли. Налоги не подняли. Либо бюджет вырос, либо сократили расходы. Следовательно, расходы сократили») и постройте таблицу на 8 строк. Назовите тип каждого шага и вердикт по всему аргументу.
Вопросы для самопроверки
Как таблица истинности показывает, что аргумент невалиден?
- Находится строка, в которой все посылки и вывод ложны
- Вывод оказывается не тавтологией
- Находится строка, в которой все посылки истинны, а вывод ложен
- Число строк, где вывод истинен, меньше числа строк, где он ложен
«Все лошади суть животные, следовательно, все головы лошадей суть головы животных». Почему этот пример важен для истории логики?
- Он невалиден: чтобы вывод прошёл, нужна дополнительная посылка «у всякой лошади есть голова», а её в аргументе не дано
- Он показывает, что силлогистика содержит внутреннее противоречие: она признаёт вывод валидным и одновременно не может его получить
- Он валиден только при допущении, что лошади существуют, то есть держится на экзистенциальной импортации традиционной логики
- Он валиден, но недоказуем в силлогистике, потому что требует двухместного предиката
Парадокс Расселла: (1) любому условию φ(x) соответствует множество {x : φ(x)}. (2) Берём φ(x) := x ∉ x. (3) Для любого a: a ∈ R ↔ a ∉ a. (4) Подставляем a := R. (5) Противоречие. Какой вывод из этого делает стандартная математика?
- Ложна посылка 1: принцип неограниченной свёртки надо ограничить
- Ложна посылка 3: эквивалентность «a ∈ R ↔ a ∉ a» записана неверно, в ней перепутаны стороны
- Подстановка на шаге 4 недопустима: R задано через все множества сразу, а значит, ещё не готово к моменту подстановки в собственное определение
- Противоречие показывает, что логика первого порядка неполна и потому нуждается в дополнительных правилах вывода
Какое из утверждений точно передаёт первую теорему Гёделя?
- Всякая формальная система неполна: полных систем не бывает вовсе, а пропозициональная логика просто слишком бедна, чтобы это в ней заметить
- Всякая непротиворечивая рекурсивно аксиоматизируемая система, содержащая арифметику Робинсона Q, неполна
- Существуют истины, которые нельзя доказать никакими средствами: гёделево предложение недоказуемо ни в одной системе
- Непротиворечивость арифметики недоказуема: ни средствами самой арифметики, ни какими-либо иными средствами
Аргумент Лукаса-Пенроуза: для любой непротиворечивой машины-системы F есть формула G, которую F не выдаст, а мы видим её истинность, значит ум не машина. Какая посылка делает вывод несостоятельным?
- Посылка, что гёделево предложение существует для всякой такой системы: теорема строит его лишь для систем, доказавших свою непротиворечивость
- Посылка, что машина работает по формальным правилам: обучающиеся системы правил не соблюдают, и теорема к ним неприменима
- Скрытая посылка, что человек способен установить непротиворечивость произвольной формализованной теории
- Посылка, что арифметика непротиворечива: доказать это нельзя ничем, поэтому вся конструкция висит в воздухе
Ответы и разбор открываются в самопроверке урока: она считает результат и отмечает урок пройденным. Пройти самопроверку.
Что читать
- Фреге, «Исчисление понятий» (Begriffsschrift, 1879), Предисловие и часть I: Работа, с которой логика стала математической дисциплиной: кванторы, переменные, область действия
- Витгенштейн, «Логико-философский трактат» (1921), тезисы 4.3-4.46: Первая публикация метода таблиц истинности и понятий тавтологии и противоречия
- Stanford Encyclopedia of Philosophy, «Gödel's Incompleteness Theorems» (P. Raatikainen): Точные формулировки с условиями и разбор типичных ложных выводов, включая аргумент Лукаса-Пенроуза
- Stanford Encyclopedia of Philosophy, «Russell's Paradox» (A. D. Irvine): История открытия, переписка с Фреге и сравнение решений: типы, ZF, NF