?

Log in

No account? Create an account
о доказательствах от противного - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о доказательствах от противного [апр. 15, 2017|05:17 pm]
Anatoly Vorobey
[Tags|, ]

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

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

Пусть нам нужно доказать утверждение "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:
[User Picture]From: nihao_62
2017-04-15 02:47 pm
Доказательство от противного чаще указывает на то, что нечто не существует. (Не является истинным).

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

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

(Ответить) (Thread)
From: karpion
2017-04-15 10:30 pm
"Не существует" никак не связано с "не является истинным". Например, "не существует такого объекта, который бы удовлетворял такому набору условий"; пример конкретнее: "не существует таких двух целых чисел m и n, чтобы (m/n)^2=2".
(Ответить) (Parent) (Thread)
[User Picture]From: levtsn
2017-04-15 04:21 pm

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

(Ответить) (Thread)
[User Picture]From: vzaliva
2017-04-15 05:05 pm
Нужно заметить что Intuitionistic Logic, этот метод доказательства не работает в общем случае.

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


(Ответить) (Thread)
[User Picture]From: musatych
2017-04-17 09:02 am
Проблемы возникают, только если нужно дополнительно нужно использовать снятие двойного отрицания. То есть из A ⇒ B следует ¬B ⇒ ¬A и в интуиционизме, а вот из ¬B ⇒ ¬A следует только ¬¬A ⇒ ¬¬B.

Рассуждение от противного вида "Если из A вывели одновременно B и ¬B (т.е. противоречие), то A неверно" верно и в интуиционизме. Но "Если из ¬A вывели одновременно B и ¬B (т.е. противоречие), то A верно" уже не работает.
(Ответить) (Parent) (Thread)
[User Picture]From: edd_l
2017-04-15 06:57 pm
Цитаты Харди не хватает:
Метод доказательства reductio ad absurdum, столь любимый Евклидом, - один из самых лучших инструментов математика. Это гораздо более "хитроумный" гамбит, чем любой шахматный гамбит: шахматист может пожертвовать пешку или даже фигуру, но математик жертвует партию.
(Ответить) (Thread)
[User Picture]From: avva
2017-04-15 09:00 pm
Хорошая цитата, не знал, спасибо.
(Ответить) (Parent) (Thread)
[User Picture]From: ved62
2017-04-15 08:59 pm
Утверждение "A ⇒ B и доказывать ¬B ⇒ ¬A - на практике разные вещи, хотя с строго логической точки зрения они эквивалентны" не верно. Точнее, не верно про эквивалентность. Оно верно только в двоичной логике, но если выражение ¬B (или ¬A) может породить множество, то неверно.
(Ответить) (Thread)
From: karpion
2017-04-15 10:31 pm
Ну, покажите мне пример не-двоичной логики.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: seatrotter
2017-04-15 09:08 pm
Российский суд признал математическую формулу угрозой государству и обязал математика Алексея Иванова уплатить штраф в 20 тысяч рублей за её демонстрацию.
По мнению суда, он тем самым подстрекал к неповиновению властям.
http://from-ua.com/news/403281-sud-priznal-matematicheskuyu-formulu-ugrozoi-gosudarstvu-foto.html

Интересно, если в ЖЖ опубликовать эту формулу - СУП засуспендит журнал за экстремизм и подстрекательство?
(Ответить) (Thread)
From: karpion
2017-04-15 10:33 pm
Вангую появление этой формулы на аватарах.
(Ответить) (Parent) (Thread)
[User Picture]From: occuserpens
2017-04-16 03:02 am
[ в процессе док-ва можешь узнать что-то новое и интересное про вещи, которые реально "существуют". Промежуточные этапы в доказательстве от противного скорее окажутся ни к чему не годными, не добавляющими к знаниям и интуиции ]

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

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

Edited at 2017-04-16 04:55 (UTC)
(Ответить) (Thread)
[User Picture]From: special_linear
2017-04-16 11:15 am
Изучение свойств несуществующих объектов может оказаться крайне полезным. Вот на MathOverflow был топик соответствующий: https://mathoverflow.net/questions/182006/what-is-the-most-useful-non-existing-object-of-your-field
(Ответить) (Thread)
[User Picture]From: relf
2017-04-16 02:55 pm

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

(Ответить) (Parent) (Thread)
[User Picture]From: alaev
2017-04-18 06:08 am
Вы всё правильно пишете. Я бы добавил, что доказательства от противного чем-то напоминают слова-паразиты. Они никогда не ухудшают ситуацию, но часто могут улучшить её. В результате возникает желание вообще всё доказывать от противного, что часто замутняет мысль.
(Ответить) (Thread)
[User Picture]From: livelight
2017-04-19 10:34 am
> проводишь за исследованием свойств объектов, про которые заранее знаешь, что они не существуют, и эти свойства внутренне противоречивы, просто ты еще не придумал, как это противоречие вывести на поверхность

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