Введение

Утверждение о том, что все непустые подмножества положительных чисел содержат наименьший элемент.

В математике принцип благоустроенности (или принцип хорошего упорядочения) утверждает, что каждое непустое подмножество положительных целых чисел содержит наименьший элемент. Иными словами, множество положительных целых чисел благоустроено своим "естественным" или "по величине" порядком, в котором *a* предшествует *b* тогда и только тогда, когда *b* является либо *a* плюс некоторое положительное целое число, либо равно *a* (другие упорядочения включают упорядочение ; и ). Фраза "принцип благоустроенности" иногда используется как синоним "теоремы благоустроенности". В других случаях под этим понимается утверждение о том, что множество целых чисел содержит благоустроенное подмножество, называемое натуральными числами, в котором каждое непустое подмножество содержит наименьший элемент.

Свойства

В зависимости от того, в каких рамках вводятся натуральные числа, это (свойство второго порядка) множества натуральных чисел является либо аксиомой, либо доказуемой теоремой. Например: в арифметике Пеано, арифметике второго порядка и связанных системах, и вообще в большинстве (не обязательно формальных) математических рассмотрений принципа хорошего упорядочения, этот принцип выводится из принципа математической индукции, который сам принимается за базовый. Рассматривая натуральные числа как подмножество действительных чисел и предполагая, что мы уже знаем, что действительные числа полны (опять же, либо как аксиома, либо как теорема о системе действительных чисел), то есть каждое ограниченное (снизу) множество имеет инфимум, то и каждое множество натуральных чисел имеет инфимум, скажем, . Мы можем теперь найти целое число такое, что лежит в полуоткрытом интервале , и затем показать, что должно быть , и в аксиоматической теории множеств натуральные числа определяются как наименьшее индуктивное множество (то есть множество, содержащее 0 и замкнутое относительно операции следования). Можно (даже не прибегая к аксиоме регулярности) показать, что множество всех натуральных чисел, удовлетворяющих условию "хорошо упорядочено", является индуктивным и, следовательно, должно содержать все натуральные числа; из этого свойства можно заключить, что множество всех натуральных чисел также хорошо упорядочено. Во втором смысле эта фраза используется, когда на это утверждение опираются для обоснования доказательств следующего типа: чтобы доказать, что каждое натуральное число принадлежит заданному множеству , предположим обратное, что подразумевает, что множество контрпримеров не пусто и, следовательно, содержит наименьший контрпример. Затем покажем, что для любого контрпримера существует еще меньший контрпример, что приводит к противоречию. Этот способ рассуждения является противопоставлением доказательству полной индукцией. Его в шутку называют методом "минимального преступника", и он по своей сути схож с методом Ферма "бесконечного спуска". Гарретт Биркофф и Сондерс Маклейн в "Обзоре современной алгебры" написали, что это свойство, как и аксиома наименьшей верхней границы для действительных чисел, не является алгебраическим; то есть его нельзя вывести из алгебраических свойств целых чисел (которые образуют упорядоченное целостное кольцо).

Примеры применения

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

Факторизация простых чисел

Теорема: Каждое целое число, большее единицы, может быть разложено в произведение простых чисел. Эта теорема является частью теоремы о разложении на простые множители. Доказательство (по принципу наименьшего элемента). Пусть S – множество всех целых чисел, больших единицы, которые нельзя разложить в произведение простых чисел. Докажем, что S пусто. Предположим для противоречия, что S не пусто. Тогда, по принципу наименьшего элемента, существует наименьший элемент n в S. Число n не может быть простым, поскольку простое число само по себе считается произведением простых чисел длины один. По определению составного числа, n имеет множители a и b, где a и b – целые числа, большие единицы и меньшие n. Поскольку a и b меньше n, они не принадлежат S, так как n – наименьший элемент S. Следовательно, a и b могут быть разложены в произведение простых чисел, а значит, и n = a * b может быть разложено в произведение простых чисел. Это противоречит предположению, что n принадлежит S, поэтому предположение о том, что S не пусто, должно быть ложным.

Сумма целых чисел

Теорема: для всех положительных целых чисел.
Доказательство. Предположим, ради противоречия, что вышеуказанная теорема неверна. Тогда существует непустое множество положительных целых чисел. По принципу хорошо упорядоченности, множество имеет минимальный элемент , такой, что при уравнение неверно, но верно для всех положительных целых чисел, меньших чем . Уравнение верно для , следовательно, ; является положительным целым числом, меньшим чем , поэтому уравнение верно и для , поскольку оно не входит в . Таким образом, мы получаем противоречие. Следовательно, уравнение должно быть верно для всех положительных целых чисел.