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

В математике доказательство методом бесконечного спуска , также известное как метод спуска Ферма, представляет собой особый вид доказательства от противного ^[1], используемого для того, чтобы показать, что утверждение не может быть выполнено для любого числа, показывая, что, если бы утверждение выполнялось для числа то то же самое будет верно и для меньшего числа, что приведет к бесконечному спуску и, в конечном счете, к противоречию. ^[2] Это метод, который основан на принципе хорошего порядка и часто используется, чтобы показать, что данное уравнение, например диофантово уравнение , не имеет решений. ^[3]^[4]

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

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

Самое раннее использование метода бесконечного спуска появляется в «Началах» Евклида . ^[3] Типичным примером является предложение 31 книги 7, в котором Евклид доказывает, что каждое составное целое число делится (в терминологии Евклида «измеряется») на некоторое простое число. ^[2]

Этот метод был значительно позже развит Ферма , который ввёл этот термин и часто использовал его для диофантовых уравнений . ^[4]^[5] Два типичных примера показывают неразрешимость диофантова уравнения и доказывают теорему Ферма о суммах двух квадратов , которая утверждает, что нечетное простое число p может быть выражено как сумма двух квадратов , когда (см. Модульная арифметика и доказательство бесконечным спуском ). Таким образом Ферма смог показать отсутствие решений во многих случаях диофантовых уравнений, представляющих классический интерес (например, задача о четырех полных квадратах в арифметической прогрессии ). $r^{2}+s^{4}=t^{4}$ $p\equiv 1{\pmod {4}}$

В некоторых случаях, на современный взгляд, его «метод бесконечного спуска» представляет собой использование обращения удвоительной функции для рациональных точек на эллиптической кривой E. Контекст представляет собой гипотетическую нетривиальную рациональную точку на E . Удвоение точки на E примерно удваивает длину чисел, необходимых для ее записи (в виде количества цифр), так что «уменьшение» точки пополам дает рациональное выражение с меньшими членами. Поскольку слагаемые положительны, они не могут уменьшаться бесконечно.

Теория чисел

В теории чисел двадцатого века метод бесконечного спуска был снова использован и доведен до такой степени, что он соединился с основным направлением алгебраической теории чисел и изучением L-функций . Структурный результат Морделла о том, что рациональные точки на эллиптической кривой E образуют конечно порожденную абелеву группу , использовал аргумент бесконечного спуска, основанный на E /2 E в стиле Ферма.

Чтобы распространить это на случай абелева многообразия A , Андре Вейлю пришлось уточнить способ количественного определения размера решения с помощью функции высоты — концепция, которая стала основополагающей. Чтобы показать, что A ( Q )/2 A ( Q ) конечно, что, безусловно, является необходимым условием конечного порождения группы A ( Q ) рациональных точек A , нужно выполнить вычисления в том, что позже было признано как Галуа. когомологии . Таким образом, абстрактно определенные группы когомологий в теории отождествляются со спусками в традиции Ферма. Теорема Морделла -Вейля положила начало тому, что позже стало очень обширной теорией.

Примеры применения

Иррациональность √ 2

Доказательство того, что квадратный корень из 2 ( √ 2 ) иррационален (т.е. не может быть выражен как дробь двух целых чисел), было обнаружено древними греками и, возможно, является самым ранним известным примером доказательства путем бесконечного спуска. Пифагорейцы открыли, что диагональ квадрата несоизмерима с его стороной, или, выражаясь современным языком, что квадратный корень из двух иррационален . Мало что известно с уверенностью о времени и обстоятельствах этого открытия, но часто упоминается имя Гиппаса из Метапонта. Некоторое время пифагорейцы считали официальной тайной открытие, что квадратный корень из двух иррационален, и, согласно легенде, Гиппас был убит за его разглашение. ^[6]^[7]^[8] Квадратный корень из двух иногда называют «числом Пифагора» или «константой Пифагора», например, Conway & Guy (1996). ^[9]

Древние греки , не имея алгебры , разработали геометрическое доказательство путем бесконечного спуска ( Джон Хортон Конвей представил другое геометрическое доказательство путем бесконечного спуска, которое может быть более доступным ^[10] ). Ниже приводится алгебраическое доказательство в том же духе:

Предположим, что √ 2 были рациональными . Тогда это можно было бы записать как

{\sqrt {2}}={\frac {p}{q}}

для двух натуральных чисел $p$ и $q$ . Тогда возведение в квадрат дало бы

2={\frac {p^{2}}{q^{2}}},

2q^{2}=p^{2},

поэтому 2 должно разделить p ² . Поскольку 2 — простое число , оно также должно делить p по лемме Евклида . Итак, p = 2 r для некоторого целого числа r .

Но потом,

2q^{2}=(2r)^{2}=4r^{2},

q^{2}=2r^{2},

это показывает, что 2 также должно делить q . Итак, q = 2 s для некоторого целого числа s .

Это дает

{\frac {p}{q}}={\frac {2r}{2s}}={\frac {r}{s}}

Следовательно, если бы √ 2 можно было записать как рациональное число, то его всегда можно было бы записать как рациональное число с меньшими частями, которое само по себе можно было бы записать с еще меньшими частями, до бесконечности . Но это невозможно в множестве натуральных чисел . Поскольку √ 2 — действительное число , которое может быть как рациональным, так и иррациональным, единственный оставшийся вариант — сделать √ 2 иррациональным. ^[11]

(С другой стороны, это доказывает, что если бы √ 2 было рационально, никакого «наименьшего» представления в виде дроби не могло бы существовать, поскольку любая попытка найти «наименьшее» представление p / q подразумевала бы существование меньшего представления, что является аналогичным противоречием. )

Иррациональность √ k , если оно не целое число

Для положительного целого числа k предположим, что √ k не является целым числом, но является рациональным и может быть выражено какм/ндля натуральных чисел m и n , и пусть q — наибольшее целое число , меньшее √ k (т. е. q — это пол √ k ). Затем

{\begin{aligned}{\sqrt {k}}&={\frac {m}{n}}\\[6pt]&={\frac {m\left({\sqrt {k}} -q\right)}{n\left({\sqrt {k}}-q\right)}}\\[6pt]&={\frac {m{\sqrt {k}}-mq}{n{ \sqrt {k}}-nq}}\\[6pt]&={\frac {\left(n{\sqrt {k}}\right){\sqrt {k}}-mq}{n\left( {\frac {m}{n}}\right)-nq}}\\[6pt]&={\frac {nk-mq}{m-nq}}\end{aligned}}

Числитель и знаменатель были умножены на выражение ( √ k − q ) — которое положительное, но меньше 1 — а затем упростилось независимо. Итак, результирующие произведения, скажем, m' и n' , сами являются целыми числами и меньше m и n соответственно. Следовательно, независимо от того, какие натуральные числа m и n используются для выражения √ k , существуют меньшие натуральные числа m' < m и n' < n , которые имеют одинаковое соотношение. Но бесконечный спуск по натуральным числам невозможен, поэтому это опровергает исходное предположение о том, что √ k можно выразить как отношение натуральных чисел. ^[12]

Неразрешимость задачи r 2 + s 4 = t 4 и ее перестановок

Неразрешимости в целых числах достаточно, чтобы показать неразрешимость в целых числах, что является частным случаем Великой теоремы Ферма , и исторические доказательства последней основывались на более широком доказательстве первой с использованием бесконечного спуска. Следующее, более позднее доказательство демонстрирует обе эти невозможности, доказывая еще более широко, что у пифагорейского треугольника не может быть никаких двух сторон, каждая из которых была бы квадратом или дважды квадратом, поскольку не существует наименьшего такого треугольника: ^[13] $r^{2}+s^{4}=t^{4}$ $q^{4}+s^{4}=t^{4}$

Предположим, существует такой треугольник Пифагора. Затем его можно уменьшить, чтобы получить примитивный (т. е. без общих факторов, отличных от 1) треугольник Пифагора с тем же свойством. Стороны примитивных треугольников Пифагора можно записать как , где a и b относительно простые , а a+b нечетные и, следовательно, y и z нечетные. То, что y и z нечетны, означает, что ни y , ни z не могут быть дважды квадратными. Более того, если x — квадрат или дважды квадрат, то каждый из a и b — квадрат или дважды квадрат. Есть три случая, в зависимости от того, какие две стороны постулируются, каждая из которых равна квадрату или дважды квадрату: $x=2ab,$ $y=a^{2}-b^{2},$ $z=a^{2}+b^{2}$

y и z : в этом случае y и z являются квадратами. Но тогда прямоугольный треугольник с катетамиигипотенузойтакже будет иметь целые стороны, включая квадратный катет () и квадратную гипотенузу (), и будет иметь меньшую гипотенузу (по сравнению с). ${\sqrt {yz}}$ $b^{2}$ $а^{2}$ $b^{2}$ $а^{2}$ $а^{2}$ $z=a^{2}+b^{2}$
z и x : z — квадрат. Целочисленный прямоугольный треугольник с катетамиигипотенузойтакже будет иметь две стороны (и), каждая из которых представляет собой квадрат или удвоенный квадрат, и меньшую гипотенузу (по сравнению с ) . $а$ $б$ ${\sqrt {z}}$ $а$ $б$ ${\sqrt {z}}$ $z$
y и x : y — квадрат. Целочисленный прямоугольный треугольник с катетамиигипотенузойбудет иметь две стороны ( b и a ), каждая из которых является квадратом или дважды квадратом, с меньшей гипотенузой, чем исходный треугольник (по сравнению с). $б$ ${\sqrt {y}}$ $а$ $а$ $z=a^{2}+b^{2}$

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

Это означает, что уравнения