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

Last updated
Save as PDF

Page ID: 65584

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

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

Визначення 4.35. Нехай\(A\subseteq \mathbb{R}\) і\(m\in A\). Тоді\(m\) називається максимальним (або найбільшим елементом)\(A\) якщо для всіх\(a\in A\), у нас є\(a\leq m\). Аналогічно\(m\) називається мінімальним (або найменшим елементом)\(A\) якщо для всіх\(a\in A\), у нас є\(m\leq a\).

Не дивно, що максимуми і мінімуми є унікальними, коли вони існують. Можливо, було б корисно переглянути Skeleton Proof 2.90 перед атакою наступного результату.

Теорема 4.36. Якщо\(A\subseteq \mathbb{R}\) такий, що максимум (відповідно, мінімум)\(A\) існує, то максимум (відповідно мінімум)\(A\) є унікальним.

Якщо максимум множини\(A\) існує, то він позначається символом\(\max(A)\). Аналогічно, якщо мінімум безлічі\(A\) існує, то він позначається символом\(min(A)\).

Проблема 4.37. Знайдіть максимум і мінімум для кожного з наступних наборів, коли вони існують.

\(\{5,11,17,42,103\}\)
\(\mathbb{N}\)
\(\mathbb{Z}\)
\((0,1]\)
\((0,1]\cap \mathbb{Q}\)
\((0,\infty)\)
\(\{42\}\)
\(\{\frac{1}{n}\mid n\in\mathbb{N}\}\)
\(\{\frac{1}{n}\mid n\in\mathbb{N}\}\cup\{0\}\)
\(\emptyset\)

Щоб довести принцип упорядкування добре, розгляньте доказ протиріччя. Припустимо,\(S\) це непорожня\(\mathbb{N}\) підмножина, що не має найменшого елемента. Визначте пропозицію\(P(n):=\) «не\(n\) є елементом\(S\)", а потім використовуйте повну індукцію, щоб довести результат.

Теорема 4.38. Кожна непорожня підмножина натуральних чисел має найменший елемент.

Виявляється, принцип упорядкування добре (теорема 4.38) і аксіома індукції (аксіома 4.1) еквівалентні. Іншими словами, можна довести принцип упорядкування добре з аксіоми індукції, як ми це зробили, але можна також довести аксіому індукції, якщо передбачається принцип упорядкування добре.

Останні дві теореми цього розділу можна розглядати як узагальнені версії принципу упорядкування добре.

Теорема 4.39. Якщо\(A\) є непорожнім підмножиною цілих чисел і існує\(\ell\in \mathbb{Z}\) таке, що\(\ell\leq a\) для всіх\(a\in A\), то\(A\) містить найменший елемент.

Теорема 4.40. Якщо\(A\) є непорожнім підмножиною цілих чисел і існує\(u\in \mathbb{Z}\) таке, що\(a\leq u\) для всіх\(a\in A\), то\(A\) містить найбільший елемент.

Елемент\(\ell\) в теоремі 4.39 називається нижньою межею,\(A\) тоді як елемент\(u\) в теоремі 4.40 називається верхньою межею для\(A\). Більш детально вивчимо нижню і верхню межі в розділі 5.1.