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

В математике принцип хорошего порядка гласит, что каждое непустое подмножество положительных целых чисел содержит наименьший элемент . ^[1] Другими словами, набор положительных целых чисел хорошо упорядочен по своему «естественному» порядку или порядку «величины», в котором $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$ непусто, должно быть ложным. ^[2]

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

Теорема: $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$ , противоречие. Итак, уравнение должно выполняться для всех положительных целых чисел. ^[2]