Доказательство по противопоставлению имеет преимущество логического эквивалента между “P подразумевает Q” и «Не Q подразумевает Не P”. Например, утверждение «Если это моя машина, то она красная» эквивалентно утверждению «Если эта машина не красная, она не моя».  А значит, чтобы доказать «Если Р, то Q» по методу противопоставления значит доказать «Если нет Q, то и не Р».

Пример: аналогия

Вот простой пример, который иллюстрирует этот метод. Утверждение будет использовать следующие определения.

Определения.

Целое х является четным ( соответственно нечетный) если есть другое целое k, для которого х=2k (соответственно 2k+1). Считается, что два целых имеют одну и ту же аналогию, если они оба случайны, или оба четные, или оба нечетные.

Теорема. Если х и у это два целых, для которых х+у будет четным, тогда х и у имеют одну и ту же аналогию.

Доказательство. Противопоставляющая версия этой теоремы такая « Если х и у это два целых и противоположной аналогией, тогда их сумма должна быть нечетной.»

А значит мы предполагаем, что х и у имеют противоположную аналогию. Так как одно из этих целых является четным, а другое нечетным, тогда не будет потери общего принципа для предположения, что х нечетное, а у четное.

Соответственно, существуют целые k и m, для которых x = 2k, а y = 2m+1. Итак, мы вычисляем сумму x+y = 2k + 2m + 1 = 2(k+m) + 1, что является нечетным целым для определения.

Как это отличается от доказательства противоречия?

Разница между противопоставления и методом противоречия очень тонкая. Давайт изучим, как эти два метода работают, когда мы пытаемся доказать «Если Р, тогда Q».

Метод противоречия: предположим, что Р и Не Q и докажем некоторую степень противоречия.

Метод противопоставления: предположим Не Q и докажем не P.

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

Тест на точный квадрат

В этом примере нам понадобятся два понятия. Целым n называется точный квадрат, если есть другое целое k, такое  как n = k2. Например, 13689 это точный квадрат когда 13689 = 1172.

Вторая идея это напоминание о арифметических операциях над абсолютными значениями чисел.

Для двух целых m and n, n mod(m) = r  будет напоминанием, результатом того, что мы делим m на n. Это значит, что существует такое целое q, такое как n = mq + r. Например, 127 mod(29) = 11 тогда как 29 перейдет в 127 4 раза с напоминанием в 11 (или, другими словами, 127 = (4)(29) + 11). Определение того, является ли точный квадрат позитивным целым, может быть сложным.  К примеру, является ли is 82,642,834,671 точным квадратом? Сначала мы вычисляем 82,642,834,671 mod(4) = 3. Затем используем следующую теорему:

Теорема.  Если n является позитивным целым, таким как n mod(4) is 2 or 3, тогда n не будет точным квадратом.

Доказательство.  Мы докажем версию противопоставления:  «Если n это точный квадрат, тогда n mod(4) должно равняться 0 or 1.» (Вы понимаете, почему эта версия является противопоставляющей?) Предположим n = k2. Есть 4 случая на рассмотрение.

Если k mod(4) = 0, тогда k = 4q, для некоторого целого q. Тогда, n = k2 = 16 q2 = 4(4 q2) , то есть n mod(4) = 0.

Если k mod(4) = 1, тогда k = 4q + 1, для некоторого целого q. Тогда, n = k2 = 16 q2 + 8 q + 1= 4(4 q2 + 2 q) + 1, i.e. n mod(4) = 1.

Если k mod(4) = 2, тогда k = 4q + 2, для некоторого целого q. Тогда, n = k2 = 16 q2 + 16 q + 4 = 4(4 q2 + 4 q + 1), то есть n mod(4) = 0.

Если k mod(4) = 3, тогда k = 4q + 3, для некоторого целого q. Tогда, n = k2 = 16 q2 + 24 q + 9 = 4(4 q2 + 6 q + 2) + 1, то есть n mod(4) = 1.

Упражнения

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

Если x и y являются двумя целыми, продуктом которого будет четное, тогда хотя бы одно из них должно быть нечетным.

Если x и y являются двумя целыми, продуктом которого будет нечетное, тогда оба должны быть нечетными.

Если n является позитивным целым, таким как n mod(3) = 2, тогда n не является точным квадратом.

Если a и b являются реальными числами, такими что продуктом a b будет иррациональное число, тогда и a, и b будут иррациональным числом.