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

[Mr. X]

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

Вопрос: Всякое ли доказательство от противного можно "переделать впрямую"?

Например, хорошо известны доказательства от противного бесконечности множества простых чисел, иррациональности $\sqrt2$, многочисленных утверждений в основаниях евклидовой геометрии ... . Всякое ли такое утверждение, которое "стандартно" доказывается от противного, можно доказать и не прибегая к этому методу или же... бывает так, что нет?

Очень рассчитываю на ответ специалистов, хотя интересно мнение и всех.

[epros]

Тут главное не путать доказательство от противного с опровержением посредством приведения к абсурду. Опровержение посредством приведения к абсурду вытекает из следующей тавтологии исчисления высказываний:

$(P \rightarrow \bot) \rightarrow \neg P$, где $\bot$ - т.н. "универсальная ложь" или "абсурд". В арифметике, например, в качестве $\bot$ может выступать $0=1$.
В каком-то смысле эту тавтологию можно рассматривать как определение отрицания.

Примеры, о которых говорите Вы, являются большей частью примерами опровержений путём приведения к абсурду. Скажем, предположение о существовании максимального простого числа сводится к противоречию с аксиомами арифметики, отсюда следует его НЕсуществование, т.е. неограниченность множества простых чисел сверху.

Доказательство же от противного, это когда предположение $\neg P$ приводится к абсурду, а в итоге мы считаем доказанным $P$. Может быть разница между одним и другим кажется Вам несущественной, но в конструктивной логике, например, опровержения посредством приведения к абсурду являются легальными, а доказательства от противного запрещены. В конструктивной логике, приведя к абсурду предположение $\neg P$, Вы докажете двойное отрицание $\neg \neg P$. Но в конструктивной логике нет закона снятия двойного отрицания, который есть в классической логике:

$\neg \neg P \rightarrow P$

Поэтому в конструктивной логике доказательство $P$ от противного недопустимо. В то время как в классической логике - допустимо.

[Mr. X]

Уважаемый epros !

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

Рассмотрим два классических доказательства.

1. Простых чисел бесконечно много. Д-во: пусть их конечное число $p_1, p_2, ..., p_n.$ Рассмотрим число $p_1p_2...p_n+1$. ... Это доказательство "от противного" или "посредством приведения к абсурду" ? Я так понимаю, в смысле Вашего поста, что это доказательство от противного. Я прав?

2. Число $\sqrt2$ -- иррационально. Д-во. Пусть $\sqrt2=p/q$. ... Правильно ли я понимаю, что это тоже доказательство от противного? Или я не прав?

Просьба: Не могли бы Вы привести пример простенького утверждения (можно из вышеописанных 1,2) и доказать его двумя способами -- от противного и приведением к абсурду, чтобы я получше уяснил для себя эту разницу.

Большое спасибо за разъяснения и уточнения. Но я вернусь к своему вопросу из первого поста. Грубо говоря, можно ли доказать, что $\sqrt2$ -- иррационально, не прибегая к его (противоречивой) записи в виде $p/q$? И этот же вопрос интересует меня относительно любого утверждения, которое доказывается подобным образом (от противного либо приведением к абсурду). (Да, можно считать,что мы находимся в рамках классической логики, т.е. закон снятия двойного отрицания действует.)

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

[Виктор Викторов]

Mr. X в сообщении #364121 писал(а):

Число $\sqrt2$ -- иррационально. Д-во. Пусть $\sqrt2=p/q$. ... Правильно ли я понимаю, что это тоже доказательство от противного?

Во-первых нужна формулировка "если А, то Б". Пока её нет разговаривать трудно. Попробуем так: "если возвести в квадрат любое рациональное число, то ответом будет не число 2".
Закон контрапозиции гласит, что вместо "если А, то Б" равносильно доказать "если не Б, то не А". В этом случае мы должны предположить, что результат 2 и доказать, что возводили в квадрат нерациональное число. Совершенно очевидно, что мы этого не делаем. Мы предполагаем, что результат 2 и доводим дело до абсурда!

[epros]

Mr. X в сообщении #364121 писал(а):

1. Простых чисел бесконечно много. Д-во: пусть их конечное число $p_1, p_2, ..., p_n.$ Рассмотрим число $p_1p_2...p_n+1$. ... Это доказательство "от противного" или "посредством приведения к абсурду" ? Я так понимаю, в смысле Вашего поста, что это доказательство от противного. Я прав?

Нет, это приведение к абсурду. Таким образом доказывается отрицательное высказывание: Простые числа НЕ ограничены сверху.

Mr. X в сообщении #364121 писал(а):

2. Число $\sqrt2$ -- иррационально. Д-во. Пусть $\sqrt2=p/q$. ... Правильно ли я понимаю, что это тоже доказательство от противного? Или я не прав?

То же самое: это приведение к абсурду. Фактически мы доказали, что возведением в квадрат рационального числа мы НЕ получим числа 2.

Mr. X в сообщении #364121 писал(а):

Просьба: Не могли бы Вы привести пример простенького утверждения (можно из вышеописанных 1,2) и доказать его двумя способами -- от противного и приведением к абсурду, чтобы я получше уяснил для себя эту разницу.

Ещё раз: С точки зрения классической логики сведение к абсурду и доказательство от противного - это одно и то же, потому что для классической логики нет разницы между $\neg \neg P$ и $P$. Но Вы-то хотите без доказательств от противного обойтись, а это можно сделать, только каким-либо образом ограничив классическую логику. Поэтому:
А) Пример должен быть не в классической логике, а в такой, которая не принимает доказательства от противного (например, в конструктивной).
Б) "Правильный" пример должен быть не про "два способа доказательства", а про утверждение, которое недоказуемо иначе как от противного.

Приведу классический пример про "два способа доказательства" (т.е. "неправильный", но зато как Вы хотели). Итак, доказываемое утверждение таково: "Существует иррациональное число, возведя которое в степень $\sqrt{2}$ мы получим рациональное число".

Очень простое классическое доказательство таково:
(a1) Если $\sqrt{2}^{\sqrt{2}}$ рационально, то $\sqrt{2}$ - пример искомого числа.
(a2) Если же $\sqrt{2}^{\sqrt{2}}$ иррационально, то $\sqrt{2}^{\sqrt{2}}$ - пример искомого числа.
Далее рассуждаем от противного:
Если предположить, что искомого числа не существует, то неверно, что $\sqrt{2}^{\sqrt{2}}$ рационально (ибо противоречит a1), и неверно, что $\sqrt{2}^{\sqrt{2}}$ иррационально (ибо противоречит a2).
Но действительное число не может одновременно не быть рациональным и не быть иррациональным. Противоречие.

Конструктивный анализ такое доказательство не признаёт, однако есть довольно сложное конструктивное доказательство того, $\sqrt{2}^{\sqrt{2}}$ иррационально. Оно помогает нам избежать рассуждений от противного. Так что "обходные доказательства" в некоторых случаях могут быть. Но они неинтересны и этот пример "неправильный" знаете почему? Потому что в классической логике "обойти" рассуждения от противного в таких случаях ещё проще. Вот пример рассуждения:
Число $\sqrt{2}^{\sqrt{2}}$ либо рационально, либо иррационально (в силу закона исключённого третьего).
Таким образом, искомым числом является либо $\sqrt{2}$ (в силу a1), либо $\sqrt{2}^{\sqrt{2}}$ (в силу a2).
Т.е. утверждение о существовании искомого числа доказано (без "рассуждений от противного").

Так что примеры того, как можно обойтись без доказательств от противного, не говорят ни о чём. Интереснее примеры случаев, когда нельзя обойтись без доказательств от противного.

Приведу пример, максимально приближенный к "быту". Итак, доказываемое утверждение: "Существуют голубые кошки". Единственный безоговорочно признаваемый нами способ доказательства - предъявление нам образца. Однако вместо реальной кошки нам предъявляют фотографию, причём в системе нашего знания имеется аксиома: "Данная фотография подлинная". Доказательство от противного тривиально:
Если предположить, что голубых кошек не бывает, то фотография подделана, что вступает в противоречие с аксиомой о добросовестности фотографа.

Теперь давайте посмотрим на точку зрения логики, которая доказательства от противного не признаёт (конструктивной). Реальной кошки не было предъявлено, так что утверждение о существовании голубых кошек, строго говоря, не было доказано. Однако предположение о том, что голубых кошек не бывает, тем не менее, вступает в противоречие с аксиомой о добросовестности фотографа. Конструктивист может сказать: "Нельзя отрицать, что голубые кошки существуют" (потому что это означало бы обвинение фотографа в недобросовестности ), - неснимаемое двойное отрицание.

[epros]

Mr. X в сообщении #364121 писал(а):

Грубо говоря, можно ли доказать, что $\sqrt2$ -- иррационально, не прибегая к его (противоречивой) записи в виде $p/q$? И этот же вопрос интересует меня относительно любого утверждения, которое доказывается подобным образом (от противного либо приведением к абсурду). (Да, можно считать,что мы находимся в рамках классической логики, т.е. закон снятия двойного отрицания действует.)

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

[Виктор Викторов]

epros в сообщении #364342 писал(а):

Ещё раз: С точки зрения классической логики сведение к абсурду и доказательство от противного - это одно и то же, потому что для классической логики нет разницы между $\neg \neg P$ и $P$.

Это неверно. Доказать от противного значит воспользоваться законом контрапозиции:

$$A\to B\equiv \neg B\to \neg A$$

а сведение к абсурду значит

$$A\to B\equiv A\wedge \neg B \to C \wedge \neg C$$

Детали смотрите в книге Юрия Шихановича "Введение в современную математику" страница 141. Книга доступна в сети.

[Mr. X]

Уважаемый epros !

Большое спасибо за Вашу бесценную консультацию. Я нашел в Ваших сообщениях (и между их строк) ответы на вопросы, которые меня интересовали и даже большее. Круг моих научных интересов (01.01.01 -- анализ) "страшно далек"от логики и оснований математики вообще. Я, как думаю и подавляющее большинство аналитиков, считает (я -считаЛ) более чем законным (например, в курсе лекций для студентов) начинать классическое доказательство иррациональности $\sqrt2$ со слов: "От противного. Пусть $\sqrt2$ -- рациональное, т.е., $\sqrt2=p/q$ ... " И многие другие доказательства в таком же духе. Оказывается, я сильно заблуждался (?). В свое слабое оправдание, могу лишь отметить, что рецензенты ни разу не были шокированы вольностью такой "фигуры речи" в моих статьях. :)

Еще раз спасибо, с большой признательностью.
-----------------------------------------------------------------------------------

Уважаемый Виктор Викторов !

Также благодарен Вам за Ваши комментарии и проявленный интерес к моим вопросам.

[epros]

Виктор Викторов в сообщении #364444 писал(а):

Это неверно.

Может быть я где-то некорректно выразился, но суть моего замечания состояла в том, что доказательства от противного нельзя изъять из классической логики (не изменяя логику).

Примерно об этом же написано, например, вот в этой статье википедии.

Суть же Вашего замечания мне непонятна. Когда проводится доказательство от противного, у нас нет двух $A$ и $B$, а есть только одно $A$, которое нам нужно доказать. И делается это сведением к противоречию предположения $\neg A$. Может быть это будет сделано выводом из $\neg A$ какого-нибудь $\neg B$, которое противоречит аксиоме $B$, а может быть из $\neg A$ будет выведено непосредственно $A$. Записанная же Вами эквиваленция $A \to B \equiv \neg B \to \neg A$ имеет отношение скорее к выводу по modus tollens, чем к выводу от противного.

И про придение к абсурду тоже непонятно. Зачем Вам тут аж три высказывания? Правило приведения к абсурду заключается в том, что когда мы из некоего предположения $A$ выводим нечто неприемлемое (это может быть $B \wedge \neg B$, но это может быть и просто $\neg A$), то мы считаем предположение опровергнутым, т.е. доказано $\neg A$. Хотя это очень близко к выводу от противного (в классической логике - вплоть до неразличимости), это вещи в принципе разные, ибо если мы отвергаем правило reductio ad absurdum, то мы вообще лишаемся возможности продуктивного определения отрицания.

-- Пт окт 22, 2010 10:40:52 --

Mr. X в сообщении #364586 писал(а):

Я, как думаю и подавляющее большинство аналитиков, считает (я -считаЛ) более чем законным (например, в курсе лекций для студентов) начинать классическое доказательство иррациональности $\sqrt2$ со слов: "От противного. Пусть $\sqrt2$ -- рациональное, т.е., $\sqrt2=p/q$ ... " И многие другие доказательства в таком же духе. Оказывается, я сильно заблуждался (?).

Как я замечал выше, в классической логике reductio ad absurdum практически неотличимо от вывода от противного, поэтому в Ваших формулировках нет ничего страшного. Объяснения этого факта Вы найдёте всё в той же статье википедии про двойное отрицание. Но отличия становятся существенными, как только Вы начинаете отличать двойное отрицание от утверждения (или, что эквивалентно, не принимаете закон исключённого третьего). Поэтому важно было понять чего Вы хотите: Обойтись только без доказательств от противного (= принять конструктивную логику) или обойтись без приведения к абсурду (= принять логику без отрицания - таковые тоже существуют).

[Maslov]

Виктор Викторов в сообщении #364444 писал(а):

Доказать от противного значит воспользоваться законом контрапозиции:

$$A\to B\equiv \neg B\to \neg A$$

а сведение к абсурду значит

$$A\to B\equiv A\wedge \neg B \to C \wedge \neg C$$

Детали смотрите в книге Юрия Шихановича "Введение в современную математику" страница 141. Книга доступна в сети.

У Шихановича так, а у Игошина (B.И.Игошин. Математическая логика и теория алгоритмов. М.: 2008. Стр. 71-72) -- по-другому:

Формы доказательство от противного:

$X \to Y \equiv \lnot Y \to \lnot X$
$X \to Y \equiv (X \land \lnot Y) \to \lnot X $
$X \to Y \equiv (X \land \lnot Y) \to (Z \land \lnot Z)$

Формы доказательства сведением к абсурду:
$(\lnot X \to \lnot Y) \to ((\lnot X \to Y) \to X)$ (приведение противоположного утверждения к абсурду)
$(X \to \lnot Y) \to ((X \to Y) \to \lnot X)$ (приведение данного утверждения к абсурду)

Схема $X \to Y \equiv (X \land \lnot Y) \to (Z \land \lnot Z)$ и туда, и туда подходит: преположив "противное" ($\lnot Y$), приходим к абсурду $(Z \land \lnot Z)$

[epros]

Maslov в сообщении #364685 писал(а):

Формы доказательство от противного:
...
Формы доказательства сведением к абсурду:
...

Без контекста непонятно что здесь доказывается и из чего. Вот это понятно без контекста:

$(\neg X \to \bot) \to X$ (доказательство $X$от противного, общая схема)

Здесь есть только одна пропозициональная переменная $X$ и она стоит в правой части импликации, стало быть её-то и доказываем. Можно, конечно, примешать сюда ещё что-нибудь, чтобы получить какую-нибудь частную схему. Например:

$(A \to (\neg X \to \neg A)) \to (A \to X)$ (вывод $X$ из аксиомы $A$ методом от противного)

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

[Maslov]

epros в сообщении #364692 писал(а):

Без контекста непонятно что здесь доказывается и из чего.

Доказывается теорема "если $X,$ то $Y$": $\vdash X \to Y$

[epros]

Maslov в сообщении #364715 писал(а):

Доказывается теорема "если $X,$ то $Y$": $\vdash X \to Y$

Тогда непонятно, как это увидеть, например, вот отсюда:

Maslov в сообщении #364685 писал(а):

$(\lnot X \to \lnot Y) \to ((\lnot X \to Y) \to X)$ (приведение противоположного утверждения к абсурду)

Я-то писал о простой вещи:
1) $(X \to \bot) \to \neg X$ - опровержение $X$ приведением к абсурду,
2) $(\neg X \to \bot) \to X$ - доказательство $X$ от противного.

С точки зрения классической логики - это одна фигня, поскольку если подставить в (1) $\neg X$ вместо $X$, то мы получим (2). Но это только в классической логике, поскольку она автоматически заменяет $\neg \neg X$ на $X$.

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

А вот если задача заключается в том, чтобы исключить доказательства от противного, то нам нужно изменить логику, т.е. выбрать такое исчисление высказываний, в котором (2) не является тавтологией. Поэтому я и спрашивал топикстартера какова его цель: исключить только (2) или исключить и (1) в том числе.

[Maslov]

epros в сообщении #364724 писал(а):

Maslov в сообщении #364715 писал(а):

Доказывается теорема "если $X,$ то $Y$": $\vdash X \to Y$

Тогда непонятно, как это увидеть, например, вот отсюда:

Maslov в сообщении #364685 писал(а):

$(\lnot X \to \lnot Y) \to ((\lnot X \to Y) \to X)$ (приведение противоположного утверждения к абсурду)

Да, Вы правы. Здесь доказывается просто $\vdash X$.

[Виктор Викторов]

Классический случай некорректного цитирования:

epros в сообщении #364675 писал(а):

Виктор Викторов в сообщении #364444 писал(а):

Это неверно.

Может быть я где-то некорректно выразился, но суть моего замечания состояла в том, что доказательства от противного нельзя изъять из классической логики (не изменяя логику).

Вот, что было на самом деле:

Виктор Викторов в сообщении #364444 писал(а):

epros в сообщении #364342 писал(а):

Ещё раз: С точки зрения классической логики сведение к абсурду и доказательство от противного - это одно и то же, потому что для классической логики нет разницы между $\neg \neg P$ и $P$.

Это неверно. Доказать от противного значит воспользоваться законом контрапозиции:

$$A\to B\equiv \neg B\to \neg A$$

а сведение к абсурду значит

$$A\to B\equiv A\wedge \neg B \to C \wedge \neg C$$