Правильный принцип упорядочения

Не путать с Теоремой о хорошем порядке .

В математике принцип хорошего порядка гласит, что каждое непустое подмножество положительных целых чисел содержит наименьший элемент . Другими словами, набор положительных целых чисел хорошо упорядочен по своему «естественному» порядку или порядку «величины», в котором $x$ предшествует $y$ тогда и только тогда, когда $y$ либо $x$ или сумма $x$ и некоторое положительное целое число (другие порядки включают в себя порядок $2,4,6,...$; и $1,3,5,...$).

Фразу «принцип хорошего порядка» иногда считают синонимом « теоремы хорошего порядка ». В других случаях под этим понимается утверждение, что множество целых чисел $\{\ldots ,-2,-1,0,1,2,3,\ldots \}$ содержит хорошо упорядоченное подмножество, называемое натуральными числами , в котором каждое непустое подмножество содержит наименьший элемент.

Свойства

В зависимости от структуры, в которой вводятся натуральные числа, это свойство (второго порядка) множества натуральных чисел является либо аксиомой , либо доказуемой теоремой. Например:

• В арифметике Пеано , арифметике второго порядка и родственных системах, а также в большинстве (не обязательно формальных) математических трактовок принципа хорошего порядка этот принцип выводится из принципа математической индукции , который сам по себе считается базовым.
• Рассматривая натуральные числа как подмножество действительных чисел и предполагая, что мы уже знаем, что действительные числа полны (опять же, либо как аксиома, либо как теорема о системе действительных чисел), т. е. каждое ограниченное (снизу) множество имеет нижнюю грань, то и каждое множество $A$ натуральных чисел имеет нижнюю границу, скажем $a^{*}$. Теперь мы можем найти целое число $n^{*}$ такой, что $a^{*}$ лежит в полуоткрытом интервале $(n^{*}-1,n^{*}]$, и затем сможем показать, что мы должны иметь $a^{*}=n^{*}$, и $n^{*}$ в $A$.
• В аксиоматической теории множеств натуральные числа определяются как наименьшее индуктивное множество (т. е. множество, содержащее 0 и замкнутое относительно операции-преемника). Можно (даже не прибегая к аксиоме регулярности ) показать, что множество всех натуральных чисел $n$ такой, что " $\{0,\ldots ,n\}$ «хорошо упорядочен» является индуктивным и поэтому должен содержать все натуральные числа; из этого свойства можно заключить, что множество всех натуральных чисел также хорошо упорядочено.

Во втором смысле эта фраза используется, когда на это предложение опираются с целью обоснования доказательств, которые принимают следующую форму: доказать, что каждое натуральное число принадлежит заданному множеству. $S$, предположим противное, что означает, что множество контрпримеров непусто и, следовательно, содержит наименьший контрпример. Затем покажите, что для любого контрпримера существует еще меньший контрпример, приводящий к противоречию. Этот способ аргументации является противоположностью доказательства методом полной индукции . Его беззаботно называют методом « минимального криминала ». и по своей природе подобен » Ферма методу « бесконечного спуска .

Гаррет Биркгоф и Сондерс Мак Лейн написали в «Обзоре современной алгебры» , что это свойство, как и аксиома наименьшей верхней границы действительных чисел, не является алгебраическим; т. е. его нельзя вывести из алгебраических свойств целых чисел (которые образуют упорядоченную область целостности ).

Примеры приложений

Принцип хорошего порядка можно использовать в следующих доказательствах.

Простая факторизация

Теорема: каждое целое число больше единицы можно разложить на множители как произведение простых чисел. Эта теорема является частью теоремы о простой факторизации .

Доказательство (по принципу упорядоченности). Позволять $C$ быть набором всех целых чисел, больших единицы, которые нельзя разложить на множители как произведение простых чисел. Мы показываем, что $C$ пусто.

Предположим ради противоречия, что $C$ не пуст. Тогда по принципу хорошего порядка существует наименьший элемент $n\in C$; $n$ не может быть простым, поскольку само простое число считается произведением простых чисел длины один. По определению непростых чисел, $n$ имеет факторы $a,b$, где $a,b$ целые числа больше единицы и меньше $n$. С $a,b<n$, их нет в $C$ как $n$ является наименьшим элементом $C$. Так, $a,b$ можно разложить как произведение простых чисел, где $a=p_{1}p_{2}...p_{k}$ и $b=q_{1}q_{2}...q_{l}$, это означает, что $n=p_{1}p_{2}...p_{k}\cdot q_{1}q_{2}...q_{l}$, произведение простых чисел. Это противоречит предположению, что $n\in C$, поэтому предположение, что $C$ непусто, должно быть ложным.

Целочисленное суммирование

Теорема: $1+2+3+...+n={\frac {n(n+1)}{2}}$ для всех положительных целых чисел $n$.

Доказательство . Предположим от противного, что приведенная выше теорема неверна. Тогда существует непустое множество натуральных чисел $C=\{n\in \mathbb {N} \mid 1+2+3+...+n\neq {\frac {n(n+1)}{2}}\}$. По принципу упорядоченности, $C$ имеет минимальный элемент $c$ такое, что когда $n=c$, уравнение неверно, но верно для всех натуральных чисел, меньших $c$. Уравнение верно для $n=1$, так $c>1$; $c-1$ целое положительное число, меньшее $c$, поэтому уравнение справедливо для $c-1$ как это не в $C$. Поэтому,

$${\begin{aligned}1+2+3+...+(c-1)&={\frac {(c-1)c}{2}}\\1+2+3+...+(c-1)+c&={\frac {(c-1)c}{2}}+c\\&={\frac {c^{2}-c}{2}}+{\frac {2c}{2}}\\&={\frac {c^{2}+c}{2}}\\&={\frac {c(c+1)}{2}}\end{aligned}}$$

что показывает, что уравнение справедливо для $c$, противоречие. Таким образом, уравнение должно выполняться для всех положительных целых чисел.