О двух версиях метода reductio ad absurdum («от противного»)

Рассмотрим теорему Кантора о мощности множества-степени [14] и ее традиционное `диагональное' доказательство в его современной ZF-форме [15].

Здесь и далее P (X) — множество-степень, и |X| - мощность произвольного множества X, и, для краткости, RAA = Reductio ad Absurdum, ДМК = Диагональный Метод Кантора, АД-элемент = Анти-Диагональный элемент, порождаемый применение ДМК.

ТЕОРЕМА-1 КАНТОРА (1890). |X| < |P (X)|.

ДОКАЗАТЕЛЬСТВО (с помощью RAA-метода). Очевидно, что |X| |P (X)|.

Допустим, что отображает X на P (X). Определим новое подмножество X* множества X следующим образом: X*={x X | x (x)}. Тогда X* X, и если X* = (y) для некоторого y X, то y X* y (y) y X* и y X* y (y) y X*. Последнее невозможно. Ч.Т.Д.

Как справедливо отмечает Есенин-Вольпин, (см. его комментарий в [15], стр.172), основным этапом доказательства Кантора является доказательство следующего утверждения: «для любого X не существует взаимно однозначного отображения X на P (X)». К сожалению, это очень важное замечание Есенина-Вольпина не было оценено по достоинству и не имело продолжения. Мы попытаемся проанализировать некоторые следствия этого комментария.

Однако, прежде, чем приступить к анализу канторовского доказательства, напомню некоторые фундаментальные утверждения современной теории множеств [14−16], которые будут использованы ниже.

ОПРЕДЕЛЕНИЕ 1. Множество, Z, является бесконечным, если и только если оно эквивалентно своему собственному подмножеству.

ЛЕММА 1. Если разность между количествами элементов двух бесконечных множеств, скажем, Z₁ и Z₂ является конечной, то множества Z₁ и Z₂ эквивалентны, т. е. |Z₁| = |Z₂|.

ОПРЕДЕЛЕНИЕ 2. Два бесконечных множества, скажем, Z₁ и Z₂ эквивалентны, т. е. |Z₁| = |Z₂|, если и только если существует 1−1-соответствие между Z₁ и Z₂.

ЛЕММА 2. Если не существует 1−1- соответствия между элементами множеств Z₁ и Z₂, то множества Z₁ и Z₂ не эквивалентны, т. е. |Z₁| |Z₂|.

Теперь, принимая во внимание комментарий Есенина-Вольпина, перепишем Теорему-1 Кантора и ее традиционное доказательство в следующей семантически эквивалентной форме.

ТЕОРЕМА-2 КАНТОРА (1873, 1890). Не существует 1−1-соответствия между X и P (X) для любого X.

ДОКАЗАТЕЛЬСТВО (с помощью RAA-метода). Допустим, что существует 1−1-соответствие, которое отображает X на P (X), т. е. YP (X)[Y]. Определим новое подмножество: X*={x X | x (x)}. Тогда X*P (X), но Y[X*Y], т. е. X*. Противоречие. Ч.Т.Д.

ТЕОРЕМА-3 КАНТОРА (1890). |X| < |P (X)|.

ДОКАЗАТЕЛЬСТВО. Из Теоремы 2 и Леммы 2 следует |X| |P (X)|, откуда, в силу очевидного неравенства |X| |P (X)|, следует строгое неравенство |X| < |P (X)|. Ч.Т.Д.

Рассмотрим теперь логическую схему классического метода контр-примера.

• 1. Имеется некоторое общее гипотетическое утверждение x P (x).
• 2. Устанавливается факт (если это удается), что x* P (x*).
• 3. Из этого единственного факта следует, что [x P (x)].

СЛЕДСТВИЕ-1. Для того, чтобы опровергнуть общее утверждение, xP (x), достаточно единственного контр-пример x *, для которого имеет место P (x*).

СЛЕДСТВИЕ-2. Мощность множества всех возможных контр-примеров, x, для которых P (x), не принимается во внимание и не используется в рамках доказательства методом контр-примера.

Рассмотрим два примера реального применения метода контр-примера в математике.

ПРИМЕР 1. В XVIII веке Эйлер сформулировал следующее общее утверждение.

ГИПОТЕЗА ЭЙЛЕРА. Для любого показателя r 3 диофантово уравнение, n^r = n₁^r + n₂^r + n₃^r + … + n_s^r, не имеет решений в натуральных числах, если s < r.

В течение более 200 лет никому не удавалось ни доказать, ни опровергнуть эту Гипотезу. Только в 1967 группа американских математиков с помощью мощного компьютера открыла… всего только один контр-пример [17], 144⁵ = 27⁵ + 84⁵ + 110⁵ + 133⁵, где r = 5, s = 4, т. е. s < r. Этот единственный контр-пример доказал, что Гипотеза Эйлера — ложна. Таким образом, для того, чтобы опровергать общее утверждение, действительно оказалось достаточно единственного контр-примера (Следствие 1). И тот факт, что множество таких контр-примеров может быть бесконечным не играет в таком опровержении никакой роли (Следствие 2). Другими словами, опровержение общего утверждения с помощью данного контр-примера и вопрос о фактическом количестве таких контр-примеров, т. е. вопрос о мощности множества всех возможных контр-примеров, являются абсолютно различными, независимыми проблемами.

Рассмотрим теперь другой пример использования метода контр-примера.

ПРИМЕР 2. Согласно допущению доказательства Теоремы-2 Кантора, имеется 1−1-соответствие, которое отображает X на P (X), т. е. {B:} все элементы множества P (X) принадлежат данному отображению. Затем Кантор определяет новое подмножество X*={x X | x (x)} такое, что X*P (X), но X*. Это означает что X*P (X)[X*], т. е. {B:} не все элементы множества P (X) принадлежат данному .

Таким образом, с точки зрения классической логики, канторовский АД-элемент X* является контр-примером, опровергающим общее утверждение B.

Эти два примера показывают, что есть две, существенно различные версии метода контр-примера: в первой версии (назовем ее классической версией), контр-пример отыскивается в множестве всех возможных реализаций данной гипотезы; во второй версии (назовем ее ДМК-версией), контр-пример алгоритмически дедуцируется из той гипотезы, которую этот контр-пример должен опровергнуть.

Заметим, что ДМК-версия является отличительной особенностью именно диагонального метода Кантора. Этот факт может быть сформулирован в следующей общей форме.

УТВЕРЖДЕНИЕ-1. Знаменитый Диагональный Метод Кантора (в любой мета-математической реализации этого метода) является специальным случаем метода контр-примера, где сам контр-пример не отыскивается в множестве всех возможных реализаций данного общего утверждения, а алгоритмически дедуцируется из того общего утверждения, которое этот контр-пример и призван опровергнуть.

Докажем теперь две теоремы, выявляющие некоторые «скрытые» логические особенности диагонального метода Кантора.

ТЕОРЕМА 1. Вывод Кантора |X| < |P (X)| противоречит Лемме 1 [12,13,18−21].

ДОКАЗАТЕЛЬСТВО. Следуя Кантору, допустим, что отображает X на P (X), т. е. |X| = |P (X)|. Представим множество P (X) в виде суммы, P (X) = P₁+P₂ где P₁ есть множество всех элементов из P (X), которые действительно принадлежат, и P₂ — дополнение к P₁ в P (X), т. е. P₂ = P (X) — P₁. В силу RAA-допущения, |P₁|=|X|, и P₂ — пустое множество.

Для данного отображения Кантор определяет X*={x X | x (x)} так, что X*P (X), но X*, т. е. X* P₁. Следовательно, X* P₂.

С точки зрения классической логики и классической математики, канторовский АД-элемент X* является контр-примером, опровергающим общее утверждение B = «данное отображение включает все элементы из P (X)». Из доказанной ложности утверждения B (доказанной именно с помощью ДМК-версии метода контр-примера) следует (по правилу modus tollens), что RAA-допущение, |X| = |P (X)|, ложно. На основании Леммы 2, вместе с очевидным неравенством |X| |P (X)|, это ведет к заключительному утверждению Кантора |X| < |P (X)|.

Таким образом, с точки зрения формальной логики, RAA-доказательство Кантора — безупречно и неопровержимо. Однако, очевидно, что для данного (фиксированного) отображения, диагональный метод Кантора способен «породить» единственный, уникальный элемент X* множества P (X), не принадлежащий данному. Это означает, что заключение Кантора |X|<|P (X)| основано на том факте, что бесконечное множество P (X) имеет на один элемент больше, чем бесконечное множество X, т. е. |P₂| = 1. Очевидно, что такое теоретико-множественное «основание» для канторовского вывода |X|<|P (X)| фатально противоречит теоретико-множественной Лемме 1, согласно которой из равенства |P (X)| - |X| =1 следует |X| = |P (X)|. Ч.Т.Д.

ТЕОРЕМА 2. Неравенство Кантора |X|<|P (X)| недоказуемо [12,13,18−21].

ДОКАЗАТЕЛЬСТВО. Единственным поводом для утверждения |X|<|P (X)|, является Теоремоа-1 Кантора. Поэтому для доказательства Теоремы 2 достаточно доказать, что традиционное доказательство Кантора не доказывает утверждения |X|<|P (X)|.

С этой целью, рассмотрим снова традиционное доказательство Кантора.

ТЕОРЕМА КАНТОРА. |X| < |P (X)|.

ДОКАЗАТЕЛЬСТВО 1. Допустим, что отображает X на P (X), т. е. |X| = |P (X)|.

Представим множество P (X) в виде суммы: P (X) = P₁₁+P₁₂, где P₁₁ — множество всех элементов из P (X), которые действительно принадлежат, и P₁₂ — дополнение к P₁₁ в P (X), т. е. P₁₂ = P (X) — P₁₁. В силу RAA-допущения, |P₁₁|=|X|, и P₁₂ = .

Для данного Кантор определяет новый элемент X*={xX | x (x)}, который не принадлежит. Но теперь, мы допускаем, что изменяя исходное отображение (без изменения, однако, количества элементов из P (X) в исходном отображении), диагональная процедура Кантора способна произвести бесконечное множество новых АД-элементов из P (X), не принадлежащих исходному отображению, т. е. принадлежащих дополнению P₁₂. Последнее означает, что теперь истинная мощность множества P (X) определяется количеством элементов дополнения P₁₂, то есть |P (X)| = |P₁₂|.

При этом возможны следующие два случая.

• (i) |P₁₂| = |X|. Тогда |P (X)| = |P₁₁ + P₁₂| =|X|, и поэтому опровергнуть RAA-допущение |X| = |P (X)| невозможно, с точки зрения аксиоматической теории множеств.
• (ii) |P₁₂| > |X|. Однако, поскольку доказательство Кантора пока еще не закончено, само существование мощности большей, чем |X|, пока не доказано, а поэтому гипотетическое утверждение |P₁₂| > |X| должно быть доказано. Это может быть сделано единственным способом — посредством ДМК, т. е. нужно теперь доказать исходную Теорему Кантора с новым символом P₁₂ вместо старого символа P (X).

ТЕОРЕМА КАНТОРА. |X| < |P₁₂|.

ДОКАЗАТЕЛЬСТВО 2. Допустим, что ₁ отображает X на P₁₂, т. е. |X| = |P₁₂|. Применение ДМК к ₁ порождает бесконечное множество элементов из P₁₂, которые не принадлежат ₁. Представим множество P₁₂ в виде суммы: P₁₂ = P₂₁+P₂₂, где P₂₁ — множество всех элементов из P₁₂, которые действительно принадлежат ₁, и P₂₂ — дополнение к P₂₁ в P₁₂. В силу RAA-допущения, |P₂₁|=|X|, и P₂₂ содержит все АД-элементы, порождаемые применением ДМК к ₁. Последнее означает, что теперь истинная мощность P₁₂ определяется количеством элементов дополнения P₂₂, то есть |P₁₂| = |P₂₂|.

Рассмотрим следующие два случая.

• (i) |P₂₂| = |X|. Тогда |P₁₂| = |P₂₁ + P₂₂| =|X|, и поэтому невозможно опровергнуть RAA-допущение, |X| = |P₁₂|, с точки зрения аксиоматической теории множеств.
• (ii) |P₂₂| > |X|. Однако, поскольку доказательство Кантора пока еще не закончено, само существование мощности, которая больше, чем |X|, пока не доказано, а поэтому гипотетическое утверждение |P₂₂| > |X| должно быть доказано. Это может быть сделано единственным способом — посредством ДМК, т. е. нужно теперь доказать исходную Теорему Кантора с новым символом P₂₂ вместо старого символа P₁₂.

И так далее до бесконечности.

Таким образом, традиционное канторовское доказательство Теоремы о мощности множества-степени, с теоретико-множественной точки зрения (!), или не способно опровергнуть RAA-допущение, |X| = |P (X)|, или сводится к бесконечной системе «вложенных» доказательств исходной Теоремы Кантора с последовательной заменой исходного символа P (X) символами P₁₂, P₂₂, P₃₂, …, т. е. сводится к следующему нефинитному, тавтологическому, и довольно бессмысленному «рассуждению» (здесь D_i = «требуется доказать, что |X| < |P_i2|»): D₁ D₂ D₃ … (*).

Очевидно, что до тех пор, пока потенциально бесконечное «рассуждение» (*) не закончено, исходное RAA-допущение |X| = |P (X)| канторовского RAA-доказательства неопровержимо с теоретико-множественной точки зрения, и, следовательно, утверждение Кантора |X| < |P (X)| - недоказуемо. Ч.Т.Д.

Итак, существуют две, принципиально различные версии метода контр-примера. Традиционное доказательство Теорем 1 и 2 Кантора проводится методом RAA и основано на явном использовании ДМК-версии метода контр-примера. Ключевым моментом канторовского RAA-доказательства является (алгоритмическое) доказательство истинности некоторого следствия (В= «X*P (X)[X*]») данного RAA-допущения (А = «|P (X)|=|X|»), которое (это следствие) дедуцируется из данного RAA-допущения. Ключевым моментом классического RAA-метода является доказательство ложности некоторого формального следствия RAA-допущения, причем это доказательство ложности основано не на методе контр-примера, а на законе противоречия и проводится независимо от дедуктивного вывода данного формального следствия из данного RAA-допущения (иначе — круг в доказательстве). Это означает, что существуют две различные версии метода RAA: ДМК-версия, на которой основано традиционное доказательство Кантора, и классическая версия, которая используется в подавляющем большинстве реальных математических доказательств.

В современной мета-математике RAA-метод (так называемое правило «введения отрицания») формулируется следующим образом [16]: если Г, А |- В и Г, А |- В, то Г |- А.(П-1).

Нетрудно показать, что данная формулировка RAA-метода является формализацией именно канторовской ДМК-версии. С другой стороны, адекватная формулировка классической версии RAA-метода имеет вид: если Г, А |- В и Г |- В, то Г |- А.(П-2).

Это означает, что ИИ-системы, использующие мета-математическую версию (П-1) RAA-метода, могут приводит к результатам, существенно искажающим семантику исходных математических моделей функционирования реальных сложных систем.