Лекция 1: Предикаты, множества и доказательства

Коротко

Первая лекция MIT 6.1200 (Mathematics for Computer Science) о том, что такое доказательство. Метод установления истины через цепочку логических выводов из набора аксиом. Лектор разбирает три термина из определения proof, propositions, axioms, оставляя logical deductions на завтра, и вводит предикаты как «пропозиции с переменными». Добрая половина времени уходит на булевы операторы и особенно на implication: false → true истинно, потому что импликация это правило вида «по средам носим розовое», а не причинность и не время. Отдельно вскрывается разрыв между разговорным «or» (на трёх примерах официанта оно оказывается то XOR, то NAND, то «anything goes») и математическим inclusive or. Заканчивается теоремой Гёделя о неполноте: нельзя иметь систему аксиом одновременно непротиворечивую и полную, и курс выбирает непротиворечивость.

Главный тезис

Математика отличается от других способов установления истины тем, что доказательство это верификация пропозиции цепочкой логических выводов из заранее объявленного набора аксиом. А разговорный язык, на котором мы вынуждены это доказательство передавать, слишком неточен. Поэтому смысл операторов задаётся строго таблицами истинности, а не интуицией.

Ключевые идеи

• 8:48 - доказательство это метод установления истины, и у общества их много: эксперимент, выборка, суд, расследование, авторитет, религия, внутреннее убеждение
• 12:38 - математическое доказательство это верификация пропозиции цепочкой логических выводов из базового набора аксиом
• 13:08 - пропозиция это утверждение, которое истинно или ложно; «Today is Thursday» ложно, но всё равно пропозиция
• 16:26 - предикат это пропозиция с переменными: «p is prime» не пропозиция, пока не подставишь p, а квантор for all превращает предикат обратно в пропозицию
• 18:49 - пример n²+n+41: простое для n от 0 до 39, но на n=41 даёт 41·43; сорок примеров не доказательство, для опровержения for all хватает одного контрпримера
• 20:22 - гипотеза Гольдбаха («каждое чётное >2 сумма двух простых») формулируется тривиально, но лежит за пределами современной математики, и это первая лекция
• 26:23 - математическое or это inclusive: ложно только когда оба ложны; разговорное «or» так почти никогда не работает
• 28:17 - три вопроса официанта показывают: «chicken or pasta» это XOR, «coffee or tea» это NAND, «cream or sugar» это «anything goes»; ни одно не совпадает с математическим or
• 35:33 - импликация ложна ровно в одном случае: A истинно, B ложно
• 36:48 - почему false → true истинно: импликация это соблюдение правила «по средам носим розовое», в остальные дни носи что хочешь, правило не нарушено
• 40:20 - в математике implies не несёт причинности и времени, только таблица истинности, в отличие от английского «A implies B»
• 48:31 - A→B эквивалентно контрапозиции ¬B→¬A, но не обратному B→A и не инверсии ¬A→¬B; мем «I do not think therefore I do not am» перепутал контрапозицию с инверсией
• 50:26 - множество это коллекция объектов без порядка и без повторов; кортеж наоборот, порядок и повторы важны, скобки вместо фигурных
• 56:26 - пустое множество подмножество всего: нельзя предъявить его элемент, которого нет в другом множестве, значит правило не нарушено (vacuous truth)
• 1:15:23 - теорема Гёделя о неполноте: система, умеющая арифметику, не может быть одновременно непротиворечивой и полной, а значит есть истинные, но недоказуемые утверждения

Почему это важно

Это вводная лекция фундаментального курса MIT, который сами преподаватели называют «proofs, proofs, and more proofs»: главный экспорт курса не факты, а навык писать точные, сжатые, корректные доказательства. Лектор строит мост от бытовой интуиции к формальной строгости и честно показывает, где эта интуиция ломается: inclusive or, false→true, пустое множество, контрапозиция против инверсии. Здесь же студенту сразу дают почувствовать край математики: гипотеза Гольдбаха и теорема Гёделя на первом занятии. Чтобы стало ясно: строгость не педантизм, а единственный способ отличить истину от правдоподобия в дисциплине, где сорок совпавших примеров ничего не гарантируют.

Идеи

• Одна и та же вещь, «истина», означает разное в физике, соцопросе, суде и математике, каждая область придумала свою процедуру её установления
• «Не верьте профессору на слово, мы ошибаемся постоянно, ловите нас на этом», лектор трижды за лекцию поправляет собственную запись на доске
• Warm-up задачи дают бесконечные попытки и мгновенный фидбек, полный балл гарантирован тому, кто просто не забыл их сделать
• Дедлайн намеренно размыт: 1% штрафа в час первые 50 часов, потом фиксированные 50% до конца семестра, чтобы убрать резкий обрыв и стресс
• «P versus NP fallacy»: иллюзия, что прочитать чужое доказательство так же легко, как построить своё
• Политика «solve together, write alone»: решай в группе, но записывай в одиночку, отложив общие заметки
• 0 это натуральное число, «вне этого класса вас будут убеждать в обратном, они неправы»
• В некоторых науках достаточного числа примеров хватает для «эффективно истинно», математикам нет
• n²+n+41 идеально мимикрирует под теорему на первых сорока значениях, ловушка индуктивного оптимизма
• Про Гольдбаха писали в Boston Globe (~1995) как об одной из крупнейших нерешённых задач, но с ошибкой в примере (9+11, где 9 не простое)
• Разговорный язык это «неточный канал», по которому люди вынуждены передавать точные вещи
• Мнемоника: ∧ похоже на заглавную A без перекладины (and), ∨ перевёрнутое, для него у лектора мнемоники нет
• <3 значит «люблю», а <4 как усилитель это математически слабее: «ты меня меньше любишь», ведь <3 влечёт <4
• Декартово «cogito ergo sum» утверждает две вещи сразу: что T истинно И что T влечёт «am»
• Ботинок не мыслит, но существует: false→true в порядке для Декарта, но мем-инверсия ломается на ботинке
• Импликацию можно выразить через базовые операторы: A→B ≡ ¬A ∨ B
• Изменение пятой аксиомы Евклида даёт целые новые геометрии, а не противоречие
• В сферической геометрии «точка» это точка вместе с её антиподом, «прямая» это большой круг, параллельных прямых нет
• В гиперболической геометрии через точку проходит бесконечно много прямых, не пересекающих данную
• Аксиомы не обязаны быть «самоочевидными», их просто принимают истинными ради текущей математики, и они могут противоречить друг другу, если не используются вместе
• «Principle of explosion»: из ложного следует что угодно, поэтому противоречивая система доказывает всё и потому бессмысленна
• Аксиомы курса это «примерно вся школьная математика»: любой достаточно общий и знакомый факт можно использовать, лишь выписав его явно
• Пустое множество это подмножество всего, но элемент только того, куда его явно вписали, «in» имеет два разных смысла
• {6,1,2,0,0} равно {6,1,2,0}: множество «не помнит», что ноль написали дважды
• Гёдель заставляет выбирать: непротиворечивость или полнота, добавление аксиом лишь порождает новые недоказуемые истины
• «Мы можем попросить в домашке доказать недоказуемое из аксиом. Мы так не делаем. Это подло»

Инсайты

• Строгость в математике это не украшение, а необходимость: без неё сорок совпавших примеров неотличимы от доказанной теоремы, а край знания неотличим от решённого
• Значение логического оператора задаётся не интуицией и не английским словом, а исключительно таблицей истинности, интуиция здесь ненадёжный проводник
• Разрыв между формальным языком и разговорным структурный: люди обречены кодировать точные утверждения в неточном канале, отсюда правило «спрашивай при любой неясности формулировки»
• Понимание и построение это разные когнитивные навыки, и субъективное «мне понятно» систематически обманывает насчёт способности воспроизвести
• Пустая истина (vacuous truth) логична, если сместить вопрос с «что здесь истинно» на «можно ли предъявить нарушение»
• Выбор аксиом это не поиск «настоящей» истины, а выбор системы: разные непротиворечивые наборы порождают разные, одинаково законные математики
• Непротиворечивость приоритетнее полноты, потому что без различия истины и лжи (принцип взрыва) теория теряет всякую информативность
• Гёдель кладёт жёсткий потолок на амбицию «доказать всё истинное»: истинность и доказуемость принципиально не совпадают
• Хорошая педагогика снижает стресс архитектурно (плавный дедлайн, бесконечные ретраи), а не призывами, стимул смещается к самой работе, а не к соблюдению срока
• Импликация ловит студентов потому, что естественный язык грузит в неё причинность и время, которых в формальном определении нет

Фреймворки

Три термина в определении доказательства (разбираются как каркас курса): proposition (истинно/ложно) → chain of logical deductions (на завтра) → base set of axioms (то, что принимаем без доказательства).

Четыре формы импликации от A→B: converse B→A, inverse ¬A→¬B, contrapositive ¬B→¬A; исходное эквивалентно только контрапозиции, converse и inverse эквивалентны между собой.

Два желаемых свойства набора аксиом: consistency (нельзя доказать, что ложь истинна) и completeness (всякую истинную пропозицию можно доказать); теорема Гёделя запрещает иметь оба сразу для системы с арифметикой.

Цитаты

«It's a method of ascertaining truth. A proof is how you show that something is true.» - 8:48 Это метод установления истины. Доказательство это как ты показываешь, что нечто истинно.

«This class could have been called proofs, proofs, and more proofs.» - 8:13 Этот курс можно было назвать «доказательства, доказательства и ещё доказательства».

«If we say for all n, we need all of the n. Just these 40 examples isn't enough.» - 18:45 Если мы говорим «для всех n», нам нужны все n. Этих сорока примеров недостаточно.

«It's really pretty that right here is beyond the cutting edge of math. First lecture.» - 21:29 Красиво, что вот это уже за передним краем математики. Первая лекция.

«Isn't language fun? None of them mean what or means.» - 32:20 Разве язык не забавен? Ни одно из них не значит того, что значит «or».

«As mathematicians, when we say the word implies, we mean this truth table and only this truth table.» - 40:42 Как математики, говоря «implies», мы имеем в виду эту таблицу истинности и только её.

«On Wednesdays, we wear pink. On all other days, I don't care. Anything goes.» - 36:48 По средам мы носим розовое. В остальные дни мне всё равно. Что угодно сойдёт.

«So you've weakened it. You love me less.» - 43:37 Так ты его ослабил. Ты меня меньше любишь.

«But a better way to think of it is prove me wrong. Show me an element on the left that isn't an element on the right. You can't.» - 56:26 Лучше думать об этом так: докажи, что я неправ. Покажи элемент слева, которого нет справа. Не можешь.

«We just assume them to be true for the sake of the math we're doing now.» - 1:07:04 Мы просто принимаем их истинными ради той математики, которую делаем сейчас.

«And then Kurt Gödel comes along and says, nope, can't have both.» - 1:15:14 А потом приходит Курт Гёдель и говорит: неа, оба сразу нельзя.

«There are true statements that cannot be proved.» - 1:16:17 Есть истинные утверждения, которые невозможно доказать.

«Conceivably, Goldbach's conjecture might be true but unprovable. Maybe? I don't know.» - 1:16:49 Возможно, гипотеза Гольдбаха истинна, но недоказуема. Может быть? Не знаю.

«Please don't do that. We make mistakes all the time, and we want you to call us out on that.» - 10:52 Пожалуйста, не надо так. Мы ошибаемся постоянно, и хотим, чтобы вы нас на этом ловили.

«Not the worst Freudian slip.» - 3:36 Не худшая оговорка по Фрейду.

Факты

• Курс MIT 6.1200 («6120»), лекции вторник/четверг 14:30–16:00, рецитации среда/пятница; посещение рецитаций 10% оценки
• Проблем-сеты выходят по вторникам, сдача понедельник 23:59; принимаются с опозданием вплоть до последнего учебного дня
• Штраф за просрочку: 1% в час первые 50 часов (со 100% до 50%), далее фиксированные 50% до конца семестра
• n²+n+41 простое для n от 0 до 39; на n=40 даёт 41², на n=41 даёт 41·43 (оба не простые)
• При n=39 выражение равно 1601 (простое), «если верить моим заметкам»
• Гипотеза Гольдбаха: каждое чётное число больше 2 есть сумма двух простых; примеры 12=7+5, 20=17+3; статус конъектуры, доказательства нет
• Гольдбаха освещали в Boston Globe примерно в 1995 году как одну из крупнейших нерешённых задач математики
• Пять стандартных множеств: ℕ (натуральные, с 0), ℤ (целые), ℚ (рациональные), ℝ (действительные), ℂ (комплексные)
• Евклид (лектор колеблется, «200 до н.э. или, может, 2000, кто-нибудь подскажет») написал «Начала» с пятью аксиомами; пятая это постулат о параллельных
• Постулат о параллельных: для точки P и не содержащей её прямой L существует единственная прямая через P, параллельная L
• Замена пятого постулата на «нет прямых» даёт сферическую геометрию, на «бесконечно много» гиперболическую
• Теорема Гёделя о неполноте (Kurt Gödel, G-O-умлаут-D-E-L): система, способная к арифметике, не может быть одновременно непротиворечивой и полной
• Принцип взрыва: из ложного следует любое утверждение
• 2160 в MIT это курс «identification, estimation, and learning» в MechE (пример, что порядок цифр в кортеже важен)
• Аксиоматика курса: любой достаточно общий факт из школьной программы можно использовать, выписав его явно (пример: «произведение двух чётных чисел чётно»)

Источники

• Euclid, «Elements» евклидова геометрия и постулат о параллельных
• Kurt Gödel теорема о неполноте
• Descartes, «cogito ergo sum» / «I think, therefore I am» пример импликации с двумя утверждениями
• Goldbach's conjecture пример недоказанной пропозиции
• Boston Globe (~1995) статья о нерешённых задачах математики
• «Mean Girls» («On Wednesdays we wear pink») источник примера про импликацию
• Canvas, Piazza, PSET Partners инструменты курса

Рекомендации

• Ходить на рецитации: 10% оценки и «одно из самых полезных времён за семестр»
• Делать warm-up до рецитации, чтобы не тратить занятие на «а что мы сегодня проходим»
• Решать проблем-сеты в группе, но записывать в одиночку, отложив общие заметки
• Освоить в первую очередь and, or, not; XOR и NAND второстепенны
• При любой неясности формулировки спрашивать: либо поймают ошибку преподавателя, либо получат уверенность в прочтении
• В доказательствах явно выписывать используемые аксиомы/факты, чтобы на каждом шаге было понятно, почему он верен

Итог

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