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

Метод математического доказательства с использованием противоречия

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

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

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

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

Метод был значительно позже развит Ферма , который ввел этот термин и часто использовал его для диофантовых уравнений . ^{[4] [5]} Два типичных примера показывают неразрешимость диофантова уравнения и доказывают теорему Ферма о суммах двух квадратов , которая утверждает, что нечетное простое число p может быть выражено как сумма двух квадратов , когда (см. Модульная арифметика и доказательство бесконечным спуском ). Таким образом, Ферма смог показать несуществование решений во многих случаях диофантовых уравнений, представляющих классический интерес (например, проблема четырех полных квадратов в арифметической прогрессии ). ${\displaystyle r^{2}+s^{4}=t^{4}}$ ${\displaystyle 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 было бы рациональным . Тогда это можно было бы записать как

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

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

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

${\displaystyle 2q^{2}=p^{2},}$

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

Но потом,

${\displaystyle 2q^{2}=(2r)^{2}=4r^{2},}$

${\displaystyle q^{2}=2r^{2},}$

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

Это дает

${\displaystyle {\frac {p}{q}}={\frac {2r}{2s}}={\frac {r}{s}}}$.

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

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

Иррациональность√ кесли это не целое число

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

${\displaystyle {\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]

Неразрешимостьг2+с4=т4и его перестановки

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

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

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

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

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

${\displaystyle r^{2}+s^{4}=t^{4},}$

${\displaystyle r^{4}+s^{2}=t^{4},}$и

${\displaystyle r^{4}+s^{4}=t^{2}}$

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

Другие подобные доказательства бесконечным спуском для случая n = 4 теоремы Ферма см. в статьях Гранта и Переллы ^[14] и Барбары ^{[15] .}

Смотрите также

• Виета прыгает

Ссылки

1. Бенсон, Дональд С. (2000). Момент доказательства: математические прозрения. Oxford University Press. стр. 43. ISBN 978-0-19-513919-8. частный случай доказательства от противного, называемый методом бесконечного спуска
2. "Что такое бесконечный спуск". www.cut-the-knot.org . Получено 10.12.2019 .
3. "Метод бесконечного спуска Ферма | Brilliant Math & Science Wiki". brilliant.org . Получено 10.12.2019 .
4. Дональдсон, Нил. "Метод спуска Ферма" (PDF) . math.uci.edu . Получено 10.12.2019 .
5. Вайль, Андре (1984), Теория чисел: подход через историю от Хаммурапи до Лежандра , Биркхойзер , стр. 75–79, ISBN 0-8176-3141-0
6. Стефани Дж. Моррис, «Теорема Пифагора», кафедра математики, Университет Джорджии .
7. Брайан Клегг, «Опасное соотношение ...», Nrich.org, ноябрь 2004 г.
8. Курт фон Фриц, «Открытие несоизмеримости Гиппасом из Метапонта», Анналы математики, 1945.
9. Конвей, Джон Х.; Гай , Ричард К. (1996), Книга чисел , Коперник, стр. 25
10. "Квадратный корень из 2 иррационален (Доказательство 8)". www.cut-the-knot.org . Получено 10.12.2019 .
11. Конрад, Кит (6 августа 2008 г.). «Бесконечный спуск» (PDF) . kconrad.math.uconn.edu . Получено 10.12.2019 .
12. Сагер, Йорам (февраль 1988 г.), «Что мог сделать Пифагор», American Mathematical Monthly , 95 (2): 117, doi :10.2307/2323064, JSTOR  2323064
13. Долан, Стэн, «Метод Ферма по спуску к бесконечности », Mathematical Gazette 95, июль 2011 г., 269–271.
14. Грант, Майк и Перелла, Малкольм, «Спуск к иррациональному», Mathematical Gazette 83, июль 1999 г., стр. 263–267.
15. Барбара, Рой, «Великая теорема Ферма в случае n  = 4», Mathematical Gazette 91, июль 2007 г., 260–262.

Дальнейшее чтение

• Бесконечный спуск в PlanetMath .
• Пример последней теоремы Ферма на PlanetMath .