о доказательствах от противного

[avva]

Константин Кноп пишет в фейсбуке:

...В чем "фишка" доказательств от противного и почему ими следует пользоваться как в обучении математике, так и в собственно математике? Этого почти никто толком не понимает, потому что в школе этого не объясняют, а потом умные люди уже не занимаются такими благоглупостями.

Пусть нам нужно доказать утверждение "A ⇒ B"... Когда вы _правильно_ используете метод доказательства от противного, то у вас есть не одно условие A, а два разных: A и ¬B (¬ означает "не"). И вот из двух условий вместе нужно всего лишь прийти к противоречию. Любому противоречию, не важно, в каком месте и с чем именно!

Понимаете? Раньше вам нужно было (непонятно, как именно) проложить ниточку рассуждений от того, которое было дано, к тому, которое надо было доказать. Это могла быть достаточно длинная ниточка, а вы держитесь за один конец клубка, и совершенно непонятно, как его разматывать, чтобы он вас привёл куда надо. А "противное" сразу позволяет опереться на два разных хвоста и мотать их совместно. Сплошь и рядом это оказывается удобнее и быстрее, потому что на двух опорах стоять проще, чем на одной. И главное - у вас нет цели нечто конкретное доказать, ваша цель намного проще: обнаружить противоречие.

Добавлю несколько соображений.

Десять лет назад я написал подробную запись (слишком подробную, на мой взгляд теперь, мог бы и покороче) о том, почему доказывать A ⇒ B и доказывать ¬B ⇒ ¬A - на практике разные вещи, хотя с строго логической точки зрения они эквивалентны. Сказанное там имеет отношение к вышепроцитированным словам про док-во от противного. Мы предпочитаем опираться на равенство и доказывать равенство, а не опираться на неравенство и доказывать неравенство, при прочих равных. Мы предпочитаем опираться на существование какого-то X и доказывать существование какого-то Y, а не опираться на "для всех X" и доказывать "для всех Y", при прочих равных. Эти предпочтения часто помогают нам выбратьм что доказывать: A ⇒ B или ¬B ⇒ ¬A. Доказательство от противного утверждения типа A ⇒ B будет особенно удобным, если и A, и ¬B получаются в удобной форме: существование и/или равенство. Тогда действительно легко и удобно будет "опереться на два разных хвоста и мотать их совместно".

Вместе с тем, у доказательств от противного на практике часто обнаруживаются следующие недостатки:

1. Нередко бывает, что доказательство оформлено как док-во от противного, но "на самом деле" не пользуется совместной силой предположений A и ¬B. Вместо этого происходит следующее (иногда это чуть замаскировано риторикой): предполагаем A и ¬B, потом доказываем ¬A, но не пользуемся совсем предположением A при этом, и наконец заключаем "противоречие" между A и ¬A. Легко видеть, что на самом деле это попросту косвенное доказательство ¬B ⇒ ¬A; оформление его в виде "противоречия" ничего не добавляет, а наоборот, может скрыть степень конструктивности док-ва.

2. Наоборот, когда и A и ¬B нетривиально используются в достижении противоречия, иногда выходит такая ситуация, что значительную часть док-ва проводишь за исследованием свойств объектов, про которые заранее знаешь, что они не существуют, и эти свойства внутренне противоречивы, просто ты еще не придумал, как это противоречие вывести на поверхность. Это немного странное и контрпродуктивное ощущение. Если доказываешь прямо A->B, то хотя бы в процессе док-ва можешь узнать что-то новое и интересное про вещи, которые реально "существуют". Промежуточные этапы в доказательстве от противного скорее окажутся ни к чему не годными, не добавляющими к знаниям и интуиции итд.

Comments

[nihao-62.livejournal.com]

Доказательство от противного чаще указывает на то, что нечто не существует. (Не является истинным).

Т.о. нет (и не нужно) последовательного движения доказательств того, что оно существует.
----

Если вам потребуется доказать именно существование чего-то, то от противного не так удобно.

[levtsn.livejournal.com]

У, противный!

[vzaliva.livejournal.com]

Нужно заметить что Intuitionistic Logic, этот метод доказательства не работает в общем случае.

[1] http://www.iep.utm.edu/reductio/
[2] https://plato.stanford.edu/entries/logic-intuitionistic/

[edd-l.livejournal.com]

Цитаты Харди не хватает:
Метод доказательства reductio ad absurdum, столь любимый Евклидом, - один из самых лучших инструментов математика. Это гораздо более "хитроумный" гамбит, чем любой шахматный гамбит: шахматист может пожертвовать пешку или даже фигуру, но математик жертвует партию.

[ved62.livejournal.com]

Утверждение "A ⇒ B и доказывать ¬B ⇒ ¬A - на практике разные вещи, хотя с строго логической точки зрения они эквивалентны" не верно. Точнее, не верно про эквивалентность. Оно верно только в двоичной логике, но если выражение ¬B (или ¬A) может породить множество, то неверно.

[avva.livejournal.com]

Хорошая цитата, не знал, спасибо.

[seatrotter.livejournal.com]

Российский суд признал математическую формулу угрозой государству и обязал математика Алексея Иванова уплатить штраф в 20 тысяч рублей за её демонстрацию.
По мнению суда, он тем самым подстрекал к неповиновению властям.
http://from-ua.com/news/403281-sud-priznal-matematicheskuyu-formulu-ugrozoi-gosudarstvu-foto.html

Интересно, если в ЖЖ опубликовать эту формулу - СУП засуспендит журнал за экстремизм и подстрекательство?

[karpion.livejournal.com]

"Не существует" никак не связано с "не является истинным". Например, "не существует такого объекта, который бы удовлетворял такому набору условий"; пример конкретнее: "не существует таких двух целых чисел m и n, чтобы (m/n)^2=2".

[karpion.livejournal.com]

Ну, покажите мне пример не-двоичной логики.

[karpion.livejournal.com]

Вангую появление этой формулы на аватарах.

[occuserpens.livejournal.com]

[ в процессе док-ва можешь узнать что-то новое и интересное про вещи, которые реально "существуют". Промежуточные этапы в доказательстве от противного скорее окажутся ни к чему не годными, не добавляющими к знаниям и интуиции ]

Про некоторые вещи, например, лошадь Мелания. наперед не скажешь, существуют они или нет. Поэтому изучение их свойств может оказаться изящным доказательством от противного.

Допустим, что Мелания - лошадь. Тогда Трамп - либо кентавр, либо зоофил. Но первое очевидно неверно, а второе - суть конспирология. Поскольку мы, в отличие от трампистов, конспирологии табуируем, Мелания - не лошадь.

[richard-grm.livejournal.com]

ну, это не формула, просто определение отстутствия предела в точке х₀.
но остроумно, да.:)

а за что его оштрафовали, надо посмотреть в решении суда.
решения суда там нет.

[ved62.livejournal.com]

Пожалуйста: Селёдка ⇒ Рыба. Обратное неверно: ¬Селёдка ⇒ ¬Рыба

[seatrotter.livejournal.com]

http://mos-gorsud.ru/rs/tverskoj/services/cases/admin/details/58777cb2-7913-4933-9a4d-ffb1a65d74ef

все что они сочли нужным опубликовать.

[richard-grm.livejournal.com]

акты они выкладывают с запаздыванием, а тут и вовсе 3 дня прошло.
в любом случае бремя доказывания на тех, кто утверждает, что оштрафовали за формулу - им полагается как-то подтвердить свои слова.

тем более, что у оштрафованного и решение на руках - мог бы выложить.


апд.
и, кстати, написал он неправильно: если |f(x)|>δ, это не значит, что у функции нет предела в некой точке x₀.
может, его за это оштрафовали?:)
за незнание математики?

[http://users.livejournal.com/_sabiko/]

Так так и задумано, это же формула беспредела, а не предела!

[kobak.livejournal.com]

???

Это не является контр-примером к эквивалентности A ⇒ B и ¬B ⇒ ¬A, у Вас стрелочка в другую сторону.

[richard-grm.livejournal.com]

именно.
но если условия на плакате выполняются, то предел, тем не менее, вполне может существовать.

т.е. это НЕ формула беспредела.
условия на плакате вообще-то выполнятся для любой функции, не равной тождественно нулю.
т.е. всегда можно найти такую дельту (дельта там не любая, а существует), при которой значение функции будет по модулю больше этой дельты.
но это не значит, что у большинства функций нет предела в той или иной точке.

[gul-kiev.livejournal.com]

Не обязательно нулю, любой константе.
Для несуществования предела следовало бы переставить местами кванторы.
"Существует такая дельта, что для любого эпсилон ...".

[gul-kiev.livejournal.com]

> условия на плакате вообще-то выполнятся для любой функции, не равной тождественно нулю.

Если функция является константой в любой (сколь угодно малой) окрестности x₀, то условия на плакате не выполнятся. Необязательно быть константой на всей области определения.

[richard-grm.livejournal.com]

пусть у вас функция f(x)=5.
чему равен предел f(x) при х->10?

[gul-kiev.livejournal.com]

Пяти, разумеется.
К чему это вы?

Я говорю о том, что, например, для функции f(x) = [x] (целая часть от x) условие на плакате не выполняется в точке x₀ = 1/2.
Вы же написали, что условия на плакате выполняются для любой функции, не равной тождественно нулю.

[gul-kiev.livejournal.com]

Прошу прощения, неправильно прочитал плакат, не понял, что там в конце написано |f(x)| > δ. Не пришло в голову, что он сделал более грубую ошибку, чем перепутанный порядок кванторов. :)

Тогда, конечно, не любой константе, а именно нулю. Но всё равно достаточно в окрестности x₀.

[richard-grm.livejournal.com]

я уже сам перепроверять начал.:)

если функция нулевая рядом с х₀, то да.
не выполнятся - именно в этой х₀.
но они выполнятся в других x, если у нас не f(x)=o.

т.е. условия будут выполняться для любой другой функции, просто не во всех точках.

[special-linear.livejournal.com]

Изучение свойств несуществующих объектов может оказаться крайне полезным. Вот на MathOverflow был топик соответствующий: https://mathoverflow.net/questions/182006/what-is-the-most-useful-non-existing-object-of-your-field

[richard-grm.livejournal.com]

а, слушайте, нет.
не выполнится, если она нулевая только в окрестности.
там же эпсилон - любой.
просто мы подразумеваем, что он сколь угодно мал - в определении предела.
потому что там выполнится для малого - выполнится и для большого.
но формально он - любой, и для достаточно больших эпсилон условие не выполнится, если у нас не f(x)=0.


апд.
в смысле, конечно, условие ВЫПОЛНИТСЯ, если она нулевая только в окрестности - это я уже сам запутался.:)

апд 2.
ладно, стоп, я, пожалуй, продолжу чуть позже, а то уже какую-то фигню пишу.:)

апд 3.
да, вы всё верно написали: для выполнения условия в x₀ достаточно нулевого значения в её окрестности.
надо пойти поспать.:)

[relf.livejournal.com]

+1
Изучение свойств несуществующих объектов помогает лучше понять свойства существующих.

[richard-grm.livejournal.com]

в ходе параллельного обсуждения (http://foxhound-lj.livejournal.com/436122.html) возникли две новые идеи.
условие на плакате НЕ будет выполняться для всех x, если функция пересекает ось абсцисс в двух и более точках, т.е. как минимум дважды равна нулю.

а вот если она только один раз пересекает абсциссу - в точке, к примеру, x₁, то при x₀=x₁ условие выполнится.
а для всех остальных точек - нет.
потому что можно будет взять достаточно большое эпсилон, и в ε-окрестность попадёт x₁, а f( x₁)=0<δ.

[karpion.livejournal.com]

Не вижу тут ничего не-двоичного.
Данный объект входит в множество "селёдка"? Да-нет.
Данный объект входит в множество "рыба"? Да-нет.
Всё двоичненько.

[musatych.livejournal.com]

Проблемы возникают, только если нужно дополнительно нужно использовать снятие двойного отрицания. То есть из A ⇒ B следует ¬B ⇒ ¬A и в интуиционизме, а вот из ¬B ⇒ ¬A следует только ¬¬A ⇒ ¬¬B.

Рассуждение от противного вида "Если из A вывели одновременно B и ¬B (т.е. противоречие), то A неверно" верно и в интуиционизме. Но "Если из ¬A вывели одновременно B и ¬B (т.е. противоречие), то A верно" уже не работает.

[alaev.livejournal.com]

Я за такую хрень, как на этой бумажке, тоже его оштрафовал бы. Квантора по x нет, логическая связка во второй строчке отсутствует, вообще чёрт знает что.

Но, может быть, ФСБ отфотошопила фото, для дискредитации оппозиции?

[alaev.livejournal.com]

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

[richard-grm.livejournal.com]

ну второпях человек писал, это понятно.
но было бы смешно, если бы решение суда включало контрпример и разъяснение про явное неуважение к обществу.:)

[alaev.livejournal.com]

Мне что-то вдруг подумалось, что это мог быть тонкий замысел (всё же не должен даже самый пропащий математик так облажаться). Мы берём определение того, что f(x) не имеет предела в точке x0 (т.е. определение беспредела), а потом начинаем над ним издеваться: переставляем кванторы, квантор по x вообще выкидываем, логическую связку тоже выкидываем и т.п.

В результате получаем беспредел в квадрате. Ну или беспредел и бардак в одном флаконе. Плюс, формально придраться очень сложно - даже в пропаганде беспредела не обвинишь.

[richard-grm.livejournal.com]

на мой взгляд, это обычная ошибка, возникающая, когда человек что-то делает второпях.
квантор при х, кстати, часто не ставится, когда пишется определение предела на семинарских занятиях - просто подразумевается любое х.
собственно, обычно это вот так и пишется - "для любого эпсилон..." - без любого икс и значка следствия, всё как он написал (только для предела).
вот он и упустил "существует х".

т.е. не надо ничего выдумавать, мне кажется.
ошибся и ошибся.
просто это - не определение беспредела, вот и всё.

[livelight]

> проводишь за исследованием свойств объектов, про которые заранее знаешь, что они не существуют, и эти свойства внутренне противоречивы, просто ты еще не придумал, как это противоречие вывести на поверхность

Ну дык, это ещё не "знание", а только ваши интуитивные гипотезы. Каковые ещё надлежит доказать.
Про геометрию Евклида с инвертированным 5-ым постулатом тоже столетиями "знали", что она не существует, просто не могли придумать, как вывести это на поверхность. А потом Лобачевский показал, что она таки существует.