6.9: Нескінченний спуск

У цьому заключному розділі ми торкнемося важливої варіації математичної індукції. Цю варіацію добре ілюструє наступна (напевно знайома) проблема.

Проблема 267 Випишіть для себе наступний стандартний доказ того, що$\sqrt{2}$нераціонально.

(i) Припустимо навпаки, що$\sqrt{2}$є раціональним. Тоді$\sqrt{2}=\frac{м}{п}$для деяких натуральних чисел m, n. Доведіть спочатку, що m повинен бути парним.

(ii) Написати$м=2{м}^{\prime }$, де${м}^{\prime }$також є цілим числом. Покажіть, що n також має бути парним.

(iii) Як це призводить до протиріччя?

Задача 267. має класичну форму доказу, яка досягає протиріччя нескінченним спуском.

1. Ми починаємо з твердження, яке ми хочемо довести, що це правда. Часто, коли ми не знаємо, з чого почати, має сенс запитати, що б сталося, якби претензія була помилковою. Це тоді гарантує, що повинен бути якийсь контрприклад, який задовольняє даній гіпотезі, але який не задовольняє затвердженому висновку.
2. Нескінченний спуск стає опцією кожного разу, коли кожен такий контрприклад породжує якийсь позитивний цілий параметр n (наприклад, знаменник у задачі 267. (i)).
3. Нескінченний спуск стає реальністю, якщо можна довести, що існування початкового контрприкладу призводить до побудови, яка дає контрприклад з меншим значенням.${п}^{\prime }$параметра n, оскільки повторення цього кроку породжує нескінченно спадну послідовність$$п>{п}^{\prime }>п\text{'}\text{'}>...>0$$натуральних чисел, що неможливо (оскільки такий ланцюжок може мати довжину не більше n).
4. Отже, початкове припущення про те, що претензія була помилковою, сама по собі повинна бути помилковою - тому претензія повинна бути істинною (за потребою).

Доказ за допомогою «нескінченного спуску» - безцінний інструмент. Але важливо усвідомити, що метод по суті є варіацією доказу математичною індукцією. В якості першого кроку в цьому напрямку варто переосмислити задачу 267. як індукційний доказ.

Проблема 268 Нехай$Р(п)$бути твердженням:

»$\sqrt{2}$не можна записати як дріб з додатним знаменником$\le п$».

(i) Поясніть, чому$Р(1)$це правда.

(ii) Припустимо, що$Р(к)$вірно для деяких$к\ge 1$. Скористайтеся доказом у задачі 267., щоб показати, що$Р(к+1)$повинні бути правдою, а також.

(iii) зробити висновок, що$Р(п)$вірно для всіх$п\ge 1$, звідки$\sqrt{2}$має бути нераціональним.

Проблема 268. показує, що в конкретному випадку завдання 267. можна перевести стандартний доказ того, що»$\sqrt{2}$є ірраціональним» в доказ індукцією. Але набагато більше вірно. Протиріччя, що виникає в кроці 3. вище, є застосуванням важливого принципу, а саме

Принцип найменшого елемента: Кожна непорожня множина S натуральних чисел має найменший елемент.

Принцип найменшого елемента еквівалентний принципу математичної індукції, який ми заявляли на початку глави:

Принцип математичної індукції: Якщо підмножина S з натуральних чисел

• містить ціле число «1» і має властивість, яка
• всякий раз, коли в множині S знаходиться ціле число k, то наступне ціле$к+1$завжди в S теж,

то S містить всі натуральні числа.

Проблема 269

(a) Припустимо принцип найменшого елемента. Припустимо, підмножина T натуральних чисел містить ціле число «1», і що всякий раз, коли k знаходиться у множині T, то$к+1$також є в наборі Т. Нехай S - множина всіх натуральних чисел, яких немає в множині T. Зробіть висновок, що S має бути порожнім, а значить, T містить всі натуральні числа.

(б) Припустимо принцип математичної індукції. Нехай T є непорожнім набором натуральних чисел, і припустимо, що T не має найменшого елемента. Нехай S — це множина всіх натуральних чисел, які не належать до множини T. Доведіть, що «1» повинен належати S, і що всякий раз, коли натуральне число k належить S, то так робить$к+1$. Виведіть протиріччя, що T повинен бути порожнім, всупереч припущенню. Зробіть висновок, що Т насправді повинен мати найменший елемент.

Щоб завершити цю заключну главу, вам пропонується розробити зовсім інший доказ ірраціональності$\sqrt{2}$.

Задача 270 Ця послідовність конструкцій передбачає, що ми знаємо — наприклад, за теоремою Піфагора — що в будь-якому квадраті$$OРQР, співвідношення

«діагональ: сторона»$=OQ:OР=\sqrt{2}:1$.

Нехай$$OРQРбути квадратом. Нехай коло з центром Q і проходить через P зустрітися$\underset{¯}{OQ}$на${Р}^{\prime }$. Побудувати перпендикуляр$\underset{¯}{OQ}$на${Р}^{\prime }$, і нехай це зустрінеться$\underset{¯}{OР}$на$Q^{\prime }$.

(i) Поясніть, чому$\underset{¯}{O{Р}^{\prime }}=\underset{¯}{{Р}^{\prime }{Q}^{\prime }}$. Побудувати точку${Р}^{\prime }$завершити квадрат$O{Р}^{\prime }{Q}^{\prime }{Р}^{\prime }$.

(ii) Приєднуйтесь$\underset{¯}{Q{Q}^{\prime }}$. Поясніть, чому$\underset{¯}{{Р}^{\prime }{Q}^{\prime }}=\underset{¯}{РQ^{\prime }}$.

(iii) Припустимо$\underset{¯}{OQ}:\underset{¯}{OР}=м:п$. Зробіть висновок, що$\underset{¯}{O{Q}^{\prime }}:\underset{¯}{O{Р}^{\prime }}=2п-м:м-п$.

(iv) Доведіть, що$п<м<2п$, і, отже,$0<м-п<п$,$0<2п-м$.

(v) Поясніть, як, якщо m, n можна обрати як натуральні цілі числа, наведена вище послідовність кроків встановлює «нескінченний спуск» - що неможливо.