Похвала математике. Часть 2, глава 1.
Итак, на новогодних каникулах я всё-таки решил продолжить :).
Часть 1, глава 1.
Часть 1, глава 2.
Часть 1, глава 3.
Часть 1, глава 4.
Часть 2. Доказательные рассуждения.
Глава 1. Reductio ad absurdum.
Знаменитое доказательство от противного. Не все математики согласны, что такое рассуждение имеет право на жизнь. Дело в том, что опирается это доказательство на «принцип исключённого третьего»: «верно либо утверждение, либо его отрицание», а верность этого принципа для многих математиков сомнительна.
Доказательство от противного работает так. Мы берём все условия нашей теоремы и добавляем к ним ещё одно утверждение - точное отрицание того, что хотим доказать. А затем мы можем выводить из всей совокупности условий противоречие с чем-то, безусловно верным. С чем угодно.
Если мы смогли логическими переходами достичь противоречия, это означает, что отталкивались мы от неверных утверждений. Значит, наше добавочное утверждение неверно - а тогда верно его отрицание, и теорема доказана.
1.(Уфнаровский) Метод доказательства от противного бесплатен. Сделав предположение «теорема неверна», мы можем просто доказывать теорему, но уже имея в распоряжении на одно условие больше. Если докажем, противоречие всё равно будет. Наше дополнительное условие («теорема неверна») будет противоречить выводу («теорема верна»).
2.(Уфнаровский) Метод доказательства от противного универсален. Если теорему вообще можно доказать, её можно доказать и методом от противного. В самом деле, доказательство от противного выглядит так: предполагаем, что теорема неверна; доказываем, что она верна (по условию это можно сделать); мы получили противоречие, которое показывает, что наше предположение «теорема неверна» неверно, следовательно, теорема верна.
Очень простой пример из математики
Задача. В вазе лежат конфеты 3 сортов. Сколько конфет нужно взять из вазы, чтобы среди взятых наверняка нашлось хотя бы 3 конфеты одного сорта?
Решение. Легко понять, что 6 конфет может не хватить. А вот как доказать, что 7 хватит обязательно?
Можно, конечно, полным перебором - 7 конфет, по 3 варианта для каждой, всего-то 73=243 варианта нужно рассмотреть (а если подумать, перебор неплохо сокращается). А можно - методом от противного.
1.Допустим, мы взяли 7 конфет, но у нас не нашлось 3 конфеты одного сорта (не правда ли, противная ситуация?).
2.Тогда очевидно, что конфет каждого из сортов никак не больше, чем 2 штуки. Ну третьей-то нет.
3.Но тогда всего конфет никак не больше 3x2=6.
4.А их, по нашему предположению, 7. Значит, неверно наше исходное предположение.
Более сложный пример из математики
В некотором смысле рациональных чисел (Все дроби вида m/n, m - целое, n - натуральное) столько же, сколько натуральных. Существует способ все рациональные числа занумеровать. То есть сказать, что вот это число - первое, вот это - второе... и так далее. Незанумерованных при этом не останется. Ну а если на каждое число приходится ровно один номер - наверное, чисел и номеров поровну, нет?
Докажем, что вещественных чисел на отрезке [0,1] в том же смысле больше, чем натуральных.
1.Предположим, что это не так. То есть предположим, что мы каким-то образом занумеровали все вещественные числа (вот эта ситуация сама по себе нисколько не противна - более того, в чём-то она приятна; однако доказательства «от приятного» в математике нет :) ).
2.Мы собираемся показать, что в таком случае существует по крайней мере одно не пронумерованное число (понятно, что это будет противоречие). Построим такое число. Первые его цифры «0,», то есть оно заведомо принадлежит нашему отрезку.
3.Рассмотрим число, имеющее номер 1. У него сразу после запятой (на месте десятых) стоит определённая цифра. Выпишем в наше число другую цифру - при этом не 0 и не 9. Цифр у нас 10 штук, использовать нельзя 3 - значит, сделать это можно, есть выбор из 7 цифр.
4.Рассмотрим число, имеющее номер 2. Выпишем в наше число на второе место после запятой (сотые) не ту цифру, что стоит на втором месте в этом числе - при этом опять же не 0 и не 9. Это возможно по тем же соображениям.
5.Дальше пойдём так же. На позицию N мы будем записывать не 0, не 9 и не ту цифру, которая стоит в числе с номером N.
6.В результате этой операции мы получим бесконечную десятичную дробь, представляющую число от 0 до 1. В этом числе нет ни 0, ни 9, поэтому оно не может оказаться записью числа, у которого больше одного десятичного представления (например, 0,2 и 0,1(9)... - одно и то же число). Очевидно, что это число не может быть среди перенумерованных (оно не может иметь номер 1, потому что его первая цифра другая; не может иметь номер 2, потому что отличается от второго числа второй цифрой; вообще, не может иметь номер K, потому что от K-го числа в K-й цифре отличается).
7.Мы получили противоречие. Из предположения, что перенумерованы все числа, мы сумели вывести непрнумерованное число.
Таким образом, мы доказали, что множество вещественных чисел несчётно.
Пример из литературы
А.К. Дойл, «Москательщик на покое».
Фабрикуя себе алиби, подозреваемый Джозия Эмберли говорит доктору Уотсону, что собирался сходить с женой в театр, но вынужден был идти туда один.
В тот памятный день старик Эмберли, желая доставить удовольствие жене, взял два билета в театр Хеймаркет, на балкон. В последний момент миссис Эмберли пожаловалась на головную боль и отказалась ехать. Он поехал один. Сомневаться в том, что это, правда, по-видимому, нет оснований: он показывал мне неиспользованный билет, который предназначался жене.
Уотсону удаётся запомнить номер места - тридцать первое в ряду Б на балконе.
Холмс на этом основании проводит классическое доказательство от противного:
1.Супруги, идущие в театр, покупают билеты на соседние места.
2.Предположим, что подозреваемый ходил в театр.
3.Тогда одно из двух мест, соседних с местом его жены - тридцатое или тридцать второе в том же ряду - должно было быть занято.
4.Однако Холмсу удаётся установить, что оба этих места заняты не были. Получено противоречие, из которого можно сделать вывод, что хотя бы одно из утверждений 1 и 2 неверно. Вполне понятно, что именно неверно, и алиби преступника рассыпается.
Пример из жизни
Опишем по работе Икеды и Джеффриса опровержение аргумента «тонкой настройки параметров Вселенной». Для тех, кто не читает по-английски - есть запись многоуважаемого a_bronx или запись в Википедии (подозреваю, того же авторства). Я попробую рассказать о том же самом без формул.
Известно, что небольшое изменение численного значения любой фундаментальной константы привело бы к тому, что высокоорганизованная жизнь во Вселенной была бы невозможна. Например, если бы константа электромагнитного взаимодействия была бы всего лишь в два раза больше, Вселенная состояла бы только из безмассовых частиц - все остальные аннигилировали бы. Коридор допустимых для естественного существования жизни значений для каждой фундаментальной константы весьма узок
Возникает впечатление, что настолько «тонкая настройка» параметров требует для своего объяснения гипотезу Сверхсущества - назовём оное Богом. Иными словами - по мнению многих, то обстоятельство, что наблюдаемые нами значения констант попали в узкие промежутки допустимости для «возможности существования жизни естественным путём», увеличивает правдоподобие гипотезы Бога.
Докажем методом «от противного», что это рассуждение не верно.
1.Предположим, наблюдаемый факт «все значения констант входят в узкие промежутки допустимости» в самом деле увеличивает правдоподобие гипотезы Бога.
2.Тогда, очевидно, обратное наблюдение («хотя бы одна константа выходит за интервал допустимости») никак не может это правдоподобие увеличивать (а по-хорошему должно бы его уменьшать :) ).
3.Но это не так! Недопустимое наблюдённое значение константы не только не уменьшает правдоподобие гипотезы Бога - оно доказывает эту гипотезу! В самом деле, в этом случае для жизни не может быть естественных оснований - следовательно, необходимы основания сверхъестественные! Кстати, именно по этой схеме пытаются пройти сторонники Разумного Замысла - основной упор делается как раз на то, что открытыми методами естественной биологической эволюции всё разнообразие видов получено быть не может.
Мы получили противоречие, которое показывает, что наше исходное предположение не может быть верным.
Часть 1, глава 1.
Часть 1, глава 2.
Часть 1, глава 3.
Часть 1, глава 4.
Часть 2. Доказательные рассуждения.
Глава 1. Reductio ad absurdum.
Знаменитое доказательство от противного. Не все математики согласны, что такое рассуждение имеет право на жизнь. Дело в том, что опирается это доказательство на «принцип исключённого третьего»: «верно либо утверждение, либо его отрицание», а верность этого принципа для многих математиков сомнительна.
Доказательство от противного работает так. Мы берём все условия нашей теоремы и добавляем к ним ещё одно утверждение - точное отрицание того, что хотим доказать. А затем мы можем выводить из всей совокупности условий противоречие с чем-то, безусловно верным. С чем угодно.
Если мы смогли логическими переходами достичь противоречия, это означает, что отталкивались мы от неверных утверждений. Значит, наше добавочное утверждение неверно - а тогда верно его отрицание, и теорема доказана.
1.(Уфнаровский) Метод доказательства от противного бесплатен. Сделав предположение «теорема неверна», мы можем просто доказывать теорему, но уже имея в распоряжении на одно условие больше. Если докажем, противоречие всё равно будет. Наше дополнительное условие («теорема неверна») будет противоречить выводу («теорема верна»).
2.(Уфнаровский) Метод доказательства от противного универсален. Если теорему вообще можно доказать, её можно доказать и методом от противного. В самом деле, доказательство от противного выглядит так: предполагаем, что теорема неверна; доказываем, что она верна (по условию это можно сделать); мы получили противоречие, которое показывает, что наше предположение «теорема неверна» неверно, следовательно, теорема верна.
Очень простой пример из математики
Задача. В вазе лежат конфеты 3 сортов. Сколько конфет нужно взять из вазы, чтобы среди взятых наверняка нашлось хотя бы 3 конфеты одного сорта?
Решение. Легко понять, что 6 конфет может не хватить. А вот как доказать, что 7 хватит обязательно?
Можно, конечно, полным перебором - 7 конфет, по 3 варианта для каждой, всего-то 73=243 варианта нужно рассмотреть (а если подумать, перебор неплохо сокращается). А можно - методом от противного.
1.Допустим, мы взяли 7 конфет, но у нас не нашлось 3 конфеты одного сорта (не правда ли, противная ситуация?).
2.Тогда очевидно, что конфет каждого из сортов никак не больше, чем 2 штуки. Ну третьей-то нет.
3.Но тогда всего конфет никак не больше 3x2=6.
4.А их, по нашему предположению, 7. Значит, неверно наше исходное предположение.
Более сложный пример из математики
В некотором смысле рациональных чисел (Все дроби вида m/n, m - целое, n - натуральное) столько же, сколько натуральных. Существует способ все рациональные числа занумеровать. То есть сказать, что вот это число - первое, вот это - второе... и так далее. Незанумерованных при этом не останется. Ну а если на каждое число приходится ровно один номер - наверное, чисел и номеров поровну, нет?
Докажем, что вещественных чисел на отрезке [0,1] в том же смысле больше, чем натуральных.
1.Предположим, что это не так. То есть предположим, что мы каким-то образом занумеровали все вещественные числа (вот эта ситуация сама по себе нисколько не противна - более того, в чём-то она приятна; однако доказательства «от приятного» в математике нет :) ).
2.Мы собираемся показать, что в таком случае существует по крайней мере одно не пронумерованное число (понятно, что это будет противоречие). Построим такое число. Первые его цифры «0,», то есть оно заведомо принадлежит нашему отрезку.
3.Рассмотрим число, имеющее номер 1. У него сразу после запятой (на месте десятых) стоит определённая цифра. Выпишем в наше число другую цифру - при этом не 0 и не 9. Цифр у нас 10 штук, использовать нельзя 3 - значит, сделать это можно, есть выбор из 7 цифр.
4.Рассмотрим число, имеющее номер 2. Выпишем в наше число на второе место после запятой (сотые) не ту цифру, что стоит на втором месте в этом числе - при этом опять же не 0 и не 9. Это возможно по тем же соображениям.
5.Дальше пойдём так же. На позицию N мы будем записывать не 0, не 9 и не ту цифру, которая стоит в числе с номером N.
6.В результате этой операции мы получим бесконечную десятичную дробь, представляющую число от 0 до 1. В этом числе нет ни 0, ни 9, поэтому оно не может оказаться записью числа, у которого больше одного десятичного представления (например, 0,2 и 0,1(9)... - одно и то же число). Очевидно, что это число не может быть среди перенумерованных (оно не может иметь номер 1, потому что его первая цифра другая; не может иметь номер 2, потому что отличается от второго числа второй цифрой; вообще, не может иметь номер K, потому что от K-го числа в K-й цифре отличается).
7.Мы получили противоречие. Из предположения, что перенумерованы все числа, мы сумели вывести непрнумерованное число.
Таким образом, мы доказали, что множество вещественных чисел несчётно.
Пример из литературы
А.К. Дойл, «Москательщик на покое».
Фабрикуя себе алиби, подозреваемый Джозия Эмберли говорит доктору Уотсону, что собирался сходить с женой в театр, но вынужден был идти туда один.
В тот памятный день старик Эмберли, желая доставить удовольствие жене, взял два билета в театр Хеймаркет, на балкон. В последний момент миссис Эмберли пожаловалась на головную боль и отказалась ехать. Он поехал один. Сомневаться в том, что это, правда, по-видимому, нет оснований: он показывал мне неиспользованный билет, который предназначался жене.
Уотсону удаётся запомнить номер места - тридцать первое в ряду Б на балконе.
Холмс на этом основании проводит классическое доказательство от противного:
1.Супруги, идущие в театр, покупают билеты на соседние места.
2.Предположим, что подозреваемый ходил в театр.
3.Тогда одно из двух мест, соседних с местом его жены - тридцатое или тридцать второе в том же ряду - должно было быть занято.
4.Однако Холмсу удаётся установить, что оба этих места заняты не были. Получено противоречие, из которого можно сделать вывод, что хотя бы одно из утверждений 1 и 2 неверно. Вполне понятно, что именно неверно, и алиби преступника рассыпается.
Пример из жизни
Опишем по работе Икеды и Джеффриса опровержение аргумента «тонкой настройки параметров Вселенной». Для тех, кто не читает по-английски - есть запись многоуважаемого a_bronx или запись в Википедии (подозреваю, того же авторства). Я попробую рассказать о том же самом без формул.
Известно, что небольшое изменение численного значения любой фундаментальной константы привело бы к тому, что высокоорганизованная жизнь во Вселенной была бы невозможна. Например, если бы константа электромагнитного взаимодействия была бы всего лишь в два раза больше, Вселенная состояла бы только из безмассовых частиц - все остальные аннигилировали бы. Коридор допустимых для естественного существования жизни значений для каждой фундаментальной константы весьма узок
Возникает впечатление, что настолько «тонкая настройка» параметров требует для своего объяснения гипотезу Сверхсущества - назовём оное Богом. Иными словами - по мнению многих, то обстоятельство, что наблюдаемые нами значения констант попали в узкие промежутки допустимости для «возможности существования жизни естественным путём», увеличивает правдоподобие гипотезы Бога.
Докажем методом «от противного», что это рассуждение не верно.
1.Предположим, наблюдаемый факт «все значения констант входят в узкие промежутки допустимости» в самом деле увеличивает правдоподобие гипотезы Бога.
2.Тогда, очевидно, обратное наблюдение («хотя бы одна константа выходит за интервал допустимости») никак не может это правдоподобие увеличивать (а по-хорошему должно бы его уменьшать :) ).
3.Но это не так! Недопустимое наблюдённое значение константы не только не уменьшает правдоподобие гипотезы Бога - оно доказывает эту гипотезу! В самом деле, в этом случае для жизни не может быть естественных оснований - следовательно, необходимы основания сверхъестественные! Кстати, именно по этой схеме пытаются пройти сторонники Разумного Замысла - основной упор делается как раз на то, что открытыми методами естественной биологической эволюции всё разнообразие видов получено быть не может.
Мы получили противоречие, которое показывает, что наше исходное предположение не может быть верным.