8.4: Природні числа добре впорядковані

Індукція - це дуже потужний інструмент, але іноді його важко застосувати (і існує багато різних версій, за якими слід стежити, як ми бачили в попередньому розділі). У цьому розділі ми демонструємо тісно пов'язану техніку, яка часто менш громіздка у використанні.

Визначення\(8.4.1\).

Нехай\(S \subset \mathbb{R}\) і\(a \in \mathbb{R}\). Ми говоримо\(a\), що це найменший елемент\(S\) iff:

• \(a \in S\), і
• \(\forall s \in S\),\(a \leq s\).

Приклад\(8.4.2\).

• Найменший елемент\(\{2,4,6,8\}\) - 2.
• Найменший елемент\(\{12,9,18,5,13\}\) - 5.

Важливо усвідомлювати, що не кожен набір чисел має найменший елемент:

Вправа\(8.4.3\).

Показати, що даний набір не має найменшого елемента.

1. \(\mathbb{Z} [Hint: If \(n \in \mathbb{Z}\), потім\(n − 1 < n\).]
2. \(\mathbb{R}^{+}=\{x \in \mathbb{R} \mid x>0\}\)[Підказка: Якщо\(x \in \mathbb{R}^{+}\), то\(x / 2 \in \mathbb{R}^{+}\).]
3. \(\varnothing\)[Підказка: набір без елементів не може мати найменшого елемента.]

Ця проблема не виникає для підмножин\(\mathbb{N}\):

Теорема\(8.4.4\) (\(\mathbb{N}\) is Well-Ordered).

Кожна непорожня підмножина\(\mathbb{N}\) має найменший елемент.

Це досить очевидне спостереження настільки ж потужне, як і всі численні варіації принципу математичної індукції. А саме, якщо для всіх\(P(n)\) можна довести,\(n \in \mathbb{N}^{+}\) використовуючи будь-яку з численних форм математичної індукції, то це також можна довести, застосувавши теорему\(8.4.4\) до множини.\[S=\left\{n \in \mathbb{N}^{+} \mid \neg P(n)\right\} .\]

Точніше, припустимо,\(P(n)\) це не так для всіх\(n \in \mathbb{N}^{+}\). Тоді той факт, що добре\(\mathbb{N}\) впорядкований, говорить нам про те, що є найменший\(n\), такий,\(P(n)\) що не відповідає дійсності. Це означає, що:

1. \(P(n)\)не відповідає дійсності, але
2. \(P(k)\)вірно для всіх\(k < n\) (таких, що\(k \in \mathbb{N}^{+}\)).

Отримання протиріччя з цих двох припущень завершить доказ, який\(P(n)\) вірний для всіх\(n \in \mathbb{N}^{+}\).

Приклад\(8.4.5\) (Alternate Proof of Example \(8.3.3\)).

Припустимо, це неправда, що\(F_{n} < 2^{n}\) для всіх\(n \in \mathbb{N}^{+}\). (Це призведе до протиріччя.) Тоді, так як\(\mathbb{N}\) добре впорядкований, є найменший\(n\), такий що\(F_{n} \geq 2^{n}\). Це означає, що

1. \(F_{n} \geq 2^{n}\), але
2. \(F_{k} < 2^{k}\)для всіх\(k < n\) (таких, що\(k \in \mathbb{N}^{+}\)).

Зверніть увагу, що, оскільки\[F_{1}=1<2=2^{1} \quad \text { and } \quad F_{2}=1<4=2^{2} ,\]

ми бачимо з (i) що\(n \notin\{1,2\}\), так\(n \geq 3\). Тому\(n − 1 \in \mathbb{N}^{+}\) і\(n − 2 \in \mathbb{N}^{+}\). Тоді, оскільки\(n − 1\) і\(n − 2\) менше\(n\), ми бачимо з (ii) що\[(*) \quad F_{n-1}<2^{n-1} \text { and } F_{n-2}<2^{n-2} .\]

Тепер у нас є\ [\ begin {вирівняний}
F_ {n} &=F_ {n-1} +F_ {n-2} &\ text {(визначення послідовності Фібоначчі)}\\
&<2^ {n-1} +2^ {n-2} & (*):\ текст {мінімальність} n)\\
&<2^ {n-1} +2^ {n-2} +2^ {n-2} +2^ {n-2} +2^ {n-2} 1} & (n-2 <n-1)\\
&=2 ^ {n} &.
\ end {вирівняний}\]

Це суперечить (i).

Вправа\(8.4.6\).

1. Доведіть\(F_{n+4} + F_{n} = 3F_{n+2}\) для всіх\(n \in \mathbb{N}^{+}\).
2. Доведіть\(2^{n} > n^{2}\) для кожного\(n \geq 5\).
3. Доведіть\(3^{n} > 2^{n} + 2n\), для кожного\(n \geq 2\).

Вправа\(8.4.7\).

1. Показати, що принцип математичної індукції (\(8.1.2\)) випливає з того, що добре\(\mathbb{N}\) впорядкований.
2. Використовуйте індукцію для доведення теореми\(8.4.4\). [Підказка: Визначте\(P(n)\) твердження «Якщо\(S \subset \mathbb{N}\) і\(S\) містить елемент\(\leq n\), то\(S\) має найменший елемент.»]