5.1: Принцип добре впорядкування

Теорія чисел вивчає властивості цілих чисел. Деякі основні результати в теорії чисел покладаються на існування певного числа. Наступна теорема може бути використана, щоб показати, що таке число існує.

Теорема\(\PageIndex{1}\label{thm:PWO}\)

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

Доказ

Ідея досить проста. Почніть з цілого числа 1. Якщо він належить\(S\), ми закінчили. Якщо ні, розглянемо наступне ціле число 2, а потім 3, і так далі, поки ми не знайдемо перший елемент в\(S\). Однак, як і принцип математичної індукції, незрозуміло, чому «і так далі» можливо. Насправді, ми не можемо довести принцип добре впорядкування лише знайомими властивостями, які задовольняють натуральні числа при додаванні та множенні. Отже, ми будемо розглядати принцип упорядкування добре як аксіому. Цікаво, однак, виявляється, що принцип математичної індукції і принцип упорядкування добре логічно рівнозначні.

Теорема\(\PageIndex{2}\label{thm:PMI-PWO}\)

Принцип математичної індукції тримається тоді і тільки тоді, коли принцип упорядкування добре тримається.

Доказ

(\(\Rightarrow\)) Припустимо,\(S\) це непорожній набір натуральних чисел, який не має найменшого елемента. Нехай\[R = \{ x\in\mathbb{N} \mid x\leq s \mbox{ for every } s\in S\}. \nonumber\] Оскільки\(S\) не має найменшого елемента, зрозуміло, що\(R\cap S = \emptyset\). Також очевидно, що\(1\in R\). Припустимо\(k\in R\). Тоді будь-яке натуральне число менше або рівне також\(k\) має бути меншим або рівним\(s\) для кожного\(s\in S\). Звідси\(1,2,\ldots,k \in R\). Тому що\(R\cap S=\emptyset\), знаходимо\(1,2,\ldots,k\notin S\). \(k+1\in S\)\(k+1\)Якби, то був би найменший елемент\(S\). Це протиріччя свідчить про це\(k+1\in R\). Тому принцип математичної індукції мав би на увазі це\(R=\mathbb{N}\). Що б зробити\(S\) порожній набір, що суперечить припущенню,\(S\) що непорожній. Тому будь-який непорожній набір натуральних чисел повинен мати найменший елемент.

(\(\Leftarrow\))\(S\) Дозволяти бути набір натуральних чисел, таких, що

1. \(1\in S\),
2. Для будь-якого\(k\geq1\), якщо\(k\in S\), то\(k+1\in S\).

Припустимо\(S\neq\mathbb{N}\). Потім\(\overline{S}=\mathbb{N}-S\neq\emptyset\). Принцип добре впорядкованості стверджує, що\(\overline{S}\) має найменший елемент\(z\). З тих пір\(1\in S\), ми виводимо те\(z\geq2\), що робить\(z-1\geq1\). Мінімалізм\(z\) означає, що\(z-1\notin \overline{S}\). Отже,\(z-1\in S\). Умова (ii) має на увазі те\(z\in S\), що є протиріччям. Тому,\(S=\mathbb{N}\).

Принцип упорядкування добре - теорема існування. Він не говорить нам, який елемент є найменшим цілим числом, а також не говорить нам, як знайти найменший елемент.

Приклад\(\PageIndex{1}\label{eg:PWO-01}\)

Розглянемо множини\[\begin{array}{r c l} A &=& \{ n\in\mathbb{N} \mid n \mbox{ is a multiple of 3} \}, \\ B &=& \{ n\in\mathbb{N} \mid n = -11+7m \mbox{ for some } m\in\mathbb{Z} \}, \\ C &=& \{ n\in\mathbb{N} \mid n = x^2-8x+12 \mbox{ for some } x\in\mathbb{Z} \}. \end{array} \nonumber\] Легко перевірити, що всі три множини непорожні, і оскільки вони містять тільки натуральні цілі числа, принцип добре впорядкування гарантує, що кожна з них має найменший елемент.

Ці найменші елементи може бути непросто знайти. Очевидно, що найменший елемент в\(A\) 3. Щоб знайти найменший елемент в\(B\), нам потрібно\(-11+7m>0\), а значить\(m>11/7\approx1.57\). Оскільки\(m\) має бути цілим числом, нам потрібно\(m\geq2\). Оскільки\(-11+7m\) є зростаючою функцією в\(m\), її найменша величина виникає при\(m=2\). Найменший елемент в\(B\) є\(-11+7\cdot2=3\).

Щоб визначити найменший елемент в\(C\), нам потрібно вирішити нерівність\(x^2-8x+12>0\). Факторизація призводить до\(x^2-8x+12 = (x-2)(x-6)>0\), тому нам потрібно\(x<2\) або\(x>6\). Тому що\(x\in\mathbb{Z}\), ми визначаємо, що мінімальне значення\(x^2-8x+12\) відбувається при\(x=1\) або\(x=7\). Так як\[1^2-8\cdot1+12 = 7^2-8\cdot7+12 = 5, \nonumber\] Найменший елемент в\(C\) 5.

Приклад\(\PageIndex{2}\label{eg:PWO-02}\)

Принцип добре впорядкування може бути невірним для дійсних чисел або від'ємних цілих чисел. Загалом, не кожен набір цілих або дійсних чисел повинен мати найменший елемент. Ось два приклади:

• Набір\(\mathbb{Z}\).
• Відкритий інтервал\((0,1)\).

\(\mathbb{Z}\)У множини немає найменшого елемента, тому що задано будь-яке ціле число\(x\), зрозуміло\(x-1<x\), що, і цей аргумент може повторюватися нескінченно довго. Значить,\(\mathbb{Z}\) не має найменшого елемента.

Подібна проблема виникає і в відкритому проміжку\((0,1)\). Якщо\(x\) лежить між 0 і 1, то так є\(\frac{x}{2}\), і\(\frac{x}{2}\) лежить між 0 і\(x\), такий, що\[0 < x < 1 \quad\Rightarrow\quad 0 < \frac{x}{2} < x < 1. \nonumber\] Цей процес може повторюватися до нескінченності, даючи\[0 < \cdots < \frac{x}{2^n} < \cdots < \frac{x}{2^3} < \frac{x}{2^2} < \frac{x}{2} < x < 1. \nonumber\] Ми продовжуємо отримувати все менше і менше числа. Всі вони позитивні і менше 1. Кінця в полі зору немає, отже, інтервал\((0,1)\) не має найменшого елемента.

Ідея принципу упорядкування може бути розширена, щоб охопити числа, відмінні від натуральних чисел.

Визначення

Набір\(T\) дійсних чисел вважається добре впорядкованим, якщо кожна непорожня підмножина\(T\) має найменший елемент.

Тому, за принципом добре впорядкованого, добре\(\mathbb{N}\) впорядкований.

Приклад\(\PageIndex{3}\label{eg:PWO-03}\)

Покажіть,\(\mathbb{Q}\) що не добре впорядковано.

Рішення

Припустимо,\(x\) це найменший елемент в\(\mathbb{Q}\). Потім\(x-1\) йде раціональне число\(x\), яке менше, що суперечить мінімалістичності\(x\). Це показує, що\(\mathbb{Q}\) не має найменшого елемента. Тому\(\mathbb{Q}\) не впорядкований.

[Наприклад: ПВО-03]

практичні вправи\(\PageIndex{1}\label{he:PWO-01}\)

Показати, що інтервал\([0,1]\) не впорядкований, знайшовши підмножину, яка не має найменшого елемента

Резюме та огляд

• Набір дійсних чисел (які можуть бути десятковими числами), як кажуть, добре впорядкований, якщо кожна непорожня підмножина в ньому має найменший елемент.
• Впорядкований набір повинен бути непорожнім і мати найменший елемент.
• Наявність найменшого елемента не гарантує, що набір дійсних чисел добре впорядкований.
• Добре впорядкований набір може бути кінцевим або нескінченним, але кінцевий набір завжди добре впорядкований.

Вправи 5.1

Вправа\(\PageIndex{1}\label{ex:PWO-01}\)

Знайти найменший елемент у кожній з цих підмножин\(\mathbb{N}\).

1. \(\{n\in\mathbb{N} \mid n=m^2-10m+28 \mbox{ for some integer}\)\(m\).
2. \(\{n\in\mathbb{N} \mid n=5q+3 \mbox{ for some integer} \)\(q\).
3. \(\{n\in\mathbb{N} \mid n=-150-17d \mbox{ for some integer} \)\(d\).
4. \(\{n\in\mathbb{N} \mid n=4s+9t \mbox{ for some integers}\)\(s\)і\(t\).

Вправа\(\PageIndex{2}\label{ex:PWO-02}\)

Визначте, які з наступних підмножин добре\(\mathbb{R}\) впорядковані:

1. \(\{\;\}\)
2. \(\{-9,-7,-3,5,11\}\)
3. \(\{0\}\cup\mathbb{Q}^+\)
4. \(2\mathbb{Z}\)
5. \(5\mathbb{N}\)
6. \(\{-6,-5,-4,\ldots\,\}\)

Вправа\(\PageIndex{3}\label{ex:PWO-03}\)

Покажіть, що інтервал\([3,5]\) не впорядкований.

Підказка

Знайдіть підмножину\([3,5]\), яка не має найменшого елемента.

Вправа\(\PageIndex{4}\label{ex:PWO-04}\)

Припустимо\(\emptyset \neq T_1 \subseteq T_2 \subseteq \mathbb{R}\). Покажіть, що якщо\(T_2\) добре впорядкований,\(T_1\) то також добре впорядкований.

Підказка

\(S\)Дозволяти бути непорожнім підмножиною\(T_1\). Ми хочемо показати, що\(S\) має найменший елемент. Для досягнення цієї мети зверніть увагу на те, що\(T_1\subseteq T_2\).

Вправа\(\PageIndex{5}\label{ex:PWO-05}\)

Доведіть, що\(2\mathbb{N}\) добре впорядкований.

Підказка

Використовуйте попередню проблему.

Вправа\(\PageIndex{6}\label{ex:PWO-06}\)

Припустимо\(\emptyset \neq T_1 \subseteq T_2 \subseteq \mathbb{R}\). Доведіть, що якщо\(T_1\) не має найменший елемент, то не\(T_2\) добре впорядкований.