Доказательство бесконечным спуском - Proof by infinite descent

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

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

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

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

Значительно позже метод был разработан Ферма, который ввел этот термин и часто использовал его для Диофантовы уравнения.^[4]^[5] Два типичных примера показывают неразрешимость диофантова уравнения р² + s⁴ = т⁴ и доказывая Теорема Ферма о суммах двух квадратов, который утверждает, что нечетное простое число п можно выразить как сумму двух квадраты когда п ≡ 1 (мод 4) (см. доказательство ). Таким образом, Ферма смог показать отсутствие решений во многих случаях диофантовых уравнений, представляющих классический интерес (например, проблема четырех полных квадратов в арифметическая прогрессия ).

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

Теория чисел

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

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

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

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

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

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

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

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

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

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

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

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

Но потом,

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

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

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

Это дает

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

.

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

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

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

Для положительного целого числа k, Предположим, что √k не является целым числом, но рационально и может быть выражено как ^м⁄_п для натуральных чисел м и п, и разреши q быть наибольшим целым числом меньше √k. потом

{ displaystyle { begin {align} { sqrt {k}} & = { frac {m} {n}} [8pt] & = { frac {m ({ sqrt {k}} - q )} {n ({ sqrt {k}} - q)}} [8pt] & = { frac {m { sqrt {k}} - mq} {n { sqrt {k}} - nq }} [8pt] & = { frac {(n { sqrt {k}}) { sqrt {k}} - mq} {n ({ frac {m} {n}}) - nq} } [8pt] & = { frac {nk-mq} {m-nq}} end {align}}}

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

Неразрешимость р² + s⁴ = т⁴ и его перестановки

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

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

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 и Икс: z это квадрат. Целочисленный прямоугольный треугольник с ножками ${ displaystyle a}$ и ${ displaystyle b}$ и гипотенуза ${ displaystyle { sqrt {z}}}$ также будет иметь две стороны ( ${ displaystyle a}$ и ${ displaystyle b}$ ) каждый из которых представляет собой квадрат или дважды квадрат и меньшую гипотенузу ( ${ displaystyle { sqrt {z}}}$ в сравнении с ${ displaystyle z}$ ).
y и Икс: y это квадрат. Целочисленный прямоугольный треугольник с ножками ${ displaystyle b}$ и ${ displaystyle { sqrt {y}}}$ и гипотенуза ${ displaystyle a}$ будет иметь две стороны (б и а) каждый из которых представляет собой квадрат или дважды квадрат с меньшей гипотенузой, чем исходный треугольник ( ${ displaystyle a}$ в сравнении с ${ Displaystyle г = а ^ {2} + Ь ^ {2}}$ ).

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

Отсюда следует, что уравнения

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

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

и

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

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

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

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

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

использованная литература

^ "Окончательный словарь высшего математического жаргона - Доказательство бесконечным спуском". Математическое хранилище. 2019-08-01. Получено 2019-12-10.
^ ^а ^б "Что такое бесконечный спуск". www.cut-the-knot.org. Получено 2019-12-10.
^ ^а ^б "Метод бесконечного спуска Ферма | Блестящая вики по математике и науке". brilliant.org. Получено 2019-12-10.
^ ^а ^б Дональдсон, Нил. «Метод спуска Ферма» (PDF). math.uci.edu. Получено 2019-12-10.
^ Вайль, Андре (1984), Теория чисел: исторический подход от Хаммурапи до Лежандра, Биркхойзер, стр. 75–79, ISBN 0-8176-3141-0
^ Стефани Дж. Моррис, «Теорема Пифагора», Кафедра математики. Ред., Университет Джорджии.
^ Брайан Клегг, "Опасное соотношение ...", Nrich.org, ноябрь 2004 г.
^ Курт фон Фриц, «Открытие несоизмеримости Гиппасом из Метапонта», Анналы математики, 1945.
^ Конвей, Джон Х.; Гай, Ричард К. (1996), Книга чисел, Коперник, стр. 25
^ «Квадратный корень из 2 иррационален (доказательство 8)». www.cut-the-knot.org. Получено 2019-12-10.
^ Конрад, Кейт (6 августа 2008 г.). "Бесконечный спуск" (PDF). kconrad.math.uconn.edu. Получено 2019-12-10.
^ Сагер, Йорам (февраль 1988 г.), «Что мог бы сделать Пифагор», Американский математический ежемесячный журнал, 95: 117, Дои:10.2307/2323064
^ Долан, Стэн, "Метод Ферма Descente Infinie", Математический вестник 95, июль 2011 г., стр. 269–271.
^ Грант, Майк и Перелла, Малкольм, «Спуск к иррациональному», Математический вестник 83, июль 1999 г., стр. 263–267.
^ Барбара, Рой "Последняя теорема Ферма в случае п = 4", Математический вестник 91, июль 2007 г., стр. 260–262.

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

[1] "Окончательный словарь высшего математического жаргона - Доказательство бесконечным спуском". Математическое хранилище. 2019-08-01. Получено 2019-12-10.

[:0-2] а ^б "Что такое бесконечный спуск". www.cut-the-knot.org. Получено 2019-12-10.

[:1-3] а ^б "Метод бесконечного спуска Ферма | Блестящая вики по математике и науке". brilliant.org. Получено 2019-12-10.

[:2-4] а ^б Дональдсон, Нил. «Метод спуска Ферма» (PDF). math.uci.edu. Получено 2019-12-10.

[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. Получено 2019-12-10.

[11] Конрад, Кейт (6 августа 2008 г.). "Бесконечный спуск" (PDF). kconrad.math.uconn.edu. Получено 2019-12-10.

[12] Сагер, Йорам (февраль 1988 г.), «Что мог бы сделать Пифагор», Американский математический ежемесячный журнал, 95: 117, Дои:10.2307/2323064

[13] Долан, Стэн, "Метод Ферма Descente Infinie", Математический вестник 95, июль 2011 г., стр. 269–271.

[14] Грант, Майк и Перелла, Малкольм, «Спуск к иррациональному», Математический вестник 83, июль 1999 г., стр. 263–267.

[15] Барбара, Рой "Последняя теорема Ферма в случае п = 4", Математический вестник 91, июль 2007 г., стр. 260–262.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]